A mixed-integer programming-based Q-learning approach for electric bus scheduling with multiple termini and service routes

Authors

Yimo Yan
Haomin Wen
Yang Deng
Andy H.F. Chow
Qihao Wu
Yong-Hong Kuo

Document Type

Journal Article

Publication Date

2024

Subject Area

place - asia, place - urban, mode - bus, infrastructure - vehicle, infrastructure - maintainance, operations - scheduling, planning - methods

Keywords

Electric buses (EBs), battery charging, scheduling

Abstract

Electric buses (EBs) are considered a more environmentally friendly mode of public transit. In addition to other practical challenges, including high infrastructure costs and short driving ranges, the operations of EBs are more demanding due to the necessary battery charging activities. Consequently, more sophisticated optimisation models and algorithms are required for effective operations. This paper presents an EB scheduling problem with multiple termini and service routes. Various realistic but complicated factors, such as shared facilities at multiple termini, the flexibility of plugging and unplugging chargers before an EB is fully charged, stochastic travel times, and EB breakdowns, are considered. We propose an integrated learning and mixed-integer linear programming (MILP) framework to overcome the computational difficulties when solving the problem. This framework leverages the strengths of reinforcement learning and MILP for fast computations due to its capability of learning from outcomes of state–action pairs and computational effectiveness guaranteed by the constraints governing the solution feasibility. Q-Learning and Twin Delayed Deep Deterministic Policy Gradient are adopted as our training methods. We conduct numerical experiments on artificial instances and realistic instances of a bus network in Hong Kong to assess the performance of our proposed approach. The results show that our proposed framework outperforms the benchmark optimisation approach, in terms of penalty on missed service trips, average headway, and variance of headway. The benefits of our proposed framework are more significant under a highly stochastic environment.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part C Home Page:

http://www.sciencedirect.com/science/journal/0968090X

Recommended Citation

Yan, Y., Wen, H., Deng, Y., Chow, A. H., Wu, Q., & Kuo, Y. H. (2024). A mixed-integer programming-based Q-learning approach for electric bus scheduling with multiple termini and service routes. Transportation Research Part C: Emerging Technologies, 162, 104570.