Studie: Lernfähige Algorithmen für die Transportplanung

Entwicklung eines selbstlernenden Optimierungsverfahrens für die Transportplanung

Nahezu alle erfolgreichen Verfahren zur Lösung von Tourenplanungsproblemen beruhen auf lokalen Suchverfahren: Dabei werden ausgehend von einer vergleichsweise schlechten Anfangslösung verschiedene Transformationen vorgenommen, um schrittweise zu besseren Lösungen zu gelangen. Diese einfachen Transformationen werden als Nachbarschaftsschritte bezeichnet. Von lokaler Suche spricht man, da die reine Anwendung dieser verbessernden Nachbarschaftsschritte in einem lokalen Optimum mündet, dessen Lage von der Anfangslösung und den angewandten Nachbarschaften abhängig ist.

Um lokale Optima wieder zu verlassen und den Lösungsraum weiträumiger zu durchsuchen, ist eine übergeordnete Heuristik vonnöten – die klassischen Vertreter dieser Verfahren bezeichnet man als Metaheuristik. Sie beziehen maximal die kurz zuvor gewählten Aktionen in ihre Entscheidungspolitik ein ohne die Historie des Suchweges zu berücksichtigen. Die im Vorhaben entwickelte Structure Guided Local Search hingegen versucht, auf der Grundlage von Erfahrungen Strukturmerkmale im Lösungsraum zu identifizieren, die den gezielten Einsatz niederer Heuristiken ermöglichen.

In der Forschungsarbeit wird dieses Verfahren mit einem besonderen Augenmerk auf diejenigen Komponenten untersucht und getestet, die die Eigenschaften der Lösung beschreiben. Im Ergebnis konnten mit der Studie vielversprechende Ergebnisse für Benchmarkinstanzen erzielt werden.