A greedy randomized destroy and repair heuristic for the dial-a-ride problem with transfers

A greedy randomized destroy and repair heuristic for the dial-a-ride problem with transfers

Janssens de Bisthoven, Sébastien (TU Delft Electrical Engineering, Mathematics and Computer Science)

van Essen, Theresia (mentor)
Pierotti, Jacopo (mentor)
Aardal, Karen (graduation committee)
Kraaikamp, Cornelis (graduation committee)

Delft University of Technology

Applied Mathematics

2020-01-21

Automated vehicles have the potential to create a future in which most cars are shared instead of being individually owned and used. The advantages of vehicle sharing are expected to be multiple: reduced traffic, freed-up parking space, safer trips and a lower environmental impact of traveling. The dial-a-ride problem with transfers (DARP-T) consists in finding a set of minimum cost routes that satisfies a set of transportation requests. Requests may share a vehicle and may be transferred from one vehicle to another at any node during their journey. In this thesis, we describe a heuristic solving moderate to large instances of the static heterogeneous DARP-T in which the requests have demanding time constraints. The heuristic builds a solution in a constructive greedy randomized procedure and subsequently improves it with a destroy and repair procedure. The heuristic is tested on instances we randomly generated containing up to 1000 requests traveling between any two of the 100 most populated cities in the Netherlands inside a four-hour timescale. These instances are also solved without transfers to determine the benefits transfers can bring and the user inconvenience they may cause. We also investigate the influence of the demand on the objective function value, look into the influence of the fleet size on the fleet usage, and present some visualizations of the solutions found.

DARP-T
Destroy and Repair
Pick-up and Delivery Problem
Transfers
Time Windows

http://resolver.tudelft.nl/uuid:88b87961-444e-46c3-91c0-940cd59d3626

Student theses

master thesis

© 2020 Sébastien Janssens de Bisthoven