TY - JOUR
T1 - Solution Approaches for Integrated Vehicle and Crew Scheduling with Electric Buses
AU - Perumal, SSG
AU - Dollevoet, Twan
AU - Huisman, Dennis
AU - Lusby, RM
AU - Larsen, J
AU - Riis, M
N1 - Funding Information:
The authors would like to thank Innovation Fund Denmark for financially supporting this work under Grant No. 5189-00128B. The authors are grateful to Trapeze Group Europe A/S for providing the instances from public transport companies for this study. The authors would also like to thank the two anonymous referees for their valuable suggestions.
Publisher Copyright:
© 2021 Elsevier Ltd
PY - 2021/8
Y1 - 2021/8
N2 - The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less flexible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, scheduling electric vehicles adds further operational difficulties. Additionally, various labor regulations challenge public transport companies to find a cost-efficient crew schedule. Vehicle and crew scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and crew scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and crew scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17–4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120–250 km) of electric vehicles.
AB - The use of electric buses is expected to rise due to its environmental benefits. However, electric vehicles are less flexible than conventional diesel buses due to their limited driving range and longer recharging times. Therefore, scheduling electric vehicles adds further operational difficulties. Additionally, various labor regulations challenge public transport companies to find a cost-efficient crew schedule. Vehicle and crew scheduling problems essentially define the cost of operations. In practice, these two problems are often solved sequentially. In this paper, we introduce the integrated electric vehicle and crew scheduling problem (E-VCSP). Given a set of timetabled trips and recharging stations, the E-VCSP is concerned with finding vehicle and crew schedules that cover the timetabled trips and satisfy operational constraints, such as limited driving range of electric vehicles and labor regulations for the crew while minimizing total operational cost. An adaptive large neighborhood search that utilizes branch-and-price heuristics is proposed to tackle the E-VCSP. The proposed method is tested on real-life instances from public transport companies in Denmark and Sweden that contain up to 1109 timetabled trips. The heuristic approach provides evidence of improving efficiency of transport systems when the electric vehicle and crew scheduling aspects are considered simultaneously. By comparing to the traditional sequential approach, the heuristic finds improvements in the range of 1.17–4.37% on average. A sensitivity analysis of the electric bus technology is carried out to indicate its implications for the crew schedule and the total operational cost. The analysis shows that the operational cost decreases with increasing driving range (120–250 km) of electric vehicles.
UR - http://www.scopus.com/inward/record.url?scp=85104427994&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2021.105268
DO - 10.1016/j.cor.2021.105268
M3 - Article
VL - 132
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
M1 - 105268
ER -