Learning-guided iterated local search for the minmax multiple traveling salesman problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916165839749120 |
|---|---|
| author | He, Pengfei Hao, Jin-Kao Xia, Jinhui |
| author_facet | He, Pengfei Hao, Jin-Kao Xia, Jinhui |
| contents | The minmax multiple traveling salesman problem involves minimizing the longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a leaning-driven iterated local search approach that combines an aggressive local search procedure with a probabilistic acceptance criterion to find high-quality local optimal solutions and a multi-armed bandit algorithm to select various removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the composing elements of the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12389 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning-guided iterated local search for the minmax multiple traveling salesman problem He, Pengfei Hao, Jin-Kao Xia, Jinhui Neural and Evolutionary Computing The minmax multiple traveling salesman problem involves minimizing the longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a leaning-driven iterated local search approach that combines an aggressive local search procedure with a probabilistic acceptance criterion to find high-quality local optimal solutions and a multi-armed bandit algorithm to select various removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the composing elements of the algorithm. |
| title | Learning-guided iterated local search for the minmax multiple traveling salesman problem |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2403.12389 |