Efficient heuristics for large-scale vehicle routing problems
Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
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
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://osnadocs.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öße | Format | |
---|---|---|---|---|
thesis_graf.pdf | Präsentationsformat | 1,01 MB | Adobe PDF | thesis_graf.pdf Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons