假设我有 N 辆出租车，有 N 个顾客在等出租车接。客户和出租车的初始位置是随机/任意的。
现在我想将每辆出租车分配给一位顾客。
顾客都静止不动，出租车都以相同的速度行驶。为简单起见，我们假设没有障碍物，出租车可以直线移动到指定的客户。
我现在想尽量减少直到最后一位顾客进入他/她的出租车的时间。
有没有解决这个问题的标准算法？我有成千上万的出租车/客户。解决方案不必是最佳的，只要“好”即可。
该问题几乎可以建模为标准的“分配问题”，可以使用匈牙利算法（Kuhn-Munkres 算法或 Munkres 分配算法）解决。但是，我想最小化最昂贵任务的成本，而不是最小化任务的成本总和。
既然您提到了匈牙利算法，我想您可以做的一件事是使用一些不同的距离度量而不是欧几里德距离，然后在其上运行匈牙利算法。例如，而不是使用
d = sqrt((x0 - x1) ^ 2 + (y1 - y0) ^ 2)
采用
d = ((x0 - x1) ^ 2 + (y1 - y0) ^ 2) ^ 10
这可能会导致算法严重惩罚大数字，这可能会限制最大距离的长度。
编辑：本文“几何有助于瓶颈匹配和相关问题”可能包含更好的算法。但是，我仍在阅读它的过程中。
我不确定匈牙利算法是否可以解决您的问题。根据链接，它运行 n ^ 3 次。将 25,000 代入 n 将产生 25,000 ^ 3 = 15,625,000,000,000。这可能需要相当长的时间才能运行。
由于解决方案不需要是最优的，您可以考虑使用模拟退火或可能的遗传算法。这些中的任何一个都应该更快，并且仍然会产生接近最佳解决方案。
如果使用遗传算法，可以设计适应度函数以最小化个人需要等待的最长时间。但是，您必须小心，因为如果这是唯一的标准，那么当只有一辆出租车最靠近最远的乘客时，该解决方案将无法很好地工作。因此，适应度函数还需要考虑其他等待时间。解决这个问题的一个想法是迭代地运行模型，并在每次迭代后删除最长的出租车行程（包括出租车和人）。但是，为所有 10,000 多辆出租车/人这样做可能会耗费大量时间。
我认为任何出租车车主或经理都不会考虑将最后一位进入出租车的顾客的等待时间最小化，而不是尽量减少所有出租车的等待时间总和——仅仅是因为他们在最大限度地减少等待总和时总体上赚了更多的钱次。至少路易·德帕尔玛（Louie DePalma）永远不会那样做...所以，我怀疑您遇到的真正问题与出租车几乎没有关系...
为了获得最佳解决方案：构建一个加权二分图，其中每个出租车和客户都有一个顶点，每个出租车到每个客户的边都有一条边，其权重是行程时间。以非递减权重的顺序扫描边缘，保持包含到目前为止扫描的边缘的子图的最大匹配。当匹配完美时停止。