期刊
EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION
卷 10, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.ejco.2022.100029
关键词
Traveling salesman; Generalized traveling salesman problem; Iterated local search; Variable neighborhood descent
资金
- Deutsche Forschungsgemeinschaft (DFG) [IR 122/7-2]
The generalized traveling salesman problem (GTSP) aims to find a minimum-cost cycle in a given graph that contains exactly one vertex from each cluster. This study introduces three new GTSP neighborhoods that allow for simultaneous permutation of cluster sequence and vertex selection. These neighborhoods, along with existing ones from literature, are combined to form an effective iterated local search (ILS) algorithm for GTSP. Computational experiments on standard GTSP libraries demonstrate that the ILS algorithm, with some refinements, can compete with state-of-the-art GTSP algorithms.
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. (c) 2022 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据