Knowledge Graph-Driven Tour Optimization for Sustainable Waste Collection

Abstract

Aktuelle gesellschaftliche Herausforderungen wie der Klimawandel, die Verschmutzung der Ökosysteme unseres Planeten und die Abhängigkeit von knappen Ressourcen in einer politisch aufgeladenen Welt motivieren den Wandel hin zu einer Kreislaufwirtschaft, wobei Recycling eine essentielle Komponente für den Übergang darstellt. Recycling von organischen Feststoffabfällen wird durch die Verunreinigung mit schädlichen Materialen erschwert, die oft dazu führen, dass die Abfälle verbrannt oder auf Deponien entsorgt werden, wodurch die Treibhausgasemissionen steigen und wertvolle Ressourcen verloren gehen. Bei der Abholung solcher Abfälle kann stark verunreinigter Müll von einer einzigen Abholung eine ganze Müllwagen-Ladung kontaminieren. Gleichzeitig würde die Entsendung mehrerer Müllwagen für eine bessere Trennung der Abfälle die Betriebskosten und die durch den Transport verursachten Emissionen erhöhen. Daher stellen wir uns die Frage, ob eine Vorsortierung der Abholungen auf der Grundlage historischer Schadstoffmessungen den Gesamtaufwand verringern und die Recycling-Quote erhöhen kann?In dieser Arbeit präsentieren wir einen Lösungsvorschlag, der Prognosemodelle und Tourenoptimierung in einem auf Knowledge Graphen basierenden Framework integriert. Dafür definieren wir dieses Problem als Pre-Collection Sorting Problem und erstellen eine problemspezifische Optimierungsontologie für die Abfallwirtschaft. Wir identifizieren zwei Strategien für die Prognose des Kontaminationslevels zukünftiger Abholungen: Klassifizierung von Haltestellen, und Modellierung von Abholungen derselben Haltestelle als Stichproben eines stochastischen Prozesses, der anhand früherer Verschmutzungsdaten parametrisiert wird. Für die Optimierung der Touren haben wir eine Greedy-Heuristik und einen lokalen Suchalgorithmus entwickelt, die auf das Problem und beide Strategien der Kontaminationsprognose zugeschnitten sind.Die entwickelten Methoden werden in 11 Emissionsszenarien an einer Probleminstanz aus Echtdaten, die über sechs Monate erhoben wurden, getestet. Wir evaluieren die Einzelkomponenten separat und integriert als Gesamtlösung. Dabei bewerten wir die Vorhersagegenauigkeit, die Routeneffizienz und resultierende Umweltauswirkungen. Im Vergleich zur Ausgangslage der aus den Daten extrahierten Status-quo-Routen reduzieren wir in allen Szenarien bis zu 2/3 der entsorgten Abfallmenge. Darüber hinaus beobachten wir eine ähnliche Reduktion der Gesamtemissionen, was demonstriert, dass es sich um eine praxisnahe Lösung für diese wichtige Herausforderung der Abfallentsorgung handelt.

Current societal challenges such as climate change, pollution of the planet's ecosystems, and the dependence on rare resources in a politically charged world motivate the change towards a circular economy, with recycling being one of the essential components to a successful transition. Organic solid waste recycling faces challenges due to contamination from harmful materials, often resulting in waste being incinerated or sent to landfills, which raises greenhouse gas emissions and wastes valuable resources. When collecting such waste, a single severely contaminated collection stop can spoil an entire truckload. Yet dispatching multiple trucks for separation increases operational costs and emissions from transportation. This raises the question whether an initial sorting phase, which involves sorting the stops according to pollution data, can reduce the total effort and improve the recycling quota?In this thesis, we address this question by proposing a solution that integrates predictive modeling and tour optimization algorithms in a knowledge graph-based framework. For this purpose, we formalize the problem at hand as a Pre-Collection Sorting Problem and establish a problem-specific layered optimization ontology for the waste domain. We identify two strategies for predicting contamination levels of future collection events: Classification of tour stops, and modeling repeated visits to the same stop as samples from a stochastic process parameterized by previous pollution records. For the tour optimization task, we designed a greedy heuristic and a sophisticated local search algorithm tailored to the problem and both contamination prediction strategies.The proposed methods are tested on 11 emission scenarios in a challenging real-world problem instance with waste collection data over six months. We evaluate the solution components separately and end-to-end, measuring prediction accuracy, route efficiency, and environmental impact. Compared to the baseline of status quo routes extracted from the data we reduce up to two thirds of disposed waste volume in all scenarios. Furthermore, we also observe a similar reduction of total greenhouse gas emissions, demonstrating a practical and sustainable solution for this real-world waste management challenge.