Optimization of Dynamic Programming Technique for Travelling Salesman Problem
DOI:
https://doi.org/10.61841/hxpet855Keywords:
TSP, Dynamic Programming, Optimal Path, Time Complexity, Root City, Initial Root CityAbstract
Travelling Salesman Problem (TSP) is a problem where an optimal path has to be calculated from source city to destination. Optimality of the path generally refers to the minimum cost (distance) between source and destination. In the proposed methodology, multiple optimal paths are calculated which not only provides the user an optimal path, but it also provides the user choice to select an optimal path from the list of multiple optimal paths having same source and destination, but different cities pattern in between them using dynamic programming. The proposed methodology has been compared with the branch and bound approach of solving TSP, and the proposed methodology came out to be faster than the latter approach, and also it provides the multiple optimal paths to the user which is not provided by any other approach.
Downloads
References
[1] Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2007). The Traveling Salesman Problem. Princeton University Press.
[2] Applegate DL, Bixby RE, Chvatal V, Cook WJ. The traveling salesman problem: a computational study. Princeton university press; 2006.
[3] Chudasama, C., Shah, S. M., & Panchal, M. (2011). Comparison of parents selection methods of genetic algorithm for TSP. In International Conference on Computer Communication and Networks CSI-COMNET-2011, Proceedings (pp. 85-87).
[4] Rai, K., Madan, L., & Anand, K. (2014). Research Paper on Travelling Salesman Problem And it’s Solution
Using Genetic Algorithm. International Journal of Innovative Research In Technology, 1(11), 103-114.
[5] Matai, Rajesh, Surya Prakash Singh, and Murari Lal Mittal. "Traveling salesman problem: an overview of applications, formulations, and solution approaches." Traveling salesman problem, theory, and applications 1 (2010).
[6] Kumbharana, Sharad N., and Gopal M. Pandey. "Solving travelling salesman problem using firefly algorithm."
International Journal for Research in Science & advanced Technologies 2.2 (2013): 53-57.
[7] Dorigo, Marco, and Luca Maria Gambardella. "Ant colonies for the travelling salesman problem." biosystems
43.2 (1997): 73-81.
[8] Lakshmi, G. Vijaya. "Lexisearch Approach to Travelling Salesman Problem."
[9] Reddy, P. M. M., Sudhakara, E., Sreenadh, S., & Varma, S. V. K. An Alternate Travelling Salesman Problem.
[10] Singh, A., & Kaur, M. Solving Multiple Travelling Salesman Problem Using Genetic Algorithm: A Case Study.
[11] Laporte, G., & Martello, S. (1990). The selective travelling salesman problem. Discrete applied mathematics,
26(2-3), 193-207.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
