運用Google Map API解決旅行業務員問題(Traveling Salesman Problem)
http://gis.rchss.sinica.edu.tw/google/?p=4221
旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題(這是個 NP-Hard 問題),旅行業務員要到 n 個城市推展業務,n 個城市分別以 1,2,…,n 表示, 從 1 出發,只經過每個城市一次,最後再回到 1,假設 Cij 表城市 i 到城市 j 的旅行成本,問題為找出一個最小成本的路徑。如果對應到真實世界,就比方說物流車要送貨到 n 個地點,要尋求最便捷的路線,以減少物流的時間與油費。類似的問題還有旅遊路線規劃、探訪路線規劃等等。
現有的Google Map路徑規畫是指定兩點或多點來依序規畫路線,但卻沒有辦法一次給指定多點進行最佳路線規劃。此時,有幾個方式可以克服這個困難:
現有的Google Map路徑規畫是指定兩點或多點來依序規畫路線,但卻沒有辦法一次給指定多點進行最佳路線規劃。此時,有幾個方式可以克服這個困難:
- 自行開發程式,例如利用已經別人開發好的API"TSP Solver for Google Maps API"來進行解算。
- 利用別人開發好的Web App,例如OptiMap – Fastest Roundtrip Solver

沒有留言:
張貼留言