426
技術社區[雲棲]
多點最優路徑規劃 - (商旅問題,拚車,餐飲配送,包裹配送,包裹取件,回程單)
標簽
PostgreSQL , PostGIS , pgrouting , 商旅問題 , 拚車 , 餐飲配送 , 包裹配送 , 包裹取件 , 回程單
背景
小長假，帶著一家人出去旅行，計劃好了去幾個地方，如何設計旅行線路是最優的？(裏麵還涉及到路費，路途時間等因素)。
又比如 拚車，餐飲配送，包裹取件、配送，都包含最佳路徑計算的共性在裏麵。
PostgreSQL 在GIS領域有這非常豐富的用戶和實際案例，路徑規劃方麵，我之前寫過一篇關於包裹配送的文章
在商旅問題，拚車，餐飲配送，包裹取件、配送，等諸多最佳路徑計算的需求方麵，PostgreSQL又是如何滿足需求的呢？
pgrouting 核心功能
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)
最佳規劃1 - 從一個點出發，經過多點，回到起點
解決 旅行、包裹配送、餐飲配送的問題
這個問題的定義如下，從一點出發，經過多點，回到起點。
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.
詳情
https://docs.pgrouting.org/latest/en/TSP-family.html
例子1
pgr_TSP - Returns a route that visits all the nodes exactly once.
從5出發，經過array[-1, 3, 5, 6, -6]，回到5。
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_withPointsCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction from pointsOfInterest',
array[-1, 3, 5, 6, -6], directed := false);
$$,
start_id := 5,
randomize := false
);
seq | node | cost | agg_cost
-----+------+------+----------
1 | 5 | 1 | 0
2 | 6 | 1 | 1
3 | 3 | 1.6 | 2
4 | -1 | 1.3 | 3.6
5 | -6 | 0.3 | 4.9
6 | 5 | 0 | 5.2
(6 rows)
例子2
pgr_eucledianTSP - Returns a route that visits all the coordinates pairs exactly once.
SET client_min_messages TO DEBUG1;
SET
SELECT* from pgr_eucledianTSP(
$$
SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr
$$,
tries_per_temperature := 0,
randomize := false
);
DEBUG: pgr_eucledianTSP Processing Information
Initializing tsp class ---> tsp.greedyInitial ---> tsp.annealing ---> OK
Cycle(100) total changes =0 0 were because delta energy < 0
Total swaps: 3
Total slides: 0
Total reverses: 0
Times best tour changed: 4
Best cost reached = 18.7796
seq | node | cost | agg_cost
-----+------+------------------+------------------
1 | 1 | 1.4142135623731 | 0
2 | 3 | 1 | 1.4142135623731
3 | 4 | 1 | 2.41421356237309
4 | 9 | 0.58309518948453 | 3.41421356237309
5 | 16 | 0.58309518948453 | 3.99730875185762
6 | 6 | 1 | 4.58040394134215
7 | 5 | 1 | 5.58040394134215
8 | 8 | 1 | 6.58040394134215
9 | 7 | 1.58113883008419 | 7.58040394134215
10 | 14 | 1.499999999999 | 9.16154277142634
11 | 15 | 0.5 | 10.6615427714253
12 | 13 | 1.5 | 11.1615427714253
13 | 17 | 1.11803398874989 | 12.6615427714253
14 | 12 | 1 | 13.7795767601752
15 | 11 | 1 | 14.7795767601752
16 | 10 | 2 | 15.7795767601752
17 | 2 | 1 | 17.7795767601752
18 | 1 | 0 | 18.7795767601752
(18 rows)
最佳規劃2 - 從一個點出發，經過多點，到達終點
拚車的問題更加複雜一些，
從一個點出發（司機位置），經過多點（所有拚車乘客的上車地點），再去到多點（拚車乘客的下車地點）。
拚車的問題可以分為兩個階段來解決，
第一個階段，從司機位置到接上所有拚車乘客。
第二個階段，從最後一個乘客上車地點，到達所有乘客的下車地點。
兩個階段的規劃需求是一樣的，從一個點出發，經過多點，到達終點。
詳情
https://docs.pgrouting.org/latest/en/TSP-family.html
例子
詳情
https://docs.pgrouting.org/latest/en/pgr_dijkstraVia.html
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<size_of(vertexvia)i<size_of(vertexvia).
參考
所有用到的路由函數，點對點成本矩陣函數，請參考
https://docs.pgrouting.org/latest/en/TSP-family.html
最後更新：2017-04-10 20:02:47