A Hybrid Control Strategy for a Dynamic Scheduling Problem in Transit Networks

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

doi:10.34768/amcs-2022-0039

Abstract

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.

References

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.10.1109/TITS.2018.2857622
Search in Google Scholar Back to article
Argote-Cabanero, J., Daganzo, C.F. and Lynn, J.W. (2015). Dynamic control of complex transit systems, Transportation Research B: Methodological 81: 146–160.10.1016/j.trb.2015.09.003
Search in Google Scholar Back to article
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.10.1016/j.trc.2017.09.020
Search in Google Scholar Back to article
Barnett, A. (1974). On controlling randomness in transit operations, Transportation Science 8(2): 102–116.10.1287/trsc.8.2.102
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.10.1007/978-3-642-85966-3_25
Search in Google Scholar Back to article
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.10.1287/trsc.15.4.338
Search in Google Scholar Back to article
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.10.1016/j.engappai.2018.07.003
Search in Google Scholar Back to article
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.1016/j.tra.2011.02.002
Search in Google Scholar Back to article
Daganzo, C.F. and Pilachowski, J. (2011). Reducing bunching with bus-to-bus cooperation, Transportation Research B: Methodological 45(1): 267–277.10.1016/j.trb.2010.06.005
Search in Google Scholar Back to article
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.10.1016/j.trc.2016.08.013
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.10.1016/j.trip.2021.100425
Search in Google Scholar Back to article
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.10.3141/1791-02
Search in Google Scholar Back to article
Furth, P.G. (1985). Alternating deadheading in bus route operations, Transportation Science 19(1): 13–28.10.1287/trsc.19.1.13
Search in Google Scholar Back to article
Furth, P.G. (1986). Zonal route design for transit corridors, Transportation Science 20(1): 1–12.10.1287/trsc.20.1.1
Search in Google Scholar Back to article
Goeke, D. and Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research 245(1): 81–99.10.1016/j.ejor.2015.01.049
Search in Google Scholar Back to article
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.10.1002/int.22466
Search in Google Scholar Back to article
Hall, R., Dessouky, M. and Lu, Q. (2001). Optimal holding times at transfer stations, Computers & Industrial Engineering 40(4): 379–397.10.1016/S0360-8352(01)00039-0
Search in Google Scholar Back to article
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.10.1155/2019/2930502
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Jordan, W.C. and Turnquist, M.A. (1979). Zone scheduling of bus routes to improve service reliability, Transportation science 13(3): 242–268.10.1287/trsc.13.3.242
Search in Google Scholar Back to article
Krizhevsky, A., Sutskever, I. and Hinton, G.E. (2017). ImageNet classification with deep convolutional neural networks, Communications of the ACM 60(6): 84–90.10.1145/3065386
Search in Google Scholar Back to article
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.10.3141/2197-08
Search in Google Scholar Back to article
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.10.1080/21680566.2018.1548312
Search in Google Scholar Back to article
Li, L., Lv, Y. and Wang, F.-Y. (2016). Traffic signal timing via deep reinforcement learning, IEEE/CAA Journal of Auto-matica Sinica 3(3): 247–254.10.1109/JAS.2016.7508798
Search in Google Scholar Back to article
Luo, S. (2020). Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning, Applied Soft Computing 91: 106208.10.1016/j.asoc.2020.106208
Search in Google Scholar Back to article
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.10.1038/nature1423625719670
Search in Google Scholar Back to article
Petit, A., Lei, C. and Ouyang, Y. (2019). Multiline bus bunching control via vehicle substitution, Transportation Research B: Methodological 126: 68–86.10.1016/j.trb.2019.05.009
Search in Google Scholar Back to article
Petit, A., Ouyang, Y. and Lei, C. (2018). Dynamic bus substitution strategy for bunching intervention, Transportation Research B: Methodological 115: 1–16.10.1016/j.trb.2018.06.001
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1007/s12469-012-0054-4
Search in Google Scholar Back to article
Vuchic, V.R. (1973). Skip-stop operation as a method for transit speed increase, Traffic Quarterly 27(2): 307–327.
Search in Google Scholar Back to article
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.10.1016/j.trc.2020.102661
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1016/j.ijepes.2021.107160
Search in Google Scholar Back to article
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.
Open DOI Search in Google Scholar Back to article
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.10.1016/j.trb.2011.07.009
Search in Google Scholar Back to article
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.10.1016/j.trc.2017.09.002
Search in Google Scholar Back to article

A Hybrid Control Strategy for a Dynamic Scheduling Problem in Transit Networks

Abstract

Paradigm

My account