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

Master thesis (2020)

Authors

S.J.M. Janssens de Bisthoven Electrical Engineering, Mathematics and Computer Science

Contributors

J.T. van Essen Discrete Mathematics and Optimization - EEMCS (mentor)
J. Pierotti Discrete Mathematics and Optimization - EEMCS (mentor)
K.I. Aardal Discrete Mathematics and Optimization - EEMCS (graduation committee member)
C. Kraaikamp Applied Probability - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2020 Sébastien Janssens de Bisthoven
More Info
expand_more

Published Date

21-01-2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.