In order to solve the total-path-shortest Multiple Traveling Salesman Problem (MTSP), an improved grouping genetic algorithm is proposed. This algorithm employs a new encoding scheme called ordered grouping encoding, which makes the adjusted individuals corresponding one by one to valid solutions of MTSP. According to the features of the encoding scheme, a fast crossover operator is constructed for the sake of reducing the running time of the algorithm. For enhancing its local search ability, the algorithm combines the greedy algorithm and the 2-opt algorithm to design a new local search operator. The comparison of results shows that the proposed algorithm can solve MTSP effectively and has an excellent search performance no matter in computing efficiency or convergence precision.
SOYLU B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J]. Computers & Industrial Engineering, 2015, 90(11): 390-401. doi: 10.1016/j.cie.2015.10.010.
[2]
KOTA L and JARMAI K. Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming[J]. Applied Mathematical Modelling, 2015, 39(12): 3410-3433. doi: 10.1016/j.apm. 2014.11.043.
XIE Binglei, LI Ying, and LIU Min. Vehicle routing problem with temporary supplementary points for spreading deicing salt[J]. Systems Engineering-Theory & Pratice, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.
LIU Ming and ZHANG Peiyong. New hybrid genetic algorithm for solving the multiple traveling salesman problem: An example of distribution of emergence materials[J]. Journal of System & Management, 2014, 23(2): 247-254.
[5]
ANN S, KIM Y, and AHN J. Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method[J]. IFAC-PapersOnLine, 2015, 48(9): 204-209. doi: 10.1016/j.ifacol.2015.08.084.
[6]
KIRALY A, CHRISTIDOU M, CHOVAN T, et al. Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem[J]. Journal of Cleaner Production, 2016, 111: 253-261. doi: 10.1016/j.jclepro.2015.05.036.
[7]
KASHAN A H, AKBARI A A, and OSTADI B. Grouping evolution strategies: an effective approach for grouping problems[J]. Applied Mathematical Modelling, 2015, 39(9): 2703-2720. doi: 10.1016/j.apm.2014.11.001.
[8]
BEKTAS T. The multiple traveling salesman problem: An overview of formulations and solution procedures[J]. Omega, 2006, 34(3): 209-219. doi: 10.1016/j.omega.2004.10.004.
[9]
SINGH A and BAGHEL A S. A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]. Soft Computing, 2009, 13(1): 95-101. doi: 10.1007/s00500-008-0312-1.
[10]
YUAN S, SKINNER B, HUANG S, et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European Journal of Operational Research, 2013, 228(1): 72-82. doi: 10.1016/j.ejor.2013.01.043.
[11]
LIU W, LI S, ZHAO F, et al. An ant colony optimization algorithm for the multiple traveling salesmen problem[C]. Proceedings of IEEE Conference on Industrial Electronics and Applications, ICIEA, Xi’an, China, 2009: 1533-1537. doi: 10.1109/ ICIEA.2009.5138451.
[12]
NECULA R, BREABAN M, and RASCHIP M. Performance Evaluation of Ant Colony Systems for the Single-depot Multiple Traveling Salesman Problem[M]. Springer International Publishing, 2015: 257-268. doi: 10.1007/ 978-3-319-19644-2_22.
[13]
XUE M, WANG T, and MAO S. Double evolutsional artificial bee colony algorithm for multiple traveling salesman problem[C]. Preoeedings of MATEC Web of Conferences, EDP Sciences, 2016: 44. doi: 10.1051/ matecconf/20164402025.
[14]
VENKATESH P and SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing, 2015, 26: 74-89. doi: 10.1016/ j.asoc.2014.09.029.
HAN Lixia, WANG Yuping, and LAN Shaojiang. Graph coloring algorithm based on ordered partition encoding[J]. Acta Electronica Sinica, 2010, 38(1): 146-150.
[16]
HELSGAUN K. General k-opt submoves for the Lin-Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009, 1(2/3): 119-163. doi: 10.1007/s12532- 009-0004-6.
[17]
ALIJLA B O, WONG L P, LIM C P, et al. A modified intelligent water drops algorithm and its application to optimization problems[J]. Expert Systems with Applications, 2014, 41: 6555-6569. doi: 10.1016/j.eswa.2014.05.010.
[18]
WANG S, WANG L, LIU M, et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J]. International Journal of Production Economics, 2013, 145(1): 387-396. doi: 10.1016/j.ijpe.2013.05.004.
