A.I.R 和google maps有什麼不同？

A.I.R是奇點無限推出的調度派遣SaaS/PaaS是嶄新的物流業排線服務，不論參展、客戶拜訪各種場合，我們總被評論『噢！幫車隊安排最佳路線，這google maps不是就有了嗎？』

這就要從『調度派遣』、『最佳路線』這些詞到底在講什麼說起，如果我的『最佳路線』和你的『最佳路線』在語意和定義上沒有對齊，那就是雞同鴨講。

絕大部分的人聽到最佳路線，直覺會想到google maps上的『規劃路線』

google maps的規劃路線

Google maps上的『規劃路線』是規劃兩點間的最佳路徑，例如上面那個例子。但是A.I.R是在幫物流車規劃『多個送貨點怎麼送才可以最快送完』的路線。通常這樣回答還不能說服聽眾。

『Google maps也可做多個點個規劃ㄚ！』

聽眾想像的是上面這個東西。

『你看這不就跟你做的一樣嗎？』。

Google maps的多點最短路徑規劃還是解決『兩點間的最佳路徑』。雖然使用者可以在google maps上的『新增目的地』新增地點，但是google maps給你的答案是依照你給的順序，告訴你點到點的最佳路徑。

但是物流車的問題並不是『點到點怎麼走？』，而是如果我要從1出發要送貨到2,3,4然後再回到1，請問2,3,4的順序是什麼才能夠最快送完？

有沒有發現？物流車的問題完全不是google maps的多點路線規劃！我們說的『最佳路線』，是『找出送貨點的順序』，司機想要解決的是『這麼多地方要送，怎樣的順序才會快？』

所以google maps不能做物流車要的『最佳路線』。

錯！google maps可以做，但是你找不到！

google maps的waypoints optimization

Google maps在今年第三季開放了waypoints optimization，就可以做到A.I.R的極小部分功能。你可以把waypoints想像成送貨點。

Google maps在API文件說：基本上，Directions服務只依據使用者提供的waypoints順序去計算waypoints之間的最佳路徑。如果使用者要的是找出這些waypoints最佳的順序，請加上適當參數，這google maps提供的這個功能就是圖論中的旅行推銷員問題(Traveling salesman problem, TSP)，如下圖。

算最佳順序很難嗎？

這種問題是吃CPU資源怪獸，以上圖為例，如果推銷員要跑37個客戶，那麼可能的組合就有37!種(請自己按計算機，應該會給你一個E)。37!大約是1.37x10^43這麼大的數字。

這個數字就是天文數字，因為目前我們可見宇宙的原子數總數也大約是10^80個原子，而一個推銷員要跑37個地方的路線組合就要10^43這麼多了。

如果以國內那幾大物流車隊，平均一輛3.5噸的堅達一天要送100個地點，100!=9.3x10^157種組合。

組合問題算是數學家和電腦科學家一直想要提升計算效能的題目，只是這種問題複雜到當今最強的超級電腦，在某些問題上，都要解幾萬年才解得出來。(待續)