Efficient heuristics for large-scale vehicle routing problems

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
Open Access logo originally created by the Public Library of Science (PLoS)
Titel: Efficient heuristics for large-scale vehicle routing problems
Autor(en): Graf, Benjamin
ORCID des Autors: https://orcid.org/0000-0002-8382-4819
Erstgutachter: Prof. Dr. Sigrid Knust
Zweitgutachter: Prof. Dr. Stefan Irnich
Zusammenfassung: 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://repositorium.ub.uni-osnabrueck.de/handle/urn:nbn:de:gbv:700-202109025316
Schlagworte: vehicle routing; vehicle routing problem with unit demands; preemptive stacker crane problem; verolog solver challenge 2019; heuristics; combinatorial optimization; operations research
Erscheinungsdatum: 2-Sep-2021
Lizenzbezeichnung: Attribution-NonCommercial-NoDerivs 3.0 Germany
URL der Lizenz: http://creativecommons.org/licenses/by-nc-nd/3.0/de/
Publikationstyp: Dissertation oder Habilitation [doctoralThesis]
Enthalten in den Sammlungen:FB06 - E-Dissertationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_graf.pdfPräsentationsformat1,01 MBAdobe PDF

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons