Effiziente und gerechte Reviere mithilfe algorithmischer Lösungsmethoden
In vielen Entsorgungsbetrieben haben sich Kolonnen- und deren tägliche Abholgebiete über einen längeren Zeitraum historisch entwickelt und bieten Optimierungspotential in zweierlei Richtung.
Zum einen sind bspw. durch Neubaugebiete oder Änderungen in der Auftragslage Gebiete entzerrt worden, wodurch in den Revieren teilweise sehr große Distanzen zurückgelegt werden müssen. Zum anderen entstehen durch Differenzen in der Auftragslage, wie zum Beispiel Entfernungen vom Auftrags- zum Sammelplatz, Erschwernisse vor Ort (Treppen, Keller, Voll-, Teilservice) oder durchunterschiedliche Behältergrößen erhebliche Abweichungen bezüglich der Arbeitslast der Mitarbeiter.
In einem gemeinsamen Projekt mit den Wirtschaftsbetrieben Duisburg sollten genau diese beiden Probleme angegangen werden:
Eine effizientere Kolonnen- und Revierplanung unter Berücksichtigung einer gleichen Aufteilung der Arbeitslasten aller Mitarbeiter.
Ausgangslage
Nach der Sichtung, Erweiterung und Anpassung aller Daten liegt nun eine gute Übersicht über die Situation vor. Etwa 70.000 Sammelpunkte teilen sich über das gesamte Stadtgebiet auf und werden von 26 verschiedenen Kolonnen bedient. In der Abbildung lässt sich gut erkennen, dass diese teilweise in die Gebiete anderer Kolonnen fahren müssen, um dort zu unterstützen.
Ist Arbeitslast messbar?
Um die Arbeitslast gleich auszulasten, ist es nötig, diese als numerischen Wertdarzustellen. Hierzu lagen den Wirtschaftsbetrieben Duisburg Zahlen vor, welche die oben genannten Ausprägungen (Distanzen, Erschwernisse, Behältergrößen)ausdrücken.
Ein entscheidender Punkt, welcher in der aktuellen Planung nicht berücksichtigt wird, ist die Distanz des jeweiligen Sammelpunkts zur Entsorgungsanlage. Weit entfernte Reviere sollten aufgrund der längeren Fahrtstrecke weniger ausgelastet sein als Reviere, welche sich nah an der Entsorgungsanlage befinden.
Durch sogenanntes Feature Engineering und Anwenden eines mathematischen Modells wurden die vorliegenden Werte um diesen Faktor erweitert, um die Auftrags- und Auslastungslage realitätsgetreu abbilden zu können.
Wie können diese gewonnen Werte sinnvoll genutzt werden?
Auf Basis dieser nun sauber abgebildeten Arbeitslast können ausbalancierte und engzugeschnittene Reviere mithilfe verschiedener Algorithmen und Methoden aus dem Bereich der Data Science generiert werden. Beispielsweise bieten sich hier Varianten des restriktiven Clusterings unter Berücksichtigung geographischer und struktureller Gegebenheiten des Auftragsgebiets an.
Die daraus entstehende Einteilung erzeugt deutlich kompaktere und klar abgegrenzte Kolonnen, welche Aushilfsfahrten weitestgehend vermeidet und natürliche Grenzen(Ruhr, Rhein) beachtet.
Um die Fairness unter den Kolonnen zu evaluieren, betrachtet man die Arbeitslast unter der Berücksichtigung der Entfernung zur Entsorgungsanlage. Hier ist die Auswirkung der mittels Feature Engineering gewonnen Daten sehr klar zuerkennen. Aktuell sind Kolonnen, welche nah an der Entsorgungsanlage liegen, auf Kosten weit entfernter Kolonnen deutlich zu wenig ausgelastet.
Links (aktuelle Planung): Westliche Kolonnen mit einer langen Fahrzeit zur Entsorgungsanlage sind zu stark ausgelastet (dunkelrot), östliche Gebiete weisen eine deutlich geringere Auslastung (dunkelblau) auf.
Rechts (adiutaByte Vorschlag): Insgesamt gleichmäßigere Auslastung unter Berücksichtigung der Reisezeiten zur Entsorgungsanlage.
Mit adiutaByte haben wir ein Unternehmen gefunden, das mit der Vielzahl an Sammelpunkten, komplexen Aufwandvorgaben und anderen Rahmenbedingungen sowie geografischen Besonderheiten der Abfallentsorgung in Duisburg umgehen kann.
Wirtschaftsbetriebe Duisburg
Reviereinteilung: Tägliche, faire Auslastung der Kolonnen
Um zusätzlich eine faire Aufteilung der Aufträge im Verlauf der Woche zu erzeugen, müssen die 26 Kolonnen in je fünf Reviere eingeteilt werden. Die Herangehensweise ähnelt hier dem Vorgehen bei der Kolonneneinteilung mit dem Ziel, insgesamt 130 bzgl. der Arbeitslast ausbalancierte Reviere zu generieren.
Zusätzlich dazu müssen hier zwei Besonderheiten berücksichtigt werden. Zum einen existieren Aufträge, welche mehrmals pro Woche bearbeitet werden müssen. Um kompakte Reviere und kurze Reisezeiten zu garantieren, wurde hier so gut wie möglich darauf geachtet, dass solche Aufträge der Grenzregion zweier Reviere liegen und diese Reviere einen regulären Abholzyklus darstellen.
Zum anderen muss darauf geachtet werden, dass zweiwöchentliche Aufträge so eingeplant werden, dass auch zwischen geraden und ungeraden Kalenderwochen keine Imbalance entsteht und die Arbeitslast auch hier fair aufgeteilt wird. Beide Besonderheiten wurden mithilfe von algorithmischer Approximationsmethoden gelöst.
Somit konnte die Varianz der Arbeitslast unter allen Revieren insgesamt stark verringert werden. Aktuell beträgt die Reichweite der Arbeitslasten Sammelzeiten von ca. 3 Stunden bis 7 Stunden pro Tag, durch die algorithmische Lösung des Problems entstehen Arbeitslasten von 4,5 bis 5,5 Stunden pro Tag.
Fazit & Prognose
Das Ziel des Projekts bestand darin, eine neue kompakte und faire Kolonnen- und Reviereinteilung auf Basis der Arbeitslast zu generieren und diese neuen Gebiete mit der aktuellen Situation unter Hinzuahme von Kennwerten zu vergleichen.
Besonders ersichtlich ist die gleichmäßig ausbalancierte Arbeitslast bzw. Sammelzeit des gesamten Auftragsgebiets. Dabei wird deutlich, dass nicht nur die Kolonnen insgesamt ausgeglichener sind, sondern dass zusätzlich auch die Einzeltouren (Reviere) im Verlauf der Woche eine uniformere Verteilung der Sammelzeit aufweisen.
Zusätzlich wurden mit der durch Feature Engineering erweiterten Datenbasis unter Berücksichtigung von geographischen Gegebenheiten deutlich kompaktere Gebiete erzeugt, welche Hilfstouren in anderen Kolonnengebieten vermeidet. Dieser Effekt führt zu einer Reduktion der zurückzulegenden Kilometer und des CO²-Ausstoßes. Nach Analyse der realen Spurdaten lässt sich eine Einsparung von ca. 15% prognostizieren.
Die Zusammenarbeit und Kommunikation mit adiutaByte und die Projektergebnisse haben uns überzeugt, dass eine KI-basierte Tourenplanung eine gleichmäßige Auslastung und hohe Effizienz erreichen kann.
Wirtschaftsbetriebe Duisburg
Die im Laufe Projekts erarbeitete Daten- und Methodengrundlage kann darüber hinaus genutzt werden, um verschiedene Szenarien abzubilden. Beispielsweise wurde in der Simulation die Kolonneneinteilung in Bezug auf Mitarbeiter pro Depot bzw. Mitarbeiter pro Kolonne beibehalten. Diese könnte man verändern und Auswirkungen auf die Gebiete beobachten. Zusätzlich könnte die Anzahl der Fahrzeuge reduziert oder erhöht werden.
Möchten Sie mehr über unsere Projekte in der Entsorgungsbranche erfahren?
Dann vereinbaren Sie ein unverbindliches Gespräch mit uns!
Efficient and equitable precincts using algorithmic solution methods
In many waste management operations, convoy areas and their daily collection areas have historically developed over a long period of time and offer optimization potential in two directions.
On the one hand, new construction areas or changes in the order situation have led to areas being divided up, which in some cases means that very long distances have to be covered in the areas. On the other hand, differences in the order situation, such as distances from the order site to the collection site, difficulties on site (stairs, cellars, full, partial service) or different container sizes result in considerable deviations in terms of the workload of the employees.
In a joint project with Wirtschaftsbetriebe Duisburg, the aim was to address precisely these two problems:
More efficient convoy and precinct planning, taking into account an equal distribution of workloads among all employees.
Initial situation
After reviewing, expanding and adapting all data, a good overview of the situation is now available. About 70,000 collection points are distributed over the entire city area and are served by 26 different convoys. In the figure, it is easy to see that these sometimes have to travel to the areas of other convoys to provide support.
Is workload measurable?
In order to calculate the workload in the same way, it is necessary to represent it as a numerical value. For this purpose, Wirtschaftsbetriebe Duisburg had figures available which express the above-mentioned characteristics (distances, difficulties, container sizes).
A decisive point, which is not considered in the current planning, is the distance of the respective collection point to the disposal plant. Due to the longer travel distance, distant collection points should be less utilized than collection points that are close to the disposal facility.
Through so-called feature engineering and the application of a mathematical model, the available values were expanded by this factor in order to be able to realistically represent the order and utilization situation.
How can these values gained be put to good use?
Based on this now cleanly mapped workload, balanced and tightly clustered precincts can be generated using various algorithms and methods from the field of data science. For example, variants of restrictive clustering taking into account geographic and structural conditions of the job area are suitable here.
The resulting classification generates significantly more compact and clearly delineated convoys, which largely avoids temporary trips and respects natural boundaries (Ruhr, Rhine).
To evaluate the fairness among the convoys, we consider the workload taking into account the distance to the disposal plant. Here the effect of the data obtained by feature engineering is very clear. Currently, convoys that are close to the disposal facility are significantly underutilized at the expense of convoys that are far away.
Left (current planning): Western columns with a long travel time to the disposal facility are overutilized (dark red), eastern areas have a much lower utilization (dark blue).
Right (adiutaByte proposal): Overall more even utilization considering travel times to the disposal facility.
With adiutaByte, we have found a company that can handle the large number of collection points, complex effort requirements and other general conditions as well as geographical peculiarities of waste disposal in Duisburg.
Wirtschaftsbetriebe Duisburg
Precinct assignment: Daily, fair utilization of the convoys
In order to also generate a fair distribution of jobs over the course of the week, the 26 convoys must be divided into five precincts each. The approach here is similar to the procedure for dividing up the convoys with the aim of generating a total of 130 precincts that are balanced in terms of workload.
In addition, two special features must be taken into account here. On the one hand, there are orders that have to be processed several times a week. In order to guarantee compact precincts and short travel times, care was taken here as far as possible to ensure that such orders are located in the border region of two precincts and that these precincts represent a regular pickup cycle.
Secondly, care must be taken to schedule bi-weekly jobs in such a way that there is no imbalance between even and odd calendar weeks and that the workload is distributed fairly here as well. Both special features were solved with the help of algorithmic approximation methods.
Thus, the variance of the workload among all precincts could be greatly reduced overall. Currently, the range of workloads is collection times of about 3 hours to 7 hours per day; the algorithmic solution to the problem results in workloads of 4.5 to 5.5 hours per day.
Conclusion & Prognosis
The aim of the project was to generate a new compact and fair convoy and precinct division based on the workload and to compare these new areas with the current situation using characteristic values.
Particularly evident is the evenly balanced workload or collection time of the entire order area. It becomes clear that not only the convoys are more balanced as a whole, but also that the individual tours (precincts) show a more uniform distribution of collection time over the course of the week.
In addition, with the extended data base created by feature engineering, significantly more compact areas were created, which, among other things, avoids auxiliary tours to other convoy areas. This effect leads to a reduction of the kilometers to be covered and the CO² emissions. After analyzing the real lane data, a saving of about 15% can be predicted.
The collaboration and communication with adiutaByte and the project results convinced us that AI-based route planning can achieve consistent utilization and high efficiency.
Wirtschaftsbetriebe Duisburg
The data and methods developed in the course of the project can also be used to depict various scenarios. For example, in the simulation, the convoy division in terms of employees per depot or employees per convoy was retained. This could be changed and effects on the areas observed. Additionally, the number of vehicles could be reduced or increased.
Would you like to learn more about our projects in the waste management industry?
Then book a non-binding appointment with us!
