Open-Source Public Transportation Mobility Simulation Engine DTALite-S: A Discretized Space–Time Network-Based Modeling Framework for Bridging Multi-agent Simulation and Optimization

Abstract

Recently, an open-source light-weight dynamic traffic assignment (DTA) package, namely DTALite, has been developed to allow a rapid utilization of advanced dynamic traffic analysis capabilities. Aiming to bridge the modeling gaps between multi-agent simulation and optimization in a multimodal environment, we further design and develop DTALite-S to simplify the traffic flow dynamic representation details in DTALite for future extensions. We hope to offer a unified modeling framework with inherently consistent space–time network representations for both optimization formulation and simulation process. This paper includes three major modeling components: (1) mathematic formulations to describe traffic and public transportation simulation problem on a space–time network; (2) transportation transition dynamics involving multiple agents in the optimization process; (3) an alternating direction method of multipliers (ADMM)-based modeling structure to link different features between multi-agent simulation and optimization used in transportation. This unified framework can be embedded in a Lagrangian relaxation method and a time-oriented sequential simulation procedure to handle many general applications. We carried out a case study by using this unified framework to simulate the  passenger traveling process in Beijing subway network which contains 18 urban rail transit lines, 343 stations, and 52 transfer stations. Via the ADMM-based solution approach, queue lengths at platforms, in-vehicle congestion levels and absolute deviation of travel times are obtained within 1560 seconds.The case study indicate that the open-source DTALite-S integrates simulation and optimization procedure for complex dynamic transportation systems and can efficiently generate comprehensive space-time traveling status.

Keywords

Space–time network / Dynamic traffic assignment / Multi-agent simulation / Lagrangian relaxation / Alternating direction method of multipliers

References

[1] Osorio C, Bierlaire M. A simulation-based optimization framework for urban transportation problems. Oper Res, 2013, 61(6): 1333-1345

[2] Xiong C, Zhu Z, Chen X, Zhang L. Optimal travel information provision strategies: an agent-based approach under uncertainty. Transp B Transp Dyn, 2018, 6(2): 129-150.

[3] Mahmassani HS, Fei X, Eisenman S, Zhou X, Qin X (2005) DYNASMART-X evaluation for real-time TMC application: CHART test bed. Maryland Transportation Initiative, University of Maryland, College Park, Maryland, pp 1–144

[4] Nedic A, Ozdaglar A. Distributed subgradient methods for multi-agent optimization. IEEE Trans Autom Control, 2009, 54(1): 48-61

[5] Fagnant D, Hall CJ, Kockelman KM. The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios. Transp Res Part C, 2014, 40(1): 1-13

[6] Newell GF. A simplified theory of kinematic waves in highway traffic, part iii: multi-destination flows. Transp Res Part B Methodol, 1993, 27(4): 281-287

[7] Zhou X, Taylor J, Pratico F. DTALite: a queue-based mesoscopic traffic simulator for fast model evaluation and calibration. Cogent Eng, 2014, 1(1): 961345

[8] Spieser K, Treleaven KB, Zhang R, Frazzoli E, Morton D, Pavone M. Toward a systematic approach to the design and evaluation of automated mobility-on-demand systems: a case study in Singapore, 2014, Road Vehicle Automation: Springer International Publishing

[9] Yu Y, El Kamel A, Gong G, Li F. Multi-agent based modeling and simulation of microscopic traffic in virtual reality system. Simul Model Pract Theory, 2014, 45: 62-79

[10] Bierlaire M. Simulation and optimization: a short review. Transp Res Part C Emerg Technol, 2015, 55: 4-13

[11] Kloostra B, Roorda MJ (2017) Fully autonomous vehicles: analyzing transportation network performance and operating scenarios in the Greater Toronto Area, Canada. In: TRB 2017 annual meeting

[12] Khattak A, Yangsheng J, Lu H, Juanxiu Z. Modeling and simulation of metro transit station walkway as a state-dependent queuing system based on the phase-type distribution. Int J Traffic Transp Eng, 2016, 5(5): 103-111.

[13] Liang X, de Almeida Correia GH, Van Arem B. Optimizing the service area and trip selection of an electric automated taxi system used for the last mile of train trips. Transp Res Part E Logist Transp Rev, 2016, 93: 115-129

[14] Mahmassani HS. 50th anniversary invited article—autonomous vehicles and connected vehicle systems: flow and operations considerations. Transp Sci, 2016, 50(4): 1140-1162

[15] Qu Y, Zhou X. Large-scale dynamic transportation network simulation: a space-time-event parallel computing approach. Transp Res Part C Emerg Technol, 2017, 75: 1-16

[16] Martinez LM, Correia GH, Viegas JM. An agent-based simulation model to assess the impacts of introducing a shared-taxi system: an application to Lisbon (Portugal). J Adv Transp, 2015, 49(3): 475-495

[17] Golubev K, Zagarskikh A, Karsakov A. A framework for a multi-agent traffic simulation using combined behavioral models. Procedia Comput Sci, 2018, 136: 443-452

[18] Sun Y, Zhang C, Dong K, Lang M. Multiagent modelling and simulation of a physical internet enabled rail-road intermodal transport system. Urban Rail Transit, 2018, 4(3): 141-154

[19] Wen J, Chen YX, Nassir N, Zhao J. Transit-oriented autonomous vehicle operation with integrated demand-supply interaction. Transp Res Part C Emerg Technol, 2018, 97: 216-234

[20] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3(1): 1-122

[21] Mahmoudi M, Zhou X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations. Transp Res Part B Methodol, 2016, 89: 19-42

[22] Tong LC, Zhou L, Liu J, Zhou X. Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing. Transp Res Part C Emerg Technol, 2017, 85: 451-475

[23] Wei Y, Avcı C, Liu J, Belezamo B, Aydın N, Li PT, Zhou X. Dynamic programming-based multi-vehicle longitudinal trajectory optimization with simplified car following models. Transp Res Part B Methodol, 2017, 106: 102-129

[24] Zhou X, Tong L, Mahmoudi M, Zhuge L, Yao Y, Zhang Y, Shang P, Liu J, Shi T. Open-source VRPLite package for vehicle routing with pickup and delivery: a path finding engine for scheduled transportation systems. Urban Rail Transit, 2018, 4(2): 68-85

[25] Zhao M, Li X, Yin J, Cui J, Yang L, An S. An integrated framework for electric vehicle rebalancing and staff relocation in one-way carsharing systems: model formulation and Lagrangian relaxation-based solution approach. Transp Res Part B Methodol, 2018, 117: 542-572

[26] Lu CC, Liu J, Qu Y, Peeta S, Rouphail NM, Zhou X. Eco-system optimal time-dependent flow assignment in a congested network. Transp Res Part B Methodol, 2016, 94: 217-239

[27] Lawson TW, Lovell DJ, Daganzo CF. Using input-output diagram to determine spatial and temporal extents of a queue upstream of a bottleneck. Transp Res Rec, 1997, 1572(1): 140-147

[28] Tong L, Zhou X, Miller HJ. Transportation network design for maximizing space–time accessibility. Transp Res Part B Methodol, 2015, 81: 555-576

[29] Ma J, Li X, Zhou F, Hao W. Designing optimal autonomous vehicle sharing and reservation systems: a linear programming approach. Transp Res Part C Emerg Technol, 2017, 84: 124-141

[30] Alonso-Mora J, Samaranayake S, Wallar A, Frazzoli E, Rus D. On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment. Proc Natl Acad Sci, 2017, 114(3): 462-467

[31] Vazifeh MM, Santi P, Resta G, Strogatz SH, Ratti C. Addressing the minimum fleet problem in on-demand urban mobility. Nature, 2018, 557(7706): 534

[32] Lu CC, Zhou X, Zhang K. Dynamic origin-destination demand flow estimation under congested traffic conditions. Transp Res Part C Emerg Technol, 2013, 34: 16-37

[33] Douglas J, Rachford HH. On the numerical solution of heat conduction problems in two and three space variables. Trans Am Math Soc, 1956, 82(2): 421-439

[34] Yao Y, Zhu X, Dong H, Wu S, Wu H, Zhou X (2018). An alternating direction method of multiplier based problem decomposition scheme for iteratively improving primal and dual solution quality in vehicle routing problem. Working paper

Funding

Collaborative Research: Improving Spatial Observability of Dynamic Traffic Systems through Active Mobile Sensor Networks and Crowdsourced Data(CMMI 1538105)

Real-time Management of Large Fleets of Self-Driving Vehicles Using Virtual Cyber Tracks(CMMI 1663657)