最佳旅游线路的数学模型

《最佳旅游线路的数学模型》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、【摘要】本文通过对自驾游云南的几个旅游景点，求出了最佳旅游线路的数学模型，为旅游者设计旅游线路提供有一定价值的参考。首先，本文对所求问题做出合理假设，然后运用“分枝定界法”建立并寻找最佳旅游线路的图论模型使问题简单明了，并充分利用线性规划建立模型，得出了最优的线路设计，最后提出该模型的算法及求解过程。【关键字】分枝定界法Floyd（弗劳德）算法哈密顿圈旅游线路一、问题重述云南是我国的旅游大省，拥有丰富的旅游资源，吸引了大批的省外游客，旅游业正在成为云南的支柱产业。随着越来越多的人选择到云南旅游，旅行社也推出了各种不同类型的旅行路线，使得公众的面临多条线路的选择问题。某

2、一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明，且旅行者采取自驾游的旅行方式。二、符号说明1、，：加权图的顶点即云南各旅游景点；2、：各景点间的距离构成的矩阵；3、：各景点间的距离构成的矩阵中每一行减去该行的最小的元素及每一列减去该列的最小元素后所构成的矩阵；4、：加权图的边，即权，表示两景点间的距离；5、：为任意两顶点与顶点在图中最短路径长度。三、模型假设1、假设旅游者在各景点的逗留时间、花费等都相同；2、旅游者最终要返回昆明，假设昆明是旅游者要去的一个旅游景点；3、假设旅游者所经过的公路是同一等级公路，在汽车恒速及单位路程所耗油量

3、相同的条件下，各景点的路程与时间及耗油量成正比，即在较短时间及较低耗油量内，旅游较多景点，为此我们制定一条路线使得路程最短，这样就能使旅游者花费时间最短而耗油量又最低得情况下旅游相同的景点。四、模型建立与求解1、根据旅游者采取的是自驾游的旅行方式，我们可以得到云南省部分旅游景点的交通路线中（自驾游可以自选路线，每两个旅游景点间都有可行路程）每两景点间的路程，任意两旅游景点间的路程如下表所示（单位：公里）：昆明大理丽江石林西双版纳泸沽湖香格里拉昆明031950285542567629大理3190183397854448314丽江50218305811037260178石

4、林853975810603654707西双版纳5428541037603012261164泸沽湖56744826065412260434香格里拉62931417870711644340表1各旅游景点间的路程表下图是云南省旅游景点地图：图1云南省旅游景点图由上面的地图可画出所给旅游景点的路线图如下：香格里拉丽江大理泸沽湖昆明石林西双版纳图2每两景点之间的旅游线路图由表1和图1可得到加权无向图图2如下：712345662931954256785314397854448183581103717826060370765412261164434502图3注：1.昆明2.大理3.

5、丽江4.石林5.西双版纳6.泸沽湖7.香格里拉2、“分枝定界法”模型：用阶矩阵中的各个元素来表示各个景点之间的距离，且各个景点之间的距离是没有方向的，那么阶矩阵是对称型矩阵,中的所有元素减去该行的最小非零元素，得到新的矩阵，再抽取矩阵每列的最小非零元素，并令矩阵各列的所有元素减去该列的最小非零元素，得到新的矩阵，这样得到矩阵是每行每列都至少有一个零元素存在。然后，选择起点与某景点之间距离为零的元素，把这个元素所在的行和列从矩阵中划去，得到新的矩阵，同时，把起点与某景点组成一条路。对矩阵重复矩阵变化到矩阵的步骤操作，得到新的景点加入到最近路的末顶点的后面，使其成为一条新

6、路。直到得到的最后矩阵是，且这条路包含所有的景点，所有的景点在这条路上只能出现一次，这样操作才算停止，否则重复上面的步骤。3、“分枝定界法”模型求解，用“分枝定界法”寻找近似最佳旅游线路的算法如下：步骤1：用Floyd算法求任意两景点之间的距离，构建一个加权无向图，每条边的权叫为顶点与顶点在图中最短路径长度。步骤2：随机搜索加权无向图中已指定的起点的若干个哈密顿圈，或者找出它的任意一个初始的哈密顿圈。步骤3：用二边逐次修改法对步骤2中的哈密顿圈进行优化，从而得到近似最佳的哈密顿圈。步骤4：比较上述哈密顿圈，找出权值最小的一个，即为所要找的最佳哈密顿的近似解。4、“分枝

7、定界法”模型求解的具体过程：123456712345671234567由“分枝定界法”的模型建立和矩阵算法，选择一条路，并令再把矩阵的第一行，第四列划去，得到矩阵:123567123567123567从矩阵中，可以选择顶点5添加在路中，则有路，将第一行，第四列划去，令得：123671236712367从矩阵中，选择将顶点2添加到路，即得到路，将第一行，第二列划去，令得1367将顶点3添加到路上得路，将第一行，第二列划去并令得：167将顶点7添加到路上得路，将第一行第三列划去，并令得：16最后将顶点6添加得，从而可得总权数最小的哈密顿圈，即总权数为29