The Electric Dial-a-Ride Problem on a Fixed Circuit

Abstract

Shared mobility services involving electric autonomous shuttles have increasingly been implemented in recent years. Because of various restrictions, these services are currently offered on fixed circuits and operated with fixed schedules. This study introduces a service variant with flexible stopping patterns and schedules. Specifically, in the electric dial-a-ride problem on a fixed circuit (eDARP-FC), a fleet of capacitated electric shuttles operates on a given circuit consisting of a recharging depot and a sequence of stations where passengers can be picked up and dropped off. The shuttles may perform multiple laps, between which they may need to recharge. The goal of the problem is to determine the vehicles' stopping sequences and schedules, including recharging plans, so as to minimize a weighted sum of the total passenger excess time and the total number of laps. The eDARP-FC is formulated as a nonstandard lap-based mixed integer linear programming and is shown to be NP-Hard. Efficient polynomial time algorithms are devised for two special scheduling subproblems. These algorithms and several heuristics are then applied as subroutines within a large neighborhood search metaheuristic. Experiments on instances derived from a real-life system demonstrate that the flexible service results in a 32%-75% decrease in the excess time at the same operational costs.