多點最優路徑規劃 - (商旅問題,拼車,餐飲配送,包裹配送,包裹取件,回程單)

postgresql , postgis , pgrouting , 商旅問題 , 拼車 , 餐飲配送 , 包裹配送 , 包裹取件 , 回程單

小長假，帶着一家人出去旅行，計劃好了去幾個地方，如何設計旅行線路是最優的？(裡面還涉及到路費，路途時間等因素)。

又比如 拼車，餐飲配送，包裹取件、配送，都包含最佳路徑計算的共性在裡面。

postgresql 在gis領域有這非常豐富的使用者和實際案例，路徑規劃方面，我之前寫過一篇關于包裹配送的文章

<a href="https://github.com/digoal/blog/blob/master/201611/20161114_01.md">《聊一聊雙十一背後的技術 - 物流、動态路徑規劃》</a>

在商旅問題，拼車，餐飲配送，包裹取件、配送，等諸多最佳路徑計算的需求方面，postgresql又是如何滿足需求的呢？

pgrouting library contains following features:

all pairs shortest path, johnson’s algorithm

all pairs shortest path, floyd-warshall algorithm

shortest path a*

bi-directional dijkstra shortest path

bi-directional a* shortest path

shortest path dijkstra

driving distance

k-shortest path, multiple alternative paths

k-dijkstra, one to many shortest path

traveling sales person

turn restriction shortest path (trsp)

解決 旅行、包裹配送、餐飲配送的問題

這個問題的定義如下，從一點出發，經過多點，回到起點。

given a collection of cities and travel cost between each pair, find the cheapest way for visiting all of the cities and returning to the starting point.

詳情

<a href="http://docs.pgrouting.org/latest/en/tsp-family.html#tsp">http://docs.pgrouting.org/latest/en/tsp-family.html#tsp</a>

pgr_tsp - returns a route that visits all the nodes exactly once.

從5出發，經過array[-1, 3, 5, 6, -6]，回到5。

pgr_euclediantsp - returns a route that visits all the coordinates pairs exactly once.

拼車的問題更加複雜一些，

從一個點出發（司機位置），經過多點（所有拼車乘客的上車地點），再去到多點（拼車乘客的下車地點）。

拼車的問題可以分為兩個階段來解決，

第一個階段，從司機位置到接上所有拼車乘客。

第二個階段，從最後一個乘客上車地點，到達所有乘客的下車地點。

兩個階段的規劃需求是一樣的，從一個點出發，經過多點，到達終點。

<a href="http://docs.pgrouting.org/latest/en/pgr_dijkstravia.html#pgr-dijkstravia">http://docs.pgrouting.org/latest/en/pgr_dijkstravia.html#pgr-dijkstravia</a>

given a list of vertices and a graph, this function is equivalent to finding the shortest path between vertexivertexi and vertexi+1vertexi+1 for all i&lt;size_of(vertexvia)i&lt;size_of(vertexvia).

所有用到的路由函數，點對點成本矩陣函數，請參考

<a href="http://pgrouting.org/">http://pgrouting.org/</a>