Vehicle Routing Problem

Formulierung als Problem der Graphentheorie

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

Eine Menge von ${\displaystyle K\in \mathbb {N} }$ identischen Fahrzeugen, die jeweils die Kapazität ${\displaystyle 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 ${\displaystyle K}$ Kreise in ${\displaystyle 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 ${\displaystyle v_{0}}$.
• Jeder Kunde ${\displaystyle 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 ${\displaystyle x_{ijk}\in \{0,1\}}$ gibt an, ob die Strecke ${\displaystyle (i,j)}$ von Fahrzeug ${\displaystyle k}$ benutzt wird (${\displaystyle x_{ijk}=1}$) oder nicht (${\displaystyle x_{ijk}=0}$). Außerdem wird die Binärvariable ${\displaystyle y_{ik}\in \{0,1\}}$ eingeführt, um zu modellieren, ob Kunde ${\displaystyle i}$ von Fahrzeug ${\displaystyle 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 ${\displaystyle i}$ von genau einem Fahrzeug ${\displaystyle 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 ${\displaystyle k}$ den Kunden ${\displaystyle i}$ genau dann über eine eingehende Kante und eine ausgehende Kante bedient, falls ${\displaystyle 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 ${\displaystyle C}$ jedes Fahrzeugs ${\displaystyle k}$ nicht überschritten wird.
• Die Restriktionen $${\displaystyle \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 ${\displaystyle S}$ von ${\displaystyle V}$ exponentiell in der Anzahl der Knoten in ${\displaystyle V}$ wächst. Vielmehr werden diese im Stil eines Schnittebenenverfahrens nur bei Bedarf iterativ hinzugefügt.

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.