Home About APEM Events News Sponsorship
Advances in Production Engineering & Management

Archives > Volume 16 | Number 2 | June 2021 > pp 173–184

Advances in Production Engineering & Management
Volume 16 | Number 2 | June 2021 | pp 173–184

https://doi.org/10.14743/apem2021.2.392

Improved Genetic Algorithm (VNS-GA) using polar coordinate classification for workload balanced multiple Traveling Salesman Problem (mTSP)
Wang, Y.D.; Lu, X.C.; Shen, J.R.
ABSTRACT AND REFERENCES (PDF)  |  FULL ARTICLE TEXT (PDF)

A B S T R A C T
The multiple traveling salesman problem (mTSP) is an extension of the traveling salesman problem (TSP), which has wider applications in real life than the traveling salesman problem such as transportation and delivery, task allocation, etc. In this paper, an improved genetic algorithm (VNS-GA) that uses polar coordinate classification to generate the initial solutions is proposed. It integrates the variable neighbourhood algorithm to solve the multiple objective optimization of the mTSP with workload balance. Aiming to workload balance, the first design of this paper is about generating initial solutions based on the polar coordinate classification. Then a distance comparison insertion operator is designed as a neighbourhood action for allocating paths in a targeted manner. Finally, the neighbourhood descent process in the variable neighbourhood algorithm is fused into the genetic algorithm for the expansion of search space. The improved algorithm is tested on the TSPLIB standard data set and compared with other genetic algorithms. The results show that the improved genetic algorithm can increase computational efficiency and obtain a better solution for workload balance and this algorithm has wild applications in real life such as multiple robots task allocation, school bus routing problem and other optimization problems.

A R T I C L E   I N F O
Keywords • Multiple traveling salesman problem (mTSP); Workload balance; Variable neighbourhood search algorithm (VNS); Genetic algorithm (GA); Polar coordinates; Classification
Corresponding authorLu, X.C.
Article history • Received 4 June 2021, Revised 15 June 2021, Accepted 17 June 2021
Published on-line • 25 June 2021

E X P O R T   C I T A T I O N
» RIS format (EndNote, ProCite, RefWorks, and most other reference management software)
» BibTeX (JabRef, BibDesk, and other BibTeX-specific software)
» Plain text

< PREVIOUS PAPER   |   NEXT PAPER >