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

1蚁群算法与模拟退火算法对旅游路线问题的探究张煊张恒伟徐晓辉摘要：本文针对旅游中国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元。本文综合采用了蚁群算法和模拟退火算法，计算得到的最优路线能满足问题的需要。就周先生的外出旅行提供了参考方案，搜集了大量的数据，紧密的与实2际相结合，得到的方案可行性强，能很好地解决旅行方案的优化问题及类似的组合优化问题，并可以广泛的应用于其它领域。关键词：模拟退火算法蚁群算法旅行路线评价指标1.问题重述计算从哈尔滨走遍全国34个城市的最短距离，设计出合理算法规划出不同约束条件下的不同最优方案：1．首先在不考虑外部因素的情况下，利用地球的经纬度，计算各个城市之间距离，建立数学模型，并规划出最优游遍34座城市的最短路线。2．若2010年5月1日从哈尔滨市出发，在每个城市停留3天，利用航空、铁路（快车卧铺或动车）交通工具，考虑到车次、航班情况，设计出游遍34座城市的最经济的旅行互联网上订票方案。3．在综合实际情况下考虑省钱、省时又方便，设定出相应的评价准则和指标，建立相应改进后的数学模型，并在此前提下修订上述两种方案。4．对本文所用到的算法作复杂性、可行性及误差分析。5．针对旅行商问题提出对自己所采用的算法的理解及评价。2模型假设与符号说明2.1模型假设（1）近期内火车票视为定值；（2）飞机票的取值均取自打折后的；（3）飞机票均取自近期内的；（4）估算城市之间的距离时忽略地形如丘陵盆地等自然因素对估算结果的影响；2.2符号说明BAA、B两市之间的距离),(GGEVG加权图GV定点（城市）的集合GE赋权边的集合纬度经度dij第i个城市到第j个城市的距离)(iroutei个城市构成的环路矩阵3Tk第k时刻的温度（k=1,2,…，m）a温度控制系数L退火算法内循环循环次数ktabu（k=1，2，…，m）禁忌表，记录蚂蚁k当前已走过的城市ij表示城市i转移到城市j的期望程度m蚁群算法中，蚂蚁总数)(tij表示t时刻在路径（i，j）连线上残留的信息量Nc蚁群算法的循环次数kL第k只蚂蚁在本次循环中所走路径的总长度M旅行费用t旅行时间Q旅行评价指标3.问题分析该问题是一个旅行路径的组合优化问题，其形式化描述为：用节点来表示34个城市,连接两节点之间的边表示旅行路线,并将路线的长度等属性表示为该边的权值,那么就可以把城市旅行网络抽象为一个带权有向图。给定一个带权有向图G为二元组G=(V,{E}),其中V是包含n个节点的集合,E是包含h条边(弧段)的集合,（i,j）是E中从节点i至j的边,wji,是边（i,j）的非负权值。设S,T分别为V中的起始节点和目标节点,则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。，则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。在不同需求条件的影响下，城市旅行路线网不仅有道路路线等物理属性,同时也具有路线长度、旅行时间、车票价格等各种其它逻辑属性，因而改变着旅行的最优路线。问题（1）中，我们根据实际的地理位置经纬度，利用几何知识计算出每两个城市之间的距离，并以距离为权，进而建立模型，求解。设定出游遍34座城市的最优旅行路线。问题（2）中，设定方案针对各个城市之间交通条件的不同，考虑实际情况，通过互联网上的票务查询得到近期城市间的火车票价与飞机票价，并以价格为权，建立相应数学模型得到有关费用最低的最优旅行路线。问题（3）中，在问题（1）、（2）分析的基础之上，建立经济、省时又方便的评价准则，提出自己观点，以此修订最优旅行方案。问题（4）中，对所用算法进行复杂性、可行性及误差分析讨论；4问题（5）中，关于旅行商问题提出求解所采用的相应算法的理解及评价。本问题属于旅行商（TSP）的一类问题，可以采用模拟退火算法和蚁群算法来对数据进行搜索解决，得到合理的优化路线。4.模型的建立与求解4.1模型Ⅰ的建立与求解根据问题分析，我们首先创建城市旅行网络图，给定加权图),(GGEVG，其中GV表示顶点（城市）的集合表示为：}34,,2,1{GV。GE为赋权边(表示两个城市间的距离)的集合，即两地间距离（km）。表示为RwVjiwjiEijGijG,,,,,。Hamilton路径图可以表示为：121vvvvSn；其中GiVv，jivvji,341，且对341i，有GvvniiEwvvnii),,(1)mod(1)mod(。记)(GH为G中所有Hamilton回路的集合，定义1111)(nivvvvniiwwSw；目的是要寻找一条最短的Hamilton回路*S，使得)(min)()(*SwSwGHS。分别利用蚁群算法和模拟退火式算法对所得数据进行搜索计算。4.1.1城市间距离的估算34个城市经纬度具体数值（如表1）所示：表1各个城市经纬度编号省会纬度(北纬)经度(东经)1哈尔滨4445631262乌鲁木齐544363873长春4543911254沈阳8441521235呼和浩特8440141116北京5539421167天津2039211178银川7238611069石家庄20380311410太原45373311211济南04360011712西宁83368410113兰州40361510314郑州64340411315西安713475108516南京30326411817合肥25317111718上海41319212119武汉53307111420成都04304010421杭州61300112022重庆95294510623拉萨9329809124南昌04285511525长沙21289511226贵阳53262410627福州50268111928昆明40252410229台北30250312130广州80234111331南宁84229110832香港32212111533澳门33217011534海口202002110图1.地球几何解析图首先把地球看成是标准球体，球心为点O，把任意两个城市看成是A、B两点，则地球上的两个点A、B在赤道面上的投影点分别为A、B。假设地S（南极）首子午线纬线赤道经线N(北极)6球平均半径为R，A点北纬i，东经i，B点北纬j，东经j，基于球体几何知识因此可以得到：iRcosAO，jRcosBO（1）投影下来的BOA=ji（2）图2地球经纬度利用余弦定理可得到：)cos(RcosRcos2cosRcosRBAj22222jijii（3）)sin(sinRBAji（4）利用勾股定理得到：222BABAAB（5）将（3）、（4）代入（5）式中：2AB=jijijisinsin2R)cos(coscos2R2R222（6）令AOB为，同样利用余弦定理可得到：cosRR2RRAB222（7）化简得：jijijisinsin)cos(coscoscos（8）则地球上两点AB之间距离即AB弧长为)sinsin)cos(coscos(cosjijijiarRRBA（9）即BA为两地之间的实际路径。OjijiZYXB’A’1BA7因此我们根据表一中所示的各城市经纬度经过计算得到各城市间的距离（详见附录1）。4.1.2蚁群算法建立模型蚁群觅食的过程与此组合优化问题的求解相似，找到一条只经过每个城市一次且回到起点的、最短路径的回路。设城市i和j之间的距离为ijd。求解中，假设蚁群算法中的每只蚂蚁是具有下列特征的简单智能体。（1）每次周游，每只蚂蚁在其经过的支路（i，j）上都留下信息素。（2）蚂蚁选择城市的概率与城市之间的距离和当前连接支路上所包含的信息素余量有关。（3）为了强制蚂蚁进行合法的周游，知道一次周游完成后，才允许蚂蚁游走已访问过的城市（这可由禁忌表来控制）。蚁群算法中的基本变量和常数有：m，蚁群中蚂蚁的总数；n，TSP问题中城市的个数；ijd为城市i和j之间的距离，其中(1,34)j,i；)(tij，表示t时刻在路径（i，j）连线上残留的信息量。在初始时刻各条路径上信息量相等，并设)0(ij=const（const为常数）。蚂蚁k（k=1，2，…，m）在运动过程中，根据各条路径上的信息量决定其转移方向。)(tpkij表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率，根据各条路径上残留的信息量)(tij及路径的启发信息ij来计算的，如（10）所示。表示蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向。)(tpkij=其他0)]([)]([)]([)]([kallowedsisisij