Automating the search for the shortest closed path in transport network by means of MATLAB

The paper considers the problem of automating the search and construction of the shortest closed route for a group of merchant ships on a given set of transit nodes of the transport network with known coordinates. The goal is to find the shortest closed route that passes through all hosts only once and ends at the outgoing node. In general, a weighted graph can serve as a mathematical model of such a transport network, in which the criterion for the efficiency of the desired route can be, for example, the distance between cities or ports, time or operating costs. This allows you to identify time reserves that can be used to save fuel and energy, taking into account the load and cost of goods, travel costs and other factors. The work uses a combinatorial method using stochastic (probabilistic) programming, which is implemented using an annealing simulation algorithm supplemented by a recursive step-by-step optimization procedure. The problem belongs to the class of transcomputational even with a small network dimension, which makes it impossible to solve it by brute force on modern computers in a reasonable time. The proposed modification of the simulated annealing algorithm eliminates this limitation and allows not only to evaluate the shortest paths in the network, but also to build closed paths that pass through all the vertices of the network once. The use of an iterative strategy in the algorithm using a probabilistic scenario according to the Monte Carlo method allows you to avoid the solution falling into the local minimum and provides global optimization. The algorithm is implemented in MATLAB codes in the form of a recursive step-by-step optimization procedure with the construction of a curve of a closed route on the coordinate plane through the entire set of nodes of the transport network without mutual intersections of its sections. It is shown that the result of recursive optimization is to obtain a numerical estimate of the closed path of the minimum weight in the full weighted graph, which is a model of the transport network with the definition of an array of transit node numbers on this route. The developed algorithm and global optimization procedure can be used to automate the search for energy-efficient solutions in the control of robotic and unmanned objects, as well as ships in the performance of cargo transportation in water transport.

1. Sakharov V, I. A. Sikarev and A. A. Chertkov “Avtomatizatsiya poiska optimal’nykh marshrutov i gruzovykh potokov v transportnykh setyakh sredstvami tselochislennogo lineynogo programmirovaniya.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 10.3 2018:647–657. — DOI: 10.21821/2309-5180-2018-10-3-647-657.

2. Chertkov A, A. A. Vardomskaya and A. A. Dmitriev “Rekursivnyy metod optimizatsii logisticheskikh putey sredstvami MATLAB.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 6(34). 2015:196–204. — DOI: 10.21821/2309-5180-2015-7-6-196-204.

3. Chertkov A “Avtomatizatsiya vybora kratchayshikh marshrutov sudov na osnove modifitsirovannogo algoritma Bellmana-Forda.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 9.5 2017:1113–1122. — DOI: 10.21821/2309-5180-2017-9-5-1113-1122.

4. Sakharov V, A. A. Chertkov and L. B. Ochina “Marshrutizatsiya setey s otritsatel’nymi vesami zven’ev v pakete optimizatsii MATLAB.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 11.2 2019:230–242. — DOI: 10.21821/2309-5180-2019-11-2-230-242.

5. Sakharov Vladimir. V., Alexandr. A. Chertkov, Igor. B. Ariefjew. “Network routing method for ships and other moving objects using MATLAB”. Scientific Journal of the Maritime University of Szczecin 62(134) (2020): 61–68.

6. Hornik K. TSP – Infrastructure for the traveling salesperson problem Journal of statistical software 23 (2) (2007): 1‒21. DOI: 10.18637/jss.v023.i02.

7. Boroznov V “Issledovanie resheniya zadachi kommivoyazhera.” Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya: Upravlenie, vychislitel’naya tekhnika i informatika 2. 2009:147–151.

8. T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo Parameter Adaptation in Ant Colony Optimization. Technical Report. IRIDIA, Université Libre de Bruxelles, 2010.

9. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford. Algorithms: Postroenie i analiz. 2 izd. М.: Vilyams, 2011.

10. Kostjuk. Ju. L. “Effektivnaya realizatsiya algoritma resheniya zadachi kommivoayzhera metodom vetvey i granits” // Prikladnaya diskretnaya matematika, vychislitelnye metody v diskretnoy matematike, 2 (20) (2010):78-90.

11. Kirsanov, M. N. “Analiz algoritmov vybora optimalnykh marshrutov gruppy sudov.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 2(36) (2016): 183‒190. DOI: 10.21821/2309-5180-2016-8-2-183-190.

12. Metropolis V. N., Rosenbluth A. W., Rosenbluth M. N., Teller A. H., Teller E. “Equations of state calculations by fast computing machines.” J. Chem. Phys. 21 (1953): 1087–1092

13. Winkler, Gerhard. Image analysis, random fields and Markov chain Monte Carlo methods: a mathematical introduction. Vol. 27. Springer Science & Business Media, 2012.

14. Ermakov, S. M., D. V. Kulikov and S. N. Leora “K analizu metoda imitatsii otzhiga v mnogoekstremalnom sluchae.” Vestnik Sankt-Peterburgskogo universiteta. Matematika. Mekhanika. Astronomiya 4.2 (2017): 220‒226. DOI: 10.21638/11701/spbu01.2017.205.

15. Kostin, A. S. and N. N. Majorov “Issledovanie modelej i metodov marshrutizatsiii prakticheskogo vypolneniya avtonomnogo dvizheniya bespilotnymi transportnymi sistemami dlya dostavki gruzov.” Vestnik gosudarstvennogo universiteta morskogo i rechnogo flota im. admirala S.O. Makarova 15.3 (2023): 524‒536. DOI: 10.21821/2309-5180-2023-15-3-524-536.