Gebietsplanung: erst das Gebiet, dann die Tour.

Was Gebietsplanung ist

Gebietsplanung ist ein eigener Problemtyp des Operations Research, nicht bloß eine Dispositionsgewohnheit. Ihr Ziel ist, kleine geographische Einheiten – sogenannte Basisgebiete wie Straßenzüge, Postleitzahlbereiche, Stadtteile oder Landkreise – zu übergeordneten Gebieten zusammenzufassen: Bezirken, Clustern, Territorien.1 Die Anwendungsfelder reichen von Wahlkreisen über Vertriebsgebiete und Schulbezirke bis zu den Einsatzgebieten von Müllabfuhr und Winterdienst.

Die Kriterien sind in allen Feldern dieselben und erstaunlich wenige:1

• Ausgeglichenheit. Die Gebiete sollen ungefähr gleich stark sein – gemessen an Einwohnerzahl, Kaufkraft, Menge oder Arbeitsauslastung. Welches Maß gewählt wird, entscheidet mehr über das Ergebnis als jedes Verfahren.
• Kapazitätsgrenzen. Das Aktivitätsmaß eines Gebiets darf eine Grenze nicht überschreiten. In der Logistik ist das die Fahrzeug- oder Schichtkapazität.
• Kompaktheit und Zusammenhang. Gebiete sollen eine sinnvolle Form haben und nicht aus verstreuten Inseln bestehen. Die Begründung ist bei Wahlkreisen juristisch, in der Logistik ökonomisch: kurze Anfahrtswege.
• Exklusive und vollständige Zuordnung. Jede Basiseinheit gehört zu genau einem Gebiet. Das klingt banal und ist der Satz, an dem in der Praxis die meisten Sonderfälle scheitern – der Großkunde, den zwei Fahrer anfahren, ist genau die Verletzung dieser Regel.

In der Tourenplanung ist Gebietsplanung damit nicht ein Thema neben der Optimierung, sondern eine Entscheidung vor ihr. Wer Gebiete festlegt, hat den Lösungsraum der späteren Optimierung bereits zerschnitten. Was danach an Verfahren läuft, steht in unserem Überblick zu den Verfahren der Tourenoptimierung.

Cluster first, route second: ein Kind knapper Rechenleistung

Die Zerlegung in zwei Stufen – erst zuordnen, dann die Reihenfolge innerhalb jeder Gruppe lösen – ist so alt wie die rechnergestützte Tourenplanung selbst. Der bekannteste Vertreter ist der Sweep: Die Stopps werden nach ihrem Polarkoordinatenwinkel um das Depot sortiert und der Reihe nach eingesammelt, bis die Last- oder Entfernungsgrenze eines Fahrzeugs erreicht ist; danach beginnt ein neues Fahrzeug, und innerhalb jeder Gruppe wird die Tour verbessert.3 Die Idee, Fahrzeuge von einem oder mehreren Depots aus so zuzuteilen, geht auf eine Leeds-Arbeit von 1972 zurück, auf die Google OR-Tools bei seiner Startstrategie SWEEP bis heute verweist.29

Der Grund für die Zerlegung steht in derselben Arbeit, und er ist bemerkenswert ehrlich: Der Rechenaufwand wächst nur dann linear mit der Zahl der Standorte, wenn die durchschnittliche Zahl der Stopps je Tour ungefähr konstant bleibt; bei fester Standortzahl wächst er quadratisch mit der Zahl der Stopps je Tour. Ein Problem mit 100 Standorten brauchte rund 115 Sekunden auf einer IBM 360/67.3 Kleine Gruppen zu bilden war keine planerische Überzeugung, sondern die einzige Möglichkeit, überhaupt zu rechnen.

Die zweite klassische Variante ersetzt den Winkel durch Mathematik: Fisher und Jaikumar formulieren 1981 die Zuordnung der Kunden zu Fahrzeugen als generalisiertes Zuordnungsproblem, dessen Zielfunktion die Zustellkosten annähert. Ihr Verfahren hat zwei Eigenschaften, die es bis heute interessant machen: Es findet immer eine zulässige Lösung, wenn eine existiert – was keine der dort verglichenen Heuristiken garantieren konnte –, und es lässt sich parametrisch über die Flottengröße fahren, um die kleinste Flotte zu bestimmen, die die Nachfrage noch bedient.4

Die Gegenrichtung: route first, cluster second

Dass die Reihenfolge der beiden Schritte keine Naturkonstante ist, zeigt die Gegenrichtung. 1983 beschreibt Beasley Verfahren, die zuerst eine einzige große Rundreise über alle Stopps bilden und diese anschließend in fahrbare Abschnitte zerschneiden.5 Die Zuordnung zu Fahrzeugen entsteht dabei nicht vorab, sondern als Ergebnis eines optimalen Schnitts durch eine Tour. Die Familie hat sich unter dem Namen order first, split second etabliert und 2014 einen eigenen Überblicksartikel bekommen.6

Praktisch relevant ist das, weil moderne Metaheuristiken genau diese Zerlegung als Decoder verwenden: Eine Lösung wird als Reihenfolge gespeichert und erst beim Bewerten in Touren geschnitten. Wie solche Verfahren arbeiten, steht in unserem Beitrag zu Metaheuristiken in der Tourenoptimierung; die klassische Savings-Heuristik, die weder vorab clustert noch vorab routet, ist in Clarke und Wright beschrieben.

Für die Disposition ist die Gegenrichtung vor allem ein Denkwerkzeug. Sie zeigt, dass die Gebietsgrenze keine Eigenschaft des Versorgungsgebiets ist, sondern eine Entscheidung – und Entscheidungen haben einen Preis, den man ausrechnen kann.

Warum Luftlinien-Cluster die falsche Aufgabe lösen

Der häufigste Fehler bei der Gebietsbildung ist, sie als geometrische Aufgabe zu behandeln: Stopps auf eine Karte, Clusterverfahren darüber, fertig. Das Ergebnis sieht ordentlich aus und ignoriert drei Dinge, die über die Fahrbarkeit entscheiden.

• Das Straßennetz. Zwei Stopps an gegenüberliegenden Ufern eines Flusses, an zwei Seiten einer Bahntrasse oder beiderseits einer Autobahn ohne Querung liegen in der Luftlinie nebeneinander und in der Fahrzeit weit auseinander. Kompaktheit im Sinne der Gebietsplanung meint kurze Anfahrtswege,1 nicht kurze Abstände. Belastbare Gebiete entstehen deshalb auf einer Fahrzeitmatrix des echten Netzes – bei schweren oder geländegängigen Fahrzeugen auf einem fahrzeugspezifischen Netz, wie wir es im Custom Routing bauen.
• Die Kapazität. Ein geometrisch schönes Gebiet kann mehr Menge enthalten, als ein Fahrzeug fasst. Kapazität ist in der Gebietsplanung ein eigenes Kriterium,1 in reinen Abstandsverfahren kommt sie nicht vor – deshalb ist der Sweep ausdrücklich mit einer Last- und Entfernungsgrenze je Fahrzeug formuliert.3
• Die Zeit. Zeitfenster, Standzeiten, Lenk- und Ruhezeiten sind in keinem Abstandsmaß enthalten. Ein Gebiet, das mengenmäßig passt, kann zeitlich unfahrbar sein. Welche Restriktionen über Machbarkeit entscheiden, haben wir in Restriktionen in der Tourenplanung aufgeschrieben, die Fensterseite in Zeitfenstermanagement.

Dazu kommt, dass die Aufgabe selbst nicht durch Hinsehen lösbar ist. Eine eigene Herleitung zur Größenordnung: Bei 60 Lieferstellen und fünf Gebieten gibt es rein kombinatorisch 5 hoch 60 mögliche Zuordnungen, also rund 8,7 mal 10 hoch 41 – und das ohne jede Nebenbedingung und ohne die Reihenfolge innerhalb der Gebiete. Deshalb arbeitet die Literatur seit fünfzig Jahren mit Heuristiken statt mit Vollständigkeit.10

Das eigentliche Argument für feste Gebiete heißt Konstanz

Wer feste Gebiete mit Kilometern begründet, argumentiert schwach: Jede Gebietsgrenze schließt Tauschzüge aus, die eine freie Optimierung nutzen würde. Die gute Begründung ist eine andere – und sie ist in der Forschung ein eigener Problemtyp. Das Consistent Vehicle Routing Problem verbindet die üblichen Kapazitäts- und Tourlängenrestriktionen mit der Anforderung, dass derselbe Fahrer denselben Kunden möglichst immer zur selben Tageszeit besucht; untersucht wurde es unter anderem an einem Realdatensatz mit über 3.700 Kunden.7

Übersetzt in den Alltag: Gebietskenntnis, bekannte Ansprechpartner, eingespielte Abläufe an der Rampe, verlässliche Ankunftszeiten. Das sind echte Werte, sie stehen nur in keiner Kilometerstatistik. Besonders ausgeprägt ist das im Service und Außendienst, wo die Kundenbeziehung Teil der Leistung ist – siehe Routenoptimierung im Außendienst.

Was feste Gebiete allerdings nicht leisten, ist Ausgeglichenheit im Tagesgeschäft. Auch das lässt sich beziffern, hier wieder als eigene Herleitung: Ein Versorgungsgebiet mit 600 Kunden wird in zwölf Gebiete zu je 50 Kunden geteilt, perfekt ausgeglichen nach Kundenzahl. Bestellt jeder Kunde an einem beliebigen Tag mit 20 Prozent Wahrscheinlichkeit, liegt die erwartete Stoppzahl je Gebiet bei 10, die Standardabweichung aber bei der Wurzel aus 50 mal 0,2 mal 0,8, also rund 2,8. Zwei Drittel der Tage liegen damit zwischen 7 und 13 Stopps, und in einem Gebiet von zwölf ist an fast jedem Tag eines dabei, das deutlich darüber oder darunter liegt. Ein nach Stammdaten perfekt ausgeglichener Zuschnitt ist an keinem einzelnen Tag ausgeglichen.

Wann welche Reihenfolge richtig ist

• Feste Gebiete, Touren darin optimiert – wenn Kundenbeziehung, Gebietskenntnis oder gleiche Besuchszeiten den Ausschlag geben, wenn Fahrer dauerhaft zugeordnet sind, oder wenn die Ausschreibung sie vorschreibt. Dann gehört die Gebietsgrenze als harte Restriktion ins Modell und nicht als Bauchgefühl in die Disposition.
• Tägliche Neuzuordnung ohne Gebietsgrenze – wenn die Auftragslage stark schwankt, wenn die Fahrzeuge austauschbar sind, wenn Kapazität und Zeitfenster der Engpass sind. Hier kostet jede fixierte Grenze unmittelbar Kilometer und Fahrzeuge.
• Gebiete als Startlösung, Grenzen als weiche Kosten – der Mittelweg, der in der Praxis am häufigsten trägt: Die Gebietsstruktur bleibt als Regelfall bestehen, ein Grenzübertritt ist erlaubt, kostet aber einen Strafterm. Damit entscheidet die Rechnung, ob sich der Bruch lohnt, und nicht die Hausordnung.
• Sammel- statt Zustelltouren – bei Abfall, Winterdienst oder Straßenreinigung ist die Basiseinheit der Straßenzug, nicht der Stopp. Was eine Bezirksgrenze dort kostet, haben wir an einer ganzen Stadt durchgerechnet: gleich große Bezirke, kürzere Wege.

Was das für Ihre Disposition heißt

Die nützlichste Frage an einen bestehenden Gebietszuschnitt lautet nicht, ob er gut ist, sondern wann er entstanden ist und auf welcher Datengrundlage. In vielen Betrieben stammt er aus einer Zeit mit anderer Kundenstruktur, anderen Mengen und anderen Fahrzeugen; seitdem ist er gepflegt, aber nicht nachgerechnet worden.

Nachrechnen heißt: dieselben vier Wochen echter Aufträge einmal mit und einmal ohne Gebietsgrenzen gegen dieselben Restriktionen rechnen. Die Differenz ist der Preis der Konstanz – und erst wenn er auf dem Tisch liegt, ist die Entscheidung für feste Gebiete eine Entscheidung und keine Gewohnheit. Wie wir dabei vorgehen, steht unter Tourenplanung und Logistikplanung; die Verfahrensgrundlagen stehen in Tourenoptimierung.