The electric dial-a-ride problem on a fixed circuit

Yves Molenbruch, Ohad Eisenhändler, Mor Kaspi, Kris Braekers

Research output: Unpublished contribution to conferenceUnpublished abstract


Innovative shared mobility services involving electric autonomous shuttles have increasingly been implemented in recent years. Due to various restrictions, these services are currently offered on fixed circuits and operate on fixed schedules. This study introduces a service variant in which the shuttles’ stopping patterns and schedules are determined in a flexible way. Specifically, in the Electric Dial-aRide 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 users can be picked up or 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 user journey time and the total number of performed laps.

The eDARP-FC is formulated as a novel lap-based MILP and is shown to belong to the class of NP-Hard problems. Efficient polynomial time algorithms are devised for two special scheduling sub-problems. These algorithms and several faster heuristics are then applied as subroutines within a Cross-Entropy metaheuristic tailored to the eDARPFC’s structure. Experiments on instances derived from a real-life system demonstrate that the flexible service allows providers to reduce operational costs and improve service quality.
Original languageEnglish
Publication statusPublished - 2021
EventEURO 2021 - 31st European Conference on Operational Research - Athens, Greece
Duration: 11 Jul 202114 Jul 2021


ConferenceEURO 2021 - 31st European Conference on Operational Research


Dive into the research topics of 'The electric dial-a-ride problem on a fixed circuit'. Together they form a unique fingerprint.

Cite this