Augmented tour construction heuristics for the travelling salesman problem

Authors

  • Ziauddin Ursani Swansea University
  • Ahsan Ahmad Ursani Mehran University of Engineering and Technology

DOI:

https://doi.org/10.12928/ijio.v4i2.7875

Keywords:

Travelling Salesman Problem, Tour Construction Heuristics, Complexity Analysis

Abstract

Tour construction heuristics serve as fundamental techniques in optimizing the routes of a traveling salesman. These heuristics remain significant as foundational methods for generating initial solutions to the Traveling Salesman Problem (TSP), facilitating subsequent applications of tour improvement heuristics. These heuristics effectively comprise the iterative application of city node selection and insertion. However, thus far, no attempts have been made to enhance the basic structure of tour construction heuristics to bring a better initial solution for the advanced heuristics. This study aims to enhance tour construction heuristics without compromising their theoretical complexity. Specifically, an iterative step of partial tour deconstruction has been introduced to the existing heuristics. This additional step has been implemented and evaluated with three highly performing tour construction heuristics: the farthest insertion heuristic, the max difference insertion heuristic, and the fast max difference insertion heuristic. The results demonstrate that augmenting these heuristics with the partial tour deconstruction step improves the best, worst, and average solutions while preserving their theoretical complexity

References

R. Bellman, "Combinatorial Processes and Dynamic Programming," in Bellman, R.; Hall, M. Jr. (eds.), Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, American Mathematical Society, 1958, pp. 217–249. Available online: https://apps.dtic.mil/sti/tr/pdf/AD0606844.pdf

R. Bellman, "Dynamic Programming Treatment of the Travelling Salesman Problem," J. Assoc. Comput. Mach., vol. 9, pp. 61–63, 1962, doi: https://doi.org/10.1145/321105.321111.

M. Held and R. M. Karp, "A Dynamic Programming Approach to Sequencing Problems," J. Soc. Ind. Appl. Math., vol. 10, no. 1, pp. 196–210, 1962, doi: https://doi.org/10.1137/0110015, hdl:10338.dmlcz/103900

P. T. E. Cusack, "The Seven Millennium Problems & AT Math," J. Math. Techniques Comput. Math., vol. 2, no. 2, pp. 89-103, 2023. Available online: https://www.opastpublishers.com/open-access-articles/the-seven-millenium-problems--at-math.pdf

"Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur" (The Travelling Salesman — How He Must Be and What He Should Do in Order to Get Commissions and Be Sure of the Happy Success in His Business — by an Old Commis-Voyageur), 1832.

K. Menger, "Das botenproblem," Ergebnisse eines mathematischen kolloquiums, vol. 2, no.4, pp 11-12, 1932.

D. Dal and E. Celik, "Investigation of the impact of different versions of GCC on various metaheuristic-based solvers for traveling salesman problem," J. Supercomputing, pp. 1-47, 2023, doi: https://doi.org/10.1007/s11227-023-04109-0.

M. Grötschel, M. Jünger, and G. Reinelt, "Optimal Control of Plotting and Drilling Machines: A Case Study," Math. Methods Oper. Res., vol. 35, no. 1, pp. 61-84, Jan. 1991. doi: https://doi.org/10.1007/BF01453944.

R. D. Plante, T. J. Lowe, and R. Chandrasekaran, "The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristics," Oper. Res., vol. 35, pp. 772-783, 1987. doi: https://doi.org/10.1287/opre.35.5.772.

R. E. Bland and D. E. Shallcross, "Large traveling salesman problem arising from experiments in X-ray crystallography: a preliminary report on computation," Oper. Res. Lett., vol. 8, no. 3, pp. 125-128, 1989. doi: https://doi.org/10.1016/0167-6377(89)90051-3.

J. K. Lenstra and A. H. G. Rinnooy Kan, "Some Simple Applications of the Travelling Salesman Problem," BW 38/74, Stichting Mathematisch Centrum, Amsterdam, 1974. Available online: https://ir.cwi.nl/pub/21760/21760A.pdf

H. D. Ratliff and A. S. Rosenthal, "Order-Picking in a Rectangular Warehouse: A Solvable Case for the Travelling Salesman Problem," Oper. Res., vol. 31, pp. 507-521, 1983. doi: https://doi.org/10.1287/opre.31.3.507.

L. Gouveia, A. Paias, and M. Ponte, "The travelling salesman problem with positional consistency constraints: An Application to healthcare services," Eur. J. Oper. Res., vol. 308, no. 3, pp. 960-989, 2023. doi: https://doi.org/10.1016/j.ejor.2021.06.013.

A. Maya-López, A. Martínez-Ballesté, and F. Casino, "A compression strategy for an efficient TSP-based microaggregation," Expert Syst. Appl., vol. 213, 118980, 2023. doi: https://doi.org/10.1016/j.eswa.2020.118980.

C. Cariou, L. Moiroux-Arvis, F. Pinet, and J. P. Chanet, "Evolutionary Algorithm with Geometrical Heuristics for Solving the Close Enough Traveling Salesman Problem: Application to the Trajectory Planning of an Unmanned Aerial Vehicle," Algorithms, vol. 16, no. 1, 44, 2023. doi: https://doi.org/10.3390/a16010044.

Y. Wang and N. Wang, "Moving-target travelling salesman problem for a helicopter patrolling suspicious boats in antipiracy escort operations," Expert Syst. Appl., vol. 213, p. 118986, 2023. doi: https://doi.org/10.1016/j.eswa.2020.118986.

A. Di Placido, C. Archetti, and C. Cerrone, "A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance," Comput. Oper. Res., vol. 145, p. 105831, 2022, doi: https://doi.org/10.1016/j.cor.2021.105831.

Z. Zhang and J. Yang, "A discrete cuckoo search algorithm for traveling salesman problem and its application in cutting path optimization," Comput. Ind. Eng., vol. 169, p. 108157, 2022. doi: https://doi.org/10.1016/j.cie.2022.108157.

A. Gharehgozli, C. Xu, and W. Zhang, "High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system," Eur. J. Oper. Res., vol. 289, no. 2, pp. 495-507, 2021. doi: https://doi.org/10.1016/j.ejor.2020.08.041.

P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov, "A transformation technique for the clustered generalized traveling salesman problem with applications to logistics," Eur. J. Oper. Res., vol. 285, no. 2, pp. 444-457, 2020. doi: https://doi.org/10.1016/j.ejor.2020.02.024.

S. Mirjalili, J. Song Dong, and A. Lewis, "Ant colony optimizer: theory, literature review, and application in AUV path planning," In: Mirjalili, S., Song Dong, J., Lewis, A. (eds) Nature-Inspired Optimizers. Studies in Computational Intelligence, vol 811. Springer, Cham, pp. 7-21, 2020, doi: https://doi.org/10.1007/978-3-030-12127-3_2

J. Wu, L. Zhou, Z. Du, and Y. Lv, "Mixed steepest descent algorithm for the traveling salesman problem and application in air logistics," Transp. Res. Part E: Logist. Transp. Rev., vol. 126, pp. 87-102, 2019. doi: https://doi.org/10.1016/j.tre.2019.03.003.

S. Baressi Šegota, I. Lorencin, K. Ohkura, and Z. Car, "On the traveling salesman problem in nautical environments: an evolutionary computing approach to optimization of tourist route paths in Medulin, Croatia," Pomorski zbornik, vol. 57, no. 1, pp. 71-87, 2019. doi: https://doi.org/10.18048/2019.57.05.

A. S. Elgesem, E. S. Skogen, X. Wang, and K. Fagerholt, "A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping," Eur. J. Oper. Res., vol. 269, no. 3, pp. 844-859, 2018. doi: https://doi.org/10.1016/j.ejor.2018.02.041.

U. Hacizade and I. Kaya, "GA based traveling salesman problem solution and its application to transport routes optimization," IFAC-Pap., vol. 51, no. 30, pp. 620-625, 2018. doi: https://doi.org/10.1016/j.ifacol.2018.11.106.

Y. Luo, B. Golden, S. Poikonen, and R. Zhang, "A fresh look at the Traveling Salesman Problem with a Center," Comput. Oper. Res., vol. 143, p. 105748, 2022. doi: https://doi.org/10.1016/j.cor.2022.105748.

B. Manthey and J. van Rhijn, "Approximation Ineffectiveness of a Tour-Untangling Heuristic," arXiv preprint arXiv:2302.11264, 2023, doi: https://doi.org/10.48550/arXiv.2302.11264

J. Perttunen, "On the significance of the initial solution in travelling salesman heuristics," J. Oper. Res. Soc., vol. 45, no. 10, pp. 1131-1140, 1994. doi: https://doi.org/10.1057/jors.1994.150.

S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem," Oper. Res., vol. 21, no. 2, pp. 498-516, 1973. doi: https://doi.org/10.1287/opre.21.2.498.

D. J. Rosenkrantz, R. E. Stearns, and I. Lewis, "An analysis of several heuristics for the traveling salesman problem," SIAM J. Comput., vol. 6, no. 3, pp. 563-581, 1977. doi: https://doi.org/10.1137/0206041.

D. S. Johnson and L. A. McGeoch, "Experimental analysis of heuristics for the STSP," in The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen, Eds., vol. 12 of Combinatorial Optimization, chapter 9, pp. 369-443, Kluwer Academic Publishers, 2002, doi: https://doi.org/10.1007/0-306-48213-4_9

J. J. Bentley, "Fast algorithms for the geometric travelling salesman problem," ORSA J. Comput., vol. 4, no. 4, pp. 387-411, 1992. doi: https://doi.org/10.1287/ijoc.4.4.387.

D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: a case study in local optimization," in Local Search in Combinatorial Optimization, vol. 1, pp. 215-310, John Wiley & Sons, 1997, Available online: http://techfak.uni-bielefeld.de/ags/wbski/lehre/digiSA/WS0304/IntAlg/TSPchapter.pdf.

M. Goutham, M. Menon, S. Garrow, and S. Stockar, "A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean and Precedence Constrained TSPs," arXiv preprint arXiv:2302.06582, 2023, doi: https://doi.org/10.48550/arXiv.2302.06582

K. N. Qureshi, F. Bashir, and A. H. Abdullah, "Distance and signal quality aware next hop selection routing protocol for vehicular ad hoc networks," Neural Comput. Appl., vol. 32, pp. 2351-2364, 2020. doi: https://doi.org/10.1007/s00521-018-3520-2.

J. J. Bentley, "Fast algorithms for the geometric travelling salesman problem," ORSA J. Comput., vol. 4, no. 4, pp. 387-411, 1992. doi: https://doi.org/10.1287/ijoc.4.4.387.

Z. Ursani and D. W. Corne, "Introducing Complexity Curtailing Techniques for the Tour Construction Heuristics for the Travelling Salesperson Problem," J. Optim., vol. 2016, Article ID 4786268, 15 pages, 2016. doi: https://doi.org/10.1155/2016/4786268.

R. Hassin and A. Keinan, "Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP," Oper. Res. Lett., vol. 36, no. 2, pp. 243-246, 2008. doi: https://doi.org/10.1016/j.orl.2007.09.002.

J. Renaud, F. F. Boctor, and J. Ouenniche, "A heuristic for the pickup and delivery traveling salesman problem," Comput. Oper. Res., vol. 27, no. 9, pp. 905-916, 2000. doi: https://doi.org/10.1016/S0305-0548(99)00066-3.

MP-TESTDATA - The TSPLIB Symmetric Traveling Salesman Problem Instances http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html (Accessed 20/03/2020).

Downloads

Published

2023-09-11

How to Cite

Ursani, Z., & Ursani, A. A. (2023). Augmented tour construction heuristics for the travelling salesman problem. International Journal of Industrial Optimization, 4(2), 131–144. https://doi.org/10.12928/ijio.v4i2.7875

Issue

Vol. 4 No. 2 (2023)

Section

Articles

License

Copyright (c) 2023 Ziauddin Ursani, Ahsan Ahmad Ursani

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

License and Copyright Agreement

In submitting the manuscript to the journal, the authors certify that:

  • They are authorized by their co-authors to enter into these arrangements.
  • The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
  • That it is not under consideration for publication elsewhere,
  • That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
  • They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
  • They agree to the following license and copyright agreement.

Copyright

Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.