') ;?>
') ;?>
'); ?>
Routingprobleme sind aus kombinatorischer Sicht ,,schwere`` Probleme. Das heißt, dass wir nicht hoffen können, einen Algorithmus zu finden, der solche Probleme in jedem Fall in annehmbarer Zeit löst. Dies hat zur Entwicklung einer Vielzahl von Heuristiken geführt, also von Algorithmen, die auf den jeweiligen Anwendungsfall abgestimmt sind und hier eine vernünftige (wenn auch mathematisch zumindest nicht beweisbar optimale) Lösung liefern. Dennoch ist die Optimierung von Vehicle Routing Problemen immer eine faszinierende Forschungsaufgabe geblieben. Um die Schwierigkeiten zu verstehen, die das VRP beinhaltet, sollte man sich vor Augen führen, dass heute Instanzen des Traveling Salesman Problem mit mehreren tausend Knoten mit Branch-and-Cut-Methoden gelöst werden können, während beim VRP schon Instanzen mit über 70 Knoten eine große Herausforderung darstellen.
Am ZAIK wurde zu diesem Thema von Ulrich Blasum eine Dissertation angefertigt. Zur Lösung von VRP-Instanzen mittels Branch-and-Cut ist das Aufinden von geeigneten, verletzten Ungleichungen von zentraler Bedeutung. Im Rahmen der Dissertation wurden bisher bekannte Ungleichungstypen weiterentwickelt und neue gefunden. Ausserdem wurden Heuristiken und neue exakte Methoden zur Identifikation verletzter Ungleichungen entwickelt.
Dadurch gelang es erstmals zwei klassische Benchmarkinstanzen mit 76 Knoten auf einem einzelnen Prozessor zu lösen. Der im Rahmen der Arbeit entwickelte Code ist sehr effizient und findet die Lösungen innerhalb weniger Stunden, bisher verwendete Methoden benötigten mehrere Tage auf Parallelcomputern.
') ;?>
') ;?>
'); ?>