Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem

Zenodo (CERN European Organization for Nuclear Research)

Abstract

Abstract: The traveling salesman problem (TSP) is a well-known NP-hard discrete combinatorial optimization problem, and exact approaches such as branch-and-bound, cutting planes and dynamic programming become ineffective as the number of nodes grows. This chapter applies the Queuing Search Algorithm (QSA), a recent metaheuristic, to the TSP for the first time. To adapt QSA to this combinatorial problem, solution arrays are converted to discrete values with an order-based decoding approach, the initial population is generated with the roulette wheel method, and the 2-opt local search is applied at every iteration to accelerate convergence and improve solution quality, yielding the Improved Discrete QSA (IQSA). Standard QSA and IQSA were run ten times on 31 TSPLIB benchmark instances ranging from 30 to 1002 cities, and mean values, standard deviations and gaps to the best-known solutions are reported. IQSA reaches the optimum on several instances and stays close to it on the others, clearly outperforming the standard QSA and the other algorithms compared. IQSA is therefore a very effective algorithm for the TSP and can be applied to other combinatorial and discrete problem types in future work. Keywords: Traveling salesman problem, Queuing search algorithm, Metaheuristics, Combinatorial optimization, 2-opt, TSPLIB Publication details: Book chapter in: International Research in Engineering Sciences VII, edited by Arif Emre Dursun, pp. 31-56. Eğitim Publishing, Konya, Türkiye, July 2023. ISBN: 978-625-6489-68-4. How to cite / Kaynak gösterimi APA 7: Gülmez, B. (2023). Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem. In A. Dursun (Ed.), International Research in Engineering Sciences VII (pp. 31–56). Eğitim Publishing. https://doi.org/10.5281/zenodo.23037710 IEEE: B. Gülmez, "Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem," in International Research in Engineering Sciences VII, A. Dursun, Ed. Konya, Türkiye: Eğitim Publishing, 2023, pp. 31–56, doi: 10.5281/zenodo.23037710. Chicago: Gülmez, Burak. 2023. "Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem." In International Research in Engineering Sciences VII, edited by Arif Emre Dursun, 31–56. Konya, Türkiye: Eğitim Publishing. https://doi.org/10.5281/zenodo.23037710. MLA 9: Gülmez, Burak. "Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem." International Research in Engineering Sciences VII, edited by Arif Emre Dursun, Eğitim Publishing, 2023, pp. 31–56. https://doi.org/10.5281/zenodo.23037710. Harvard: Gülmez, B. (2023) 'Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem', in A. Dursun (Ed.), International Research in Engineering Sciences VII. Konya, Türkiye: Eğitim Publishing, pp. 31–56. doi: 10.5281/zenodo.23037710. BibTeX: @incollection{Gulmez2023improved, author = {Gülmez, Burak}, title = {Improved Discrete Queuing Search Algorithm for Traveling Salesman Problem}, booktitle = {International Research in Engineering Sciences VII}, editor = {Dursun, Arif Emre}, pages = {31--56}, year = {2023}, publisher = {Eğitim Publishing}, address = {Konya, Türkiye}, isbn = {978-625-6489-68-4}, doi = {10.5281/zenodo.23037710} }

Authors 1

1. Burak Gülmez corresponding Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Leiden, The Netherlands