根据以上算法我们利用matlab软件编程（程序见附录5），得到最优旅行路径为
哈尔滨—长春—沈阳—天津—北京—呼和浩特—太原—石家庄—济南—郑州—西安—银川—兰州—西宁—乌鲁木齐—拉萨—昆明—成都—重庆—贵阳—南宁—海口—广州—澳门—香港—台北—福州—南昌—长沙—武汉—合肥—南京—杭州—上海—哈尔滨，旅行路线总长为1.6013万千米。
504540纬度35302520859095100105110经度115120125130
图 8 蚁群算法的最优路线图
21.951.91.851.81.751.71.651.64平均距离和最短距离x 100200400600蚁群算法的路径演化过程
图 7 蚁群算法的路径演化过程图
11
4．1．3模拟退火算法
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温（即退火），使之达到能量最低点。反之，如果急速降温（即淬火）则不能达到最低点。加温时，固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(?E(bT))，其中E为温度T时的内能，e为其改变量，b为Boltzman常数。
应用到本问题中，优化问题的一条旅行途径route及目标函数f（route）分别可以看成物体的一个状态和物体的能量函数，而其最优解就是最低能量状态。因而对应的设定的初始温度、基于Metropolis准则的搜索和控制温度参数t控制的下降过程也就相当于物理退火过程的加温、等温和冷却过程。
等温的过程中，我们采用Metropolis准则邻域搜索移动方法，也就是说根据一定概率决定当前解是否移向新解。由初始解由初始假设路径和控制参数初值t开始，对当前解重复产生“新解?计算目标函数差?接受或舍弃”的迭代，并逐步衰减t的值，算法终止时的当前解即为所得近似最优解，这是基于Metropolis的一种启发式随机搜索过程。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子，每个t值时的迭代次数L和控制温度系数a，因而我们所以我们可以通过上面的思想写出解决最短路径的模拟退火算法。算法步骤如下： (1)初始化：初始温度T0（充分大），初始解状态route(i)（随机选取一条旅行路线，算出走完此路线的长度f(x)作为目标函数，这是算法迭代的起点），每个T值的迭代次数L；
(2)对k=1至k=L最第(3)至第(6)步;
(3)产生新解route(j) (利用矩阵route(i)翻转来产生新的路径)； (4)计算增量?f?f(j)?f(i)，其中f(x)为目标函数；
(5)若?f?0则接受route(j)作为新的当前解，否则以概率exp（?f(Tk)/Tk） 接受route(j)作为新当前解；
(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法；
(7)Tk逐渐衰减，Tk?1?aTk，因而Tk趋于最低温度Tf，然后转第2步运算。
如下图所示（模拟退火算法框图）：
12
开始 产生i∈s，k=0，初始温度Tk?T0 设定L(Tk)，L=0 产生j∈s，L←L+1 计算?f?f(j)?f(i) Y ?f?0 N Y Exp（?f(T)?0） ki=j N N L?L(Tk) Y k←k+1,Tk降温 N Tk?Tf Y 结束 图3 模拟退火算法框图
13
5.554.54x 104路径总长度3.532.521.510500100015002000退火算法的路径长度演化过程25003000
图4 退火算法迭代运算图
根据以上算法我们利用matlab软件编程（程序见附录6），得到最优旅行路径为：哈尔滨—长春—沈阳—北京—天津—济南—石家庄—太原—呼和浩特—银川—西宁—兰州—成都—重庆—西安—郑州—武汉—长沙—南昌—合肥—南京—上海—杭州—福州—台北—香港—澳门—广州—海口—南宁—贵阳—昆明—拉萨—乌鲁木齐—哈尔滨，旅行路线总长为1.6676万千米。
504540纬度35302520859095100105110j经度115120125130
图5 退火算法求得的最佳路径图
14
4.2 模型Ⅱ的建立与求解
首先，我们利用火车票网查询到每两个城市之间的最经济火车票矩阵与最经济的飞机票矩阵，将二者每个对应元素取最小组成新的费用矩阵。（如附录2所示）
对问题（2）所求的最优订票方案在一定程度上相似于模型Ⅰ的所得的最短路径，所以我们利用原有的旅行网络的城市之间车费的逻辑属性代替原有的城市之间的路线长度的物理属性。
所以在城市旅行网络加权图上，我们将赋权边EG改为表示两个城市间的最经济的旅行方式的费用，表示为：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(imdon)?1,wviv(idmovivi?1n)?1记H(G))?EG。
为G中所有Hamilton回路的集合，定义w(S)??w1?i?n?1?wvnv1；目的是要寻
找一条最短的Hamilton回路S*， 使得w(S*)?min格最经济的订票方案。
3.5x 104S?H(G)w(S)，即可得到旅行价
32.5总费用21.510.5050010001500退火算法演化过程20002500
图 9 退火算法总费用计算图
在模拟退火算法与蚁群算法的基础上，我们利用新的矩阵计算得到最经济的
15