假設我有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