Please use this identifier to cite or link to this item:
http://hdl.handle.net/20.500.11861/7430
Title: | A Genetic Algorithm with New Local Operators for Multiple Traveling Salesman Problems |
Authors: | Lo, Kin Ming Yi, Wei-Ying Wong, Pak-Kan Prof. LEUNG Kwong Sak Leung, Yee Mak, Sui-Tung |
Issue Date: | 2018 |
Source: | International Journal of Computational Intelligence Systems ,2018, vol. 11(1), pp. 692-705 |
Journal: | International Journal of Computational Intelligence Systems |
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. |
Type: | Peer Reviewed Journal Article |
URI: | http://hdl.handle.net/20.500.11861/7430 |
ISSN: | 1875-6883 1875-6891 |
DOI: | 10.2991/ijcis.11.1.53 |
Appears in Collections: | Applied Data Science - Publication |
Find@HKSYU Show full item record
SCOPUSTM
Citations
33
checked on Nov 17, 2024
Page view(s)
35
Last Week
0
0
Last month
checked on Nov 21, 2024
Google ScholarTM
Impact Indices
Altmetric
PlumX
Metrics
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.