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.