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

Yves Molenbruch (), Kris Braekers (), Ohad Eisenhandler () and Mor Kaspi ()
Additional contact information
Yves Molenbruch: Research Foundation Flanders, 1000 Brussels, Belgium; Mobility, Logistics and Automotive Technology Research Centre, Vrije Universiteit Brussel, 1050 Brussels, Belgium
Kris Braekers: Research Group Logistics, Hasselt University, 3500 Hasselt, Belgium
Ohad Eisenhandler: Department of Industrial Engineering, Afeka College of Engineering, Tel Aviv 6998812, Israel
Mor Kaspi: Department of Industrial Engineering, Iby and Aladar Fleischman Faculty of Engineering, Tel Aviv University, Tel Aviv 6997801, Israel

Transportation Science, 2023, vol. 57, issue 3, 594-612

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.

Keywords: electric autonomous vehicles; pickup and delivery; dial-a-ride; dynamic programming (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.1208 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:3:p:594-612

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().