Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem
DOI:
https://doi.org/10.70356/josapen.v2i2.32Keywords:
Dynamic Programming, Efficient Solutions, Traveling Salesman ProblemAbstract
This study aims to enhance dynamic programming techniques for efficiently solving the Traveling Salesman Problem, a fundamental combinatorial optimization challenge. Given its NP-hard classification, traditional exact algorithms become computationally infeasible as the problem size increases. The research revisits foundational dynamic programming principles, notably the Held-Karp algorithm, and identifies existing limitations. The study begins with a comprehensive literature review, followed by an analysis of the dynamic programming challenges specific to TSP. Novel algorithms are then developed, implemented, and rigorously tested against benchmark instances. Performance evaluation is conducted using metrics such as execution time, memory usage, and solution optimality across different problem sizes. Results demonstrate significant improvements in efficiency and scalability, with enhanced algorithms achieving optimal solutions in reduced time and computational resource usage. However, the exponential growth in complexity remains a challenge for larger instances. The study concludes with recommendations for future research, focusing on further algorithmic refinements and exploring hybrid approaches to address large-scale TSPs.
Downloads
References
A. Hamza, A. H. Darwish, and O. Rihawi, “Intelligent Systems with Applications A new local search for the bees algorithm to optimize multiple traveling salesman problem,” Intell. Syst. with Appl., vol. 18, no. May, p. 200242, 2023, doi: 10.1016/j.iswa.2023.200242.
M. Scianna, “The AddACO : A bio-inspired modified version of the ant colony optimization algorithm to solve travel salesman problems,” Math. Comput. Simul., vol. 218, no. November 2023, pp. 357–382, 2024, doi: 10.1016/j.matcom.2023.12.003.
E. Mizutani and S. Dreyfus, “A tutorial on the art of dynamic programming for some issues concerning Bellman’s principle of optimality,” ICT Express, vol. 9, no. 6, pp. 1144–1161, 2023, doi: 10.1016/j.icte.2023.07.001.
E. De Klerk and C. Dobre, “A comparison of lower bounds for the symmetric circulant traveling salesman problem,” Discret. Appl. Math., vol. 159, no. 16, pp. 1815–1826, 2011, doi: 10.1016/j.dam.2011.01.026.
M. Boccia, A. Masone, A. Sforza, and C. Sterle, “An Exact Approach for a Variant of the FS-TSP,” Transp. Res. Procedia, vol. 52, pp. 51–58, 2021, doi: 10.1016/j.trpro.2021.01.008.
Ö. Ergun and J. B. Orlin, “A dynamic programming methodology in very large scale neighborhood search applied to the traveling salesman problem,” Discret. Optim., vol. 3, no. 1, pp. 78–85, 2006, doi: 10.1016/j.disopt.2005.10.002.
B. Toaza and D. Esztergár-Kiss, “A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems [Formula presented],” Appl. Soft Comput., vol. 148, no. October, 2023, doi: 10.1016/j.asoc.2023.110908.
R. Martí, M. Sevaux, and K. Sörensen, “50 Years of Metaheuristics,” Eur. J. Oper. Res., no. April, 2024, doi: 10.1016/j.ejor.2024.04.004.
D. A. F. Anggraeni, V. R. Dianutami, and R. Tyasnurita, “Investigation of Simulated Annealing and Ant Colony optimization to Solve Delivery Routing Problem in Surabaya, Indonesia,” Procedia Comput. Sci., vol. 234, pp. 592–601, 2024, doi: 10.1016/j.procs.2024.03.044.
S. Sariel, N. Erdogan, and T. Balch, “An Integrated Approach To Solving the Real-World Multiple Traveling Robot Problem,” 5th Int. Conf. Electr. Electron. Eng., 2007.
C. Jiang, Z. Wan, and Z. Peng, “A new efficient hybrid algorithm for large scale multiple traveling salesman problems,” Expert Syst. Appl., vol. 139, 2020, doi: 10.1016/j.eswa.2019.112867.
K. Sundar and S. Rathinam, “Algorithms for Heterogeneous, Multiple Depot, Multiple Unmanned Vehicle Path Planning Problems,” J. Intell. Robot. Syst. Theory Appl., vol. 88, no. 2–4, pp. 513–526, 2017, doi: 10.1007/s10846-016-0458-5.
M. A. Al-Omeer and Z. H. Ahmed, “Comparative study of crossover operators for the MTSP,” 2019 Int. Conf. Comput. Inf. Sci. ICCIS 2019, pp. 1–6, 2019, doi: 10.1109/ICCISci.2019.8716483.
P. Venkatesh and A. Singh, “Two metaheuristic approaches for the multiple traveling salesperson problem,” Appl. Soft Comput., vol. 26, pp. 74–89, 2015, doi: 10.1016/j.asoc.2014.09.029.
R. I. Bolaños, M. G. Echeverry, and J. W. Escobar, “A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the multiple traveling salesman problem,” Decis. Sci. Lett., vol. 4, no. 4, pp. 559–568, 2015, doi: 10.5267/j.dsl.2015.5.003.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Adriel Moses Anson
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
