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.
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 language | English |
---|---|
Publication status | Published - 2021 |
Event | EURO 2021 - 31st European Conference on Operational Research - Athens, Greece Duration: 11 Jul 2021 → 14 Jul 2021 |
Conference
Conference | EURO 2021 - 31st European Conference on Operational Research |
---|---|
Country/Territory | Greece |
City | Athens |
Period | 11/07/21 → 14/07/21 |