Abstract
Diese Arbeit taucht in die komplizierte Welt des Symmetrischen Quadratischen Traveling Salesman Problem (SQTSP) ein und konzentriert sich insbesondere auf Fälle, in denen beim Wechsel zwischen zwei Arten von Kanten Kosten für das Umsteigen anfallen. Ein solches Szenario ist nicht nur in verschiedenen praktischen Anwendungen wie Logistik und Routenplanung realistisch, sondern stellt auch eine besondere Herausforderung für traditionelle Lösungsmethoden dar. Das Hauptziel dieser Forschungsarbeit ist es, die Effektivität bestehender Linearisierungsverfahren der Ganzzahligen Linearen Programmierung (ILP), insbesondere diverse Ungleichungen sowie Heuristiken, wie sie in der Literatur dokumentiert sind, rigoros zu testen und zu bewerten, wenn sie auf das SQTSP angewendet werden, das die Umladekostenkomponente modelliert.Zusätzlich zu der evaluativen Studie leistet diese Arbeit einen Beitrag durch die Entwicklung einer neuen Heuristik, die speziell für diese einzigartige Variante des SQTSP entwickelt wurde. Diese neue Heuristik ist darauf zugeschnitten, die Komplexität, die durch die Umladekosten eingeführt wird, effektiv zu handhaben, und zielt darauf ab, die Traversalsequenz in einer Weise zu optimieren, die die traditionellen Optimierungsziele des SQTSP mit den spezifischen Kostenüberlegungen in Einklang bringt. Die Ergebnisse zeigen eine nuancierte Interdependenz zwischen der Zusammensetzung des Graphen und der Komplexität des Solvers, insbesondere unter dem Einfluss des Verhältnisses zwischen markierten und nicht markierten Kanten und der relativen Größe der Umladekosten. Bemerkenswert ist, dass die Laufzeiten der Lösungsmethoden eine glockenförmige Kurve aufweisen, die einer Normalverteilung ähnelt, wenn sie in Bezug auf den Prozentsatz der markierten Kanten betrachtet werden, wobei sie ihren Höhepunkt erreichen, wenn dieser Prozentsatz einem Gleichgewicht von 50/50 nahekommt. Gleichzeitig reagieren die Laufzeiten auf einen Anstieg der Umladekosten im Verhältnis zu den durchschnittlichen Kantenkosten auf exponentielle Weise, was die komplexen, nicht-linearen Dynamiken verdeutlicht.Die in dieser Arbeit vorgestellten Untersuchungen und Ergebnisse tragen nicht nur zum theoretischen Fortschritt auf dem Gebiet des Operations Research bei, sondern haben auch Auswirkungen auf praktische Anwendungen. Durch die Erweiterung des vorhandenen Wissens über SQTSP und die Einführung neuer Methoden zur Bewältigung der Komplexität von Umladekosten liefert diese Arbeit wertvolle Erkenntnisse sowohl für die Wissenschaft als auch für die Praxis im Bereich der Optimierung und Logistik. Im Wesentlichen navigiert diese Arbeit durch die theoretischen und praktischen Landschaften des SQTSP mit Umladekosten und bietet eine umfassende Analyse bestehender Methoden und bahnt einen neuen Ansatz, um die nuancierten Herausforderungen dieses Problems anzugehen.
Titel in Übersetzung | Symmetrisches quadratisches Traveling Salesman Problem mit Umladekosten: Anwendungen & Lösungsansätze |
---|---|
Originalsprache | Englisch |
Qualifikation | Dipl.-Ing. |
Gradverleihende Hochschule |
|
Betreuer/-in / Berater/-in |
|
Datum der Bewilligung | 28 Juni 2024 |
DOIs | |
Publikationsstatus | Veröffentlicht - 2024 |
Bibliographische Notiz
nicht gesperrtSchlagwörter
- SQTSP
- Umladekosten
- Linearisierung
- ILP
- Subtour Eliminierungs-Ungleichung