最佳旅游线路的数学模型

【摘要】本文通过对自驾游云南的几个旅游景点，求出了最正确旅游线路的数学模型，为旅游者设计旅游线路提供有一定价值的参考。首先，本文对所求问题做出合理假设，然后运用“分枝定界法”建立并寻找最正确旅游线路的图论模型使问题简单明了，并充分利用线性规划建立模型，得出了最优的线路设计，最后提出该模型的算法及求解过程。【关键字】分枝定界法Floyd〔弗劳德〕算法哈密顿圈旅游线路一、问题重述云南是我国的旅游大省，拥有丰富的旅游资源，吸引了大批的省外游客，旅游业正在成为云南的支柱产业。随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众的面临多条线路的选择问题。某一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明，且旅行者采取自驾游的旅行方式。二、符号说明1、，：加权图的顶点即云南各旅游景点；2、：各景点间的距离构成的矩阵；3、：各景点间的距离构成的矩阵中每一行减去该行的最小的元素及每一列减去该列的最小元素后所构成的矩阵；4、：加权图的边，即权，表示两景点间的距离；5、：为任意两顶点与顶点在图中最短路径长度。三、模型假设1、假设旅游者在各景点的逗留时间、花费等都相同；2、旅游者最终要返回昆明，假设昆明是旅游者要去的一个旅游景点；3、假设旅游者所经过的公路是同一等级公路，在汽车恒速及单位路程所耗油量相同的条件下，各景点的路程与时间及耗油量成正比，即在较短时间及较低耗油量内，旅游较多景点，为此我们制定一条路线使得路程最短，这样就能使旅游者花费时间最短而耗油量又最低得情况下旅游相同的景点。四、模型建立与求解1、根据旅游者采取的是自驾游的旅行方式，我们可以得到云南省局部旅游景点的交通路线中〔自驾游可以自选路线，每两个旅游景点间都有可行路程〕每两景点间的路程，任意两旅游景点间的路程如下表所示〔单位：公里〕：昆明大理丽江石林西双版纳泸沽湖香格里拉昆明031950285542567629大理3190183397854448314丽江50218305811037260178石林853975810603654707西双版纳5428541037603012261164泸沽湖56744826065412260434香格里拉62931417870711644340表1各旅游景点间的路程表下列图是云南省旅游景点地图：图1云南省旅游景点图由上面的地图可画出所给旅游景点的路线图如下：香格里拉丽江大理香格里拉丽江大理泸沽湖昆明石林西双版纳由表1和图1可得到加权无向图图2如下：71712345662931954256785314397854448183581103717826060370765412261164434502注：1.昆明2.大理3.丽江4.石林5.西双版纳6.泸沽湖7.香格里拉2、“分枝定界法”模型：用阶矩阵中的各个元素来表示各个景点之间的距离，且各个景点之间的距离是没有方向的，那么阶矩阵是对称型矩阵,中的所有元素减去该行的最小非零元素，得到新的矩阵，再抽取矩阵每列的最小非零元素，并令矩阵各列的所有元素减去该列的最小非零元素，得到新的矩阵，这样得到矩阵是每行每列都至少有一个零元素存在。然后，选择起点与某景点之间距离为零的元素，把这个元素所在的行和列从矩阵中划去，得到新的矩阵，同时，把起点与某景点组成一条路。对矩阵重复矩阵变化到矩阵的步骤操作，得到新的景点参加到最近路的末顶点的后面，使其成为一条新路。直到得到的最后矩阵是，且这条路包含所有的景点，所有的景点在这条路上只能出现一次，这样操作才算停止，否那么重复上面的步骤。3、“分枝定界法”模型求解，用“分枝定界法”寻找近似最正确旅游线路的算法如下：步骤1：用Floyd算法求任意两景点之间的距离，构建一个加权无向图，每条边的权叫为顶点与顶点在图中最短路径长度。步骤2：随机搜索加权无向图中已指定的起点的假设干个哈密顿圈，或者找出它的任意一个初始的哈密顿圈。步骤3：用二边逐次修改法对步骤2中的哈密顿圈进行优化，从而得到近似最正确的哈密顿圈。步骤4：比拟上述哈密顿圈，找出权值最小的一个，即为所要找的最正确哈密顿的近似解。4、“分枝定界法”模型求解的具体过程：123456712345671234567由“分枝定界法”的模型建立和矩阵算法，选择一条路，并令再把矩阵的第一行，第四列划去，得到矩阵:123567123567123567从矩阵中，可以选择顶点5添加在路中，那么有路，将第一行，第四列划去，令得：123671236712367从矩阵中，选择将顶点2添加到路，即得到路，将第一行，第二列划去，令得1367将顶点3添加到路上得路，将第一行，第二列划去并令得：167将顶点7添加到路上得路，将第一行第三列划去，并令得：16最后将顶点6添加得，从而可得总权数最小的哈密顿圈，即总权数为2904。所以最正确的旅游路线是：昆明石林西双版纳大理丽江香格里拉泸沽湖昆明。五、模型推广在模型求解过程中，我们可以应用“最邻近插入法”，0-1变量等方法寻找近似的最正确旅游线路，对景点较少而言，具体操作过程简单，但对有较多的景点时，具体操作过程比拟复杂，因此用这种方法寻找近似最正确的旅游线路存在一定的缺陷。而用“分枝定界法”寻找近似的最正确旅游线路，能在有限的时间内根据个人条件尽可能游览较多的景点，是游客所关心的问题。该模型能寻找出较多景点的最正确旅游线路，并用Floyd〔弗劳德〕算法更简单快捷的求解问题。六、模型评价为了寻找最正确旅游路线的问题，在“最邻近插入法”，0-1变量法和“分枝定界法”中，0-1变量法是用代数的方法转化为lindo或lingo中求解，“最邻近插入法”和“分枝定界法”均是将其转化为在给定加权无向图中寻找总权数最小的哈密顿圈。但由于求解的模型和算法不同，“最邻近插入法”的求解过程更为直观、便于理解，而“分枝定界法”在景点较多的情况下，可通过计算机编程求解。所以，在实践中运用“分枝定界法”来寻找近似的最正确旅游线路更有优势。一般来说，一个整数规划问题的可行解或是无限或是有限的。对于有限的可行解来说，我们自然想到列举法〔或称枚举法〕，把所有可能的整数可行解组合列出来，然后得到目标函数的最优值和最优解。但是如果断策变量很多或整数可行解组合多得惊人时，列举法就没有实用价值了。因此，就要寻求一种可行方法，使之仅检查局部整数可行解组合，从而得出最优的整数解。分枝定界法〔branchandboundmethod〕就是其中一种，它灵活且便于用计算机求解，是解整数规划的重要方法。七、参考文献[1]周溪召主编.运筹学及应用.——北京：化学工业出版社，2009.1[2]王文平等编著.运筹学.——北京：科学出版社，2007[3]栗雪娟，崔尚森，张柯．最正确旅游路线选择的神经网络方法[J]．交通与计算机，2006[4]张杰，周硕主编；邢丽娟等编写.运筹学模型与实验.——北京：中国电力出版社，2007