TY - JOUR
T1 - An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem
AU - Wen, M.
AU - Linde, E.
AU - Ropke, S.
AU - Mirchandani, P.
AU - Larsen, A.
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2016/12/1
Y1 - 2016/12/1
N2 - This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.
AB - This paper addresses the Electric Vehicle Scheduling Problem (E-VSP), in which a set of timetabled bus trips, each starting from and ending at specific locations and at specific times, should be carried out by a set of electric buses or vehicles based at a number of depots with limited driving ranges. The electric vehicles are allowed to be recharged fully or partially at any of the given recharging stations. The objective is to firstly minimize the number of vehicles needed to cover all the timetabled trips, and secondly to minimize the total traveling distance, which is equivalent to minimizing the total deadheading distance. A mixed integer programming formulation as well as an Adaptive Large Neighborhood Search (ALNS) heuristic for the E-VSP are presented. ALNS is tested on newly generated E-VSP benchmark instances. Result shows that the proposed heuristic can provide good solutions to large E-VSP instances and optimal or near-optimal solutions to small E-VSP instances.
KW - Electric vehicles
KW - Large neighborhood search
KW - Partial charging
KW - Vehicle scheduling
UR - http://www.scopus.com/inward/record.url?scp=84977665966&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2016.06.013
DO - 10.1016/j.cor.2016.06.013
M3 - Article
AN - SCOPUS:84977665966
SN - 0305-0548
VL - 76
SP - 73
EP - 83
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -