| Title: | Improved genetic algorithm (VNS-GA) using polar coordinate classification for workload balanced multiple traveling salesman problem (mTSP) |
|---|
| Authors: | ID Wang, Y. D. (Author)
ID Lu, X. C. (Author)
ID Shen, J. R. (Author) |
|---|
| Files: |  APEM16-2_173-184.pdf (987,57 KB)
MD5: B37C96E656B31FE80CBA5D7141024952
 https://apem-journal.org/Archives/2021/Abstract-APEM16-2_173-184.html
|
|---|
| Language: | English |
|---|
| Work type: | Article |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FS - Faculty of Mechanical Engineering
|
|---|
| Abstract: | GThe 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. |
|---|
| Keywords: | multiple traveling salesman problem (mTSP), workload balance, variable neighbourhood search algorithm (VNS), genetic algorithm (GA), polar coordinates, classification |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 04.06.2021 |
|---|
| Article acceptance date: | 17.06.2021 |
|---|
| Publication date: | 25.06.2021 |
|---|
| Publisher: | Univerza v Mariboru |
|---|
| Year of publishing: | 2021 |
|---|
| Number of pages: | str. 173-184 |
|---|
| Numbering: | Vol. 16, no. 2 |
|---|
| PID: | 20.500.12556/DKUM-97322  |
|---|
| UDC: | 658.7:004.021 |
|---|
| ISSN on article: | 1854-6250 |
|---|
| COBISS.SI-ID: | 269806851 |
|---|
| DOI: | 10.14743/apem2021.2.392 |
|---|
| Publication date in DKUM: | 27.02.2026 |
|---|
| Views: | 140 |
|---|
| Downloads: | 3 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
