A greedy randomized destroy and repair heuristic for the dial-a-ride problem with transfers
S.J.M. Janssens de Bisthoven (TU Delft - Electrical Engineering, Mathematics and Computer Science)
J. Theresia van Essen – Mentor (TU Delft - Discrete Mathematics and Optimization)
Jacopo Pierotti – Mentor (TU Delft - Discrete Mathematics and Optimization)
Karen Aardal – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
C. Kraaikamp – Graduation committee member (TU Delft - Applied Probability)
More Info
expand_more
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.
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.