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
https://osnadocs.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202109025316
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 | Size | Format | |
---|---|---|---|---|
thesis_graf.pdf | Präsentationsformat | 1,01 MB | Adobe PDF | thesis_graf.pdf View/Open |
This item is licensed under a Creative Commons License