交通网络旅行商路径优化的遗传禁忌搜索算法

doi:10.13485/j.cnki.11-2089.2014.0184

摘要/Abstract

摘要：

旅行商路径优化问题是经典的网络分析问题之一。由于旅行商问题具有NP Hard特性，主要通过智能优化方法或启发式算法来获得近似最优解。然而，单一智能优化方法存在运算量过大、参数选择苛刻，对初值依赖性强等缺陷，很难快速实现全局优化。结合多种优化机制和邻域搜索结构设计混合启发式算法可在一定程度上解决这一问题。本文结合遗传算法的全局寻优能力和禁忌搜索的记忆功能，设计实现了一种基于分散集中策略的禁忌遗传算法，即采用遗传变异算子作为分散策略构造邻域，开辟新的搜索空间，有效提升获得全局最优解的概率；将禁忌搜索作为集中策略进行局部寻优，避免迂回探测，充分体现禁忌搜索较强的“爬山”能力，并通过实际交通网络和不同规模的节点集合，从求解精度、稳定性和效率三个方面对算法进行了评价。结果表明，本文提出的交通网络旅行商路径优化的禁忌遗传算法平均求解精度比禁忌搜索算法提高了9%，略优于ArcGIS；当与ArcGIS求解的TSP路径长度差异在1%以内时，禁忌搜索算法已经难以获得对应精度的TSP路径，而禁忌遗传算法效率比遗传算法提高了50%。且禁忌遗传算法具有很好的并行化潜力。

关键词: 旅行商问题, 交通网络, 禁忌搜索, 遗传算法, 启发式算法

Abstract:

Traveling salesman problem is one of the classic network analysis problems. Due to it is NP Hard, people mainly take optimization method or heuristic algorithm to obtain the approximate optimal solution. However, single heuristic algorithms have some drawbacks, such as large computational complexity, rigorous parameter selection, strong dependence for the initial value and so on, which are difficult to quickly achieve whole optimization. Hybrid heuristic algorithm can solve this problem to some extent, which combines with a variety of optimization mechanisms and structures of neighborhood search. Considering the global optimization ability of genetic algorithm and the memory function of tabu search, this paper designed and implemented a tabu genetic algorithm based on decentralized and centralized strategy. Genetic mutation operator as a decentralized strategy was used to construct neighborhood, which exploited the new search space and enhanced the probability to obtain the global optimal solution. Tabu search as a centralized strategy was used to local search, which avoided circuitous detection and embodied the powerful "mountain climbing" ability. Moreover, this paper evaluated the algorithm from three aspects of accuracy, stability and efficiency using different scale of traffic network data. The results show that the tabu-genetic algorithm has higher accuracy which is increased by 9% than the tabu search algorithm, when the accuracy error is within 1%. And it can reduce the time consumption over 50% compared with genetic algorithm. Moreover, the tabu-genetic algorithm has the potential of parallelism.

Key words: traveling salesman problem, transportation network, tabu search, genetic algorithm, heuristic algorithm

中图分类号:

P208

余丽陆锋. 交通网络旅行商路径优化的遗传禁忌搜索算法[J]. 测绘学报, 2014, 43(11): 1197-1203.

YU Li. A Hybrid Algorithm for Traveling Salesman Problem in Road Network[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(11): 1197-1203.

参考文献

[1] LU Feng. Shortest Path Algorithms: Taxonomy and Advance in Research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 30(3): 269-275. （陆锋. 最短路径算法：分类体系与研究进展[J]. 测绘学报, 2001, 30(3): 269-275.）
[2] LI Kai, ZHONG Ershun, ZENG Zhiming, et al. An Optimal Path Algorithm Based on Hierarchically Structured Topographical Network[J]. Journal of Image and Graphics, 2006, 11(7): 1004-1009. （李楷, 钟耳顺, 曾志明, 等. 基于分层网络拓扑结构的最优路径算法[J]. 中国图象图形学报, 2006, 11(7): 1004-1009.）
[3] LI Qingquan, ZHANG Jinting, HUANG Jingnan. An Optimizational Algorithm for Logistics Distribution[J]. Geomatics and Information Science of Wuhan University, 2003, 28(1): 9-13. （李清泉, 张金婷, 黄经南. 一个物流配送优化算法[J]. 武汉大学学报?信息科学版, 2003, 28(1): 9-13.）
[4] LI Qingquan, LI Qiuping, FANG Zhixiang. An Emergency Evacuation Routing Optimization Method Based on Space-time Congestion Concept[J].Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 517-523. （李清泉, 李秋萍, 方志祥. 一种基于时空拥挤度的应急疏散路径优化方法[J]. 测绘学报, 2011, 40(4): 517-523.）
[5] XIAO Hui, YANG Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439. （肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报?信息科学版, 2008, 33(4): 437-439.）
[6] QI Yutao, LIU Fang, JIAO Licheng. Immune Algorithm with Self-Adaptive Reduction for Large-Scale TSP[J]. Journal of Software. 2008, 9(16): 1265-1273. （戚玉涛, 刘芳, 焦李成. 求解大规模TSP问题的自适应归约免疫算法[J]. 软件学报, 2008, 9(16): 1265-1273.）
[7] ZOU Peng, ZHOU Zhi, CHEN Guoliang, et al. A Multilevel Reduction Algorithm to TSP[J]. Journal of Software, 2003, 14(1): 35-42. （邹鹏, 周智, 陈国良, 等. 求解TSP问题的多级归约算法[J]. 软件学报, 2003, 14(1): 35-42.）
[8] Helsgaun K. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic[J]. European Journal of Operational Research, 2000, 126(1): 106-130.
[9] Grefenstette J J, Gopal R, Rosmaita B, et al. Genetic Algorithm for TSP[C]. Proceedings of the First International Conference on Genetic Algorithms of the First International Conference on Genetic Algorithms and Their Applications, 1985, 160-168.
[10] Kirkpatrick S, Gelatt J C D, Vecchi M P. Optimization by Simulated Annealing[J]. Science, 1983, 220(4596): 671-680.
[11] CHEN Huagen, WU Jian sheng, WANG Jialin, et al. Mechanism Study of Simulated Annealing Algorithm[J]. Journal of Tongji University(Natural Science), 2010, 26(1): 23-24. （陈华根, 吴健生, 王家林, 等. 模拟退火算法机理研究[J]. 同济大学学报(自然科学版), 2010, 26(1): 23-24.）
[12] Glover F, Kelly J P, Laguna M. Genetic Algorithms and Tabu Search: Hybrids for Optimization[J]. Computers & Operations Research, 1995, 22(1): 111-134.
[13] HE Yi, LIU Guangyuan, QIU Yuhui. A Novel Adaptive Search Strategy of Intensification and Diversification in Tabu Search[J]. Journal of Computer Research and Development, 2004, 41(1): 162-166. （贺一, 刘光远, 邱玉辉. Tabu Search中集中性和多样性的自适应搜索策略[J]. 计算机研究与发展, 2004, 41(1): 162-166.）
[14] DAI Qiguo, JI Junzhong, LIU Chunnian. Knowledge-Guiding Pheromone Control Strategy of Ant Colony Optimization[J]. Journal of Beijing University of Technology, 2011, 37(8): 1236-1241. （代启国, 冀俊忠, 刘椿年. 蚁群算法中基于知识引导的信息素控制策略[J]. 北京工业大学学报, 2011, 37(8): 1236-1241.）
[15] WANG Ling, ZHENG Dazhong. Meta-Heuristic Algorithms: A Review[J]. Control and Decision, 2000, 15(3): 257-262. （王凌, 郑大钟. Meta-heuristic算法研究进展[J]. 控制与决策, 2000, 15(3): 257-262.）
[16] Fred G. Future Paths for Integer Programming and Links to Artificial Intelligence[J]. Computers & Operations Research, 1986, 13(5): 533-549.
[17] XI Yugeng. Survey on Genetic Algorithm[J]. Control Theory and Applications, 1996, 13(6): 697-708. （席裕庚, 柴天佑, 恽为民. 遗传算法综述[J]. 控制理论与应用, 1996, 13(6): 697-708.）
[18] Yang N, Tian W F, Jin Z H. Crossover Tabu Search for Traveling Salesman Problem[J]. Journal of System Simulation, 2006, 18(4): 897-908.
[19] SUN Yanfeng. A Hybrid Strategy Based on Genetic Algorithm and Tabu Search[J]. Journal of Beijing University of Technology, 2006, 32(3): 258-262. （孙艳丰. 基于遗传算法和禁忌搜索算法的混合策略及其应用[J]. 北京工业大学学报, 2006, 32(3): 258-262.）
[20] KEKe, ZHANG Shiying. Research on the Tabu Hierarchy Genetic Algorithm[J]. Control and Decision, 2001, 16(4): 480-483. （柯珂, 张世英. 禁忌-递阶遗传算法研究[J]. 控制与决策, 2001, 16(4): 480-483.）
[21] Thamilselvan R, Balasubramanie P. A Genetic Algorithm with a Tabu Search for Traveling Salesman Problem[J]. International Journal of Recent Trends in Engineering, 2009, 1(1): 607-610.
[22] LIU Jun, WANG Jiesheng. Solving Traveling Salesman Problem(TSP) with Pseudo Parallel Genetic Algorithms[J], Control Theory and Applications, 2007,24(2): 279-282. （刘军, 王介生. 旅行商问题(TSP)的伪并行遗传算法[J]. 控制理论与应用, 2007,24(2): 279-282.）
[23] CAI Zhihua, PENG Jingao, GAO Wei, et al. An Improved Evolutionary Algorithm for the Traveling Salesman Problem[J]. Chinese Journal of Computers, 2005,28(5): 823-828. （蔡之华, 彭锦国, 高伟, 等. 一种改进的求解TSP问题的演化算法[J]. 计算机学报, 2005,28(5): 823-828.）
[24] GAO Song, LU Feng. The Kth Shortest Path Algorithms: Accuracy and Efficiency Evaluation[J]. Journal of Image and Graphics, 2009,14(8): 1677-1683. （高松, 陆锋. K则最短路径算法效率与精度评估[J]. 中国图象图形学报, 2009,14(8): 1677-1683.）
[25] Sextona R S, Alidaeeb B, Dorsey R E, et al. Global Optimization for Artificial Neural Networks: A Tabu Search Application[J]. European Journal of Operational Research, 1998, 106(2): 570-584.