💻 computer science

A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

Dieses Paper stellt ILS+SP vor, eine hybride Metaheuristik, die Iterated Local Search mit einer Set-Partitioning-Postoptimierung kombiniert, welche die bestehenden State-of-the-Art-Methoden zur Lösung des Family Capacitated Vehicle Routing Problem signifikant übertrifft, indem sie nahezu optimale Lösungen für großskalige Benchmark-Instanzen erzielt.

Ursprüngliche Autoren: Bruno Oliveira, Diogo Lima, Marcos Roboredo

Veröffentlicht 2026-07-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bruno Oliveira, Diogo Lima, Marcos Roboredo

Originalarbeit lizenziert unter CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Manager eines Lieferunternehmens. Sie verfügen über eine Flotte identischer LKWs, die alle von einem zentralen Lagerhaus aus starten. Ihre Aufgabe ist es, Pakete an verschiedene Kunden zu liefern.

Aber hier ist der Clou: Ihre Kunden sind nicht einfach nur Einzelpersonen; sie sind in Familien organisiert. Zum Beispiel hat die „Familie Smith“ fünf Häuser in verschiedenen Straßen, aber Ihr Vertrag schreibt nur vor, dass Sie zwei dieser Häuser beliefern müssen. Die „Familie Garcia“ hat drei Häuser, aber Sie müssen nur eines besuchen.

Dies ist das Family Capacitated Vehicle Routing Problem (F-CVRP). Es ist ein riesiges Rätsel mit zwei Hauptregeln:

Die Familien-Regel: Sie müssen genau die Anzahl an Häusern besuchen, die für jede Familie erforderlich ist, aber Sie können wählen, welche spezifischen Häuser Sie besuchen.
Die LKW-Regel: Jeder LKW hat eine Gewichtsgrenze (Kapazität). Sie dürfen ihn nicht überladen.

Das Ziel ist einfach: Finden Sie den günstigsten Weg, um alle LKWs zu fahren, um diese Regeln zu erfüllen, ohne Benzin oder Zeit zu verschwenden.

Das Problem: Es ist zu schwer, es perfekt zu lösen

Mit der Anzahl der Familien und Häuser wächst die Zahl der möglichen Routen so stark an, dass selbst die schnellsten Supercomputer der Welt Jahre bräuchten, um die perfekte Antwort zu finden. Deshalb haben die Autoren Bruno, Diogo und Marcos einen „intelligenten Ratenden“ (eine Metaheuristik) entwickelt, um sehr schnell eine sehr gute Antwort zu finden.

Sie nennen ihre Lösung ILS+SP. Lassen Sie uns das unter Verwendung einer Kochanalogie aufschlüsseln.

Das Rezept: ILS+SP

1. Die „Iterated Local Search“ (ILS) – Der verkostende Koch

Stellen Sie sich einen Koch vor, der versucht, ein Suppenrezept zu perfektionieren.

Der Anfang: Der Koch bereitet eine Basis-Suppe zu (eine initiale Lösung).
Der Geschmackstest (Local Search): Der Koch probiert die Suppe und nimmt kleine Anpassungen vor: „Vielleicht eine Prise Salz mehr?“ oder „Tausche die Karotten gegen Kartoffeln aus?“ Er nimmt immer wieder diese kleinen Änderungen vor, um den Geschmack zu verbessern.
Der „Simulated Annealing“-Twist: Manchmal macht eine Änderung die Suppe vorübergehend schlechter. Ein normaler Koch würde dies sofort ablehnen. Aber dieser Koch nutzt eine spezielle Regel (Simulated Annealing): Wenn die Suppe nur ein wenig schlechter schmeckt, akzeptiert er es trotzdem. Warum? Weil man manchmal die Suppe ein wenig „schwierig“ machen muss, um später ein völlig neues, fantastisches Aromaprofil zu entdecken. Dies hilft ihm, aus „schlechten Nachbarschaften“ zu entkommen, in denen er bei einem mittelmäßigen Rezept feststeckt.
Das Aufschütteln (Perturbation): Wenn der Koch in einer Schleife aus kleinen Anpassungen stecken bleibt, die nicht helfen, unternimmt er etwas Drastisches: Er schüttet die Hälfte der Suppe aus und beginnt mit einer völlig neuen Kombination von Zutaten. Dies wird „Perturbation“ genannt. Es zwingt die Suche, in einem völlig neuen Teil der Küche nachzusehen.

Die Autoren haben dem Werkzeugkasten dieses Kochs eine spezielle Zutat hinzugefügt: MemberRelocate. Da dies ein „Familien“-Problem ist, tauscht der Koch nicht nur Zutaten aus; er tauscht Familienmitglieder aus. Wenn er das Haus Nr. 1 der Smiths besucht, fragt er vielleicht: „Warte, Haus Nr. 2 liegt näher. Lassen Sie uns Haus Nr. 1 gegen Haus Nr. 2 tauschen und sehen, ob das Zeit spart.“

2. Die „Set Partitioning“ (SP) – Der Meistereditor

Nachdem der Koch Stunden mit dem Verfeinern, Aufschütteln und Probieren verbracht hat, hat er ein riesiges Notizbuch voller verschiedener Suppen-Variationen (Routen) gesammelt, die er ausprobiert hat.

Der Schritt der Set Partitioning ist wie ein Meistereditor, der dieses gesamte Notizbuch durchsieht. Der Editor kocht nicht; er wählt nur aus. Er schaut sich alle besten „Suppen-Stücke“ an, die der Koch während des Tages hergestellt hat, und fragt: „Wenn ich diese spezifische Route von 10:00 Uhr morgens mit jener spezifischen Route von 14:00 Uhr kombiniere, kann ich daraus eine perfekte Mahlzeit machen?“

Dieser letzte Schritt stellt sicher, dass selbst wenn der Koch während des Kochprozesses die perfekte Kombination verpasst hat, der Editor sie findet, indem er die besten Teile des Arbeitstages mathematisch zusammenstellt.

Die Ergebnisse: Hat es funktioniert?

Die Autoren haben ihr „ILS+SP“-Rezept gegen die derzeit besten Methoden der Welt getestet.

Der Test: Sie verwendeten 144 große, schwierige Rätsel (mit über 50 Kunden), die andere Forscher bereits versucht hatten zu lösen.
Die Punktzahl: Ihre Methode hat in jedem einzelnen Fall gewonnen oder war gleichauf.
Die Verbesserung: Vor dieser Arbeit lagen die besten Methoden im Durchschnitt etwa 1,84 % von der perfekten Lösung entfernt. Die Methode der Autoren reduzierte diese Lücke auf 0,01 %. In der Welt der Logistik ist das so, als würde man von einer leicht daneben liegenden Schätzung zu einem fast jeden Mal ins Schwarze treffen gelangen.
Geschwindigkeit: Sie testeten es auch auf noch größeren Rätseln (bis zu 142 Kunden). Ihre Methode fand großartige Lösungen in durchschnittlich etwa 37 Sekunden.

Zusammenfassung

Das Paper präsentiert einen neuen, hybriden Weg zur Lösung eines komplexen Lieferrouting-Problems, bei dem man entscheiden muss, welche Familienmitglieder man besucht. Durch die Kombination eines „verkostenden Kochs“, der kluge, manchmal riskante kleine Änderungen vornimmt, mit einem „Meistereditor“, der die besten Teile des Arbeitstages zusammenstellt, haben sie ein Werkzeug geschaffen, das schneller und genauer ist als alles bisher für dieses spezifische Problem veröffentlichte.

Technisches Resümee: Eine hybride Metaheuristik für das Family Capacitated Vehicle Routing Problem

Problemdefinition

Die Arbeit befasst sich mit dem Family Capacitated Vehicle Routing Problem (F-CVRP), einer Verallgemeinerung des Family Traveling Salesman Problem (FTSP) und des klassischen Capacitated Vehicle Routing Problem (CVRP). Beim F-CVRP fährt eine homogene Flotte von $K$ Fahrzeugen mit Kapazität $Q$ von einem einzigen Depot aus, um eine Menge von Kunden zu bedienen, die in Familien unterteilt sind. Im Gegensatz zum Standard-CVRP, bei dem jeder Kunde besucht werden muss, erfordert das F-CVP, dass eine spezifische Anzahl von Mitgliedern ( $v_l$ ) jeder Familie $l$ besucht wird, während die übrigen Mitglieder dieser Familie unbesucht bleiben können. Das Ziel ist es, die Gesamtkosten der Routenplanung zu minimieren, während die Fahrzeugkapazitätsbeschränkungen eingehalten und die exakten Besuchsanforderungen für jede Familie erfüllt werden.

Mit zunehmender Skalierung der Probleminstanzen werden exakte Methoden rechentechnisch prohibitiv. Folglich konzentriert sich die Arbeit auf die Entwicklung einer schnellen, hochwertigen Heuristik, die in der Lage ist, Lösungen innerhalb enger Zeitbudgets zu liefern, und die sowohl als eigenständiger Solver als auch als Lieferant von Primarschranken für exakte Frameworks dient.

Methodik: Die ILS+SP Hybrid-Metaheuristik

Die Autoren schlagen ILS+SP vor, eine hybride Metaheuristik, die einen Iterated Local Search (ILS) Rahmen mit einer Set Partitioning (SP) Post-Optimierungsphase kombiniert. Der Algorithmus arbeitet wie folgt:

1. Iterated Local Search (ILS) Kern

Die Suche wird durch einen ILS-Rahmen gesteuert, der einen Pool von Routen ( $P$ ) verwaltet und die beste gefundene zulässige Lösung ( $s^*$ ) verfolgt.

Initiallösung: Erzeugt mittels einer Best Parallel Insertion (BPI) Heuristik, die $K$ Routen erstellt, indem Kunden iterativ eingefügt werden, um Kostensteigerungen zu minimieren und dabei sicherzustellen, dass die Besuchszahlen der Familien erfüllt werden.
Lokale Suche (RVND): Die lokale Suche verwendet eine Random Variable Neighborhood Descent (RVND) Strategie. Sie exploriert ein Portfolio von neun Nachbarschaften:
- Inter-Route (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
- Intra-Route (3): Exchange, Reinsertion, Or-opt2.
- Spezialisiert (1): MemberRelocate, ein problemspezifischer Operator, der ein besuchtes Kundenmitglied entfernt und ein nicht besuchtes Mitglied derselben Familie an der besten Position über alle Routen hinweg einfügt.
- Alle Nachbarschaften wahren die strukturellen Beschränkungen der Familienbesuchszahlen und der Anzahl der aktiven Routen ( $K$ ).
Akzeptanzkriterium: Im Gegensatz zur Standard-Lokalsuche akzeptiert der Algorithmus verschlechternde Züge basierend auf einem Simulated Annealing (SA) Kriterium mit einem zeitgesteuerten Cooling Schedule. Dies ermöglicht es der Suche, aus lokalen Minima zu entkommen.
Perturbation: Um die Suche zu diversifizieren, wendet der Algorithmus eine von drei zufälligen Perturbationen (RandomSwap, RandomShift oder RandomMemberRelocate) auf die aktuelle Lösung an, bevor er die lokale Suche erneut betritt.
Strafhandhabung: Kapazitätsverletzungen werden über einen dynamischen Strafkoeffizienten ( $\theta$ ) in der Zielfunktion gehandhabt, der basierend auf der Zulässigkeit der aktuellen Lösung angepasst wird, um die Suche in zulässige Regionen zu leiten.

2. Set Partitioning (SP) Post-Optimierung

Nach Erschöpfung des Zeitbudgets führt der Algorithmus einen finalen Optimierungsschritt durch. Er formuliert ein Set Partitioning Problem über den Pool der kapazitätszulässigen Routen ( $P$ ), der während des gesamten Suchprozesses gesammelt wurde.

Das SP-Modell wählt eine Teilmenge von Routen aus, um die Gesamtkosten zu minimieren, während die Besuchsanforderungen der Familien erfüllt und exakt $K$ Routen verwendet werden.
Da der Pool $P$ die Routen enthält, aus denen die bisher beste Lösung ( $s^*$ ) besteht, ist die optimale Lösung des SP garantiert mindestens so gut wie $s^*$ .

Wesentliche Beiträge

Die Arbeit hebt vier primäre Beiträge hervor, die diese Arbeit vom aktuellen Stand der Technik (speziell dem ILS von Bernardino und Paias, 2024) unterscheiden:

Hybridisierung mit Set Partitioning: Die Einführung einer SP Post-Optimierungsphase zur Re-Optimierung des Routen-Pools, eine Matheuristik-Komponente, die in früheren Ansätzen fehlte.
Verbesserte lokale Suche: Die Implementierung der MemberRelocate Nachbarschaft, welche nicht besuchte Familienmitglieder optimal in die beste Position über alle Routen hinweg einfügt, statt sie lediglich an Ort und Stelle auszutauschen.
Randomisierte Nachbarschaftsexploration: Die Verwendung von RVND zur Randomisierung der Reihenfolge der Nachbarschaftsexploration, im Gegensatz zur festen Reihenfolge in der bisherigen Literatur.
Simulated Annealing Akzeptanz: Die Anwendung eines SA-Kriteriums zur Akzeptanz verschlechternder Lösungen, welches das strikte Verbesserung-nur-Prinzip früherer Methoden ersetzt und somit das Gleichgewicht zwischen Intensivierung und Diversifizierung verbessert.

Kompütationsergebnisse

Die Autoren evaluierten ILS+SP auf zwei Benchmark-Sets:

Standard-Benchmark (144 Instanzen): Abgeleitet aus dem Augerat et al. (1995) Set, das Instanzen mit mehr als 50 Kunden enthält.
- Performance: Die Methode hat bei jeder Instanz gegen die State-of-the-Art Heuristik von Bernardino und Paias (2024) gewonnen oder war gleichauf.
- Gap-Reduktion: Die durchschnittliche Lücke zur Best Known Solution (BKS) wurde von 1,84 % (vorheriger Bestwert) auf 0,01 % reduziert.
Skalierbarkeits-Benchmark (120 Instanzen): Ein neues Set größerer Instanzen (bis zu 142 Kunden), abgeleitet aus dem CVRP Set X (Uchoa et al., 2017).
- Performance: Der Algorithmus erreichte eine durchschnittliche Lücke von 0,47 % bei einer durchschnittlichen Laufzeit von 37 Sekunden, was die Skalierbarkeit auf größere Problemgrößen demonstriert.

Bedeutung und Ansprüche

Die Arbeit positioniert ILS+SP als eine robuste und skalierbare Lösung für das F-CVRP. Die Autoren behaupten, dass durch die Integration einer Matheuristik-Post-Optimierung (SP) mit einem anspruchsvollen ILS-Framework, das problemspezifische Nachbarschaften und SA-Akzeptanz nutzt, die Methode bestehende Heuristiken signifikant übertrifft. Die Ergebnisse legen nahe, dass der Ansatz nicht nur in der Lage ist, die besten bekannten Lösungen für etablierte Benchmarks zu erreichen oder zu verbessern, sondern auch effektiv auf größere, komplexere Instanzen skaliert, was ihn zu einem wertvollen Werkzeug sowohl für die eigenständige Anwendung als auch für die Integration in exakte Lösungsframeworks macht.