Використання алгоритму Дейкстри для оптимізації задач управління та планування перевезень у навчальному процесі

Abstract

UA: У статті розглядаються можливості застосування алгоритмів теорії графів для розв’язання задач управління та планування транспортних перевезень у навчальному процесі підготовки фахівців з інформаційних технологій, автоматизації та логістики. Проаналізовані особливості використання алгоритму пошуку найкоротшого шляху (алгоритм Дейкстри), для оптимізації маршрутів у транспортних мережах. Розглянута математична модель транспортної мережі у вигляді зваженого графа, де вершини відповідають транспортним вузлам, а ребра – можливим маршрутам переміщення з певними ваговими характеристиками. Наведений алгоритмічний опис процедури знаходження оптимального маршруту та приклад розрахунку найкоротшого шляху між пунктами мережі. Показано доцільність використання таких моделей у навчальному процесі для формування у студентів практичних навичок моделювання транспортних систем та застосування алгоритмів оптимізації. Наведений приклад використання алгоритму Дейкстри в курсах комп’ютерного моделювання, дискретної математики та інформаційних технологій з використанням пакету MATLAB.

EN: The article examines the possibilities of applying graph theory algorithms to solving transportation management and transportation planning problems within the educational process of training specialists in information technologies, automation, and logistics. Modern transportation and logistics systems are characterized by a steady increase in traffic volumes, growing network complexity, and a large number of interrelated elements, which makes the search for optimal routes one of the most common tasks arising at practically every level of management on railway transport, in logistics centers, dispatching control systems, and information-management systems. The features of using the shortest path search algorithm, namely Dijkstra's algorithm, for route optimization in transport networks are analyzed in detail, including its computational scheme, the conditions under which it is applicable, and its place among other well-known shortest-path methods such as the Bellman-Ford, Floyd-Warshall, and A* algorithms. A mathematical model of a transport network is considered in the form of a weighted graph, where the vertices correspond to transport nodes and the edges represent possible transportation routes, each characterized by a weight that may express distance, travel time, transportation cost, or resource consumption. Within this model, the transportation planning problem is formalized as the problem of finding a path between a source and a destination vertex that minimizes the total weight of the route. An algorithmic description of the procedure for finding the optimal route is presented step by step, together with a worked example of calculating the shortest path in a five-node transport network, illustrated by an iteration table that traces the change of the shortestdistance estimates at every step of the algorithm until the optimal route and its total length are obtained. The expediency of using such graph-based models in the educational process is demonstrated: they allow students to formalize transport networks as adjacency matrices, build graphical representations of transport systems, determine shortest routes between nodes, analyze the influence of edge-weight changes on optimization results, and compare different routing algorithms. This combination of mathematical modeling, algorithmic thinking, and computational practice contributes to the formation of practical skills in transport-system modeling and the application of optimization algorithms among students. A practical implementation of Dijkstra's algorithm in MATLAB is presented, including adjacency matrix construction, graph visualization, and highlighting of the optimal route. The obtained results confirm the effectiveness of the proposed approach for incorporation into courses on computer modeling, discrete mathematics, and IT for transport specialists.