自2009/01/01 以來已有 人次上線瀏覽         Feed on Posts or Comments

Google Map 廖泫銘 on 04 四月 2012 11:10 下午

運用Google Map API解決旅行業務員問題(Traveling Salesman Problem)

旅行業務員問題 (Traveling Salesman Problem) 是個有名的難題(這是個 NP-Hard 問題),旅行業務員要到 n 個城市推展業務,n 個城市分別以 1,2,…,n 表示, 從 1 出發,只經過每個城市一次,最後再回到 1,假設 Cij 表城市 i 到城市 j 的旅行成本,問題為找出一個最小成本的路徑。如果對應到真實世界,就比方說物流車要送貨到 n 個地點,要尋求最便捷的路線,以減少物流的時間與油費。類似的問題還有旅遊路線規劃、探訪路線規劃等等。

現有的Google Map路徑規畫是指定兩點或多點來依序規畫路線,但卻沒有辦法一次給指定多點進行最佳路線規劃。此時,有幾個方式可以克服這個困難:

  1. 自行開發程式,例如利用已經別人開發好的API”TSP Solver for Google Maps API“來進行解算。
  2. 利用別人開發好的Web App,例如OptiMap – Fastest Roundtrip Solver

不過在使用上仍須注意,不要一次給太多要納入規劃的點位,因為計算複雜度 (computational complexity) 回隨著n值呈指數上升,在n值相當大時,往往只能求得近似路徑而非最佳路徑。

2 Responses to “運用Google Map API解決旅行業務員問題(Traveling Salesman Problem)”

  1. on 26 五月 2012 at 14:38:45 1.Prada Schuhe said …

    Good job! I have found many articles to read but you do a good thing. That is a boy. Thank you so much for sharing the delicious post. Expect your next article

  2. on 26 五月 2012 at 14:48:07 2.Classic Chanel Bags said …

    Generally I do not post on blogs, but I would like to say that this post really forced me to do so, Excellent post!

Trackback This Post | Subscribe to the comments through RSS Feed

Leave a Reply