Volume 55, Number 5, September-October 2021
|Page(s)||3021 - 3039|
|Published online||14 October 2021|
A beam search for the equality generalized symmetric traveling salesman problem
Logistics Department, Institut Superieur du Transport et de la Logistique de Sousse, University of Sousse, Sousse, Tunisia
2 Engineering Department, Kings College London, FNMES, Department of Engineering Strand, London WC2R 2LS, UK
* Corresponding author: firstname.lastname@example.org
Accepted: 18 September 2021
This paper studies the equality generalized symmetric traveling salesman problem (EGSTSP). A salesman has to visit a predefined set of countries. S/he must determine exactly one city (of a subset of cities) to visit in each country and the sequence of the countries such that s/he minimizes the overall travel cost. From an academic perspective, EGSTSP is very important. It is NP-hard. Its relaxed version TSP is itself NP-hard, and no exact technique solves large difficult instances. From a logistic perspective, EGSTSP has a broad range of applications that vary from sea, air, and train shipping to emergency relief to elections and polling to airlines’ scheduling to urban transportation. During the COVID-19 pandemic, the roll-out of vaccines further emphasizes the importance of this problem. Pharmaceutical firms are challenged not only by a viable production schedule but also by a flawless distribution plan especially that some of these vaccines must be stored at extremely low temperatures. This paper proposes an approximate tree-based search technique for EGSTSP . It uses a beam search with low and high level hybridization. The low-level hybridization applies a swap based local search to each partial solution of a node of a tree whereas the high-level hybridization applies 2-Opt, 3-Opt or Lin-Kernighan to the incumbent. Empirical results provide computational evidence that the proposed approach solves large instances with 89 countries and 442 cities in few seconds while matching the best known cost of 8 out of 36 instances and being less than 1.78% away from the best known solution for 27 instances.
Mathematics Subject Classification: 90-08 / 90-B06 / 90-B10 / 90-C06 / 90-C08 / 90-C27 / 90-C59
Key words: Generalized traveling salesman / beam search / symmetric traveling salesman / k-opt / Lin-Kernighan heuristic
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.