Abstract
•A practical extension of the Dial-a-Ride Problem (DARP) is studied.•Electric vehicles with battery-swap stations and a realistic energy consumption function are used.•Three enhanced Evolutionary Variable Neighborhood Search algorithms are proposed and compared against each other.•The proposed algorithms are competitive with the current state-of-the-art algorithm for the DARP in terms of solution quality in a reasonable computational time.
The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for customers with special needs and/or disabilities. The DARP with Electric Vehicles and battery swapping stations (DARP-EV) concerns scheduling a fleet of EVs to serve a set of pre-specified transport requests during a certain planning horizon. In addition, EVs can be recharged by swapping their batteries with charged ones from any battery-swap stations. We propose three enhanced Evolutionary Variable Neighborhood Search (EVO-VNS) algorithms to solve the DARP-EV. Extensive computational experiments highlight the relevance of the problem and confirm the efficiency of the proposed EVO-VNS algorithms in producing high quality solutions.