一、 问题重述
摘要
喜欢旅游的人越来越多，而环球旅游更是很多人的梦想。首先环球旅游的概念应该是经过每个洲，而每个洲在典型的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