[Back]

K. Edlinger:
"Optimierung der periodischen Tourenplanung in der Müllentsorgung";
Supervisor: G. Raidl, M. Ruthmair; Institut für Computergraphik und Algorithmen, 2011; final examination: 2011-07.

The volume of waste is rising in Austria - especially private households are producing more and
more garbage. It is quite a difficult logistical problem to bring all the garbage to recycling centers
and land fills. In Vienna alone, 100.000 garbage bins are emptied every day. 270 compactor
trucks bring the garbage to land fills. To plan the waste collection is a challenge for many cities.
A lot of time and know-how is invested in the planing process, still the solutions are not always
satisfactory. In the literature there are already some solution procedures for waste collection, but
none are viable in practice. This thesis tries to answer the question if it is possible to support the
planning process for periodic waste collection to reduce the cost of operations.
A plan is created not just for one day, but for several, e.g. one week. After this period of
time the plan is repeated. In the planing period some garbage bins have to be emptied more
than once. Visiting schedules can be derived from this frequency. A visiting schedule states on
which days of the planing period a garbage bin is emptied. Once each site has been assigned one
visiting schedule, we can create tours for the compactor trucks. A tour is a sequence of sites, and
each tour is assigned to one vehicle. Each truck starts its daily tour from its depot. There may
be several depots from which the vehicles depart. On its tour, the vehicle will empty garbage
bins. Before the vehicle reaches its maximum capacity, it will drive to a land fill and unload the
garbage. Land fills, recycling centers, and incinerating facilities are summarized under the term
Intermediate Facilities (IF). For the planner, there are several IFs to choose from. Not always
is the nearest IF the best choice and in some cases policies mandate that a certain IF is used
or preferred. At the end of the tour the vehicle returns to its depot. A specialty is that a truck
is also allowed to return to the depot partially loaded and drive to an IF on the next day. The
literature classifies the basic problem as a Multi-Depot Periodic Vehicle Routing Problem with
Intermediate Facilites (MDPVRP-IF).
The MDPVRP-IF with the described extensions requires a flexible solving method. The
Variable Neighborhood Search (VNS) has already proved its ability to find good solutions for
similar problems and has been adopted for this problem. As local search we use 2-opt. The
acceptance criteria has been enriched with principles from Simulated Annealing (SA). The VNS
heuristic has been tested with real data from an Austrian waste collection company. The solving
procedure could solve all test instances in under 30 minutes. The dispatcher of the company
that provided the data stated that all solutions show an improvement over the existing solutions.
Thus the company intends to use the solution procedure in the next planning process.

Das Müllaufkommen in Österreich steigt stetig an, auch das der Privathaushalte. Den produzierten
Müll zu entsorgen, stellt mittlerweile ein großes logistisches Problem dar. So werden inWien
täglich an die 100:000 Müllbehälter entleert. 270 Fahrzeuge bringen den Müll zu Mülldeponien.
Die Planung der periodischen Entleerung von Abfallbehältern stellt für viele Städte eine Herausforderung
dar. Viel Knowhow und Zeit werden in die Planung investiert, und trotzdem werden
nicht immer zufriedenstellende Lösungen gefunden. In der Fachliteratur existieren zwar 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?
Genauer betrachtet, handelt es sich bei dem Problem der periodischen Entleerung von Abfallbehältern
bei Müllsammelstellen um ein Multi-Depot Periodic Vehicle Routing Problem with
Intermediate Facilites (MDPVRP-IF). Das bedeutet, dass ein oder mehrere Fahrzeuge von verschiedenen
Depots aus losfahren und Müllbehälter entleeren. Dies passiert über eine längere
Planungsperiode (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. Ein solches Besuchsmuster gibt an, an welchen Tagen ein Abfallbehälter
entleert wird und an welchen nicht. 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, auch Intermediate
Facility (IF) genannt. Eine Besonderheit der Müllsammlung ist, dass die Fahrzeuge unter bestimmten
Umständen auch beladen ins Depot fahren dürfen und erst am nächsten Tag zu einer
IF. Eine weitere Eigenart besteht in der Auswahl der IFs. Durch Verträge mit IFs kann es notwendig
sein, dass nicht zur nächstgelegenen IF gefahren wird, sondern zu einer anderen.
Diese Erweiterungen des MDPVRP-IF verlangen ein flexibles Lösungsverfahren. Das Variable
Neighborhood Search-Verfahren (VNS) hat schon bei ähnlichen Problemen seine Vorzüge
bewiesen und wurde in der vorliegenden Arbeit für dieses Problem adaptiert. Als lokale Suche
kommt 2-Opt zum Einsatz und als Akzeptanzkriterium wird Simulated Annealing (SA) verwendet.
Getestet wurde das VNS mit Echtdaten eines österreichischen Entsorgungsunternehmens.
Die Ergebnisse sind vielversprechend: In weniger als 30 Minuten lieferte das Verfahren für alle
Testszenarien Lösungen, die von einem Disponenten als Verbesserungen im Vergleich zu den
bisherigen Lösungen bezeichnet wurden. Ein Einsatz des Lösungsverfahrens in der nächsten
Planungsperiode ist angedacht.

http://publik.tuwien.ac.at/files/PubDat_200741.pdf