A hybrid control strategy for a dynamic scheduling problem in transit networks

Liu, Zhongshan ; Yu, Bin ; Zhang, Li ; Wang, Wensi 

International Journal of Applied Mathematics and Computer Science, Tome 32 (2022) no. 4, pp. 553-567.

Résumé

Public transportation is often disrupted by disturbances, such as the uncertain travel time caused by road congestion. Therefore, the operators need to take real-time measures to guarantee the service reliability of transit networks. In this paper, we investigate a dynamic scheduling problem in a transit network, which takes account of the impact of disturbances on bus services. The objective is to minimize the total travel time of passengers in the transit network. A two-layer control method is developed to solve the proposed problem based on a hybrid control strategy. Specifically, relying on conventional strategies (e.g., holding, stop-skipping), the hybrid control strategy makes full use of the idle standby buses at the depot. Standby buses can be dispatched to bus fleets to provide temporary or regular services. Besides, deep reinforcement learning (DRL) is adopted to solve the problem of continuous decision-making. A long short-term memory (LSTM) method is added to the DRL framework to predict the passenger demand in the future, which enables the current decision to adapt to disturbances. The numerical results indicate that the hybrid control strategy can reduce the average headway of the bus fleet and improve the reliability of bus service.

Détail

Keywords: service reliability, transit network, proactive control method, deep reinforcement learning, hybrid control strategy
Mots-clés : niezawodność usług, sieć tranzytowa, uczenie głębokie, kontrola hybrydowa

Bibliographie

[1] [1] Alesiani, F., Moreira-Matias, L. and Faizrahnemoon, M. (2018). On learning from inaccurate and incomplete traffic flow data, IEEE Transactions on Intelligent Transportation Systems 19(11): 3698–3708.

[2] [2] Argote-Cabanero, J., Daganzo, C.F. and Lynn, J.W. (2015). Dynamic control of complex transit systems, Transportation Research B: Methodological 81: 146–160.

[3] [3] Aslani, M., Mesgari, M.S. and Wiering, M. (2017). Adaptive traffic signal control with actor-critic methods in a real-world traffic network with different traffic disruption events, Transportation Research C: Emerging Technologies 85: 732–752.

[4] [4] Barnett, A. (1974). On controlling randomness in transit operations, Transportation Science 8(2): 102–116.

[5] [5] Cao, S., Shao, H. and Shao, F. (2022). Sensor location for travel time estimation based on the user equilibrium principle: Application of linear equations, International Journal of Applied Mathematics and Computer Science 32(1): 23–33, DOI: 10.34768/amcs-2022-0003.

[6] [6] Ceder, A. (1988). Designing transit short-turn trips with the elimination of imbalanced loads, in J.R. Daduna et al. (Eds), Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Vol. 308, Springer, Berlin, pp. 288–303.

[7] [7] Ceder, A. and Stern, H.I. (1981). Deficit function bus scheduling with deadheading trip insertions for fleet size reduction, Transportation Science 15(4): 338–363.

[8] [8] Cheng, Y., Huang, Y., Pang, B. and Zhang, W. (2018). ThermalNet: A deep reinforcement learning-based combustion optimization system for coal-fired boiler, Engineering Applications of Artificial Intelligence 74: 303–311.

[9] [9] Cortés, C.E., Jara-Díaz, S. and Tirachini, A. (2011). Integrating short turning and deadheading in the optimization of transit services, Transportation Research A: Policy and Practice 45(5): 419–434.

[10] [10] Daganzo, C.F. and Pilachowski, J. (2011). Reducing bunching with bus-to-bus cooperation, Transportation Research B: Methodological 45(1): 267–277.

[11] [11] Estrada, M., Mensión, J., Aymamí, J.M. and Torres, L. (2016). Bus control strategies in corridors with signalized intersections, Transportation Research C: Emerging Technologies 71: 500–520.

[12] [12] Fang, K., Fan, J. and Yu, B. (2022). A trip-based network travel risk: Definition and prediction, Annals of Operations Research, DOI: 10.1007/s10479-022-04630-6.

[13] [13] Farazi, N.P., Zou, B., Ahamed, T. and Barua, L. (2021). Deep reinforcement learning in transportation research: A review, Transportation Research Interdisciplinary Perspectives 11: 100425.

[14] [14] Fu, L. and Yang, X. (2002). Design and implementation of bus-holding control strategies with real-time information, Transportation Research Record 1791(1): 6–12.

[15] [15] Furth, P.G. (1985). Alternating deadheading in bus route operations, Transportation Science 19(1): 13–28.

[16] [16] Furth, P.G. (1986). Zonal route design for transit corridors, Transportation Science 20(1): 1–12.

[17] [17] Goeke, D. and Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research 245(1): 81–99.

[18] [18] Guan, Y., Li, S.E., Duan, J., Li, J., Ren, Y., Sun, Q. and Cheng, B. (2021). Direct and indirect reinforcement learning, International Journal of Intelligent Systems 36(8): 4439–4467.

[19] [19] Hall, R., Dessouky, M. and Lu, Q. (2001). Optimal holding times at transfer stations, Computers Industrial Engineering 40(4): 379–397.

[20] [20] Hao, J., Liu, X., Shen, X. and Feng, N. (2019). Bilevel programming model of urban public transport network under fairness constraints, Discrete Dynamics in Nature and Society 2019: 2930502.

[21] [21] Hu, H., Jia, X., He, Q., Fu, S. and Liu, K. (2020). Deep reinforcement learning based AGVs real-time scheduling with mixed rule for flexible shop floor in Industry 4.0, Computers Industrial Engineering 149: 106749.

[22] [22] Jordan, W.C. and Turnquist, M.A. (1979). Zone scheduling of bus routes to improve service reliability, Transportation science 13(3): 242–268.

[23] [23] Krizhevsky, A., Sutskever, I. and Hinton, G.E. (2017). ImageNet classification with deep convolutional neural networks, Communications of the ACM 60(6): 84–90.

[24] [24] Larrain, H., Giesen, R. and Muñoz, J.C. (2010). Choosing the right express services for bus corridor with capacity restrictions, Transportation Research Record 2197(1): 63–70.

[25] [25] Laskaris, G., Cats, O., Jenelius, E., Rinaldi, M. and Viti, F. (2019). Multiline holding based control for lines merging to a shared transit corridor, Transportmetrica B: Transport Dynamics 7(1): 1062–1095.

[26] [26] Li, L., Lv, Y. and Wang, F.-Y. (2016). Traffic signal timing via deep reinforcement learning, IEEE/CAA Journal of Automatica Sinica 3(3): 247–254.

[27] [27] Luo, S. (2020). Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning, Applied Soft Computing 91: 106208.

[28] [28] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S. and Hassabis, D. (2015). Human-level control through deep reinforcement learning, Nature 518(7540): 529–533.

[29] [29] Petit, A., Lei, C. and Ouyang, Y. (2019). Multiline bus bunching control via vehicle substitution, Transportation Research B: Methodological 126: 68–86.

[30] [30] Petit, A., Ouyang, Y. and Lei, C. (2018). Dynamic bus substitution strategy for bunching intervention, Transportation Research B: Methodological 115: 1–16.

[31] [31] Van Hasselt, H., Guez, A. and Silver, D. (2016). Deep reinforcement learning with double q-learning, Proceedings of the AAAI Conference on Artificial Intelligence, Phoenix, USA, pp. 2094–2100.

[32] [32] Van Oort, N., Boterman, J. and van Nes, R. (2012). The impact of scheduling on service reliability: Trip-time determination and holding points in long-headway services, Public Transport 4(1): 39–56.

[33] [33] Vuchic, V.R. (1973). Skip-stop operation as a method for transit speed increase, Traffic Quarterly 27(2): 307–327.

[34] [34] Wang, J. and Sun, L. (2020). Dynamic holding control to avoid bus bunching: A multi-agent deep reinforcement learning framework, Transportation Research C: Emerging Technologies 116: 102661.

[35] [35] Wang, P. and Chan, C.-Y. (2017). Formulation of deep reinforcement learning architecture toward autonomous driving for on-ramp merge, 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), Yokohama, Japan, pp. 1–6.

[36] [36] Wang, T. and Tang, Y. (2021). Comprehensive evaluation of power flow and adjustment method to restore solvability based on GCRNN and DDQN, International Journal of Electrical Power Energy Systems 133: 107160.

[37] [37] Wang, W., Chen, X., Musial, J. and Blazewicz, J. (2020). Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion, International Journal of Applied Mathematics and Computer Science 30(3): 573–584, DOI: 10.34768/amcs-2020-0042.

[38] [38] Xuan, Y., Argote, J. and Daganzo, C.F. (2011). Dynamic bus holding strategies for schedule reliability: Optimal linear control and performance analysis, Transportation Research B: Methodological 45(10): 1831–1845.

[39] [39] Zhu, Y., Mao, B., Bai, Y. and Chen, S. (2017). A bi-level model for single-line rail timetable design with consideration of demand and capacity, Transportation Research C: Emerging Technologies 85: 211–233.