CVRP Löser

Pseudocode

Das CVRP ist das VRP mit einer Ladegrenze je Fahrzeug. Diese eine Nebenbedingung verändert, welche Gruppierungen überhaupt zulässig sind, und damit die gesamte Struktur der Suche.

CVRP(depot, kunden, kapazität Q):
    // Clarke-Wright-Ersparniskonstruktion
    beginne mit einer eigenen Tour je Kunde
    für jedes Paar (i, j):
        ersparnis[i][j] = d(dep,i) + d(dep,j) - d(i,j)
    Paare nach fallender Ersparnis sortieren

    für jedes Paar (i, j) in dieser Reihenfolge:
        wenn i und j in verschiedenen Touren liegen
           und beide Endpunkte ihrer Tour sind
           und bedarf(tour_i) + bedarf(tour_j) <= Q:
            die beiden Touren verschmelzen

    // Danach: 2-opt innerhalb der Touren und Bewegungen
    // zwischen Touren, stets unter Ablehnung von Kapazitätsverstößen

Der Ersparniswert misst, wie viel man gewinnt, wenn i und j in derselben Tour bedient werden statt in zwei getrennten Hin- und Rückfahrten. Die Kapazitätsprüfung ist das, was CVRP von VRP unterscheidet: eine Verschmelzung kann distanzmäßig hoch lukrativ und zugleich schlicht unzulässig sein. Jede spätere lokale Suche muss diese Prüfung bei jedem Zug wiederholen, denn ein die Distanz verbessernder Tausch zwischen Touren kann eine Tour unzulässig machen.

Durchgerechnetes Beispiel, Schritt für Schritt

Route fünf Kunden mit einem Fahrzeug der Kapazität 10 und beobachte, wie die Ladegrenze die lukrativste Verschmelzung ablehnt.

Beispielgraph: Depot plus fünf Kunden mit Bedarfen C1 gleich 4, C2 gleich 4, C3 gleich 3, C4 gleich 3 und C5 gleich 2. Jedes Fahrzeug kann 10 Einheiten transportieren.

1. Mit eigenen Touren beginnen. Fünf Touren, je eine pro Kunde, jede eine Hin- und Rückfahrt vom Depot. Das ist zulässig, aber teuer, und es ist der Ausgangspunkt des Ersparnisverfahrens.
2. Nach fallender Ersparnis verschmelzen. Das Paar mit der größten Ersparnis ist C1 und C2, die zudem geografisch nah beieinanderliegen. Ihr gemeinsamer Bedarf beträgt 4 + 4 = 8 und liegt innerhalb der Kapazität 10, die Verschmelzung wird also angenommen.
3. Die nächste lukrative Verschmelzung wird abgelehnt. Die nächstbeste Ersparnis würde C3 derselben Tour hinzufügen. Die Distanz würde sich deutlich verbessern, doch der Bedarf stiege auf 8 + 3 = 11 und damit über die Kapazität 10. Die Verschmelzung wird abgelehnt, obwohl sie distanzmäßig die beste wäre.
4. Mit den zulässigen Verschmelzungen fortfahren. C3, C4 und C5 verschmelzen untereinander mit Gesamtbedarf 3 + 3 + 2 = 8 innerhalb der Kapazität. Es bleiben zwei Touren: eine mit C1 und C2 mit Last 8 und eine mit C3, C4 und C5 mit Last 8.

Die Lösung nutzt zwei Fahrzeuge mit den Lasten 8 und 8, obwohl die distanzmäßig attraktivste Verschmelzung darin bestanden hätte, C3 der ersten Tour hinzuzufügen. Diese Ablehnung ist der ganze Unterschied zwischen VRP und CVRP: im reinen VRP wäre die Verschmelzung angenommen worden und die Lösung wäre kürzer, aber unzulässig. Beachte außerdem, dass der Gesamtbedarf 16 und die Kapazität je Fahrzeug 10 beträgt, zwei Fahrzeuge also das Minimum sind; eine Lösung mit einem einzigen existiert nicht, wie gut man auch optimiert.

Komplexität und woher sie kommt

Zeit: NP-schwer; Clarke-Wright O(n^2 log n) · Speicher: O(n^2)

Die Clarke-Wright-Ersparniskonstruktion berechnet für jedes der O(n hoch 2) Paare einen Ersparniswert und sortiert sie, was die Kosten mit O(n hoch 2 log n) dominiert. Jeder Verschmelzungsversuch ist eine Prüfung in konstanter Zeit über Lasten und Tourendpunkte, sofern man geeignete Strukturen führt. Die anschließende lokale Suche kostet O(n hoch 2) je Durchgang. Das Problem selbst ist NP-schwer, da es TSP enthält, und die Kapazität verschärft es weiter, indem sie den Raum zulässiger Lösungen unregelmäßig beschneidet. Exakte Verfahren per Spaltengenerierung lösen Benchmarkinstanzen mit rund 100 Kunden; darüber hinaus greift man zu Metaheuristiken. Eine nützliche und billige untere Schranke ist der Gesamtbedarf geteilt durch die Kapazität, aufgerundet, was die Mindestzahl an Fahrzeugen liefert.

Wann Kapazitätsbeschränkte Tourenplanung (CVRP) passt und wann nicht

Jede zusätzliche Nebenbedingung definiert eine eigene Variante mit eigener Literatur und eigenen Lösern.

Häufige Fehler

• Die Kapazität nur bei der Konstruktion prüfen. Jeder Zug der lokalen Suche, einen Kunden verschieben, zwei tauschen, ein Teilstück zwischen Touren umkehren, kann die Kapazität verletzen. Die Prüfung muss bei jedem Zug wiederholt werden, nicht nur während der Anfangskonstruktion.
• Die untere Schranke aus dem Gesamtbedarf vergessen. Der Gesamtbedarf geteilt durch die Kapazität, aufgerundet, ergibt die Mindestzahl an Fahrzeugen. Sie ist kostenlos zu berechnen und sagt dir sofort, ob eine Lösung mit weniger Fahrzeugen überhaupt möglich ist, und dient zugleich als Maßstab für die Qualität der vorhandenen.
• Annehmen, weniger Fahrzeuge seien immer besser. Eine kleinere Flotte verlängert jede Tour, und bei Stundenkosten für Fahrer oder Arbeitszeitgrenzen kann die Lösung mit weniger Fahrzeugen teurer ausfallen. Optimiere die tatsächlichen Kosten, nicht die Fahrzeuganzahl.
• Teilbare Bedarfe modellieren, wo sie es nicht sind. Das Standard-CVRP setzt voraus, dass jeder Kunde vollständig in einem Besuch bedient wird. Lässt sich eine Lieferung tatsächlich auf zwei Fahrzeuge aufteilen, handelt es sich um das VRP mit geteilten Lieferungen, ein anderes Problem mit strukturell abweichenden und oft günstigeren Lösungen.
• Die Rückladung übersehen. Bei Abholungen wächst die Last entlang der Tour, statt zu sinken, die bindende Beschränkung liegt also am Ende der Fahrt und nicht am Anfang. Lieferungen und Abholungen in derselben Tour zu mischen erfordert eine Lastprüfung an jedem Stopp.

Häufig gestellte Fragen

Was ist das kapazitierte Tourenplanungsproblem?

Das CVRP sucht die kostengünstigste Menge von Touren für eine Flotte, die von einem Depot ausfährt, wobei jeder Kunde einen Bedarf hat und kein Fahrzeug seine Ladekapazität überschreiten darf. Es ist die Standardvariante des VRP in der realen Logistik und der Warendistribution.

Was ist der Unterschied zwischen VRP und CVRP?

Das VRP führt eine Flotte ohne Ladegrenze; das CVRP fügt je Fahrzeug eine Kapazität hinzu, die keine Tour überschreiten darf. Diese Nebenbedingung verändert, welche Kundengruppierungen überhaupt zulässig sind, sodass distanzmäßig kürzere Lösungen als unzulässig ausscheiden können, wie im Beispiel, in dem die lukrativste Verschmelzung abgelehnt wird, weil sie die Kapazität um eine Einheit überschreitet.

Wie funktioniert der Clarke-Wright-Ersparnisalgorithmus?

Er beginnt mit einer eigenen Tour je Kunde und berechnet für jedes Paar, wie viel Distanz gespart wird, wenn beide in derselben Tour bedient werden statt in zwei getrennten Fahrten. Anschließend geht er die Paare nach fallender Ersparnis durch und verschmilzt die zugehörigen Touren, sofern beide Kunden Tourendpunkte sind und die kombinierte Last die Kapazität einhält.

Was ist die Mindestzahl an Fahrzeugen in einem CVRP?

Mindestens der Gesamtbedarf geteilt durch die Kapazität eines Fahrzeugs, aufgerundet. Das ist eine aus dem Bin-Packing-Problem abgeleitete untere Schranke, sofort berechenbar und nützlich, um zu erkennen, ob eine Lösung mit wenigen Fahrzeugen möglich ist, und um die Qualität der aktuellen Lösung einzuschätzen.

Wofür wird das CVRP verwendet?

Für die Planung von Warenzustellung, Lebensmittel- und Getränkedistribution, Containerlogistik, Abfallsammlung und Filialbelieferung. Es ist das Standardmodell überall dort, wo eine Flotte mit endlicher Kapazität eine Menge von Kunden mit bekannten Bedarfen von einem zentralen Depot aus bedienen muss.