DOAJ Open Access 2022

New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem

Jeanette Schmidt Stefan Irnich

Abstrak

For a given graph with a vertex set that is partitioned into clusters, the generalized traveling salesman problem (GTSP) is the problem of finding a cost-minimal cycle that contains exactly one vertex of every cluster. We introduce three new GTSP neighborhoods that allow the simultaneous permutation of the sequence of the clusters and the selection of vertices from each cluster. The three neighborhoods and some known neighborhoods from the literature are combined into an effective iterated local search (ILS) for the GTSP. The ILS performs a straightforward random neighborhood selection within the local search and applies an ordinary record-to-record ILS acceptance criterion. The computational experiments on four symmetric standard GTSP libraries show that, with some purposeful refinements, the ILS can compete with state-of-the-art GTSP algorithms.

Topik & Kata Kunci

Applied mathematics. Quantitative methods Electronic computers. Computer science

Penulis (2)

Jeanette Schmidt

Stefan Irnich

Format Sitasi

APA MLA BibTeX

Schmidt, J., Irnich, S. (2022). New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem. https://doi.org/10.1016/j.ejco.2022.100029

Akses Cepat

PDF tidak tersedia langsung

Cek di sumber asli →

Lihat di Sumber doi.org/10.1016/j.ejco.2022.100029

Informasi Jurnal

Tahun Terbit: 2022
Sumber Database: DOAJ
DOI: 10.1016/j.ejco.2022.100029
Akses: Open Access ✓