Vehicle Routing Problem

Routenplanung einer Flotte, welche ausgehend von einem Depot (D) Kunden beliefert

Das Vehicle Routing Problem (VRP) (auch Standardproblem der Tourenplanung) ist ein kombinatorisches Optimierungsproblem. Die Aufgabe besteht darin, eine optimale Routenplanung für eine Flotte von Fahrzeugen zu bestimmen, um Kunden kostengünstig zu beliefern. Das VRP ist eine Verallgemeinerung des Traveling Salesman Problem (TSP) und ein Optimierungsproblem, welches in der Regel als ganzzahliges lineares Optimierungsproblem modelliert wird. Es wurde 1959 von George Dantzig und John Ramser erstmalig formuliert und angewandt, um Benzinlieferungen an Tankstellen zu optimieren.

Problembeschreibung

Die Standardversion des Vehicle Routing Problems ist das kapazitätsbeschränke VRP, welches auch als Capacitated VRP (CVRP) bezeichnet wird. Im CVRP werden ausgehend von einem zentralen Lager alle Kunden durch eine Transportflotte beliefert. Die Nachfragen sind deterministisch, im Voraus bekannt und werden nicht aufgeteilt. Alle Fahrzeuge sind identisch und unterliegen Kapazitätsbeschränkungen. Charakteristische Ziele des VRP sind:

• Minimierung der globalen Transportkosten (abhängig von der Distanz)
• Minimierung der Fahrzeuge oder Fahrer, die erforderlich sind um alle Kunden zu bedienen
• Gewinnmaximierung
• Minimierung der Auswirkung von schlechtem Service
• Minimierung von Abweichungen in Fahrzeit und Fahrzeugbeladung

Mathematische Formulierung

Formulierung als Problem der Graphentheorie

Das kapazitätsbeschränkte Vehicle Routing Problem (CVRP) kann auf einem Graphen $G=(V,E)$ mit Ecken $V=\{v_{0},\ldots ,v_{n}\}$ und Kanten $E$ definiert werden. Die Ecke $v_{0}$ wird üblicherweise dem Depot zugewiesen, von dem aus die Kunden $v_{1},\ldots ,v_{n}$ beliefert werden, die auf den Ecken des Graphen positioniert sind. Jeder Kante $(i,j)\in E$ werden Kosten $c_{ij}\geq 0$ zugewiesen und jeder Kunde $i$ hat einen zu deckenden Bedarf $d_{i}\geq 0$.

Eine Menge von $K\in \mathbb {N}$ identischen Fahrzeugen, die jeweils die Kapazität $C\geq 0$ besitzen, stehen für den Transport bereit, wobei jedes Fahrzeug nur für jeweils eine Tour eingesetzt werden darf.

Das CVRP besteht darin, genau $K$ Kreise in $G$ zu berechnen, wobei jeder Kreis der Transportroute eines Fahrzeugs entspricht, sodass die Gesamtkosten minimal sind und folgende Bedingungen erfüllt sind:

• Jeder Kreis enthält das Depot $v_{0}$.
• Jeder Kunde $i$ ist Teil genau eines Kreises.
• Die Summe der Nachfragen der Kunden eines Kreises überschreitet nicht die Kapazität des zugewiesenen Fahrzeugs.

Formulierung als ganzzahliges lineares Optimierungsproblem

Es gibt zahlreiche Optimierungsmodelle, die das (C)VRP als Problem der ganzzahliges linearen Optimierung beschreiben und die jeweils verschiedene Vor- und Nachteile haben. Hier vorgestellt wird die sogenannte three-index vehicle flow formulation.

Die binäre Entscheidungsvariable $x_{ijk}\in \{0,1\}$ gibt an, ob die Strecke $(i,j)$ von Fahrzeug $k$ benutzt wird ($x_{ijk}=1$) oder nicht ($x_{ijk}=0$). Außerdem wird die Binärvariable $y_{ik}\in \{0,1\}$ eingeführt, um zu modellieren, ob Kunde $i$ von Fahrzeug $k$ bedient wird.

Zu minimieren ist die Zielfunktion ${\textstyle \sum _{(i,j)\in E}\sum _{k=1}^{K}c_{ij}x_{ijk}}$, welche aus dem gesamten Transportkosten aller Routen und Fahrzeuge besteht.

Außerdem sind folgende Restriktionen zu erfüllen:

• Die Nebenbedingung ${\textstyle \sum _{k=1}^{K}y_{ik}=1\quad \forall i=1,\ldots ,n}$ sorgt dafür, dass jeder Kunde $i$ von genau einem Fahrzeug $k$ bedient wird.
• Durch ${\textstyle \sum _{k=1}^{K}y_{0k}=K}$ wird erreicht, dass das Depot Teil jeder Route ist.
• Die Gleichungskette ${\textstyle \sum _{j=1}^{n}x_{ijk}=\sum _{j=1}^{n}x_{jik}=y_{ik}\ \forall i=1,\ldots ,n\ \forall k=1,\ldots ,K}$ erzwingt, dass Fahrzeug $k$ den Kunden $i$ genau dann über eine eingehende Kante und eine ausgehende Kante bedient, falls $y_{ik}=1$ gilt.
• Mit der Ungleichung ${\textstyle \sum _{i=1}^{n}d_{i}y_{ik}\leq C\ \forall k=1\ldots ,K}$ wird sichergestellt, dass die maximale Kapazität $C$ jedes Fahrzeugs $k$ nicht überschritten wird.
• Die Restriktionen
  $$\sum _{i\in S}\sum _{j\in S}x_{ijk}\leq |S|-1\quad \forall S\subseteq V\setminus \{0\},\ |S|\geq 2,\ k=1,\ldots ,K$$
  stellen eine Verallgemeinerung der Subset Elimination Constraints des TSPs dar und werden bei der Modellformulierung nicht explizit angegeben, da die Anzahl der Teilmengen $S$ von $V$ exponentiell in der Anzahl der Knoten in $V$ wächst. Vielmehr werden diese im Stil eines Schnittebenenverfahrens nur bei Bedarf iterativ hinzugefügt.

Varianten

Übersicht einiger Varianten des Vehicle Routing Problems

Es gibt viele Varianten des VRP, von denen einige wichtige hier angegeben werden. Die Basisversion sei hier das kapazitätsbeschränkte VRP (CVRP), welches oft verkürzt nur als VRP bezeichnet wird.

• Falls für alle Kosten gilt $c_{ij}=c_{ji}$, also die Kosten für Hin- und Rückwege übereinstimmen, spricht man von einem symmetric CVRP (SCVRP), andernfalls von einem asymmetric CVRP (ACVRP).
• Falls die Gesamtlänge einer Route beschränkt ist, spricht man von einem distance-constrained CVRP (DCVRP).
• Im VRP mit Rücktransport (engl. CVRP with Backhauls, kurz VRPB) werden einige Kunden beliefert und von anderen Güter abgeholt. Üblicherweise wird die zusätzliche Bedingung gestellt, dass der Hin- vor dem Rücktransport stattfinden muss.
• Falls die Kunden nur innerhalb eines Zeitfensters anzutreffen sind, spricht man von einem VRP with Time Windows (VRPTW). Üblicherweise werden hier für die Kantengewichte $c_{ij}\geq 0$ als Transportzeiten $t_{ij}\geq 0$ gewählt.
• Falls in einem VRPB zulässige Zeitfenster eingehalten werden müssen, spricht man von einem VRP with Backhauls and Time Windows (VRPBTW).
• Im VRP with Pickup and Delivery (VRPPD) finden nicht nur Transporte vom Depot zu den Kunden, sondern auch Transporte zwischen den Kunden statt. Es müssen also neben der Nachfrage eines Kunden und dessen Angebot auch die jeweiligen Transportziele modelliert werden.
• Ein VRPPD, welches zulässige Zeitfenster betrachtet, ist ein VRP with Pickup and Deliveries and Time Windows (VRPPDTW).

Komplexität

Das Vehicle Routing Problem befindet sich in der Klasse der NP-schweren Probleme, da es eine Verallgemeinerung des Travelling Salesman Problem (TSP) ist. Es sind also bis dato keine Lösungsalgorithmen bekannt, die das VRP in polynomieller Zeit lösen. Im Gegensatz zum TSP, für welches trotz der NP-Schwere Algorithmen existieren, die sehr große Probleminstanzen mit zehntausenden von Städten exakt lösen, gilt das VRP schon mit hunderten von Kunden als sehr schwieriges Problem, das in der Regel nicht mehr exakt gelöst werden kann.

Lösungsverfahren

Exakte Verfahren

Exakte Lösungen des VRPs und dessen Varianten können mit Branch-and-Bound sowie Branch-and-Cut-Verfahren berechnet werden. Hierbei wird versucht durch systematisches Verzweigen der Binärvariablen eine global optimale Lösung zu berechnen. Die Grundidee besteht darin, dass die exponentiell steigenden Anzahl möglicher Belegungen der Binärvariablen durch möglichst gute untere Schranken (basierend auf Relaxierungen, LP-Dualität und zusätzlichen Schnittebenen), sowie oberen Schranken (durch gute zulässige Lösungen aus Heuristiken) zu begegnen.

Klassische Heuristiken

Die wohl bekannteste Heuristik zur Lösung des VRPs ist der Savings-Algorithmus, welcher 1964 von Clarke und Wright veröffentlicht wurde und sukzessiv verbessert wurde. In der Zwei-Phasen-Methode wird zunächst ein Clustering der Kunden durchgeführt und anschließend die Routenplanung vorgenommen. Verbesserungs-Heuristiken konzentrieren sich darauf bereits bestehende Touren zu verbessern, was beispielsweise innerhalb einer Route durch Heuristiken des TSPs passieren kann.

Metaheuristiken

Metaheuristiken sind Heuristiken, die anwendungsunabhängig sind und demzufolge auch zur Berechnung zulässiger Punkte eines VRPs eingesetzt werden können. Bekannte Vertreter sind Simulated Annealing, Tabu Search und genetische Algorithmen.

Anwendungen

Das VRP und alle dazugehörigen Varianten können nicht nur zur Ausstellung und Einsammlung von Güter genutzt werden, sondern findet auch praktische Anwendung zu jeglichen Transportsystemen, wie zum Beispiel:

• Abfallsammlung
• Straßenreinigung
• Schulbusrouten
• Sammeltaxi
• ÖPNV
• Logistik
• Routenplanung von Drohnen

Literatur

• Paolo Toth, Daniele Vigo (Hrsg.): The vehicle routing problem, SIAM monographs on discrete mathematics and applications, 2002.