Observer of changes in the forest of the shortest paths on dynamic graphs of transport networks

The purpose of the work is the development of basic data structures, speed-efficient and memoryefficient algorithms for tracking changes in predefined decisions about sets of shortest paths on transport networks, notifications about which are received by autonomous coordinated transport agents with centralized or collective control. A characteristic feature of transport operations is the independence and asynchrony of the emergence of perturbations of optimal solutions, as well as the lack of global influence of individual perturbations on the set of all processes on the network. This clearly determines the feasibility of realizing the idea of reoptimizing existing solutions in real time as information is received about disturbances in the structure and parameters of the transport network, various restrictions on the use of existing shortest paths. In contrast to the classical problems of finding shortest paths on static or dynamic graphs, it is proposed to supplement the set of situations controlled by the observer by taking into account the associations of shortest path trees with agents that actually use such paths. This will improve the responsiveness of agent notification processes for timely switching to a new path. The space of search states is a dynamically generated bipartite sparse graph of the transport network, represented by a list of arcs. The basic algorithm for finding the shortest paths uses Dijkstra's scheme, but implements a bootstrapping method to generate the search result. The compactness of the representation of the observed forest of shortest paths is achieved by mapping individual trees of such a forest onto the projection of tree vertices in memory, where the position of each vertex corresponds to the distance from the tree root. The proposed version of the construction of the search procedure is based on the mechanisms existing in database management systems for creating different relational representations of the physical data model. This eliminates the need to solve technological problems of complexing heterogeneous models of dynamic transport networks, memory allocation. As a result, the specification of various rules for the logistics of transport operations is simplified, since such operations in terms of object-oriented models are easily determined by polymorphic classes of transitions between nodes of the transport network.

1. Sun Y., Yu X., Bie R., Song H. Discovering time-dependent shortest path on traffic graph for drivers towards green driving. Journal of Network and Computer Applications. 2017;83:204-212.

2. Rubanov I.V., Barketau M.S., Kovalyov M.Y. [Modeling movement of objects without stops in a network of crossing routes]. Informatika = Informatics. 2018;15(1):21-33. (In Russ.)

3. Rybak V.A., Ryabichina O.P. [Ecological monitoring system of the atmosphere]. Doklady BGUIR = Doklady BSUIR. 2020;18(4):36-43. (In Russ.)

4. Ferone D., Festa P., Napoletano A., Pastore T. Shortest paths on dynamic graphs: a survey. Pesquisa Operacional. 2017;37(3):487-508.

5. Pugliese L.D.P., Guerriero F. A survey of resource constrained shortest path problems: Exact solution approaches. Networks. 2013;62(3):183-200.

6. Pallottino M.S., Scutelli M.G. A new algorithm for reoptimizing shortest paths when the arc costs change. Operations Research Letters. 2003;31(2):149-160.

7. Hooks E., Yang B. Updating paths in time-varying networks given arc weight changes. Transportation Science. 2005;39(4):451-464.

8. Nicholson T.A.J. Finding the Shortest Route between Two Points in a Network. The Computer Journal. 1966;9(3):275-280.

9. Revotjuk M.P., Qaraleh M.K., Khajynova N.V. [Quick search of the shortest paths on the graph with a predetermined decision]. Doklady BGUIR = Doklady BSUIR. 2014;4(82):73-79. (In Russ.)