Methoden und Verfahren

Für die Lösung der bis jetzt vorliegenden gemischt-ganzzahligen Linearen Programme wird der Solver CPLEX verwendet. Es ist zu beachten, dass die Lösung solcher Programme grundsätzlich schwer ist, und es demzufolge sehr wichtig ist, gute Formulierungen der abzubildenden Zusammenhänge zu finden. Die vorliegenden Modelle unterscheiden sich bezüglich ihrer Rechenbarkeit teilweise erheblich, weshalb einige Aufmerksamkeit auf das Finden guter zusätzlicher Nebenbedingungen verwendet werden muss. Aber auch lokale Suchstrategien (Heuristiken) stellen ein geeignetes Hilfsmittel, zumindest als Unterstützung der eigentlichen Optimierungsvorgänge, dar.

Verwaltet werden Zeitfenster an jeder Kante. Diese stellen diejenigen Zeitintervalle dar, in denen die Kante - aufgrund der bereits gerouteten AGVs - noch befahren werden darf.

Die derart formulierten zeitlichen Sperrungen gelten in Abhängigkeit von den Dimensionen der AGVs. Hierzu werden in einem Preprocessing-Schritt zu jeder Kante Listen von geogaphisch abhängigen Kanten erzeugt. Eine Kante ist dabei geographisch abhängig, falls sie nicht gleichzeitig befahren werden können, d.h. falls die Polygone, die die Fahrt auf der jeweiligen Kante beschreiben, sich schneiden.

In der Online-Berechnung wird ein sogenannter kürzester Weg mit Zeitfenstern berechnet. D.h. es wird eine Route berechnet, die zeitlich innerhalb der Zeitfenster liegt. Algorithmisch wird hierzu ein verallgemeinerter Dijkstra-Algorithmus verwendet, Intervalle als Teil der Labelinformation verwaltet.