MIT’s Super-Efficient Dispatching Algorithm Minimizes a City’s Taxi Fleet
Times Square, New York City, New York State, Night, Taxi
By giving due weight to minimizing the distance between a taxi’s destination and the origin of its next potential trip, the model moves more passengers per vehicle over a given period of time.
A perfect solution would lay to rest the famous Traveling Salesman Problem, which tries to find the shortest path a salesman must take to hit every spot on his route. That problem quickly becomes intractable, however, as the number of spots increases. You could solve it for Mayberry, but not for Manhattan.
Instead, the MIT researchers created what they call a vehicle sharing network, similar to the network they used in 2014 for optimizing ride sharing. It looks like a graph in which each node represents a trip and each line linking two nodes represents a pair of trips that one vehicle can handle. Manipulating the layout of the graph provides ways of improving (if not perfecting) the solution.
See the full story here: https://spectrum.ieee.org/cars-that-think/transportation/mass-transit/mit-finds-mathy-way-to-minimize-taxi-fleet