The traveling salesman problem: An overview of exact and approximate algorithms

Citations

Cited by:

1. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
2. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex," European Journal of Operational Research, Elsevier, vol. 124(2), pages 267-282, July.
3. Amir Hossein Gharehgozli & Yugang Yu & Xiandong Zhang & René de Koster, 2017. "Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System," Transportation Science, INFORMS, vol. 51(1), pages 19-33, February.
4. Lorena, Luiz Antonio N. & Goncalves Narciso, Marcelo, 2002. "Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems," European Journal of Operational Research, Elsevier, vol. 138(3), pages 473-483, May.
5. Schmitt, Lawrence J. & Amini, Mohammad M., 1998. "Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study," European Journal of Operational Research, Elsevier, vol. 108(3), pages 551-570, August.
6. Castellano, Davide & Gallo, Mosè & Grassi, Andrea & Santillo, Liberatina C., 2019. "The effect of GHG emissions on production, inventory replenishment and routing decisions in a single vendor-multiple buyers supply chain," International Journal of Production Economics, Elsevier, vol. 218(C), pages 30-42.
7. Voudouris, Christos & Tsang, Edward, 1999. "Guided local search and its application to the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 113(2), pages 469-499, March.
8. Chatterjee, Sangit & Carrera, Cecilia & Lynch, Lucy A., 1996. "Genetic algorithms and traveling salesman problems," European Journal of Operational Research, Elsevier, vol. 93(3), pages 490-510, September.
9. Antonio Martinez‐Sykora & Tolga Bektaş, 2015. "Transformations of node‐balanced routing problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(5), pages 370-387, August.
10. Chen, Thomas Ying-Jeh & Riley, Connor Thomas & Van Hentenryck, Pascal & Guikema, Seth David, 2020. "Optimizing inspection routes in pipeline networks," Reliability Engineering and System Safety, Elsevier, vol. 195(C).
11. Luitpold Babel, 2020. "New heuristic algorithms for the Dubins traveling salesman problem," Journal of Heuristics, Springer, vol. 26(4), pages 503-530, August.
12. Chen, Thomas Ying-Jeh & Guikema, Seth David & Daly, Craig Michael, 2019. "Optimal pipe inspection paths considering inspection tool limitations," Reliability Engineering and System Safety, Elsevier, vol. 181(C), pages 156-166.
13. Benati, Stefano & Ponce, Diego & Puerto, Justo & Rodríguez-Chía, Antonio M., 2022. "A branch-and-price procedure for clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 297(3), pages 817-830.
14. Xu, Liang & Xu, Zhou & Xu, Dongsheng, 2013. "Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree," European Journal of Operational Research, Elsevier, vol. 227(2), pages 284-292.
15. Gagliardi, Jean-Philippe & Ruiz, Angel & Renaud, Jacques, 2008. "Space allocation and stock replenishment synchronization in a distribution center," International Journal of Production Economics, Elsevier, vol. 115(1), pages 19-27, September.
16. Alice Vasconcelos Nobre & Caio Cézar Rodrigues Oliveira & Denilson Ricardo de Lucena Nunes & André Cristiano Silva Melo & Gil Eduardo Guimarães & Rosley Anholon & Vitor William Batista Martins, 2022. "Analysis of Decision Parameters for Route Plans and Their Importance for Sustainability: An Exploratory Study Using the TOPSIS Technique," Logistics, MDPI, vol. 6(2), pages 1-12, May.
17. Menezes, Mozart B.C. & Ruiz-Hernández, Diego & Verter, Vedat, 2016. "A rough-cut approach for evaluating location-routing decisions via approximation algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 87(C), pages 89-106.
18. Kafle, Nabin & Zou, Bo & Lin, Jane, 2017. "Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 62-82.
19. Gharehgozli, Amir Hossein & Yu, Yugang & de Koster, René & Udding, Jan Tijmen, 2014. "An exact method for scheduling a yard crane," European Journal of Operational Research, Elsevier, vol. 235(2), pages 431-447.
20. Florios, Kostas & Mavrotas, George, 2014. "Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems," MPRA Paper 105074, University Library of Munich, Germany.
21. Tatiana Bassetto & Francesco Mason, 2007. "The 2-period balanced traveling salesman problem," Working Papers 154, Department of Applied Mathematics, Università Ca' Foscari Venezia, revised Oct 2007.
22. Kress, Dominik & Meiswinkel, Sebastian & Pesch, Erwin, 2019. "Straddle carrier routing at seaport container terminals in the presence of short term quay crane buffer areas," European Journal of Operational Research, Elsevier, vol. 279(3), pages 732-750.
23. Yang, Kaidi & Roca-Riu, Mireia & Menéndez, Mónica, 2019. "An auction-based approach for prebooked urban logistics facilities," Omega, Elsevier, vol. 89(C), pages 193-211.
24. Scianna, Marco, 2024. "The AddACO: A bio-inspired modified version of the ant colony optimization algorithm to solve travel salesman problems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 218(C), pages 357-382.
25. Teodor Gabriel Crainic & Federico Malucelli & Maddalena Nonato & François Guertin, 2005. "Meta-Heuristics for a Class of Demand-Responsive Transit Systems," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 10-24, February.
26. Sakakibara, Katsuaki, 1998. "New edges not used in shortest tours of TSP," European Journal of Operational Research, Elsevier, vol. 104(1), pages 129-138, January.
27. Diclehan Tezcaner Öztürk & Murat Köksalan, 2016. "An interactive approach for biobjective integer programs under quasiconvex preference functions," Annals of Operations Research, Springer, vol. 244(2), pages 677-696, September.
28. Chen, Xi, 2018. "When does store consolidation lead to higher emissions?," International Journal of Production Economics, Elsevier, vol. 202(C), pages 109-122.
29. Mengtang Li & Guoku Jia & Xun Li & Hao Qiu, 2023. "Efficient Trajectory Planning for Optimizing Energy Consumption and Completion Time in UAV-Assisted IoT Networks," Mathematics, MDPI, vol. 11(20), pages 1-19, October.
30. Babel, Luitpold, 2017. "Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles," European Journal of Operational Research, Elsevier, vol. 262(1), pages 335-346.
31. Burger, M. & Su, Z. & De Schutter, B., 2018. "A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 265(2), pages 463-477.
32. Ouyang, Zhiyuan & Leung, Eric Ka Ho & Huang, George Q., 2022. "Community logistics for dynamic vehicle dispatching: The effects of community departure “time” and “space”," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
33. Yannis Marinakis & Athanasios Migdalas & Panos M. Pardalos, 2009. "Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 134-156, February.
34. Mladenović, Nenad & Urošević, Dragan & Hanafi, Saı¨d & Ilić, Aleksandar, 2012. "A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 270-285.
35. Toth, Paolo, 2000. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 125(2), pages 222-238, September.
36. Sam Thangiah & Adel Fergany & Salman Awan, 2007. "Real-time split-delivery pickup and delivery time window problems with transfers," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 15(4), pages 329-349, November.
37. Bektaş, Tolga, 2012. "Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing," European Journal of Operational Research, Elsevier, vol. 216(1), pages 83-93.
38. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
39. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
40. Amir Hossein Gharehgozli & Gilbert Laporte & Yugang Yu & René de Koster, 2015. "Scheduling Twin Yard Cranes in a Container Block," Transportation Science, INFORMS, vol. 49(3), pages 686-705, August.
41. Divsalar, Ali & Vansteenwegen, Pieter, 2016. "A two-phase algorithm for the cyclic inventory routing problemAuthor-Name: Chitsaz, Masoud," European Journal of Operational Research, Elsevier, vol. 254(2), pages 410-426.
42. Masoumeh Mahdieh & Alistair Clark & Mehdi Bijari, 2018. "A novel flexible model for lot sizing and scheduling with non-triangular, period overlapping and carryover setups in different machine configurations," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 884-923, December.
43. Fernández, Elena & Pozo, Miguel A. & Puerto, Justo & Scozzari, Andrea, 2017. "Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem," European Journal of Operational Research, Elsevier, vol. 260(3), pages 886-903.
44. Dodin, B. & Elimam, A.A., 2008. "Integration of equipment planning and project scheduling," European Journal of Operational Research, Elsevier, vol. 184(3), pages 962-980, February.
45. A. S. Santos & A. M. Madureira & M. L. R. Varela, 2018. "The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance," Journal of Mathematics, Hindawi, vol. 2018, pages 1-14, July.
46. N. A. Arellano-Arriaga & J. Molina & S. E. Schaeffer & A. M. Álvarez-Socarrás & I. A. Martínez-Salazar, 2019. "A bi-objective study of the minimum latency problem," Journal of Heuristics, Springer, vol. 25(3), pages 431-454, June.
47. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
48. Bassetto, Tatiana & Mason, Francesco, 2011. "Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs," European Journal of Operational Research, Elsevier, vol. 208(3), pages 253-262, February.
49. Heber F. Amaral & Sebastián Urrutia & Lars M. Hvattum, 2021. "Delayed improvement local search," Journal of Heuristics, Springer, vol. 27(5), pages 923-950, October.
50. Baker, Barrie M. & Sheasby, Janice, 1999. "Extensions to the generalised assignment heuristic for vehicle routing," European Journal of Operational Research, Elsevier, vol. 119(1), pages 147-157, November.
51. Pages, Laia & Jayakrishnan, R. & Cortes, Cristian E., 2005. "Real-Time Mass Passenger Transport Network Optimization Problems," University of California Transportation Center, Working Papers qt7w88d089, University of California Transportation Center.
52. Cheng-Hsiung Tsai & Yu-Da Lin & Cheng-Hong Yang & Chien-Kun Wang & Li-Chun Chiang & Po-Jui Chiang, 2023. "A Biogeography-Based Optimization with a Greedy Randomized Adaptive Search Procedure and the 2-Opt Algorithm for the Traveling Salesman Problem," Sustainability, MDPI, vol. 15(6), pages 1-14, March.
53. Agatz, N.A.H. & Bouman, P.C. & Schmidt, M.E., 2016. "Optimization Approaches for the Traveling Salesman Problem with Drone," ERIM Report Series Research in Management ERS-2015-011-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
54. A Lim & B Rodrigues & J Zhang, 2005. "Tabu search embedded simulated annealing for the shortest route cut and fill problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(7), pages 816-824, July.
55. J Renaud & A Ruiz, 2008. "Improving product location and order picking activities in a distribution centre," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1603-1613, December.
56. del Castillo, Jose M., 1998. "A heuristic for the traveling salesman problem based on a continuous approximation," Transportation Research Part B: Methodological, Elsevier, vol. 33(2), pages 123-152, April.
57. Novaes, Antonio G. N. & Graciolli, Odacir D., 1999. "Designing multi-vehicle delivery tours in a grid-cell format," European Journal of Operational Research, Elsevier, vol. 119(3), pages 613-634, December.
58. Renaud, Jacques & Boctor, Fayez F., 2002. "A sweep-based algorithm for the fleet size and mix vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 140(3), pages 618-628, August.
59. Kusum Deep & Hadush Mebrahtu & Atulya K. Nagar, 2018. "Novel GA for metropolitan stations of Indian railways when modelled as a TSP," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(3), pages 639-645, June.
60. Crainic, Teodor Gabriel & Laporte, Gilbert, 1997. "Planning models for freight transportation," European Journal of Operational Research, Elsevier, vol. 97(3), pages 409-438, March.
61. Tim Gruchmann & Ani Melkonyan & Klaus Krumme, 2018. "Logistics Business Transformation for Sustainability: Assessing the Role of the Lead Sustainability Service Provider (6PL)," Logistics, MDPI, vol. 2(4), pages 1-19, October.
62. Arroyo, Federico, 2024. "Cost Allocation in Vehicle Routing Problems with Time Windows," Junior Management Science (JUMS), Junior Management Science e. V., vol. 9(1), pages 1241-1268.
63. Zhouchun Huang & Qipeng Phil Zheng & Eduardo Pasiliao & Vladimir Boginski & Tao Zhang, 2019. "A cutting plane method for risk-constrained traveling salesman problem with random arc costs," Journal of Global Optimization, Springer, vol. 74(4), pages 839-859, August.
64. Rayhaneh Nazempour & Jianhua Yang, 2019. "A Study to Assess the Personality of Supply Chain Managers and its Effect on Supply Chain Performance," International Journal of Social and Administrative Sciences, Asian Economic and Social Society, vol. 4(1), pages 57-65, March.
65. Yu-Wei An & Hong-Sen Yan, 2016. "Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6718-6735, November.
66. Marie-Claude Bolduc & Jacques Renaud & Benoit Montreuil, 2006. "Synchronized routing of seasonal products through a production/distribution network," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(2), pages 209-228, June.
67. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M., 2017. "Clustering data that are graph connected," European Journal of Operational Research, Elsevier, vol. 261(1), pages 43-53.
68. Mathirajan, M. & Ramanathan, R., 2007. "A (0-1) goal programming model for scheduling the tour of a marketing executive," European Journal of Operational Research, Elsevier, vol. 179(2), pages 554-566, June.
69. Su, E. & Qin, Hu & Li, Jiliu & Pan, Kai, 2023. "An exact algorithm for the pickup and delivery problem with crowdsourced bids and transshipment," Transportation Research Part B: Methodological, Elsevier, vol. 177(C).
70. Lobo, Fernando G. & Bazargani, Mosab & Burke, Edmund K., 2020. "A cutoff time strategy based on the coupon collector’s problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 101-114.
71. Duygu Pamukcu & Burcu Balcik, 2020. "A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 1-42, March.
72. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
73. Dirk Briskorn & Philipp Zeise, 2019. "A cyclic production scheme for the synchronized and integrated two-level lot-sizing and scheduling problem with no-wait restrictions and stochastic demand," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(4), pages 895-942, December.
74. Wang, Yadong & Meng, Qiang & Jia, Peng, 2019. "Optimal port call adjustment for liner container shipping routes," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 107-128.
75. H-J Kim & Y-D Kim & D-H Lee, 2005. "Scheduling for an arc-welding robot considering heat-caused distortion," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(1), pages 39-50, January.
76. Jun Xu & Wei Hu & Wenjuan Gu & Yongguang Yu, 2023. "A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem," Mathematics, MDPI, vol. 11(14), pages 1-23, July.
77. G Laporte, 2010. "A concise guide to the Traveling Salesman Problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 35-40, January.
78. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
79. Zhan, Yang & Wang, Zizhuo & Wan, Guohua, 2021. "Home service routing and appointment scheduling with stochastic service times," European Journal of Operational Research, Elsevier, vol. 288(1), pages 98-110.
80. Jiefeng Xu & Steve Y. Chiu & Fred Glover, 1999. "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search," Management Science, INFORMS, vol. 45(3), pages 330-345, March.
81. Berkoune, Djamel & Renaud, Jacques & Rekik, Monia & Ruiz, Angel, 2012. "Transportation in disaster response operations," Socio-Economic Planning Sciences, Elsevier, vol. 46(1), pages 23-32.
82. A. Herraiz & M. Gutierrez & M. Ortega-Mier, 2022. "Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(4), pages 1427-1450, December.
83. Laurik Helshani, 2015. "An Android Application for Google Map Navigation System, Solving the Travelling Salesman Problem, Optimization throught Genetic Algorithm," Proceedings of FIKUSZ 2015, in: Jolán Velencei (ed.),Proceedings of FIKUSZ '15, pages 89-102, Óbuda University, Keleti Faculty of Business and Management.
84. Marielle Christiansen & Kjetil Fagerholt, 2002. "Robust ship scheduling with multiple time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(6), pages 611-625, September.