Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem

WANG Yongzhen; CHEN Yan; YU Yingying

doi:10.11999/JEIT160211

Volume 39 Issue 1

Jan. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2017 > 39(1): 198-205

WANG Yongzhen, CHEN Yan, YU Yingying. 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

Citation:

WANG Yongzhen, CHEN Yan, YU Yingying. 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

Citation:

PDF( 603 KB)

Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem

doi: 10.11999/JEIT160211

Funds:

The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2014BAH24F04), The National Natural Science Foundation of China (71271034)

Received Date: 2016-03-07
Rev Recd Date: 2016-07-22
Publish Date: 2017-01-19

Abstract

Abstract

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.
- Grouping Genetic Algorithm (GGA),
- Multiple Traveling Salesman Problem (MTSP),
- Encoding,
- 2-opt algorithm

FullText(HTML)

References(23)

References

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.

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.

谢秉磊, 李颖, 刘敏. 带临时补充点的融雪剂撒布车辆路径问题[J]. 系统工程理论与实践, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.

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.

刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例[J]. 系统管理学报, 2014, 23(2): 247-254.

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.

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.

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.

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.

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.

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.

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.

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, Xian, China, 2009: 1533-1537. doi: 10.1109/ ICIEA.2009.5138451.

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.

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.

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.

韩丽霞, 王宇平, 兰绍江. 基于有序划分编码的图着色算法[J]. 电子学报, 2010, 38(1): 146-150.

HAN Lixia, WANG Yuping, and LAN Shaojiang. Graph coloring algorithm based on ordered partition encoding[J]. Acta Electronica Sinica, 2010, 38(1): 146-150.

HELSGAUN K. General k-opt submoves for the LinKernighan TSP heuristic[J]. Mathematical Programming Computation, 2009, 1(2/3): 119-163. doi: 10.1007/s12532- 009-0004-6.

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.

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.

王军强, 郭银洲, 崔福东, 等. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

WANG Junqiang, GUO Yinzhou, CUI Fudong, et al. Diversity enhancement-based adaptive genetic algorithm for open-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

Relative Articles

Supplements(0)

Cited By

Proportional views