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

张煊 张恒伟 徐晓辉

摘要： 本文针对旅游中国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