Efficient heuristics for large-scale vehicle routing problems

Please use this identifier to cite or link to this item:
https://osnadocs.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202109025316
Open Access logo originally created by the Public Library of Science (PLoS)
Title: Efficient heuristics for large-scale vehicle routing problems
Authors: Graf, Benjamin
ORCID of the author: https://orcid.org/0000-0002-8382-4819
Thesis advisor: Prof. Dr. Sigrid Knust
Thesis referee: Prof. Dr. Stefan Irnich
Abstract: In this thesis we consider three challenging vehicle routing problems representing specific aspects of complex real-world problems: (i) the vehicle routing problem with unit demands, (ii) the preemptive stacker crane problem and (iii) a multi-period vehicle and technician routing problem. For the vehicle routing problem with units demands we continue research on the exponential multi-insertion neighborhood, investigate its properties and propose heuristic solution methods utilizing the neighborhood. For the preemptive stacker crane problem we study structural properties and provide bounds on the benefits of preemption and the benefits of so-called explicit drop nodes that are used exclusively to facilitate preemption. We propose construction heuristics that improve on the state-of-the-art in computational time and solution quality. The multi-period vehicle and technician routing problem is the subject of the VeRoLog Solver Challenge 2019. We develop a solution method that adapts to the limited computational budget and the given instance parameters. In summary, this thesis contributes to the structural analysis of the considered problems and proposes efficient heuristic solution methods that are effective even on large-scale instances and under tight restrictions of the computational budget. The methods combine global and local search approaches and take the available computational budget into account to realize an adaptive best-effort allocation of the resources.
URL: https://osnadocs.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202109025316
Subject Keywords: vehicle routing; vehicle routing problem with unit demands; preemptive stacker crane problem; verolog solver challenge 2019; heuristics; combinatorial optimization; operations research
Issue Date: 2-Sep-2021
License name: Attribution-NonCommercial-NoDerivs 3.0 Germany
License url: http://creativecommons.org/licenses/by-nc-nd/3.0/de/
Type of publication: Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:FB06 - E-Dissertationen

Files in This Item:
File Description SizeFormat 
thesis_graf.pdfPräsentationsformat1,01 MBAdobe PDF
thesis_graf.pdf
Thumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons