Planung optimaler Pfade für multiple Roboter auf Grafen

In diesem Papier untersuchen wir das Problem der optimalen Pfadplanung für mehrere Roboter (MPP) auf Grafen. Wir schlagen zwei auf Multiflow basierende Modelle der ganzzahligen linearen Programmierung (ILP) vor, die die minimalen Ankunftszeiten und die minimale Gesamtdistanz für unsere MPP-Formulierung berechnen. Die resultierenden Algorithmen aus diesen ILP-Modellen sind vollständig und garantieren echte optimale Lösungen. Darüber hinaus kann unser flexibles Rahmenwerk leicht andere Varianten des MPP-Problems aufnehmen. Fokussiert auf den zeitoptimalen Algorithmus bewerten wir dessen Leistung, sowohl als eigenständigen Algorithmus als auch als generische Heuristik zur schnellen Lösung großer Problemstellungen. Die computergestützten Ergebnisse bestätigen die Effektivität unserer Methode.