An Assignment-Based Approach to Efficient Real-Time City-Scale Taxi Dispatching

This study proposes and evaluates an efficient real-time taxi dispatching strategy that solves the linear assignment problem to find a globally optimal taxi-to-request assignment at each decision epoch. The authors compare the assignment-based strategy with two popular rule-based strategies. They evaluate dispatching strategies in detail in the city of Berlin and the neighboring region of Brandenburg using the microscopic large-scale MATSim simulator. The assignment-based strategy produced better results for both drivers (less idle driving) and passengers (less waiting). However, computing the assignments for thousands of taxis in a huge road network turned out to be computationally demanding. Certain adaptations pertaining to the cost matrix calculation were necessary to increase the computational efficiency and assure real-time responsiveness.

Online Taxi Dispatching

Choosing the right simulator is of the utmost importance. Commercial micro- or nanosimulators, such as Vissim, Aimsun, Paramics, and DynusT, either are unable to perform network loadings with millions of persons or vehicles, or they do not trace persons or vehicles throughout the whole day. Noncommercial approaches include the Transportation Analysis Simulation System (TRAN-SIMS),¹³ Simulation of Urban Mobility (SUMO),¹⁴ Mezzo,¹⁵ and the Multi-Agent Transport Simulator (MATSim).¹⁶ Out of these, MATSim is arguably the least focused on traffic flow realism, but has the highest computing speed and the best behavioral model on the trip-planning side; therefore, we chose it as the simulation platform. To simulate taxi dispatching, we used MATSim's Dynamic Vehicle Routing Problem (DVRP) extension.¹⁷ In this module, each driver is modeled as an agent whose schedule is dynamically reoptimized by the optimization algorithm in response to incoming events (such as request submissions and vehicle departures and arrivals). Fleet vehicles are simulated along with the whole traffic, and their movement is monitored in order to detect any divergences from the schedule (such as delays due to traffic congestion). Also, the interaction among the dispatcher, drivers, and passengers is simulated in detail, including such actions as calling a ride or picking up and dropping off passengers.