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

徐 锋，杜军平XU Feng，DU Jun-ping北京邮电大学 智能通信软件与多媒体北京市重点实验室，北京 100876Beijing Key Lab of Intelligent Telecommunication Software and Multimedia，School of Computer Science，Beijing Univ 徐 锋，杜军平 XU Feng，DU Jun-ping 北京邮电大学 智能通信软件与多媒体北京市重点实验室，北京 100876 Beijing Key Lab of Intelligent Telecommunication Software and Multimedia，School of Computer Science，Beijing University of Posts and Telecommunications，Beijing 100876，China E-mail： HYPERLINK mailto:junpingdu@126.com junpingdu@126.com XU Feng，DU Jun -ping .Study on travel route planning based on improved ant colony algorithm.Computer Engineering and Applications，2009，45（23）：193-195. Abstract：This paper presents the casual meeting algorithm based on the basic ant colony algorithm and increases the quality for ant’s each tour for ant colony algorithm.Facing to the issue of travel route planning，this paper improves the calculating method of distance，and realizes the dynamic route planning for this algorithm and achieve scenic spot load balancing.The effec－ tive method for travel route planning based on improved ant colony algorithm is put forward.The experimental results show that the method is effective and practical. Key words：ant colony algorithm；combinational optimization；route planning；tourism 摘 要：在研究了基本蚁群算法后提出了偶遇算法，提高了蚁群算法蚂蚁一次周游的质量。针对旅游路线规划的问题，改进了路径 的求法，使蚁群算法可以实现动态规划，从而实现旅游景区的负载均衡。提出一种基于改进蚁群算法的旅游路线规划问题求解的 有效方法。实验结果表明该方法具有较好的有效性和实用性。 关键词：蚁群算法；组合优化；路线规划；旅游 DOI：10.3778/j.issn.1002-8331.2009.23.054 文章编号：1002－8331（2009）23-0193-03 文献标识码：A 中图分类号：TP311 旅游路线规划从区域范围可以分为三个部分：城市之间的 旅游路线规划、城市内各景区的旅游路线规划、景区内各景点 的旅游路线规划。城市之间的旅游路线规划和景区内各景点的 旅游路线规划 都是从一点出发，经过其他点，且只经过一次， 最后回到出发点的路线规划，即 TSP 回路问题[1]。这是一个经 典的 NP 难问题。所以解决方法非常多。其中包括：蚁群算法、 退火算法、遗传算法、粒子群算法和禁忌有哪些信誉好的足球投注网站算法等。该文采用 动态组合优化和蚁群算法进行问题求解 。 蚁 群 算 法（ant colony algorithm）是一种模拟进化算法，该算法由意大利学者 M.Dorigo、V.Maniezzo、A.Colorini 等人首先提出[2-4]，它是一种应 用于组合优化问题的启发式有哪些信誉好的足球投注网站算法，该算法在求解 TSP 问 题、分配问题[5]、job-shop 调度问题等都取得了较好的效果。 在旅游路线的规划中，需要系统在用户提交请求后，在最 短的时间内给出一个最优的路线规划