2 ms·

I don't understand why they're bringing the traveling salesman problem into this at all. The core problem Uber has to solve is simply to get one driver (of man

by 9999 16y ago

I don't understand why they're bringing the traveling salesman problem into this at all. The core problem Uber has to solve is simply to get one driver (of many) to the customer as fast as possible, not to determine the most efficient route between all of the customers.

kragen 16y ago
It's not that simple. They need to figure out which assignment of drivers to customers maximizes some utility function. If they just send the closest available driver, that may degrade service for some other customer, or leave an important area of the city uncovered for the next unexpected call. It's not the same problem as TSP, but it's surely reducible to it, given the NP-completeness proof.