Calculating taxi movements

Question

Let's say I have N taxis, and N customers waiting to be picked up by the taxis. The initial positions of both customers and taxis are random/arbitrary.

Now I want to assign each taxi to exactly one customer.

The customers are all stationary, and the taxis all move at identical speed. For simplicity, let's assume there are no obstacles, and the taxis can move in straight lines to assigned customers.

I now want to minimize the time until the last customer enters his/her taxi.

Is there a standard algorithm to solve this? I have tens of thousands of taxis/customers. Solution doesn't have to be optimal, just ‘good’.

The problem can almost be modelled as the standard “Assignment Problem”, solvable using the Hungarian algorithm (the Kuhn–Munkres algorithm or Munkres assignment algorithm). However, I want to minimize the cost of the costliest assignment, not minimize the sum of costs of the assignments.

Answer 1

I'm not sure that the Hungarian algorithm will work for your problem here. According to the link, it runs in n ^ 3 time. Plugging in 25,000 as n would yield 25,000 ^ 3 = 15,625,000,000,000. That could take quite a while to run.

Since the solution does not need to be optimal, you might consider using simulated annealing or possibly a genetic algorithm instead. Either of these should be much faster and still produce close to optimal solutions.

If using a genetic algorithm, the fitness function can be designed to minimize the longest period of time that an individual would need to wait. But, you would have to be careful because if that is the sole criteria, then the solution won't work too well for cases when there is just one cab that is closest to the passenger that is furthest away. So, the fitness function would need to take into account the other waiting times as well. One idea to solve this would be to run the model iteratively and remove the longest cab trip (both cab & person) after each iteration. But, doing that for all 10,000+ cabs/people could be expensive time wise.

I don't think any cab owner or manager would even consider minimizing the waiting time for the last customer entering his cab over minimizing the sum of the waiting time for all cabs - simply because they make more money overall when minimizing the sum of the waiting times. At least Louie DePalma would never do that... So, I suspect that the real problem you have has little or nothing to do with cabs...

Answer 2

For an optimal solution: construct a weighted bipartite graph with a vertex for each taxi and customer and an edge from each taxi to each customer whose weight is the travel time. Scan the edges in order of nondecreasing weight, maintaining a maximum matching of the subgraph containing the edges scanned so far. Stop when the matching is perfect.

Answer 3

Since you mentioned Hungarian Algorithm, I guess one thing you could do is using some different measure of distance rather than the euclidean distance and then run t Hungarian Algorithm on it. For example, instead of using

d = sqrt((x0 - x1) ^ 2 + (y1 - y0) ^ 2)

use

d = ((x0 - x1) ^ 2 + (y1 - y0) ^ 2) ^ 10

that could cause the algorithm to penalize big numbers heavily, which could constrain the length of the max distance.

EDIT: This paper "Geometry Helps in Bottleneck Matching and Related Problems" may contains a better algorithm. However, I am still in the process of reading it.

Answer 4

A "good" algorithm that would solve your problem is a Greedy Algorithm. Since taxis and people have a position, these positions can be related to a "central" spot. Sort the taxis and people needing to get picked up in order (in relation to the "centre"). Then start assigning taxis, in order, to pick up people in order. This greedy rule will ensure taxis closest to the centre will pick up people closest to the centre and taxis farthest away pick up people farthest away.

A better way might be to use Dynamic Programming however, I am not sure nor have the time to invest. A good tutorial for Dynamic Programming can be found here