旅行互联网上的订票方案，即为：哈尔滨—1489—长春—1416—天津—1416—济南—1462—南京—1462—上海—1374—杭州—2002—福州—1216—南昌—K162—合肥—D3024—武汉——台北——澳门——西宁—1282—拉萨—K918—兰州—1043—乌鲁木齐—1043—西安—2612—郑州—T201—海口—T201—广州—T99—香港—T98—长沙—2514—南宁—2058—昆明—1236—贵阳—1248—重庆—1271—成都—1718—银川—2636—呼和浩特—2464—太原—2610—石家庄—4410—北京—1138—沈阳—1122—哈尔滨，总费用为7212元。
504540纬度35302520859095100105110经度115120125130
图 10 问题2中最佳旅行路线图
4.3 模型 Ⅲ的建立与求解
我们针对综合省钱、省时又方便的条件，建立旅行评价指标。
首先我们考虑方便的原则，在通过互联网查询每个车次航班时，优先考虑直达火车与直飞航班，避免在旅途中可能出现的转机与转车，在最大限度上确保旅途中的方便性原则。在此基础上得到，城市之间的费用矩阵与旅行时间矩阵。
然后在经济与省时的考虑下，我们假设出旅行指标
Q=fM+qt （15）
其中： f为费用启发因子，反映了旅行中所花费的车费的相对重要程度； q为时间启发因子，反映了旅行中所花费的时间的相对重要程度；
16
根据部分实际的火车票的旅行时间和车票费用，我们得到下表：
表 2 部分火车车票价格与行时对应表 车次 发站 到站 车票价钱 历时 票价∕时间 2008 哈尔滨 长春 54 02：48 19.29 K339 北京 沈阳北 172 09：14 18.63 T164 上海 兰州 410 20：39 19.85 T253 天津 郑州 195 09：03 21.55 T118 西安 南京 263 12：24 21.21 由上表大致可以得到f与q比值约为20.0，即在一定程度上一个小时与20元是等价的。因而我们得到旅行评价指标Q?
Q?=M+20t
（16）
可理解为对于A城与B城的一种旅行方案，旅行指标越小，对于周先生来说，就越有价值，越可能选择。
假设一个退休的旅行者，由于收入的制约，旅行费用会相对重视一点，所以我们对原有的指标进行修订，因而我们在原有的费用启发因子与时间启发因子的基础上分别乘以0.6与0.4的平衡系数得到新的费用启发因子与时间启发因子，最终得到旅行评价指标Q
Q=0.6M+8t （17） 在旅行评价指标的基础之上，我们将赋权边EG改为表示两市之间最小的旅行费用指标，并根据公式（17）得到指标矩阵(见附表3），表示为：
EG??i,j,wij?,i,j?VG,wij?R???；
Hamilton路径可以表示为：S??v1v2?vnv1?；其中，vi?VG，
1??i?j?34,vi?vj，且对1?i?34，有(vi,v(imodn)?1,wvvi(imodn)?1)?EG。
?wvnv1；目的
记H(G)为G中所有Hamilton回路的集合，定义w(S)?是要寻找一条最短的Hamilton回路S*， 使得w(S*)?min?w1?i?n?1vivi?1S?H(G)w(S)，求解结果
即为旅行经济、省时又方便的订票方案。
优化方案为：哈尔滨—2096—长春—1490—天津—1394—济南—1085—郑州—1150—西安—1085—兰州—T27—拉萨—T21—西宁—MU2790—澳门—CZ6997—台北—CA4912—武汉—D3024—合肥—D3020—南京—D5401—上海—D5655—杭州—D3107—福州—1216—南昌—T147—长沙—T98—香港—T99—广州—T201—海口—GS7441—南宁—2058—昆明—1236—贵阳—K9518—重庆—D5111—成都—K452—乌鲁木齐—SC4912—银川—1718—呼和浩特—2462—太原—2610—石家庄—4408—北京—D25—沈阳—K19—哈尔滨，Q值为6532,总费用为8092元。
17
504540纬度35302520859095100105110经度115120125130
图 11 问题3中优化旅行方案图
5．模型的复杂性与可行性分析
5．1 复杂度分析
模型Ⅰ、模型Ⅱ、模型Ⅲ都是在蚁群算法与模拟退火算法的基础上，全国34个城市旅行条件下建立的TSP问题的模型。假设此问题通过枚举的办法得到最优解，但是将以大量的时间为代价，造成理论上的可解而实际上的不可解。本题中的可行路径共有
(n?1)!2条，若以路经比较为基本操作，则需
(n?1)!2?1次比
较才可获得最优解，可能会需要上百年的时间。作为比较，以下我们对蚁群算法与模拟退火算法的复杂性进行分析。
5.1.1蚁群算法的复杂度分析
蚁群算法的复杂度分析是在理论上对蚁群算法的算法效率的分析。对于上述模型中的蚁群算法，34个城市是TSP的规模，m为蚂蚁的数量，Nc为算法的循环次数，从蚁群的算法过程我们得到各环节的时间复杂度，如下表所示：
18
Step 内容 初始化：set t=0；set Nc=0 1 set ?ij(t)= const，??ij(t)=0； 2 设置蚂蚁禁忌表 set s=0； for k= 1 to m do 置第k个蚂蚁的起始城市到禁忌表tabuk 3 每只蚂蚁单独构造解 循环计算直到禁忌表满 set s=s+1； for k= 1 to m do 根据转移概率pijk(t)选择下一个城市 将城市序号j加入禁忌表tabuk 4 解的评价和轨迹更新量的计算 将第k只蚂蚁在从禁忌表tabuk(n)转移到tabuk(1) 计算第k只蚂蚁在本次循环中的路径长度 更新最优路径 计算各条路径的信息数反馈量??ij(t) 5 信息数轨迹浓度的更新 计算各条路径在下一轮循环前的信息数强度?ij(t?n) set t =t+n; set Nc=Nc+1 6 判定是否达到终止条件 如果Nc?Ncmax,且搜索出现停止现象 清空全部禁忌表 返回step2 否则 输出最短路径 结束 T(n) O(n?m)2 O(m) O(n2m) O(n2) O(n2) O(nm)
19
5.1.2模拟退火算法的复杂度分析
模拟退火算法的复杂度分析是在理论上对模拟退火算法的算法效率的分析。对于上述模型中的模拟退火算法，34个城市是TSP的规模,每个t值时的迭代次数L是内循环的循环次数，由降温过程Tk?1?aTk我们得到控温循环次数log从模拟退火的算法过程我们得到各环节的时间复杂度，如下表所示：
STEP 内容 T（n） 初始化：设定初始温度T0 ，终止温度Tf; O(1) 1 set k =0 Tk=T0; 2 3 每个t值时的迭代次数L; for j=1 to L do； 翻转矩阵route(i)得到新的路径route(j); 计算?f?f(j)?f(i); 若?f?0则接受route(j)作为新的当前解，否则以概率exp（?f(Tk)/Tk） 接受route(j)作为新当前解； 4 5 判断是否满足内循环终止条件L 若满足，则跳出循环； 若不满足，则回到step2; 降温过程： Tk?1=aTk； T0rTf，
O(m) O(LlogT0rTf) O(LlogT0rTfT0) k=k+1; O(logrTf) 判断是否达到终止温度 如果没有满足或搜索没有出现停止现象 6 返回step2 否则 打印最短路径
O(logT0rTf)
20