Raum-Zeit-Netze modellieren den Warenfluss durch die Zeit

Zeit ist Geld und damit kostbar. Daher spielt der Faktor Zeit in Planungsproblemen häufig eine große Rolle.Wir zeigen, wie sich dieser Faktor einfach in die Planung integrieren lässt. Dieser erste Teil der Miniserie thematisiert den immensen Einfluss der Daten auf die Modellerzeugung und die Eleganz von Time-Space-Netzwerken.

Das Beispiel:

Im Gegensatz zum Beispielszenario in Optimale Tourenplanung denken wir nun etwas größer und das Planungsproblem umfasst die europaweite Lieferung unterschiedlicher Waren an Verteilzentren mit LKWs. Für diese Problemstellung gibt es eine sehr elegante Modellierung: Time-Space-Netzwerke. Wie man diese Netzwerke zur optimalen Planung einsetzen kann erfahren Sie in unserer Miniserie zum Thema Der Faktor Zeit in der Optimierung.

Die Eleganz von Flussnetzwerken

Beginnen wir mit der Eleganz, die die Lösung mit Time-Space-Netzwerken ermöglicht. Wenn etwas durch ein Netzwerk fließt – wie Wasser durch ein Rohrsystem –, dann greifen Optimierer häufig zu Flussanalysen. Der Grundgedanke ist bestechend: Dieselbe Menge, die irgendwo hinfließt, muss dort auch wieder wegfließen. Wobei hinfließen im Falle von Waren gleichbedeutend ist mit anliefern, und wegfließen mit verkaufen. Oder im Fall von LKWs, wegfahren und heimkehren.

Dieser Grundgedanke lässt sich vorzüglich nutzen, um über Zeiten hinweg zu planen, denn ein Netzwerk ist im mathematischen Sinn nicht notwendigerweise ein physisches Netzwerk oder ein Liefernetzwerk auf einer Karte.

Stattdessen reicht dieses Netzwerk durch die Zeit, aber analysieren kann man es mit den gleichen Mitteln, wie andere Netzwerke auch.

Ein einfaches Modell

Die Verteilzentren haben einen bestimmten Bedarf, der sich von Tag zu Tag unterscheidet. Der Einfachheit halber wird erst einmal in ganzen Tagen geplant (obwohl aus mathematischer Sicht jede gleich große „Zeitscheibe“ genauso gut funktioniert). Außerdem geben wird der Bedarf immer in voll beladenen Trucks angenommen – im bald erscheinenden Teil 2 wird dieser Teil realistischer modelliert und um unterschiedliche Warengruppen erweitert.

Ein Time-Space-Netzwerk nutzt die geografische Karte mit den Kunden als Grundlage, aber man betrachtet nun alle Kunden gleichzeitig zu einem festen Zeitpunkt. Dazu werden alle Kunden bzw. Orte in einer Spalte auf der Karte übereinander angeordnet.

Dabei bezeichnet eine Spalte (Position auf der X-Achse) genau einen Zeitpunkt (im Beispiel: einen Tag). Nun kopiert man die Orte in jede Zeitspalte, was bedeutet, dass in jeder Zeile nach wie vor immer derselbe Kunde eingetragen wird – nur eben zu unterschiedlichen Zeitpunkten. Das sind die Knoten unseres Time-Space-Netzwerks.

Das Netz verbindet Raum und Zeit

Bei Time-Space-Netzwerken (und, um ehrlich zu sein, normalerweise auch bei allen anderen Netzwerken) verbindet man nicht einfach alle Punkte, sondern man beachtet zwei Einschränkungen:

• Kann eine Fahrt zwischen zwei Punkten grundsätzlich stattfinden?
• Muss eine Fahrt zwischen zwei Punkten stattfinden?

Punkt 1 ergibt sich aus zwei wichtigen Daten: Der geografischen Entfernung und der Reisegeschwindigkeit der Lieferwagen (ist es möglich, innerhalb eines Zeitschritts anzukommen?). Für Punkt 2 muss man sich klar machen, dass jeder Punkt im Netzwerk auch einen Zeitpunkt beinhaltet. Man erzeugt also für einen Kunden überhaupt nur dann eine Verbindung zum Depot, wenn der Kunde zu diesem Zeitpunkt wirklich einen Bedarf hat.

Für Optimierer ist diese Aussage immens wichtig: Sie bedeutet, dass das Netzwerk sich vom theoretisch Möglichen auf das tatsächlich Relevante reduziert. Und das hilft dabei, auch große Optimierungsprobleme effizient zu behandeln.

Was nun passiert, hängt von der genauen Entscheidung ab, die man treffen möchte: Wie viele Trucks sind auf welcher Strecke (also auch: zu welchem Zeitpunkt) unterwegs?

Gemäß guter Tradition nummerieren wir alle mathematisch relevanten Aussagen. Die Nummerierung entspricht dabei der Nummerierung im Whitepaper.

Interessiert an allen Formeln dieses mathematischen Modells?

  • (D1) Wann fahren wie viele Trucks zu welchem Kunden?

  • (D2) Wann bekommt welcher Kunde seinen Bedarf nicht erfüllt?

Wir formulieren Entscheidung (D2) ausdrücklich, denn dann kann man analysieren, wo und warum eine Lieferung nicht geklappt hat. Vielleicht reicht es aus, einen Tag eher oder später zu fahren? Vielleicht muss aber auch ein weiterer Truck angeschafft werden.

Alles ist im Fluss

Der Grundgedanke der Time-Space-Netzwerke ist es, den Fluss von Dingen (hier: Trucks) durch Raum und Zeit zu formulieren. Dabei kommt eine zentrale mathematische Formulierung zum Einsatz: die Flusserhaltung.

Die Flusserhaltung präzisiert eine zentrale Annahme, die für jeden Knoten in unserer kleinen Raum-Zeit gilt: Jeder Truck, der ankommt, fährt auch wieder weg. Dabei gibt es nur zwei Ausnahmen:

  • Alle Lieferwagen starten zu Beginn am Zentrallager.
  • Am Ende kehren alle Lieferwagen wieder zurück.

Um es etwas zu vereinfachen, führen wir einen „Hier-ist-alles-fertig“-Knoten ein (in den Bildern hellgrau markiert), zu dem die Trucks am Ende zurückkehren.

Die Flusserhaltung ist eine einfache, elegante Formulierung für die zentrale Eigenschaft unseres Netzwerks:

  • (C1) Die Flusserhaltung stellt sicher, dass die Trucks immer im Netz unterwegs sind.

Um die Flusserhaltung so richtig zur Geltung zu bringen, machen wir uns zwei weitere Tricks zunutze:

  • (C2) Die maximale Anzahl an Trucks, die einen Kunden gerade ansteuert, entspricht dem Bedarf des Kunden zu diesem Zeitpunkt
  • (C3) Der verpasste Bedarf zu einem Zeitpunkt (siehe D2) entspricht der Differenz aus Bedarf und ankommenden Trucks

Und mit dieser Formulierung ist die Optimierung einfach: Wir minimieren den verpassten Bedarf:

  • (T1) minimiere den gesamten verpassten Bedarf im Netzwerk

Mehr brauchen es nicht, um ein Flussnetzwerk über die Zeit zu formulieren. Wenn man nun weiß, mit wie vielen LKWs man startet und wann welcher Kunde welchen Bedarf hat, sieht das Netz genau so aus, wie man es braucht, und die LKWs fahren fast von allein.

Meinen wir das Ernst?

Und wer sich nun fragt, ob wir das wirklich ernst meinen, dem müssen wir bei seinen Zweifeln etwas recht geben: denn eigentlich braucht man hier gar keine Optimierung: Jeder Kundenbedarf gehört zu genau einer Kante. Niemand muss hier entscheiden, welcher Weg durch das Netz genommen wird. Im Prinzip kann man schnell ausrechnen, ob der Bedarf mit den vorhandenen LKWs gedeckt werden kann.

Aber es wird interessanter. Denn eigentlich bestellen die Verteilzentren keine ganzen LKW-Ladungen, sondern unterschiedlicher Ware. Und außerdem haben sie ein lokales Lager, mit dem sie ihren Bedarf decken. Dann geht es darum, dieses Lager rechtzeitig zu füllen, damit sie den Bedarf auch wirklich decken können.

Und damit wird das Netzwerk deutlich interessanter und es ist längst nicht mehr sonnenklar, wo wie viele LKWs fahren. Und falls jemand nicht geduldig genug für Teil 2 in dem wir diese Varianten ins Modell aufnehmen, kann er im Whitepaper nicht nur das gesamte Modell, sondern auch die Erweiterung um Lager und Produktarten bereits nachlesen.