Network routing method for ships and other moving objects using MATLAB

• Autorzy: Sakharov Vladimir V. , Chertkov Alexandr A. , Ariefjew Igor B.

Identyfikatory

DOI

10.17402/420

• Języki publikacji: EN

Abstrakty

EN

Task planning involves automating the creation of the routes for vessels with known coordinates in a confined space. The management of vessel release in a given area affects the time required for a vessel to complete its voyage, and maximizing vessel performance involves identifying the shortest route. A key issue in automating the generation of the optimal (shortest) routes is selecting the appropriate mathematical apparatus. This paper considers an optimization method based on a recursive algorithm using Bellman-Ford routing tasks for large dimensions. Unlike other optimization techniques, the proposed method enables the shortest path to be assessed in a network model with a complex topology, even if there are arcs with negative weights. The practical implementation of the modified Floyd algorithm was demonstrated using a sample automated build and using it to calculate a network model with a complex topology, using an iterative procedure for a program prepared in MATLAB. Implementation of the computer model is simple, and unlike existing models, it eliminates restrictions associated with the presence of negative weights and cycles on a network and automates search shortcuts in ground branch functional means in MATLAB. To confirm the accuracy of the obtained results, we performed an example calculation using the network. The proposed algorithm and recursive procedure are recommended for finding energy-efficient solutions during the management of mobile objects on waterways.

Słowa kluczowe

EN

algorithm; path; optimization; transport; automation; moving object

• Wydawca: Wydawnictwo Naukowe Akademii Morskiej w Szczecinie
• Czasopismo: Zeszyty Naukowe Akademii Morskiej w Szczecinie
• Rocznik: 2020
• Tom: nr 62 (134)
• Strony: 61--68
• Opis fizyczny: Bibliog. 15 poz., rys.

Twórcy

autor

Sakharov Vladimir V.

• Admiral Makarov State University of Maritime and Inland Shipping 5/7 Dvinskaya St., St. Petersburg 198035, Russian Federation

autor

Chertkov Alexandr A.

• Admiral Makarov State University of Maritime and Inland Shipping 5/7 Dvinskaya St., St. Petersburg 198035, Russian Federation

autor

Ariefjew Igor B.

• Maritime University of Szczecin 11 H. Pobożnego St., 70-507 Szczecin, Poland

Bibliografia

• 1. Ariefiew, I. (2012) Forecasting and control object of management in the environment of system pert (the nod of integrated characteristics). Maritime University of Szczecin, Digital Library.
• 2. Bellman, R. (1958) On a routing problem. Quarterly of Applied Mathematics 16, 1, pp. 87–90.
• 3. Castillo, O., Trujillo, L. & Melin, P. (2007) Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots. Soft Computing 3 (11), pp. 269–279.
• 4. Chertkov, A.A. (2015) An iterative algorithm for choosing the optimal strategy of group interaction for moving objects. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 4 (32) (in Russian), pp. 207−215.
• 5. Chertkov, A.A. (2017) Automation selection shortcuts routes of ships on the basis of modified Bellman. Ford. Algorithm. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 9, 5, pp. 1113–1122. DOI: 10.21821/2309-5180-2017-9-5-1113- 1122 (in Russian).
• 6. Chertkov, А.А., Vardomskaya, A.A. & Dmitriev, A.A. (2015a) A Recursive method of optimization of the logistic ways by means of MATLAB. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 6(34), pp. 196−204 (in Russian).
• 7. Chertkov, A.A., Vardomskaya, A.A. & Dmitriev, A.A. (2015b) Automation to define critical way in logistical system. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 5 (33), pp. 194–200 (in Russian). DOI: 10.21821/2309-5180-2015-7-5- 194-200.
• 8. Fedorenko, K.V. & Olovyannikov, A.L. (2017) Research of the main parameters of the genetic algorithm for the problem of searching the optimal route. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 9, 4, pp. 714–723 (in Russian). DOI: 10.21821/2309-5180-2017-9-4-714-723.
• 9. Fonseca, C.M. & Fleming, P.J. (1993) Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: Forrest, S. (ed.) Genetic Algorithms: Proceedings of the Fifth International Conference, San Mateo, CA: Morgan Kaufman, pp. 416–423.
• 10. Kirsanov, М.N. (2016) Analysis of algorithms for the selection of optimal routes the groups vessels. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 2 (36), pp. 183–190 (in Russian). DOI: 10.21821/2309-5180-2016-8-2-183-190.
• 11. Saharov, V.V., Chertkov, A.A. & Dmitriev, A.A. (2016) Ensuring minimum transport work algorithm for goods traffic. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 1, 35, pp. 180–188 (in Russian). DOI: 10.21821/2309-5180-2016- 8-1-180-188.
• 12. Saharov, V.V., Chertkov, A.A. & Ochina, L.B. (2019) Routing the networks with negative weights of links in the MATLAB optimization package. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 11, 2, pp. 230–242 (in Russian). DOI: 10.21821/2309-5180-2019-11-2230-242.
• 13. Saharov, V.V., Chertkov, A.A. & Tormashev, D.S. (2014) Algoritm optimalnogo planirovanija gruppovogo vzaimodejstvija robotov. Morskoj Vestnik 4 (52) (214): pp. 119– 122.
• 14. Saharov, V.V., Sikarev, I.A. & Chertkov, A.A. (2018) Automating search optimal routes and goods flows in transport networks means the integer linear programming. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 10, 3, pp. 647–657 (in Russian). DOI: 10.21821/23095180-2018-10-3-647-657.
• 15. Sazonov, А.Е. & Derjabin, V.V. (2013) Forecasting to paths of the motion ship with the help of neyronnoy network. Vestnik Gosudarstvennogo Universiteta Morskogo i Rechnogo Flota Imeni Admirala S.O. Makarova 3, 22, pp. 6–13 (in Russian).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).