A Hybrid Algorithm for Traveling Salesman Problem in Road Network

doi:10.13485/j.cnki.11-2089.2014.0184

Abstract

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

CLC Number:

P208

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

References

[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.