Modifiziertes Verfahren des “Dynamic Programming“ zur Lösung eines speziellen Travelling Salesman Problems bei der optimalen Routenberechnung Bedarfsgesteuerter Busse

Wichtige Aufgabe bei der Steuerung Bedarfsgesteuerter Busse ist die Berechnung der Optimalroute. Die Optimalroutenberechnung läßt sich auf die Lösung eines speziellen asymmetrischen Travelling Salesman Problems zurückführen. Kennzeichen dieses Reihenfolgeproblems sind die Einschränkung der zulässigen Permutationen und die Einführung von Doppelknoten. Unter Berücksichtigung dieser Restriktionen und zusätzlicher Anforderungen wird ein modifiziertes Verfahren des Dynamic Programming vorgestellt, welches vergleichsweise geringen Speicherplatz und wenig Rechenzeit benötigt und sich für die Echtzeitberechnung der Optimalroute eignet.