Detailansicht
Fairness in multiple travelling salesmen problems
an analysis and computational study
Madita Freienberg
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Betriebswirtschaft
Betreuer*in
Christian Tilk
DOI
10.25365/thesis.77164
URN
urn:nbn:at:at-ubw:1-26745.06710.512673-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die zunehmende Nachfrage nach Lkws für die Auslieferung von Waren an Kunden, führt zu verstärkten Herausforderungen die Fahrzeiten und -kosten so effizient wie möglich zu halten. Daher ist die effiziente Verteilung mehrerer Lkw zu einem wichtigen Aspekt der modernen Logistik geworden, die mit dem traditionellen TSP-Modell nicht gewährleistet werden kann. Aufgrund dessen wird diese Arbeit sich mit dem multiple TSP befassen, bei dem mehr als ein Fahrzeug eingesetzt wird, um die Nachfrage zu befriedigen. Dies hat den Vorteil, dass es weitaus realistischer ist und sich auch auf Anwendungsbereiche im realen Leben anwenden lässt. Um das mTSP zeiteffizient zu lösen, wird in der Literatur oft die MinSum-Zielfunktion zur Minimierung der Gesamtreisezeit verwendet. Dies führt jedoch zu keiner fairen Verteilung zwischen den Fahrzeugen, was ebenfalls ein wichtiger Faktor geworden ist, insbesondere im Bereich des kollaborativen Transports und der Arbeitsauslastung unter den Fahrzeugen. Neben der MinSum-Zielfunktion wird in dieser Arbeit auch die MinMax-Zielfunktion analysiert, die die maximale Tourlänge minimiert. Außerdem wird eine neue Nebenbedingung für die MinSum-Zielfunktion eingeführt, um die maximale Tourdauer zu begrenzen und so eine ausgewogenere Verteilung der Routen zu erreichen. Die Zielfunktionen werden in zwei verschiedenen Formulierungen berücksichtigt, die sich einmal auf den Knoten- und einmal auf den Kantenfluss beziehen. Diese Modelle werden an 48 unterschiedlich großen Instanzen getestet und mit dem Branch-and-Bound Algorithmus in CPLEX exakt gelöst. Die Lösungen werden dann hinsichtlich ihrer Leistung im Allgemeinen sowie ihrer Fairness bei der Routenzuweisung und ihrer Zielfunktionen verglichen.
Abstract
(Englisch)
The growing demand for trucks to deliver goods to customers has led to challenges in achiving optimal travel times and costs. Therefore, the efficient distribution of several trucks has become an important aspect of modern logistics, which cannot be guaranteed by the traditional TSP model. In contrast, this thesis focusses on the multiple TSP (mTSP), where more than one vehicle is used to meet the customers’ demand. This leads to the advantage of being much more realistic and applicable to real-world applications. To solve the mTSP in a time-efficient way, the literature usually uses the MinSum objective function to minimise the total travel time. However, this does not lead to a balanced distribution among sellers, which has also become an important factor, especially in the area of collaborative transport and vehicle workload distribution. Therefore, this thesis analyses not only the MinSum objective but also the MinMax objective function, which minimises the maximum tour length. Moreover, a new constraint is introduced for the MinSum objective function to limit the maximum tour duration and thus achieve a more balanced distribution of routes. The objectives are considered in two different formulations, which are the node-flow and the arc-flow formulations. These models are tested on 48 instances of different sizes and solved the problem exactly by using the branch-and-bound algorithm in CPLEX. The solutions are then evaluated in terms of their general performance and compared in terms of their fairness in terms of route allocation and objective functions.
Schlagwörter
Schlagwörter
(Deutsch)
Travelling Salesman Problem multiple Travelling Salesmen Problem MinMax Zielfunktion MinSum Zielfunktion Branch-and-Bound Fairness
Schlagwörter
(Englisch)
Travelling Salesman Problem multiple Travelling Salesmen Problem MinMax Objective MinSum Objective Branch-and-Bound Fairness
Autor*innen
Madita Freienberg
Haupttitel (Englisch)
Fairness in multiple travelling salesmen problems
Hauptuntertitel (Englisch)
an analysis and computational study
Publikationsjahr
2024
Umfangsangabe
40, XI Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Christian Tilk
Klassifikation
85 Betriebswirtschaft > 85.99 Betriebswirtschaft. Sonstiges
AC Nummer
AC17382498
Utheses ID
72176
Studienkennzahl
UA | 066 | 915 | |