改进蚁群算法在旅游路线规划中的应用研究-副本.pdfVIP

ComputerEngineeringandApplications计算机工程与应用 2009，45(23) 193 改进蚁群算法在旅游路线规划中的应用研究 徐 锋，杜军平 XU Feng，DU Jun—ping 北京邮电大学 智能通信软件与多媒体北京市重点实验室，北京 100876 Beijing KeyLabofIntelligentTelecommunication Software and Muhimedia，SchoolofComputerScience，BeijingUniversityof PostsandTelecommunications，Beijing100876，China E—mail：junpingdu@126．eom XU Feng．DU Jun—ping．Study on travelroute planning based on improved ant colony algorithm．Computer Engineering andApplications，2009，45(23)：193—195． Abstract：Thispaper presentsthe casualmeeting algorithm based on the basic antcolony algorithm and increases the quality for ant’S each tourofr antcolony algorithm．Facing to the issue of travel route planning，this paper improves the calculating method ofdistance，and realizesthedynamic route planningforthisalgorithm and achieve scenic spotload balancing．The effec— tive method ofrtravelroute planning based on improved antcolony algorithm isputforward．The experimentalresults show that the method iseffective and practica1． Key words：antcolony algorithm；combinationaloptimization；routeplanning；tourism 摘 要：在研究了基本蚁群算法后提 出了偶遇算法，提高了蚁群算法蚂蚁一次周游的质量。针对旅游路线规划的问题 ，改进了路径 的求法，使蚁群算法可以实现动态规划，从而实现旅游景区的负载均衡。提出一种基于改进蚁群算法的旅游路线规划问题求解的 有效方法。实验结果表明该方法具有较好的有效性和实用性。 关键词：蚁群算法；组合优化；路线规划；旅游 DOI：10．3778~．issn．1002—8331．2009．23．054 文章编号：1002—8331(2009)23—0193—03 文献标识码：A 中图分类~：TP311 旅游路线规划从区域范围可以分为三个部分 ：城市之间的 有很好的表现。 旅游路线规划 、城市内各景区的旅游路线规划、景区内各景点 的旅游路线规划。城市之问的旅游路线规划和景区内各景点的 1 蚁群算法 旅游路线规划 都是从一点出发 ，经过其他点 ，且只经过一次 ， 下面以TSP问题为例说明基本蚁群算法的框架I61。没有m 最后回到出发点的路线规划，即TSP回路问题ll1。这是一个经 个城市，n只蚂蚁 ，采用d表示城市 i到城市 之间的距离，在 典的NP难问题。所以解决方法非常多。其中包括：蚁群算法 、 ． 退火算法、遗传算法、粒子群算法和禁忌有哪些信誉好的足球投注网站算法等。该文采用 欧氏TSP中，，为 i到 之间的欧氏距离，即 ，=[(-x)+(一 动态组合优化和蚁群算法进行 问题求解 。蚁群算法 (ant