假设我有N辆出租车，并且有N位乘客等待被出租车接走。客户和出租车的初始位置是随机/任意的。计算出租车运动
现在我想给每个出租车分配到唯一客户。
的客户都是固定的，出租车都在相同的速度移动。为了简单起见，我们假设没有任何障碍，出租车可以直线移动到指定的客户。
我现在想，直至最后一位进入他/她的出租车降到最低的时候。
有没有一个标准的算法来解决这个问题？我有数以万计的出租车/客户。解决方案不一定是最优的，只是'好'。
该问题几乎可以模拟为标准的“分配问题”，可使用Hungarian algorithm（Kuhn-Munkres算法或Munkres分配算法）解决。但是，我希望最大限度地降低最昂贵的分配的成本，而不是最小化分配的成本总和。
既然你提到了匈牙利算法，我想你可以做的一件事是使用一些不同的测量距离而不是欧式距离，然后运行匈牙利算法。例如，代替使用
d = SQRT（（X0 - X1）^ 2 +（Y1 - Y0）^ 2）
使用
d =（（X0 - X1）^ 2 + （y1 - y0）^ 2）^ 10
这可能会导致算法严重惩罚大数，这可能会限制最大距离的长度。
编辑：本文“几何有助于瓶颈匹配和相关 问题”可能包含更好的算法。但是，我仍然在阅读它。
非常好的方法。这是在其被定义为e ^'的总和的软* *最小的精神（ - d（X，Y）/ T）'在所有'（X，Y）'，其中'T'是参数确定最低限度应该如何硬/软。在'T - > 0'的极限内，它接近'min d（x，y）'。 – blubb 2013-04-10 20:44:26
啊，非常聪明！我相信这可以解决我的所有实际问题！ – 2013-04-10 20:56:22
“良好”的算法，将解决你的问题是Greedy Algorithm。由于出租车和人员有位置，这些位置可以与“中央”位置相关。按照顺序排列出租车和需要接载的人员（与“中心”相关）。然后开始分配出租车，以便按顺序接人。这种贪婪的规则将确保离中心最近的出租车接送离中心最近的人，最远的出租车接送最远的人。
一个更好的办法可能然而使用Dynamic Programming，我不知道也没有时间去投资。一个很好的动态规划教程可以找到here
谢谢您的回复！不幸的是，我尝试过的所有贪婪算法有时会产生不好的结果。例如，如果我正确地读出你的算法，它最终可能会以一个客户远中心的西部，一个出租车远远中心以东，作为最后的分配。我认为贪婪的方法不会产生好的结果。 – 2013-04-10 20:53:01
为获得最佳的解决方案：构建具有针对每个出租车和客户，并且从每个出租车到每个客户重量为旅行时间的边缘的顶点的加权二分图。按照非降低重量的顺序扫描边缘，保持包含到目前为止扫描的边缘的子图的最大匹配。当匹配完美时停止。
我猜测它的时间复杂度很可能是O（N^3），这与使用匈牙利算法一样糟糕。不过，无论如何，这是我所希望的那种回应。 – 2013-04-12 06:35:16
我不确定匈牙利算法是否适合您的问题。根据链接，它运行n 3次。如果以n计25,000，则产生25,000^3 = 156,250,000,000。这可能需要很长时间才能运行。
由于解决方案不需要最优化，因此可以考虑使用simulated annealing或可能使用genetic algorithm。这两者中的任何一个都应该快得多，并且仍然能够产生接近最优解的方案
如果使用遗传算法，适应度函数可以被设计成最小化的时候，一个人将需要等待的最长时间。但是，你必须要小心，因为如果这是唯一的标准，那么该解决方案将不适合的情况下工作也很好，当只有一个驾驶室最接近是最远的乘客。所以，健身功能也需要考虑其他等待时间。要解决这个问题的一个办法是将反复运行模型，并删除在每次迭代后最长的驾驶室行程（包括驾驶室&人）。但是，对于所有10,000多个出租车/人来说，这样做可能是昂贵的时间明智的。
我不认为任何出租车拥有者或经理甚至会考虑最小化最后一位客户进入他的出租车的等待时间，以最大限度地减少所有出租车的等待时间的总和 - 仅仅因为他们在最小化等待时间的总和。至少Louie DePalma永远不会这么做......所以，我怀疑你真正遇到的问题与驾驶室没什么关系......
好评。我很快就宣布解决问题。当然，这不是一个现实问题。真正的问题就是在最短的时间内将一组相同的点从一组位置移动到另一组位置。问题变得比我想象的要难得多，现在我只是好奇它是如何快速和优化地解决问题的。 – 2013-04-12 06:31:41
试着在[math.stackexchange.com]（http： //math.stackexchange.com），你可能会有更多的运气。 – Alan 2013-04-10 20:07:07
@Alan这听起来像一个典型的算法问题。 – Dukeling 2013-04-10 21:24:09