A pre-processing reduction method for the generalized travelling salesman problem
Mehdi El Krari (),
Belaïd Ahiod () and
Youssef Bouazza El Benani ()
Additional contact information
Mehdi El Krari: Mohammed V University in Rabat
Belaïd Ahiod: Mohammed V University in Rabat
Youssef Bouazza El Benani: Mohammed V University in Rabat
Operational Research, 2021, vol. 21, issue 4, No 14, 2543-2591
Abstract The generalized travelling salesman problem (GTSP) is a variant of the well-known travelling salesman problem. The cities are in this case spread into clusters and only one city from each one must be visited to make a cyclic tour with a minimal cost. Following this assumption, an instance can be subject to dimensionality reduction since removing some cities from each cluster will keep feasible solutions and then will preserve feasibility of the instance. Therefore, we propose a new preprocessing technique which consists of selecting from each cluster the nearest nodes to other clusters and removing the nodes that had never been selected in order to reduce the search space size. The suggested approach is tested on a large set of symmetric instances of different sizes picked from the different benchmarks. The reduction is performed in a negligible runtime, while the reduction rate is up to 98%, which is very competitive compared to the only reduction method for the GTSP we are aware of. State-of-the-art solvers for the GTSP were applied to the reduced instances to evaluate their performances. We show that the reduced instances help these solvers to obtain good solutions in a shorter time but do not guarantee to get the optimal ones, while they provide better solutions in a fixed time budget environment.
Keywords: Generalized travelling salesman problem; Dimensionality reduction; Combinatorial optimization; Nearest nodes (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
http://link.springer.com/10.1007/s12351-019-00533-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:21:y:2021:i:4:d:10.1007_s12351-019-00533-w
Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351
Access Statistics for this article
Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis
More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().