Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem

doi:10.16182/j.issn1004731x.joss.17-0046

Abstract

Abstract: A multi-traveling salesman model with time window is established, and two objective functions for the number of traveling salesmen and the sum of travel time are designed. A multi - chromosome coding method is designed to develop complex mutation operator tree, which overcomes the problem of large searching space of traditional genetic algorithms. The performances of algorithms are compared by simulation, and the simulation results show that the genetic algorithm with complex multi-chromosome mutation tree can balance the two objective functions of the number of TSP and total travel time well, improve the algorithm of travel speed, and reduce the total travel time by 15.8%.

Key words: multi-traveling salesman problem, time window, coding, multi-chromosome genetic algorithm, mutation operator tree

CLC Number:

TP18

Ye Duofu, Liu Gang, He Bing. Multi-chromosome Genetic Algorithm for Multiple Traveling Salesman Problem[J]. Journal of System Simulation, 2019, 31(1): 36-42.

References

[1] 王勇臻, 陈燕, 于莹莹. 求解多旅行商问题的改进分组遗传算法[J]. 电子与信息学报, 2017, 39(1):198-205. doi: 10.11999/JEIT160211.
Wang Y Z, Chen Y, Yu Y Y.Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem[J]. Journal of Electronics & Information Technology, 2017, 39(1): 198-205. doi:10.11999/ JEIT160211.
[2] KASHAN A H, AKBARI A A, OSTADI B.Grouping Evolution Strategies: an Effective Approach for Grouping Problems[J]. Applied Mathematical Modelling (S0307-904X), 2015, 39(9): 2703-2720. doi: 10.1016/ j.apm.2014.11.001.
[3] BEKTAS T.The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures[J]. Omega (S0305-0483), 2006, 34(3): 209-219. doi: 10.1016/j.omega.2004.10.004.
[4] SINGH A, BAGHEL A S.A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing (S1432-7643), 2009, 13(1): 95-101. doi: 10.1007/s00500-008-0312-1.
[5] 于宏涛, 高立群, 田卫华. 求解TSP的离散人工蚁群算法[J]. 东北大学学报(自然科学版), 2015, 36(8): 1074-1079. doi: 10.3969/j.issn.1005-3026.2015.08.003.
Yu H.T, Gao L. Q and Tian W. H, Discrete Artificial Bee Colony Algorithm for TSP[J], Journal of Northeastern University (Natural Science), 2015, 36(8): 1074-1079. doi: 10.3969/j.issn.1005-3026.2015.08.003.
[6] 贾燕花. 蚁群算法在旅行商问题(TSP)中的应用研究[J]. 计算机与数字工程, 2016, 44(9): 1664-1667.
Jia Yanhua.Application of the Ant Algorithm in TSP[J]. Computer and Digital Engineering, 2016, 44(9): 1664-1667.
[7] Tang L, Liu J, Rong A, et al.A Multiple Traveling Salesman Problem Model for Hot Rolling Scheduling in Shangai Baoshan Iron & Steel Complex[J]. European Journal of Operational Research (S0377-2217), 2000, 124(2): 267-282.
[8] Zhao F, Dong J, Li S, et al.An Improved Genetic Algorithm for the Multiple Traveling Salesman Problem[C]// Chinese Control and Decision Conference. Yantai, China: IEEE Press, 2008: 1935-1939.
[9] Koh S P, Aris I B, Ho C K, et al.Design and Performance Optimization of a Multi-TSP (Traveling Salesman Problem) Algorithm[J]. AIML Journal (S1687-4846), 2006, 6(3): 29-33.
[10] 刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例[J]. 系统管理学报, 2014, 23(2): 247-254.
Liu M, Zhang P Y.New hybrid Genetic Algorithm for Solving the Multiple Traveling Salesman Problem: an Example of Distribution Emergence Materials[J]. Systems Engineering Theory Methodology Applications, 2014, 23(2): 247-254.
[11] SINGH A, BAGHEL A S.A New Grouping Genetic Algorithm Approach to the Multiple Traveling Salesperson Problem[J]. Soft Computing (S1432-7643), 2009, 13(1): 95-101.
[12] Kara I, Bektas T.Integer Linear Progra1ng Formulations of Multiple Salesman Problems and its Variations[J]. European Journal of Operational Research (S0377-2217), 2006, 174(3): 1449-1458.
[13] Andras K, Janos A.Redesign of the Supply of Mobile Mechanics based on a novel Genetic Optimization Algorithm using Google Maps API[J]. Engineering Applications of Artificial Intelligence (S0952-1976), 2015, 38(2): 122-130.

[1]	Kaiqing Zhang, Qichun Ji. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed [J]. Journal of System Simulation, 2022, 34(4): 836-846.
[2]	Tang Jie, Cao Jinxin. Research on Integrated Optimization Approach for Car-sharing Systems [J]. Journal of System Simulation, 2021, 33(8): 1959-1968.
[3]	Lu Jiabo, Cheng Peixing, Huang Yi, Yao Jinqiang, Yang Xuemeng, Ma Xinqiang, Liu Yong. An Intelligent Method for Rapid Construction of Time Sensitive Target Strike Chain [J]. Journal of System Simulation, 2021, 33(2): 346-357.
[4]	Xuan Hua, Qin Yingying, Wang Xueyuan, Zhang Bailin. Optimization for Unrelated Parallel Machine Scheduling with Deteriorating Jobs [J]. Journal of System Simulation, 2019, 31(5): 919-924.
[5]	Chen Fatang, Yang Kang, Fu Yongli, Li Mengjie. Low-Complexity Signal Detection Algorithm based on PGQSM [J]. Journal of System Simulation, 2019, 31(10): 2078-2084.
[6]	Li Ke, Wang Yan, Ji Zhicheng. Research on FJSP Problem of Invasive Weed Optimization Based on Hybrid Strategy [J]. Journal of System Simulation, 2018, 30(5): 1918-1926.
[7]	Li Lin, Kong Liuyong. A New Image Encryption Algorithm Based On Chaos [J]. Journal of System Simulation, 2018, 30(3): 954-961.
[8]	Wang Songwei, Huang Shuman, Shi Li, Wang Mengke. Neural Coding Model for Fast and Significant Perceptual in the Pigeon Optic Tectum [J]. Journal of System Simulation, 2018, 30(11): 4086-4099.
[9]	Zhang Xin, Li Ke, Yan Dahu, Ji Zhicheng. Improved Intrusion Weed Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Journal of System Simulation, 2018, 30(11): 4469-4476.
[10]	Qu Guowei, Song Xiaoping. Hybrid Decoding Algorithm for Low-density Parity-check Codes [J]. Journal of System Simulation, 2018, 30(10): 4009-4013.
[11]	Xie Bin, Xie Shumin, Liu Shurui. Hybrid RZF Precoding Algorithm for Massive MIMO System [J]. Journal of System Simulation, 2017, 29(12): 3114-3122.
[12]	Li Feng, Wan Gang, Jiang Bingchuan, Cao Xuefeng. Spatio-Temporal Data Organization Model of Unified Ground and Aerial Battlefield and Its Application [J]. Journal of System Simulation, 2017, 29(11): 2637-2643.
[13]	Xing Zhiwei, Tang Yunxiao. Flight Support Service Time Estimation of Hub Airport [J]. Journal of System Simulation, 2017, 29(11): 2856-2865.
[14]	Qu Guowei, Deng Songfeng. Low-complexity Soft-Decision Decoding Algorithm for BCH Code in BeiDou System [J]. Journal of System Simulation, 2016, 28(8): 1790-1794.
[15]	Zhang Junfeng, Wang Fei, Ge Tengteng. Dynamic Arrival Sequencing & Scheduling Based on Branch & Bound Algorithm [J]. Journal of System Simulation, 2016, 28(8): 1909-1914.