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

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.