C题 环球旅游的路线设计

一、 问题重述

摘要

喜欢旅游的人越来越多，而环球旅游更是很多人的梦想。首先环球旅游的概念应该是经过每个洲，而每个洲在典型的3个代表城市停留3天；另外，丰富的旅游路线应该选择不同的交通工具，包括飞机，轮船和汽车；如果能够去过北极和南极，环球旅游就更加完美；当然旅游者最后要回到自己的出发地。分别针对旅行路线路径最短、费用最少和时间最优建立模型，

关键词： TSP问题 蚁群算法 0-1变量

C题 环球旅游的路线设计

喜欢旅游的人越来越多，而环球旅游更是很多人的梦想。首先环球旅游的概念应该是经过每个洲，而每个洲在典型的3个代表城市停留3天；另外，丰富的旅游路线应该选择不同的交通工具，包括飞机，轮船和汽车；如果能够去过北极和南极，环球旅游就更加完美；

1

当然旅游者最后要回到自己的出发地。如果你有时间和金钱，身体又足够强壮，你能设计一条环球旅游的路线吗？

七大洲典型城市和地区

亚洲 北美洲 大洋洲 欧洲 非洲 南极洲 南美洲 北京 渥太华 悉尼 莫斯科 开普敦 南极 利马

（1） 设计经过地球典型城市和地区的环球旅行路线，旅行路线路径最短。 （2） 如果考虑费用最少，重新设计经过上面城市和地区的环球旅行路线。 （3） 能否设计一条时间最优的环球旅行路线，经过上面的城市和地区。 注意：1，费用需要独立查询，并注明航空，轮船和汽车的资料 2，假设每个城市的停留时间是3天

东京 洛杉矶 苏瓦 斯德哥尔摩 喀土穆 里约热内卢 曼谷 阿拉斯加 奥克兰 日内瓦 圣地亚哥

二、 问题假设

1、理想化城市，即地方任意两点都有交通工具。

2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑；

3、所有游客均健康，并且忽略上下飞机、列车和轮船的时间； 4、列车车次、飞机航班和轮船航班没有晚点等情况发生； 5、列车、飞机和轮船的票足够，没有买不到票的情况发生； 6、列车、航班和轮船的运营不受天气的影响； 7、绘图时，经线和纬线近似平行分布； 8、将城市和路径的关系转化为图论问题；

9、假设列车、飞机和轮船的速度均以国际标准计算；

三、 符号说明

GV 2

有向图矩阵 城市

A 路径 要经过的城市总数 任意两城市之间的距离 是否经过两座城市 路径上的信息量 启发函数 信息启发式因子 期望启发式因子 蚂蚁k在t时刻由i城市转向j城市的转移概率 第k只蚂蚁的禁忌搜索表 信息素挥发系数 tndij xij?ij nij? ?kpij?t? tabuk?k ??ij?t?L短时刻k蚂蚁在路径ij上留下的信息素量 蚂蚁携带的信息素量 到目前为止所找到的全局最短路径长度 本次循环中第k只蚂蚁所走的路程长度 蚂蚁的总数量 蚂蚁的编号 所记录的循环次数 最大循环次数 QLkmkncncmax 四、 问题分析

4.1问题一的分析

针对问题一，要求经过地球典型城市和地区的环球旅行路线，旅行路线路径最短。这类问题是单变量优化设计问题，问题一得变量是距离。因为运用传统的动态规划解法，解法的空间复杂性和时间复杂性都十分庞大，不利于求解，所以采用蚁群算法，通过计算机Matlab软件进行编程得到路程最短的旅行路线。，从而采用蚁群算法进行求解。

最后得出一个路径最短的旅游行程表。

4.2问题二的分析

针对问题二，要求设计一条费用最少的环球旅行路线。这和TSP问题,即旅行商问题有些类似，所以本文将问题向TSP问题进行一定的转化，从而进行求解。 因题目要求时间不限，用最少的费用环球旅行，而考虑到不同交通工具的速度和票价都不相同，所以我们对其行程进行详细的安排，尽量减少其在交通的费用，减少不必要的花费。

3

最后得出一个最少环球旅游费用的旅游行程表。 4.3问题三的分析

针对问题三，要求设计一条时间最优（时间最短）的环球旅行路线。因为考虑到交通工具的不同导致时间上的差异问题，所以仅用问题二的模型不能求解。但是由于任意两座城市之间都能相连接起来，且每座城市只经过一次，所以将任意两座城市之间的路程转变为时间，建立最优化模型，通过计算机Lingo软件进行编程，到时间最短的旅游路线。

然后，根据题目要求，再对其行程进行详细的安排，尽量避免不必要的时间。 最后得出一个最短时间的旅游行程表。

五、 模型的建立与求解

5.1问题一的求解

5.1.1建立图论的数学模型

将各个旅游景点之间的关系转化为图论问题，并做以下分析：

建立有向图G?(V,A)。其中V?{V1,V2,......,Vn}称为图G的顶点集，V中的

n称为该图的一个顶点，在该题中表示n城市；每一个元素Vi(i?1,2,......A?{a1,a2,......an}称为图G的弧集，A中的每个元素ak?(Vi,Vj)称为该图的一条0或1（1表示走

从Vi到Vj的弧，在此题中表示各个城市两两连线的集合。[1]

设城市个数为n，dij表示两个城市i与j之间的距离，xij?过城市i到城市j的路，0表示没有选择走这条路）。本题可以向TSP问题进行转

化，则TSP问题的数学模型为：

min?dijxij

i?j5.1.2建立蚂蚁算法的数学模型 (1)状态转移规则

因为蚂蚁k不能重复经过一个城市，所以建立禁忌表tabuk(k记录蚂蚁走过的城市，禁忌表随着时间做动态变化。

建立蚂蚁k由i城市转移到j城市的状态转移概率如下：

?1,2,......m)来

????ij(t)???ik(t)???? j?tabuk??kpij(t)?????is(t)???is(t)?? （1）

?s?tabuk? 0 j?tabuk??上式中?为信息启发式因子，表示路径的相对重要性，是对所积累的信息素

影响作用的一个加权值；?为期望启发式因子，表示能见度的相对重要性；

每只蚂蚁必须依据以城市距离和连接边上信息素的数量为变量的概率函数，决定选择下一个城市的概率。

每只蚂蚁必须根据禁忌表和概率函数寻找下一个城市，以保证该蚂蚁从起点出发经过所有城市有且只有一次，并且最终返回到起点。 (2)信息素的全局更新规则

当m只蚂蚁成功的完成一次寻径过程之后，将选出目标函数值最小的路径，用以完成全局信息素的更新，使得较优解保留下来，对后继蚂蚁产生影响，加快收敛到最优解的速度。

4

设i，j为两个相连接点，则有：

?ij(i,j)????1????ij?i,j??????ij?i,j? （2）

其中，变量??ij?i,j?是在t时刻，节点i,j之间路上信息素的增加量

?(L)??ij?i,j???短?0?1if?i,j??global?best?tourotherwise

?是位于[0,1]上的“激素”挥发因子；L短为到目前为止所找到全局最短路

径长度。

(3)信息素的局部更新

对于第k只蚂蚁，在建立一个解得过程中也同时进行激素迹的更新，如果节点i,j是它所选择路径上的两个相邻节点，规则如下：

?ij(t)????1????ij?t??????ij?t?

否则，不更新。其中，0＜?＜1，??ij(t)??0，?0是各条路上的信息素的初始值，通常取同一值，表示同一环境。

信息素的更新策略有很多种方法，每种更新策略的主要差别体现在??ijk?t?的求法上。我们规定蚂蚁在完成一个循环后更新所有路径上的信息素，其方程式为：

??ijkQ? k蚂蚁本次循环经过（i,j）?Lk （3） ?t????0 否则?上式中Q表示蚂蚁携带信息素的量，其值的大小影响算法的收敛速度；Lk表

示第k只蚂蚁在本次循环中所走的路程总长度。 5.1.3基于蚁群算法的实现步骤[2]

本题基于蚁群算法的实现步骤如下：

step1：初始化。时间t?0，循环次数nc?0，设置最大循环次数为nc，

max??ij?0??0；

step2：循环次数nc??；

；

step4：蚂蚁选择可以到达的城市，按照状态转移规则移动到下一个城市j； step5：对于城市j，由于已经到达，所以添加到禁忌表中；

step6：判断所有城市是否都经过，若未完全经过，表明蚂蚁个数没有达到

m，则转向执行step3，否则执行step7；

step7：由于信息素改变，要求按照公式（2）（3）更新最短路径信息素，

使得较优解保留，加快收敛到最优解的速度；

step8：若nc＜nc表明没有满足终止条件，即转向执行step2，否则执行

maxstep3：蚂蚁个数k??step9；

step9：输出最优结果。

5.1.4模型的求解

(1)求解城市之间的距离

首先，假设经线和纬线近似平行分布，根据附表1（见附录I）可知18座城市的经纬坐标。建立直角坐标系，以纬度最低的城市所在的纬线为x轴，以经度

5

最小的城市所在的经线为y轴，计算18座城市的坐标。

将城市进行编号，计算相应城市间的距离得到附表2（见附录I），得到编程数据（见附录II）。 (2)求解最短路径

利用上述蚁群算法的步骤，使用附录II的数据，编写Matlab程序，得出以下结果：

Shortest_Route =

1→ 2→ 8 →9 →7 →3 →14 →13 →15 →17 →18 →16 →5→ 6→ 4 →11

→12 →10

图一：Matlab模拟图

对上述结果进行处理，根据城市编号求出最优解为：

北京→东京→苏丹→奥克兰→悉尼→曼谷→喀土穆→开普敦→南极→里约热内卢→圣地亚哥→利马→洛杉矶→阿拉斯加→渥太华→斯德哥尔摩→日内瓦→莫斯科

由上面结果可以在中国地图上模拟出最短路线，如下：

6

图二：问题一模拟路径图

5.1.5设计旅游行程表和求出总费用

我们根据蚁群算法得出游览全部城市的最短路径，在得出的最短路径的基础上，我们通过查阅火车票价、车次、运营时间，等大量资料和数据，尽可能的减少其在行程上的花费并且得出最少的总旅游费用为56430元。 5.2问题三的求解 5.3.1模型的建立 基于第一问的模型，我们稍作改进。因为第二问要求安排时间最短的旅游行程表，而费用不限，由于飞机费用过大，所以在第一问我们未做考虑，但由于其时间比火车和汽车都要快的多，所以我们把飞机作为首要考虑对象加入第二问中。

第一问的模型中，是把任意两点之间的距离作为参数，从而进行求解，得出最短路径。在第二问中，我们把任意两点之间的所乘坐的交通工具的最短时间作为参数，建立时间最优化模型,结合Lingo软件（程序见附录III）求出经过所有旅游景点的花费时间最短的路线。 5.3.2模型的解释

在模型中，我们引入0-1变量，若通过两城市之间的路径，则赋值为1；若不通过两城市之间的路径，则赋值为0。对于无向图的最短时间路径问题，可以这样理解，从点到点和点到点的边，看成有向弧，其他各条边均看成有不同方向的双弧，因此，可以按照前面介绍有向图的最短时间路径问题来编程。[3] 5.3.3模型的求解

利用上述算法的步骤，使用附录II的数据，编写Lingo程序，得出以下结果：

7

Variable X( 1, 2) X( 2, 6) X( 3, 1) X( 4, 11) X( 5, 4) X( 6, 5) X( 7, 3) X( 8, 7) X( 9, 8) X( 10, 15) X( 11, 14) X( 12, 10) X( 13, 17) X( 14, 13) X( 15, 9) X( 16, 18) X( 17, 16) X( 18, 12) Value 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 Reduced Cost 2210.000 5534.000 3280.000 6011.000 3808.000 3674.000 7520.000 3217.000 2106.000 1688.000 5002.000 2421.000 6069.000 5676.000 1688.000 2460.000 3779.000 1169.000

即最短时间路径：

1→ 2→ 6 →5 →4 →11 →14 →13 →17 →16 →18 →12 →10 →15 →9 →

8 →7 →3

对上述结果进行处理，根据城市编号求出最优解为：

北京→东京→阿拉斯加→洛杉矶→渥太华→斯德哥尔摩→喀土穆→开普敦→里

8

约热内卢→利马→圣地亚哥→日内瓦→莫斯科→南极→奥克兰→悉尼→苏瓦→曼谷。

由上面结果可以在世界地图上模拟出最短路线，如下：

图三：问题二模拟路径图

六、 模型评价与改进

6.1模型的优点

1)在解题过程中，使用Matlab软件进行编程，在分析和运算方面有较高的精度，时间大大缩短，使答案更加明了。

2)合理恰当的使用了表格和图形，使数据的体现和意思的表达更加清晰。 3)答案详细、具体，并且接近实际，具有较强的可操作性。 4）解题过程中使用蚁群算法，避免繁琐的计算. 6.2模型的缺点

1)没有根据实际路况来解题，与实际存在很大的差异。 2)大多数数据来自于网络，数据缺乏准确性。

3)对问题五没有采用更精确的方法进行预测，缺乏合理性。 4）机票、车票和船票数据不是十分清晰,有待进一步提高.

9

本文来源：https://www.bwwdw.com/article/v196.html