走遍全中国
摘要
本文解决了周游先生周游全中国的最短路径的选取及基于省钱、省时又方便的互联网订票方案。
对于问题（1），考虑到从34个城市中制定最短的旅游路线，这是一个对称的旅行商问题（TSP），如果采用动态规划进行求解，空间复杂性及时间复杂性都十分庞大。因此，为解决问题（1），本文采用人工蚁群算法进行求解，即利用MATLAB进行计算机求解，得出全国34个城市点到点最短路径的最优解，此方法节约计算资源，具有良好的可扩展性和健壮性。
对于问题（2）与问题（3）本文将其归为一类考虑，即在问题（1）得出的路线最优解的前提下，设计省钱、省时又方便的互联网订票方案。为解决问题（2）（3）,本文将此问题归为多属性决策问题，本文综合考虑了每一个车次或航班的出发时间、达到时间、旅途时间、里程或航程、票价和交通方式，并且将这些因素同周游先生主观因素结合起来，设计决策树，制定相应的问卷调查，然后计算周游先生对城市甲到城市乙中每一个车次和航班的满意度，将满意度最高的作为此路段的最佳订票结果，进而得出全部订票结果（详见附录-最佳订票方案）。
部分结果：总旅行时间Tz?103天；购票总价Pz?19857元；总行程（实际行程）
Sz?18793km；平均满意度Hz?7.438
关键词：TSP ； 人工蚁群 ； 最短路径 ； 决策树 ； 满意度
1
一、
1.1
问题重述
问题重述与分析
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
（1）按地理位置（经纬度）设计最短路旅行方案；
（2）如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
（3）要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
（4）对你的算法作复杂性、可行性及误差分析；
（5）关于旅行商问题提出对你自己所采用的算法的理解及评价。
1.2 问题分析
随着人们生活水平的不断提高，旅游已经成为人们忠爱的休闲方式之一。 在制定旅游计划的同时需要考虑很多方面的问题，比如：旅游路线的选择、交通工具的选择、旅途用时、经济花销等等。为了在完成旅游计划的基础上实现省时、方便、经济的目标，需要制定一个最优的旅游方案。
本文给出周游先生的旅游计划—游遍中国的省会城市、直辖市、香港、澳门以及台北，要求达到旅途最短、经济、省时又方便的目的，为了实现这一目标，需要制定一个最优的旅游方案。首先要实现旅途最短，本问题属于一个对称旅行商（TSP）问题，很显然，如果利用传统的动态规划解法在N为34的情况下，解法的空间复杂性及时间复杂性都十分庞大，不利于旅行方案的确定，因此，本文采用人了工蚁群算法，通过计算机编程可以得到最优以及次优的旅行路线。
得到优化后的旅游路径后，本文需要考虑另外的条件，经济问题、时间问题、方便问题等，为了综合考虑这几方面的因素，需要制定一个决策模型，设计决策树与问卷调查，通过问卷调查可以得到人们对于出发时间、达到时间、旅途时间、里程或航程、票
2
价和交通工具的选择标准，再通过合理的计算，得出满意的互联网订票方案。
二、 模型的基本假设和符号说明
2.1 模型假设
（1）省会与省会之间的距离为球面最短距离； （2）绘图时省会分布图上经线、纬线近似平行分布； （3）票价不考虑除打折以外的其他优惠；
（4）在旅行过程中只考虑购票的经济花费，不考虑其他的消费； （5）旅行中所乘的车次或航班均准点到达； 2.2 符号说明 模型（1）：
N： 要经过的城市总数；
dij: 任意两城市之间的距离；
L(s)： 表示蚂蚁s行走的城市集合； f(w): 表示城市1 2??n的一个排列；
?ij： 信息值；
?k: 挥发因子； W： 城市经纬度；
S1: 最短路径最优解； S2: 最短路径次优解；
模型（2）、（3）：
mi : 两城市间的旅行方式（动车m1、快车卧铺m2、航空m3）；
N: 车次或航班；
t： 车次或航班的出发时间； tt: 车次或航班的到达时间；
3
T: 车次或航班的旅行时间； S： 车次或航班的里程；
P： 车次或航班的票价；
G(m)： 旅行方式的重要性程度；
G(t)： 出发时间的重要性程度； G(tt)： 到达时间的重要性程度； G(T)： 旅行时间的重要性程度； G(S)： 旅行里程的重要性程度； G(P)： 旅行价格的重要性程度；
Hlm(m)： 旅行方式的满意度；
Hlt(t) ： 出发时间的满意度；
Hltt(tt)： 到达时间的满意度； HlT(T) ： 旅行时间的满意度；
HlS(s) ： 旅途里程的满意度；
HlP(P) ： 旅途价格的满意度； TX： 总行程时间；
Ty： 总的停留天数； Sz： 总行程；
Pz： 购票总价；
TZ： 完成旅游计划总用时； Hz： 平均满意度；
4
三、模型的建立及求解
3.1 问题（1）模型的建立及求解 3.1.1 模型的建立
周游先生要在全国省会包括直辖市、香港、澳门共34个地点旅游，要求出最短旅行路线。
本问题属于一个对称旅行商（TSP）问题，利用传统的动态规划解法[1]在N为34的
[6]情况下，解法的空间复杂性及时间复杂性都十分庞大，因此，本文采用人工蚁群算法[2]、进行求解。
图1
如图1所示，蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。
图2
5