AN IMPROVED GEOMETRIC ALGORITHM AND SOFTWARE IN TRANSPORT ROUTE OPTIMIZATION PROBLEMS
DOI:
https://doi.org/10.32689/maup.it.2023.4.1Keywords:
combinatorial optimization, traveling salesman problem, optimal route, execution time, accuracyAbstract
Modern transport route management systems require the development of software that implements more accurate and faster algorithms for solving the traveling salesman problem, which provide for a large number of points the search for the best route with a relatively small error in a shorter time. The main disadvantages of the existing implementations are stochasticity, limited adaptability to the parameters of the problem and high sensitivity to the initial conditions, which leads to incorrect decisions and loss of resources. The article presents the formulation of the problem of finding the smallest possible circular route passing through a given set of cities, starting and ending in the same city. As a result, the algorithm must find a sequence of visiting cities so that the total length of the path between them is minimal, and the path passes through each city exactly once. Experimental studies were conducted, and the efficiency of the improved geometric algorithm was compared for 10, 50, 100 and 1000 cities. The performance of the improved geometric algorithm for 10 cities is compared to the basic geometric algorithm and the brute force algorithm to verify that there is an improvement not only in the route search time but also in the length of the path found. For 50, 100, 1000 cities, the results of the improved geometric algorithm will be compared with the basic geometric algorithm, the genetic algorithm, and the ant colony optimization algorithm to make sure that the improved geometric algorithm works no worse and faster than other algorithms. In cases where the improved geometric algorithm works with an error relative to other algorithms, it allows to obtain a significant gain in execution time. Experiments show that the improved geometric algorithm proposed in the article allows deterministically finding the best route with an error of 6.82% for 1000 cities. At the same time, it finds solutions 2.8 times faster than the ant colony optimization algorithm and 265 times faster than the genetic algorithm. The example of implementation of the improved geometric algorithm in the swift programming language for use on the iOS platform is given.
References
Lawler, E. L., et al. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley. 1985. P. 25-31.
Monnot, J., & Toulouse, S. The traveling salesman problem and its variations. Paradigms of combinatorial optimization: problems and new approaches. 2014. P. 173-214.
Chandra, A., & Naro, A. A comparative study of metaheuristics methods for solving traveling salesman problem. International Journal of Information Science and Technology. 2022. №6(2), P.1-7.
Zhang, C., & Sun, P. Heuristic Methods for Solving the Traveling Salesman Problem (TSP): A Comparative Study. In 2023 IEEE 34th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC). 2023. P. 1-6. IEEE.
Reinelt, G. The Traveling Salesman: Computational Solutions for TSP Applications. Springer. 1994. P. 18-21.
Toth, P., et al. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. SIAM. 2002. P. 39-41.
Nagata, Y. Recent developments in combinatorial optimization for the traveling salesman problem: A survey. European Journal of Operational Research. 2011. №213(1). P. 1-10.
Vansteenwegen, P., et al. The Traveling Salesman Problem: A Case Study in Local Optimization. Operations Research Perspectives. 2011. P. 65-77.
Gutin, G., Punnen, A. The traveling salesman problem and its variations. Springer Science & Business Media, 2006.
Jiang, C., Wan, Z., & Peng, Z. A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Systems with Applications. 2020. №139. P. 112867.
Cheikhrouhou, O., & Khoufi, I. A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy. Computer Science Review. 2021. №40. P. 100369.
Lawler, E. L., et al. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley. 1985. P. 49-52.
Dorigo, M., et al. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics. 1996. №26(1). P. 29-41.
Dorigo, M., et al. Ant Colony Optimization. MIT Press. 2004. P. 16-20.
Blum, C., et al. The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics. 2004. №34(2). P. 1161-1172.
Holland, J. H. Adaptation in Natural and Artificial Systems. University of Michigan Press. 1975. P. 17-22.
Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional. 1989. P. 24-27.
Mitchell, M. An Introduction to Genetic Algorithms. MIT Press. 1998. P. 30-33.
Cormen, T. H., et al. Introduction to Algorithms. MIT Press. 2022.
An Improvement to the 2-Opt Heuristic Algorithm for Approximation of Optimal TSP Tour. URL: https://www.mdpi.com/2076-3417/13/12/7339
