Optimierung der periodischen Tourenplanung in der Müllentsorgung

Abstract

Das Müllaufkommen in Österreich steigt stetig an. Den produzierten Müll zu entsorgen, stellt ein großes logistisches Problem dar. Viel Knowhow und Zeit werden in die Planung investiert, und trotzdem werden nicht immer zufriedenstellende Lösungen gefunden. In der Fachliteratur existieren einige Lösungsverfahren für die Müllsammlung, doch keines, das auch die vielen Voraussetzungen für den Praxiseinsatz erfüllen würde. Sollte es aber nicht doch möglich sein, die Planungsbeauftragten bei ihren Aufgaben zu unterstützen und dadurch die Kosten zu reduzieren? Geplant wird die regelmäßige Müllabholung für einen gewissen Zeitraum (z.B.: eine Arbeitswoche). In diesem Planungszeitraum müssen einige Behälter mehrmals entleert werden. Aus der Anzahl der notwendigen Entleerungen im Planungszeitraum ergeben sich Besuchsmuster. Für jeden Müllcontainer muss ein Besuchsmuster ausgewählt werden. Daraus ergibt sich für die Fahrzeuge jeden Tag eine Liste an Behältern, die sie entleeren. Hat ein Fahrzeug einige Müllbehälter entleert und seine maximale Ladekapazität fast erreicht, so muss das Fahrzeug zu einer Entladestation fahren. Modelliert werden kann die Müllsammlung als Multi-Depot Periodic Vehicle Routing Problem with Intermediate Facilities (MDPVRP-IF). Nach einer zufälligen Auswahl eines Besuchsmusters für alle Abfallbehälter wird mit der Savings-Heuristik eine Startlösung erstellt. Das Variable Neighborhood Search-Verfahren (VNS) hat schon bei ähnlichen Problemen seine Vorzüge bewiesen und wurde für die Müllsammlung adaptiert. Als lokale Suche kommt 2-Opt zum Einsatz und als Akzeptanzkriterium wird Simulated Annealing (SA) verwendet.<br />Getestet wurde das VNS mit Echtdaten eines Entsorgungsunternehmens. In weniger als 60 Minuten lieferte das VNS-Verfahren für alle Testszenarien Lösungen, die von einem Disponenten als Verbesserungen im Vergleich zu den bisherigen Lösungen bezeichnet wurden. Ein Praxis-Einsatz des Lösungsverfahrens in der nächsten Planungsperiode ist angedacht.