A Survey on Approaches to Solve Travelling Sa- lesman Problem
DOI:
https://doi.org/10.61841/k5cqqr02Keywords:
Salesman Problem, Survey on Approaches,, Optimal RouteAbstract
Travelling Salesman Problem (TSP) is widely used in traffic management and the transportation in- dustry where the route optimization would speed up services and increase efficiency. In this paper, we survey the most popular approaches including dynamic and meta-heuristic algorithms to solve the Travelling Salesman Prob- lem. Our survey clearly indicates that meta-heuristic algorithms like Ant Colony Optimisation (ACO) take addition- al time to arrive at the solution but returns the best optimal route when compared with others. Hence, we take our research forward in improving the ACO technique to support environmental changes like weather, traffic conges- tions and delays in real time and return the optimal route.
Downloads
References
[1] Peter Hart, Nils Nilsson and Bertram Raphael - “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” IEEE Transactions on Systems Science and Cybernetics ( Volume: 4, Issue: 2, July 1968 )
[2] Kennedy and Eberhart - "Particle swarm optimization,” 1995 IEEE International Conference on Neural Net- works (ICNN 95), IEEE, Nov 27-Dec 01. 1995, pp.1942-1948.
[3] H.Shimizu, M.Kobayashi and Y.Yonezawa - “Dynamic route search algorithms of a traffic network” Proceed- ings of the 36th SICE Annual Conference. International Session Papers, 1997
[4] M. Dorigo et L.M. Gambardella - “Ant Colony System : A Cooperative Learning Approach to the Traveling Salesman Problem”- IEEE Transactions on Evolutionary Computation, volume 1, pages 53-66, 1997.
[5] Y. Murat, and N. Uludag - “ Route choice modelling in urban transportation networks using fuzzy logic and logistic regression methods” Journal of Scientific & Industrial Research, 2008 vol. 67, pp. 19-27.)
[6] Li-Pei Wongi, Malcolm Yoke Hean Lowii and Chin Soon Chong - ”A Bee Colony Optimization Algorithm for Traveling Salesman Problem” IEEE transaction on second Asia International Conference on simulation and modeling, pp 818-823, June 2008
[7] R. Nallusamy, K. Duraiswamy, R. Dhanalaksmi, and P. Parthiban - “Optimization of multiple Vehicle Routing Problems using Approximation Algorithms,” International Journal of Engineering Science and Technology, 2009 vol 1 (3).
[8] Salehinejad and Talebi - “Dynamic Fuzzy Logic- Ant Colony System-Based Route Selection System,” Applied Computational Intelligence and Soft Computing, Hindawi Publishing Corporation, 2010.
[9] Y. Bykov and S. Petrovic. - "A Step Counting Hill Climbing Algorithm applied to University Examination Timetabling." Journal of Scheduling, pp. 1-14, 2014.
[10] Sh. Zhan, J. Lin, Z. Zhang, and Y. Zhong. - "List- Based Simulated Annealing Algorithm for Traveling Sales- man Problem." Computational intelligence and neuroscience 2016.
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.
