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.

Geroliminis, Nikolaos
Kaspi, Mor
Lausanne, EPFL

Note: The status of this file is: Anyone

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

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)