The electric autonomous dial-a-ride problem

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a-Ride Problem (e-ADARP), and includes battery management and autonomous aspects along with classic dial-a-ride features. The e-ADARP operational frameworks undertaken in this thesis consider static problems, in which demand is assumed to be known in advance, and dynamic problems, in which demand is revealed on-line. The static e-ADARP is formulated as a Mixed-Integer Linear Program and solved through a Branch-and-Cut framework, enhanced by problem-specific valid inequalities and lifted inequalities from the literature, as well as purpose-based separation heuristics. Computational experiments are performed on adapted benchmark instances from the DARP literature and on instances based on real data. Results show that the problem-specific valid inequalities are among the most effective and especially useful when battery management aspects are relevant. %Instances with up to 5 vehicles and 40 requests are solved to optimality. The dynamic e-ADARP is developed through a simulation-based optimization approach, which incorporates a new extension to the family of large neighborhood search (LNS) metaheuristics. The extension considers a machine learning component which exploits historical information to select destroy-repair operators from a pool of competing algorithms, all along the search. Computational experiments are performed on dynamic e-ADARP instances based on real data. Results show that combining machine learning within LNS-based metaheuristics produces a competitive alternative to benchmark methodologies from the literature and in the context of on-line operations. Finally, the e-ADARP is a hardly-constrained problem which is challenged by the addition of autonomous and battery management aspects within the vehicle scheduling algorithm. As such, this thesis proposes a novel scheduling procedure for the e-ADARP, which aims at finding minimal excess-time and battery-feasible schedules for fixed routes. Results on instances based on real data show that the algorithm is able to efficiently return optimal scheduling solutions.


Advisor(s):
Geroliminis, Nikolaos
Kaspi, Mor
Year:
2020
Publisher:
Lausanne, EPFL
Keywords:
Laboratories:
LUTS


Note: The status of this file is: Anyone


 Record created 2020-09-11, last modified 2020-10-29

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)