Weiszfeld算法的「公路」距離？

問題是要找到最小化在不同地區想要在同一地點見面的約100人的旅行距離的一點。旅行是乘汽車而不是飛機。Weiszfeld算法的「公路」距離？

假設我可以訪問一個API，根據任意兩點之間的高速公路出行，我可以找到滿足的最佳地點？

在其他Stackexchange站點上（gis.stackexchange.com/questions/65563/meeting-point-minimizing-travel-distance-for-participants）我得到了Weiszfeld算法來解決這個幾何中位數問題。

我懷疑千米距離複雜的問題，因爲它成爲可能卡住局部最小值。我不知道從哪裏開始。任何指針，將不勝感激。

來源

2013-07-09 seinecle

你能得到方向（即最短路徑上的中間點）以及距離嗎？ –

是的，我可以合理地期望訪問此信息。 – seinecle

我看到問題被擱置。我可以澄清嗎？這裏的問題相當困難，現有的經典問題解決方案（Weiszfeld算法找到交匯點）與我提出的解決類似問題（不是歐幾里得距離，而是駕駛距離）的解決方案確實存在很大差距。正因爲如此，目前還沒有代碼，因爲您需要提示哪種解決方案首先具有意義。將問題轉移到其他論壇？有廣泛的光盤。 Weiszfeld在SO上，這使得它成爲獲得知情建議的最佳場所。 – seinecle

即使它可能遭受當地最低限度，我會嘗試本地搜索，因爲道路網絡沒有對抗設計。選擇一個隨機起點，然後按如下所示進行迭代。計算從當前點到100個客戶的方向。評估方向中的每一個倒數第二站，並將點移至最佳位置。

來源

2013-07-09 13:23:55

如果考慮的距離是曼哈頓距離，那麼最佳交會點是其中x座標等於某個輸入點的x座標，y座標等於y座標的點之一，某些輸入點的座標。

來源

2013-07-09 11:28:57 Aravind

但這不是曼哈頓距離。根據高速公路的存在或不存在，點之間的距離是高度可變的。任何兩點之間的距離必須通過api呼叫來確定，例如谷歌地圖或mappy.com（在歐洲）的專門服務 – seinecle

@seinecle：我很抱歉，我不知道如何爲一般案件。 – Aravind

Weiszfeld算法的「公路」距離？

回答

相關問題