Approximate Dynamic Programming für mehrperiodisches Taxi-Dispatching

Taxis spielen als Transportmittel vor allem im innerstädtischen Bereich eine große Rolle. Meist erfolgt die Steuerung der Taxiflotten jedoch über einfache Heuristiken, welche die vielen Unsicherheiten des Zuordnungsproblems nicht adäquat berücksichtigen und somit zu ineffizienten Lösungen führen.

Im Rahmen dieser Arbeit wird das Problem Aufträge zu Taxis zuzuordnen als das allgemeine dynamische Taxi-Dispatching-Problem mit mehrperiodischen Fahrzeiten definiert. Zur Lösung des Problems werden die Grundlagen des Approximate Dynamic Programmings (ADP) dargelegt und auf das Taxi-Dispatching-Problem angewendet. Dabei werden verschiedene Methoden zur Wertfunktionsapproximation innerhalb des ADPs verglichen. Resultierend zeigt sich anhand realer Taxidaten aus New York City, dass eine Anwendung des Verfahrens in Echtzeit möglich ist und zu hohen Erlössteigerungen für den Taxi-Dispatcher führt. Gleichzeitig wird aufgezeigt, wann sich welche Wertfunktionsapproxmationsmethode für einen erlösmaximierenden Taxi-Dispatcher eignet.