Neues CP-Modell: Sequence Variables erleichtern Fahrzeug‑Routing
Ein kürzlich auf arXiv veröffentlichter Beitrag präsentiert ein neues Konzept für Constraint Programming (CP), das die Modellierung von Fahrzeug-Routing-Problemen deutlich vereinfacht. Im Gegensatz zu klassischen Successor‑Modellen, die oft mit optionalen Besuchspunkten und Einfügeheuristiken kämpfen, nutzt das vorgestellte Modell sogenannte Sequence Variables. Diese ermöglichen die direkte Handhabung von optionalen Stopps und unterstützen Einfügeheuristiken, darunter auch die Large‑Neighborhood‑Search‑Methode.
Der Artikel liefert eine klare Definition des neuen Domänenbereichs, beschreibt die notwendigen Update‑Operationen und führt verschiedene Konsistenz‑Levels für die damit verbundenen Constraints ein. Zudem wird eine Implementierung vorgestellt, die die erforderlichen Datenstrukturen für die Integration in bestehende trail‑basierte CP‑Solver aufzeigt. Speziell entwickelte globale Constraints für Sequence Variables und Fahrzeug‑Routing runden das Paket ab. In einer Testreihe am Dial‑a‑Ride‑Problem zeigt sich, dass die neue Herangehensweise die Modellierung vereinfacht und gleichzeitig konkurrenzfähige Rechenzeiten erzielt.