Electric buses (e-buses) are increasingly adopted in the transit systems for their benefits of reduced roadside pollution and better onboard experience. E-bus scheduling is a critical problem in the operation planning stage of transit management to ensure efficient and reliable transit service. In Chinese mega cities, the e-bus networks are operated with many bus routes characterized by high service frequency and long operation time, making the e-bus scheduling a large-scale problem. Besides, the transit agency requires the vehicle-depot constraint to limit the e-bus reposition since it is not cost-efficient. An efficient method to generate optimized schedules that meet the above requirements is desired by the transit agencies. In this paper, we address a large-scale multi-depot electric bus scheduling problem considering the vehicle-depot constraint and partial recharging policy. A mixed integer programming model and an efficient branch-and-price (BP) algorithm are developed to solve the problem. In the BP algorithm, we devise a heuristic method to generate good initial solutions and adopted heuristic decisions in the label setting algorithm to solve the pricing problem. In this way, the efficiency of the BP algorithm is achieved and the large-sized problem instances can be solved. We conduct extensive numerical experiments based on the fixed-route and multi-route operation cases in Shenzhen. The results show that the BP algorithm can generate provable high-quality solutions. Sensitivity analysis indicates that increasing battery capacity and charging rate can reduce the operational cost. The optimal charging schedules can also provide guide in determining the capacity of the charging facilities.
A Branch-and-Price Algorithm for Large-Scale Multidepot Electric Bus Scheduling
IEEE Transactions on Intelligent Transportation Systems ; 24 , 12 ; 15355-15368
2023-12-01
3355424 byte
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
A Branch-and-Price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes
Online Contents | 2014
|A Branch-and-Cut Algorithm for the Multidepot Rural Postman Problem
British Library Online Contents | 2018
|A Framing Link Based Tabu Search Algorithm for Large-Scale Multidepot Vehicle Routing Problems
BASE | 2014
|Multidepot Vehicle Routing with Uncertain Demands: Chance Constrained Approach
Transportation Research Record | 2004
|Multidepot UAV Routing Problem with Weapon Configuration and Time Window
DOAJ | 2018
|