蚁群算法与模拟退火算法对旅游路线问题的探究(附matlab程序)

蚁群算法与模拟退火算法对旅游路线问题的探究

张煊 张恒伟 徐晓辉

摘要： 本文针对旅游中国34个城市的路线最优化问题，收集各城市经纬度坐标和实际城市间火车票与飞机票，在此大量数据的基础之上，采用蚁群算法和模拟退火算法进行启发式搜索，就实际问题给出了合理最优的旅行路线和订票方案。

按照问题要求，首先建立了城市旅行网络，同时对网络图赋权，对数据进行了收集和简单的处理，得到了经纬度坐标、火车票矩阵、飞机票矩阵及其对应的时间矩阵。

对于问题（1），我们根据各城市经纬度坐标，利用经纬度知识和球体的几何知识，计算出各城市之间的距离，得到各个城市之间的距离矩阵，分别采用蚁群算法与模拟退火算法搜索，将结果比较得到最短旅行路线为：哈尔滨—长春—沈阳—天津—北京—呼和浩特—太原—石家庄—济南—郑州—西安—银川—兰州—西宁—乌鲁木齐—拉萨—昆明—成都—重庆—贵阳—南宁—海口—广州—澳门—香港—台北—福州—南昌—长沙—武汉—合肥—南京—杭州—上海—哈尔滨，旅行路线总长为1.6013万千米。

在问题（2）的求解中，首先用城市旅行网络的车费价格代替城市之间距离，重新赋权，在模型Ⅰ的基础上，利用最小费用矩阵，采用蚁群算法和模拟退火算法搜索，比较计算结果得到最经济的订票方案为：哈尔滨—1489—长春—1416—天津—1416—济南—1462—南京—1462—上海—1374—杭州—2002—福州—1216—南昌—K162—合肥—D3024—武汉—MU517—台北—CZ6997—澳门—MU2790—西宁—1282—拉萨—K918—兰州—1043—乌鲁木齐—1043—西安—2612—郑州—T201—海口—T201—广州—T99—香港—T98—长沙—2514—南宁—2058—昆明—1236—贵阳—1248—重庆—1271—成都—1718—银川—2636—呼和浩特—2464—太原—2610—石家庄—4410—北京—1138—沈阳—1122—哈尔滨，费用7212元。

针对问题（3）中所述的经济、省时又方便的原则，我们建立了旅行路线评价指标Q，综合考虑各方面因素，并以人为本修正指标参数，最终得到指标表达式Q=0.6M+8t，并以此为权，处理数据得到指标矩阵，在模型Ⅰ的基础上得到最优旅行路线：哈尔滨—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元。

本文综合采用了蚁群算法和模拟退火算法，计算得到的最优路线能满足问题的需要。就周先生的外出旅行提供了参考方案，搜集了大量的数据，紧密的与实

1

际相结合，得到的方案可行性强，能很好地解决旅行方案的优化问题及类似的组合优化问题，并可以广泛的应用于其它领域。

关键词： 模拟退火算法 蚁群算法 旅行路线评价指标

1.问题重述

计算从哈尔滨走遍全国34个城市的最短距离，设计出合理算法规划出不同约束条件下的不同最优方案：

1．首先在不考虑外部因素的情况下，利用地球的经纬度，计算各个城市之间距离，建立数学模型，并规划出最优游遍34座城市的最短路线。

2．若2010年5月1日从哈尔滨市出发，在每个城市停留3天，利用航空、铁路（快车卧铺或动车）交通工具，考虑到车次、航班情况，设计出游遍34座城市的最经济的旅行互联网上订票方案。

3．在综合实际情况下考虑省钱、省时又方便，设定出相应的评价准则和指标，建立相应改进后的数学模型，并在此前提下修订上述两种方案。

4．对本文所用到的算法作复杂性、可行性及误差分析。

5．针对旅行商问题提出对自己所采用的算法的理解及评价。

2 模型假设与符号说明

2.1 模型假设

（1） 近期内火车票视为定值；

（2） 飞机票的取值均取自打折后的； （3） 飞机票均取自近期内的；

（4） 估算城市之间的距离时忽略地形如丘陵盆地等自然因素对估算结果的影

响；

2.2 符号说明

?A、B两市之间的距离 AB

G?(VG,EG) 加权图

定点（城市）的集合

VG

EG赋权边的集合

纬度 经度

第i个城市到第j个城市的距离 i个城市构成的环路矩阵

? ?

d

ijroute(i)

2

Tk

a L

tabuk（k=1，2，?，m ）

?ij

第k时刻的温度（k=1,2, ?，m） 温度控制系数

退火算法内循环循环次数

禁忌表，记录蚂蚁k当前已走过的城市 表示城市i转移到城市j的期望程度

蚁群算法中，蚂蚁总数

表示t时刻在路径（i，j）连线上残留的信息量 蚁群算法的循环次数

第k只蚂蚁在本次循环中所走路径的总长度 旅行费用 旅行时间

旅行评价指标

m

?ij(t)

Nc

Lk

M t Q

3. 问题分析

该问题是一个旅行路径的组合优化问题，其形式化描述为：用节点来表示34个城市,连接两节点之间的边表示旅行路线,并将路线的长度等属性表示为该边的权值,那么就可以把城市旅行网络抽象为一个带权有向图。给定一个带权有向图G为二元组G=(V,{E}),其中V是包含n个节点的集合,E是包含h条边(弧段)的集合,（i, j）是E 中从节点i 至j 的边,wi,j是边（i,j）的非负权值。设S,T 分别为 V中的起始节点和目标节点,则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。，则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。

在不同需求条件的影响下，城市旅行路线网不仅有道路路线等物理属性,同时也具有路线长度、旅行时间、车票价格等各种其它逻辑属性，因而改变着旅行的最优路线。

问题（1）中，我们根据实际的地理位置经纬度，利用几何知识计算出每两个城市之间的距离，并以距离为权，进而建立模型，求解。设定出游遍34座城市的最优旅行路线。

问题（2）中，设定方案针对各个城市之间交通条件的不同，考虑实际情况，通过互联网上的票务查询得到近期城市间的火车票价与飞机票价，并以价格为权，建立相应数学模型得到有关费用最低的最优旅行路线。

问题（3）中，在问题（1）、（2）分析的基础之上，建立经济、省时又方便的评价准则，提出自己观点，以此修订最优旅行方案。

问题（4）中，对所用算法进行复杂性、可行性及误差分析讨论；

3

问题（5）中，关于旅行商问题提出求解所采用的相应算法的理解及评价。 本问题属于旅行商（TSP）的一类问题，可以采用模拟退火算法和蚁群算法来对数据进行搜索解决，得到合理的优化路线。

4.模型的建立与求解

4.1 模型Ⅰ的建立与求解

根据问题分析，我们首先创建城市旅行网络图，给定加权图G?(VG,EG)，其中VG表示顶点（城市）的集合表示为：VG?{1,2,?,34}。EG为赋权边(表示两个城市间的距离)的集合，即两地间距离（km）。表示为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

S?H(G)w(S)。

分别利用蚁群算法和模拟退火式算法对所得数据进行搜索计算。 4.1.1 城市间距离的估算

34个城市经纬度具体数值（如表1）所示：

表1 各个城市经纬度 编号 省会 纬度(北纬) 45?44? 1 哈尔滨 43?45? 2 乌鲁木齐 43?54? 3 长春 41?48? 4 沈阳 40?48? 5 呼和浩特 39?55? 6 北京 39?02? 7 天津 38?27? 8 银川 38?02? 9 石家庄 37?54? 10 太原 36?40? 11 济南 36?38? 12 西宁 36?04? 13 兰州 34?46? 14 郑州 34?17? 15 西安

4

经度(东经) 126?36? 87?36? 125?19? 123?25? 111?41? 116?24? 117?12? 106?16? 114?30? 112?33? 117?00? 101?48? 103?51? 113?40? 108?57?

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

经线 南京 合肥 上海 武汉 成都 杭州 重庆 拉萨 南昌 长沙 贵阳 福州 昆明 台北 广州 南宁 香港 澳门 海口 32?03? 31?52? 31?14? 30?35? 30?40? 30?16? 29?59? 29?39? 28?40? 28?12? 26?35? 26?05? 25?04? 25?03? 23?08? 22?48? 21?23? 21?33? 20?02? 118?46? 117?17? 121?29? 114?17? 104?04? 120?10? 106?54? 91?08? 115?55? 112?59? 106?42? 119?18? 102?42? 121?30? 113?14? 108?19? 115?12? 115?07? 110?20? N(北极) 纬线 ?赤道 首子午线 S（南极） 图1. 地球几何解析图

首先把地球看成是标准球体，球心为点O，把任意两个城市看成是A 、B两点，则地球上的两个点A、 B在赤道面上的投影点分别为A?、B? 。假设地

5

根据以上算法我们利用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

旅行互联网上的订票方案，即为：哈尔滨—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

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