Detailansicht
Solving a real data waste collection VRP using Google OR-tools
Katarina Đajić
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
Karl Franz Dörner
Mitbetreuer*in
Alina-Gabriela Müller
DOI
10.25365/thesis.79771
URN
urn:nbn:at:at-ubw:1-16289.98657.849616-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Masterarbeit bewertet die Fähigkeiten von Google OR-Tools bei der Lösung realer Vehicle Routing Problem anhand einer Fallstudie zur kommunalen Abfallsammlung in Sarajevo, der Hauptstadt von Bosnien und Herzegowina. Die Ineffizienz bei der Zuweisung von Fahrzeugen zu Routen und das wachsende Abfallaufkommen machten einen systematischen Ansatz zur Verbesserung der betrieblichen Effizienz und Nachhaltigkeit erforderlich. Die Studie konzentriert sich auf die Minimierung der Gesamtfahrstrecken für die Sammlung von Einwegabfällen, die in gemischten Abfallbehältern entsorgt werden. Da einige Behälter täglich, andere zweimal oder dreimal pro Woche geleert werden, wird das Problem als Periodic Vehicle Routing Problem (PVRP) über einen wöchentlichen Zeithorizont formuliert. Diese periodische Natur des Problems erfordert einen zweistufigen Ansatz. In der ersten Phase wird die heuristische Methode Large Neighborhood Search (LNS) angewendet, um die Container den Tagen im wöchentlichen Planungszeitraum zuzuordnen. In der zweiten Phase werden die täglichen Routen mit OR-Tools, einem Open-Source-Optimierungstool, generiert. Unter Verwendung realer Geodaten, die über die OpenRouteService-API bezogen wurden, berechnet die Arbeit realistische Fahrstrecken, und dieselbe API wird zur Visualisierung der Routen verwendet. Das primäre Ziel des Problems ist die Minimierung der Gesamtfahrstrecken. Python wird für die Datenverarbeitung, Modellimplementierung und Ergebnisvisualisierung verwendet, während die Openrouteservice-API für die interaktive Routenpräsentation eingesetzt wird. Die Studie bewertet verschiedene Algorithmuslösungen für unterschiedliche Problemgrößen und analysiert Faktoren wie Rechenzeit und Gesamtfahrstrecke. Die Ergebnisse zeigen, dass der Solver bei Benchmark-Instances eine gute Leistung erbracht hat, indem er in mehreren Fällen die besten bekannten Lösungen (BKS) erzielte und bei allen ausgewählten Instances innerhalb von 10 % der BKS blieb. In Bezug auf den realen Fall hat der Solver innerhalb eines angemessenen Zeitrahmens erfolgreich realisierbare Routen generiert. Um die Qualität der Lösung jedoch besser beurteilen zu können, ist ein Vergleich mit dem bestehenden Routenplan erforderlich, um zu bewerten, ob die Fahrstrecke verkürzt oder die Fahrzeugauslastung verbessert wurde. Insgesamt zeigen die Ergebnisse, dass OR-Tools als Open-Source-Optimierungstool den Entscheidungsprozess effektiv unterstützen und eine kostengünstige Alternative zu kommerziellen Softwarelizenzen darstellen kann, was zu effizienteren Abfallsammelplänen beiträgt, die Kosten senken und die Ressourcennutzung verbessern.
Abstract
(Englisch)
This master’s thesis evaluates the capabilities of Google OR-Tools in solving real-life vehicle routing problems, using municipal waste collection in Sarajevo, the capital of Bosnia and Herzegovina, as a case study. The inefficiency in assigning vehicles to routes and the growing waste volume raised a need for a systematic approach to improve operational efficiency and sustainability. The study focuses on minimizing total travel distances of routes for the collection of a single-type waste deposited in mixed-waste containers. Given that some containers are emptied every day, others twice or three times a week, the problem is formulated as a Periodic Vehicle Routing Problem (PVRP) over a weekly time horizon. This periodic nature of the problem requires a two-phase approach. In the first phase Large Neighborhood Search (LNS) heuristic is applied to assign containers to days across the weekly planning horizon. In the second phase, the daily routes are generated using OR-Tools, an open-source optimization tool. Using real-world geospatial data obtained via the OpenRouteService API, the thesis calculates realistic driving distances, and the same API is used to visualize the routes. The primary objective of the problem is to minimize total travel distances. Python is used for data processing, model implementation, and result visualization, while OpenRouteService API is used for interactive route presentation. The research evaluates different algorithm solutions across varying problem sizes, analyzing factors such as computational time and total travel distance. The results indicate that the solver demonstrated good performance on benchmark instances, achieving best-known (BKS) solutions in several instances, and remaining within 10% of the BKS across all selected instances. Regarding real-life case, the solver successfully generated feasible routes within a reasonable time frame. However, to assess the quality of the solution more, comparison with the existing route plan to evaluate whether travel distance is reduced or vehicle utilization is improved is required. Overall, the findings show that OR-Tools, as an open-source optimization tool, can effectively support decision-making process and provide a cost-efficient alternative to commercial software licenses, contributing to the more efficient waste collection plans that reduce costs and improve resource utilization.
Schlagwörter
Schlagwörter
(Deutsch)
Routenoptimierung Abfallsammlung Tourenplanung
Schlagwörter
(Englisch)
Periodic Vehicle Routing Problem Waste Collection Multi Trip Vehicle Routing Problem
Autor*innen
Katarina Đajić
Haupttitel (Englisch)
Solving a real data waste collection VRP using Google OR-tools
Publikationsjahr
2025
Umfangsangabe
85 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Karl Franz Dörner
Klassifikation
85 Betriebswirtschaft > 85.00 Betriebswirtschaft. Allgemeines
AC Nummer
AC17723471
Utheses ID
78161
Studienkennzahl
UA | 066 | 915 | |