On the solution of classical and synchronized routing problems

dc.contributor.authorSchmidt, Jeanette
dc.date.accessioned2024-11-04T08:47:17Z
dc.date.available2024-11-04T08:47:17Z
dc.date.issued2024
dc.description.abstractThe focus of this thesis is to contribute to the development of exact and heuristic solution methods for classical and synchronized routing problems. In particular, we present a problem-tailored iterated local search (ILS) algorithm to solve the Generalized Traveling Salesman Problem (GTSP) and derive full-fledged branch-price-and-cut (BPC) algorithms to solve three routing problems with synchronization constraints, namely the Last-Mile Delivery Problem with Scheduled Lines, the Vehicle Routing Problem with Drones, and the Vehicle Routing Problem with Drones and Time Windows. In all approaches, we employ the individual, problem-specific structure to model effective solution methods. For the GTSP, we develop three new GTSP neighborhoods and combine them with existing neighborhoods from the literature within the local search part of the ILS. For all routing problems with synchronization constraints, the focus is on designing effective labeling algorithms to solve the corresponding pricing problems and on strengthening the linear relaxation of the master problem with valid inequalities. In extensive computational analyses, we consider different objective functions, provide managerial insights, and prove the usefulness of the proposed methods.en_GB
dc.description.abstractDie vorliegende Dissertation leistet einen Beitrag zur Entwicklung von exakten und heuristischen Lösungsverfahren für verschiedene Tourenplanungsprobleme. Insbesondere werden ein maßgeschneideter Iterated-Local-Search-Algorithmus (ILS) zur Lösung des Generalized Traveling Salesman Problem (GTSP) vorgestellt und vollwertige Branch-Price-and-Cut-Algorithmen (BPC) zur Lösung der folgenden Tourenplanungsprobleme mit Synchronisationsbedingungen entwickelt: das Last-Mile Delivery Problem with Scheduled Lines, das Vehicle Routing Problem with Drones und das Vehicle Routing Problem with Drones and Time Windows. Für alle genannten Probleme wird die individuelle, problemspezifische Struktur ausgenutzt, um leistungsfähige Algorithmen zu entwickeln. Für das GTSP werden drei neue GTSP-Nachbarschaften vorgestellt und mit bestehenden Nachbarschaften aus der Literatur innerhalb der lokalen Suche der ILS kombiniert. Für alle weiteren Probleme liegt der Schwerpunkt auf der Entwicklung effektiver Labeling-Algorithmen zur Lösung der problemspezifischen Pricing-Probleme sowie auf der Stärkung der linearen Relaxation des Master-Problems mittels gültiger Ungleichungen. In umfangreichen Rechenstudien werden verschiedene Zielfunktionen betrachtet, betriebswirtschaftliche Erkenntnisse gewonnen und die Wirksamkeit der vorgestellten Algorithmen belegt.de_DE
dc.identifier.doihttp://doi.org/10.25358/openscience-10796
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/10815
dc.identifier.urnurn:nbn:de:hebis:77-openscience-119b5588-ef6a-4a8f-982e-d6024cb332a16
dc.language.isoengde
dc.rightsInC-1.0*
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/*
dc.subject.ddc330 Wirtschaftde_DE
dc.subject.ddc330 Economicsen_GB
dc.titleOn the solution of classical and synchronized routing problemsen_GB
dc.typeDissertationde
jgu.date.accepted2024-09-26
jgu.description.extentxiii, 188 Seiten ; Diagrammede
jgu.organisation.departmentFB 03 Rechts- und Wirtschaftswissenschaftende
jgu.organisation.nameJohannes Gutenberg-Universität Mainz
jgu.organisation.number2300
jgu.organisation.placeMainz
jgu.organisation.rorhttps://ror.org/023b0x485
jgu.rights.accessrightsopenAccess
jgu.subject.ddccode330de
jgu.type.dinitypePhDThesisen_GB
jgu.type.resourceTextde
jgu.type.versionOriginal workde

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
on_the_solution_of_classical_-20241017120013642.pdf
Size:
2 MB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
3.57 KB
Format:
Item-specific license agreed upon to submission
Description: