PDF(3256 KB)
A Distributionally Robust Optimization Method for Passenger Flow Control Strategy and Train Scheduling on an Urban Rail Transit Line
Yahan Lu, Lixing Yang, Kai Yang, Ziyou Gao, Housheng Zhou, Fanting Meng, Jianguo Qi
Engineering ›› 2022, Vol. 12 ›› Issue (5) : 202-220.
PDF(3256 KB)
PDF(3256 KB)
A Distributionally Robust Optimization Method for Passenger Flow Control Strategy and Train Scheduling on an Urban Rail Transit Line
Regular coronavirus disease 2019 (COVID-19) epidemic prevention and control have raised new requirements that necessitate operation-strategy innovation in urban rail transit. To alleviate increasingly serious congestion and further reduce the risk of cross-infection, a novel two-stage distributionally robust optimization (DRO) model is explicitly constructed, in which the probability distribution of stochastic scenarios is only partially known in advance. In the proposed model, the mean-conditional value-atrisk (mean-CVaR) criterion is employed to obtain a tradeoff between the expected number of waiting passengers and the risk of congestion on an urban rail transit line. The relationship between the proposed distributionally robust model and the traditional two-stage stochastic programming (SP) model is also depicted. Furthermore, to overcome the obstacle of model solvability resulting from imprecise probability distributions, a discrepancy-based ambiguity set is used to transform the robust counterpart into its computationally tractable form. A hybrid algorithm that combines a local search algorithm with a mixedinteger linear programming (MILP) solver is developed to improve the computational efficiency of largescale instances. Finally, a series of numerical examples with real-world operation data are executed to validate the proposed approaches.
Passenger flow control / Train scheduling / Distributionally robust optimization / Stochastic and dynamic passenger demand / Ambiguity set
| [1] |
Yin J, D’Ariano A, Wang Y, Yang L, Tang T. Timetable coordination in a rail transit network with time-dependent passenger demand. Eur J Oper Res 2021;295(1):183–202.
|
| [2] |
Barrena E, Canca D, Coelho LC, Laporte G. Exact formulations and algorithm for the train timetabling problem with dynamic demand. Comput Oper Res 2014;44:66–74.
|
| [3] |
Mesa JA, Ortega FA, Pozo MA. Locating optimal timetables and vehicle schedules in a transit line. Ann Oper Res 2014;222(1):439–55.
|
| [4] |
Niu HM, Zhou XS. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions. Transp Res Part C Emerg Technol 2013;36(16):212–30.
|
| [5] |
Shi J, Yang L, Yang J, Gao Z. Service-oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: an integer linear optimization approach. Transport Res B-Meth 2018;110:26–59.
|
| [6] |
Xu XY, Liu J, Li HY, Jiang M. Capacity-oriented passenger flow control under uncertain demand: algorithm development and real-world case study. Transport Res E-Log 2016;87:130–48.
|
| [7] |
Jiang M, Li HY, Xu XY, Xu S, Miao JR. Metro passenger flow control with stationto-station cooperation based on stop-skipping and boarding limiting. J Cent South Univ 2017;24(1):236–44.
|
| [8] |
Xu XY, Li HY, Liu J, Ran B, Qin LQ. Passenger flow control with multi-station coordination in subway networks: algorithm development and real-world case study. Transportmetrica B 2018;7(1):446–72.
|
| [9] |
Shi J, Yang L, Yang J, Zhou F, Gao Z. Cooperative passenger flow control in an oversaturated metro network with operational risk thresholds. Transp Res Part C Emerg Technol 2019;107:301–36.
|
| [10] |
Yang S, Yang K, Yang L, Gao Z. MILP formulations and a TS algorithm for reliable last train timetabling with uncertain transfer flows. J Oper Res Soc 2018;69(8):1318–34.
|
| [11] |
Meng FT, Yang LX, Shi JG, Jiang ZZ, Gao ZY, et al. Collaborative passenger flow control for oversaturated metro lines: a stochastic optimization method. Transportmetrica A. In press.
|
| [12] |
Ben-Tal A, Ghaoui LE, Nemirovski A. Robust optimization. Princeton: Princeton University Press; 2009.
|
| [13] |
Rockafellar RT, Uryasev S. Optimization of conditional value-at-risk. J Risk 1999;2(3):21–42.
|
| [14] |
Wang L, Yan X, Wang Y. Modeling and optimization of collaborative passenger control in urban rail stations under mass passenger flow. Math Probl Eng 2015;2015:1–8.
|
| [15] |
Yuan F, Sun H, Kang L, Wu J. Passenger flow control strategies for urban rail transit networks. Appl Math Model 2020;82:168–88.
|
| [16] |
Meng F, Yang L, Wei Y, Li S, Gao Z, Shi J. Collaborative passenger flow control on an oversaturated metro line: a path choice approach. Transportmetrica B 2020;8(1):376–404.
|
| [17] |
Hoogendoorn SP, Daamen W. Design assessment of Lisbon transfer stations using microscopic pedestrian simulation. Computers in Railways 2004;74:135–47.
|
| [18] |
Zhang JX, Han BM, Li DW. Application of VISSIM in pedestrian simulation of MTR stations. Comput Simul 2007;6:239–42. Chinese.
|
| [19] |
Seriani S, Fernandez R. Pedestrian traffic management of boarding and alighting in metro stations. Transp Res Part C Emerg Technol 2015;53:76–92.
|
| [20] |
Fei S, Liu ZL. Simulation analysis of metro congestion points and optimization method. Urban Mass Transit 2018;21(7):100–5.
|
| [21] |
Jiang ZB, Gu JJ, Fan W, Liu W, Zhu BQ. Q-learning approach to coordinated optimization of passenger inflow control with train skip-stopping on an urban rail transit line. Comput Ind Eng 2019;127:1131–42.
|
| [22] |
Niu H, Zhou X, Gao R. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: nonlinear integer programming models with linear constraints. Transport Res B-Meth 2015;76:117–35.
|
| [23] |
Li DW, Zhang TY, Dong XL, Yin Y, Cao J. Trade-off between efficiency and fairness in timetabling on a single urban rail transit line under time-dependent demand condition. Transportmetrica B 2019;7(1):1–29.
|
| [24] |
Yin JT, D’Ariano A, Wang YH, Xun J, Su S, Tang T. Mixed-integer linear programming models for coordinated train timetabling with dynamic demand. In: Bogenberger K, Tang T, Knoll A, Dietmayer K, Hu J, Zöllner JM, editors. IEEE Intelligent Transportation Systems Conference; 2019 Oct 27–30; Auckland, New Zealand. New York City: Curran Associates; 2019. p. 863–8.
|
| [25] |
Yang LX, Di Z, Dessouky MM, Gao ZY, Shi JG. Collaborative optimization of lasttrain timetable with passenger accessibility: a space-time network design based approach. Transp Res Part C Emerg Technol 2020;114:572–97.
|
| [26] |
Liu P, Schmidt M, Kong Q, Wagenaar JC, Yang L, Gao Z, et al. A robust and energy-efficient train timetable for the subway system. Transp Res Part C Emerg Technol 2020;121:102822.
|
| [27] |
Huang Y, Mannino C, Yang L, Tang T. Coupling time-indexed and big-M formulations for real-time train scheduling during metro service disruptions. Transport Res B-Meth 2020;133:38–61.
|
| [28] |
Tian XP, Niu HM. Optimization of demand-oriented train timetables under overtaking operations: a surrogate-dual-variable column generation for eliminating indivibility. Transport Res B-Meth 2020;142:143–73.
|
| [29] |
Mo P, D’Ariano A, Yang L, Veelenturf LP, Gao Z. An exact method for the integrated optimization of subway lines operation strategies with asymmetric passenger demand and operating costs. Transport Res B-Meth 2021;149:283–321.
|
| [30] |
Qi J, Cacchiani V, Yang L, Zhang C, Di Z. An integer linear programming model for integrated train stop planning and timetabling with time-dependent passenger demand. Comput Oper Res 2021;136:105484.
|
| [31] |
Xu XY. Calculation of station service capacity and adaptability in urban rail transit [dissertation]. Beijing: Beijing Jiaotong University; 2015. Chinese.
|
| [32] |
Gong C, Mao B, Wang M, Zhang T. Equity-oriented train timetabling with collaborative passenger flow control: a spatial rebalance of service on an oversaturated urban rail transit line. J Adv Transp 2020;2020. 8867404.
|
| [33] |
Yang W, Su Q, Huang SH, Wang Q, Zhu Y, Zhou M. Simulation modeling and optimization for ambulance allocation considering spatiotemporal stochastic demand. J Manage Sci Eng 2019;4(4):252–65.
|
| [34] |
Zhang Z, Liu Y, Tong Q, Guo S, Li D. Evacuation based on spatio–temporal resilience with variable traffic demand. J Manage Sci Eng 2021;6(1):86–98.
|
| [35] |
Gong C, Shi J, Wang Y, Zhou H, Yang L, Chen D, et al. Train timetabling with dynamic and random passenger demand: a stochastic optimization method. Transp Res Part C Emerg Technol 2021;123:102963.
|
| [36] |
Errico F, Desaulniers G, Gendreau M, Rei W, Rousseau LM. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. Eur J Oper Res 2016;249(1):55–66.
|
| [37] |
Qi J, Cacchiani V, Yang L. Robust train timetabling and stop planning with uncertain passenger demand. Electron Notes Discret Math 2018;69:213–20.
|
| [38] |
Cacchiani V, Qi J, Yang L. Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty. Transport Res B-Meth 2020;136:1–29.
|
| [39] |
Delage E, Ye Y. Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper Res 2010;58 (3):595–612.
|
| [40] |
Esfahani PM, Kuhn D. Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Math Program 2018;171(1):115–66.
|
| [41] |
Shang C, You F. Distributionally robust optimization for planning and scheduling under uncertainty. Comput Chem Eng 2018;110:53–68.
|
| [42] |
Van BP, Kuhn D, Goulart PJ, Morari M. Distributionally robust control of constrained stochastic systems. IEEE Trans Automat Contr 2015;61 (2):430–42.
|
| [43] |
Shang XT, Yang K, Jia B, Gao Z. Distributionally robust cluster-based hierarchical hub location problem for integration of urban and rural public transport system. Comput Ind Eng 2021;155:107181.
|
| [44] |
Wang WQ, Yang K, Yang LX, Gao Z. Tractable approximations for the distributionally robust conditional vertex p-center problem: application to the location of high-speed railway emergency rescue stations. J Oper Res Soc 2020.
|
| [45] |
Yang K, Lu Y, Yang L, Gao Z. Distributionally robust last-train coordination planning problem with dwell time adjustment strategy. Appl Math Model 2021;91:1154–74.
|
| [46] |
Wang S, Chen Z, Liu T. Distributionally robust hub location. Transport Sci 2020;54(5):1189–210.
|
| [47] |
Zhang Y, Zhang Z, Lim A, Sim M. Robust data-driven vehicle routing with time windows. Oper Res 2021;69(2):469–85.
|
| [48] |
Domencich TA, McFadden D. Urban travel demand: a behavioral analysis. Oxford: North-Holland Publishing Company Limited; 1975.
|
| [49] |
Ma L, Liu Y, Liu Y. Distributionally robust design for bicycle-sharing closedloop supply chain network under risk-averse criterion. J Clean Prod 2020;246:118967.
|
| [50] |
Mevissen M, Ragnoli E, Yu JY. Data-driven distributionally robust polynomial optimization. In: Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, editors. Proceedings of the 26th International Conference on Neural Information Processing Systems; 2013 Dec 5–10; Lake Tahoe, USA. New York City: Curran Associates; 2013. p. 37–45.
|
/
| 〈 |
|
〉 |
AI Summary
