International Journal of Computational Intelligence Systems

<Previous Article In Issue
Next Article In Issue>
Volume 11, Issue 1, 2018, Pages 692 - 705

A Genetic Algorithm with New Local Operators for Multiple Traveling Salesman Problems

Authors
Kin-Ming Lo1, *, kmlo@cse.cuhk.edu.hk, Wei-Ying Yi1, Pak-Kan Wong1, Kwong-Sak Leung1, Yee Leung2, Sui-Tung Mak3
1Department of Computer Science and Engineering, The Chinese University of Hong Kong, Hong Kong, China
2Institute Of Future Cities, The Chinese University of Hong Kong, Hong Kong, China
3Department of Electronics and Computer Science, University of Southampton, University Road, Southampton SO17 1BJ, United Kingdom
*Corresponding author
Corresponding Author
Received 20 June 2017, Accepted 21 January 2018, Available Online 5 February 2018.
DOI
10.2991/ijcis.11.1.53How to use a DOI?
Keywords
Multiple Traveling Salesman Problem; Genetic Algorithm; Branch and Bound algorithm; Local operators
Abstract

Multiple Traveling Salesman Problem (MTSP) is able to model and solve various real-life applications such as multiple scheduling, multiple vehicle routing and multiple path planning problems, etc. While Traveling Salesman Problem (TSP) focuses on searching a path of minimum traveling distance to visit all cities exactly once by one salesman, the objective of the MTSP is to find m paths for m salesmen with a minimized total cost - the sum of traveling distances of all salesmen through all of the respective cities covered. They have to start from a designated depot which is the departing and returning location of all salesmen. Since the MTSP is a NP-hard problem, a new effective Genetic Algorithm with Local operators (GAL) is proposed in this paper to solve the MTSP and generate high quality solution within a reasonable amount of time for real-life applications. Two new local operators, Branch and Bound (BaB) and Cross Elimination (CE), are designed to speed up the convergence of the search process and improve the solution quality. Results demonstrate that GAL finds a better set of paths with a 9.62% saving on average in cost comparing to two existing MTSP algorithms.

Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Download article (PDF)
View full text (HTML)

<Previous Article In Issue
Next Article In Issue>
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
11 - 1
Pages
692 - 705
Publication Date
2018/02/05
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.11.1.53How to use a DOI?
Copyright
© 2018, the Authors. Published by Atlantis Press.
Open Access
This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

risenwbib
TY  - JOUR
AU  - Kin-Ming Lo
AU  - Wei-Ying Yi
AU  - Pak-Kan Wong
AU  - Kwong-Sak Leung
AU  - Yee Leung
AU  - Sui-Tung Mak
PY  - 2018
DA  - 2018/02/05
TI  - A Genetic Algorithm with New Local Operators for Multiple Traveling Salesman Problems
JO  - International Journal of Computational Intelligence Systems
SP  - 692
EP  - 705
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.53
DO  - 10.2991/ijcis.11.1.53
ID  - Lo2018
ER  -