Dynamic modeling of the optimal route in the multimodal transport network

Receipt date: 
Bibliographic description of the article: 

Lebedeva O. A. Dinamicheskoye modelirovaniye optimal'nogo marshruta v mul'timodal'noy transportnoy seti [Dynamic modeling of the optimal route in the multimodal transport network]. Sovremennye tekhnologii. Sistemnyi analiz. Modelirovanie [Modern Technologies. System Analysis. Modeling], 2020, Vol. 65, No. 1, pp. 44–50. 10.26731/1813-9108.2020.1(65).44-50

Journal number: 


Article File: 

The task of optimizing the route transport system has been widely studied for the road network, but less tested for the urban public transport system. The multimodal route networks laid along the shortest path are able to reduce system performance at the time of reaching maximum throughput. The main objective of the study is to develop a dynamic model of the optimal route system for a multimodal transport network. A multimodal transport network is represented by a multilevel oriented graph with many nodes and arcs, which is modeled as a multilevel structure, where each level represents a unimodal subnet and is connected by lines. The network is modeled to simulate passenger movements and operations of transit vehicles. The task of a dynamic system optimization is formulated as the problem of variational inequality for the dynamic equilibrium of a user from the point of view of time-dependent marginal costs. The calculation of the unsteady marginal cost of the journey is based on the additional waiting time for passengers due to denied boarding on arriving vehicles. Therefore, the path is represented by an acyclic directional route on a multi-level oriented graph connecting a pair of departure-destination points. A transfer is considered because of vehicle capacity limitations. The dynamics of the transport system is studied by applying a multi-agent approach to account for operations and the process of waiting for passengers at stations (stopping points). The proposed algorithm is based on the solution of the general problem of the dynamic distribution of the transport flow. The method is a stochastic optimization algorithm for solving combinatorial problems. It links a stochastic mechanism to generate feasible solutions and iteratively improves quality based on performance. The algorithm relies on minimizing the distance (cross-entropy) to the unknown optimal equilibrium density. An experimental study of the solution of a dynamic problem is carried out on a small multimodal transport network. In most cases, the method for solving the dynamic optimal routing problem gives real results. As expected, with increasing load factor, the travel time of the route increases. This is due to the fact that, as the level of congestion increases, some users may be offered a longer route to reduce the total travel time. Since the possible routes for redistributing passengers are relatively limited, the percentage increase in overall time savings becomes not very significant when the system is heavily overloaded. Numerical research provides a basis for comparing optimal system routing at various congestion levels.


List of references: 
  1. Lebedeva O.A. Pokazateli otsenki effektivnosti raboty obshchestvennogo transporta [Performance indicators for public transport]. Sovremennye tekhnologii i nauchno-tekhnicheskii progress [Modern technologies and scientific and technological progress], 2018, Vol. 1, pp. 108–109.
  2. Lebedeva O.A., Antonov D.V. Osnovnye printsipy razvitiya transportnykh sistem gorodov [The basic principles of the development of transport systems of cities]. Vestnik Angarskoi gosudarstvennoi tekhnicheskoi akademii [The Bulletin of the Angarsk State Technical Academy], Angarsk: AGTA Publ., 2014, pp. 149–155.
  3. Gozbenko V.E., Ivankov A.N., Kolesnik M.N., Pashkova A.S. Metody prognozirovaniya i optimizatsii transportnoi seti s uchetom moshchnosti passazhiro- i gruzopotokov. Deponirovannaya rukopis' No. 330-V2008 17.04.2008 [Methods of forecasting and optimizing the transport network, taking into account the capacity of passenger and cargo flows. The deposited manuscript No. 330-V2008 04.17.2008].
  4. Gozbenko V.E., Kripak M.N., Ivankov A.N. Sovershenstvovanie transportno-ekspeditsionnogo obsluzhivaniya gruzovladel'tsev [Improving freight forwarding services for cargo owners]. Irkutsk, 2011.
  5. Kripak M.N., Gozbenko V.E., Kolesnik A.I. Optimizatsiya struktury transporta kak mera povysheniya effektivnosti funktsionirovaniya sistemy gorodskogo passazhirskogo transporta [Optimization of the transport structure as a measure of increasing the efficiency of the functioning of the urban passenger transport system]. Sb. nauch. tr. AnGTU [Proc. of AnSTU]. Angarsk: AnGTU Publ., 2013, pp. 229–232.
  6. Poltavskaya Yu.O., Mikhailov A.Yu. Segment gorodskoi ulitsy pri otsenke kachestva funktsionirovaniya gorodskogo obshchestvennogo passazhirskogo transporta [A segment of a city street in assessing the quality of functioning of urban public passenger transport]. Shag v budushchee: teoreticheskie i prikladnye issledovaniya sovremennoi nauki. Materialy 8 molodezhnoi mezhdunarodnoi nauchno-prakticheskoi konferentsii studentov, aspirantov i molodykh uchenykh [Step into the future: theoretical and applied research of modern science. Materials of the 8th youth international scientific and practical conference of students, graduate students and young scientists]. Otkrytie Scientific Publishing Centre, 2015, pp. 40–44.
  7. Mikhailov A.Yu., Sharov M.I. K voprosu razvitiya sovremennoi sistemy kriteriev otsenki kachestva funktsionirovaniya obshchestvennogo passazhirskogo transporta [On the development of a modern system of criteria for assessing the quality of functioning of public passenger transport]. Izv. Volgograd. gos. tekhn. un-ta [News of Volgograd State Tech. Un-ty], 2014, Vol. 9, No. 19 (146), pp. 64–66.          
  8. Sharov M.I., Mikhailov A.Yu., Kovaleva T.S. Otsenka nadezhnosti raboty gorodskogo passazhirskogo transporta v Irkutske [Assessment of the reliability of urban passenger transport in Irkutsk]. Vestnik IrGTU [The Bulletin of Irkutsk State Technical University], 2012, Vol. 68, No. 9, pp. 174–178.
  9. Weymann J., Farges J.L., Henry J.J. Optimization of traffic dynamic route guidance with drivers' reactions in a queue-based model. IEEE Transactions on Systems, Man and Cybernetics, Vol. 25, No. 7, 1995, pp. 1161–1165.
  10. Jahn O., Möhring R., Schulz A., Moses N. S. System-Optimal Routing of Traffic Flows with User Constraints in Networks with Congestion. Operations research, Vol. 53, No. 4, 2005, pp. 600–616.
  11. Bottom J.A. Consistent anticipatory route guidance. Ph.D. thesis, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, MA, 2000.
  12. Chow A. H. F. Properties of system optimal traffic assignment with departure time choice and its solution method. Transportation Research Part B, Vol. 43, 2009, pp. 325–344.
  13. Ma T.-Y., Lebacque J.P. A cross entropy based multi-agent approach to traffic assignment problems. In: Appert-Rolland C., Chevoir F., Gondret P. Lassarre S., Lebacque J.P., Schreckenberg M. (Eds.), Proceedings of the Traffic and Granular Flow ’07, Springer Berlin Heidelberg, 2007, pp. 161–170.
  14. Powell W.B., Sheffi Y. The Convergence of Equilibrium Algorithms with Predetermined Step Sizes. Transportation Science, Vol. 16, 1982, pp. 45–55.
  15. Beckmann M., McGuire C.B., Winsten C.B. Studies in the economics of transportation. 1955: Yale University Press, New Haven, Conneticut; also published as Rand-RM-1488-PR, Rand Corporation, Santa Monica.
  16. Peeta S., Mahmassani H. System optimal and user equilibrium time-dependent traffic assignment in congested networks. Annals of Operations Research, Vol. 60, No. 1, 1995, pp. 80–113.
  17. Tong C.O., Wong S.C. A predictive dynamic traffic assignment model in congested capacity-constrained road networks. Transportation Research Part B, Vol. 34, No. 8, 2000, pp. 625–644.
  18. Lebacque J.-P., Ma T.-Y., Khoshyaran M.M. The cross-entropy field for multimodal dynamic assignment. In: Proceedings of the Traffic and Granular Flow ’09, 2009, Springer (to appear).
  19. Helvik B.E., Wittner O. Using the Cross-Entropy Method to Guide. Govern Mobile Agent's Path Finding. Networks. Lecture Notes in Computer Science, 2001, Vol. 2164, 2001, pp. 255–268.
  20. Bliemer M., Taale H. Route generation and dynamic traffic assignment for large networks. In: Proceedings of the first International Symposium on Dynamic Traffic Assignment, 2006, Leeds, UK.
  21. Lebedeva O.A., Kripak M., Gozbenko V.E. Increasing effectiveness of the transportation network through by using the automation of a Voronoi diagram. Transportation Research Procedia, 36, 427–433.