# 多点最优路径规划 - (商旅问题,拼车,餐饮配送,包裹配送,包裹取件,回程单)

## 背景

PostgreSQL 在GIS领域有这非常丰富的用户和实际案例，路径规划方面，我之前写过一篇关于包裹配送的文章

《聊一聊双十一背后的技术 - 物流、动态路径规划》

## 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.

http://docs.pgrouting.org/latest/en/TSP-family.html#tsp

### 例子1

pgr_TSP - Returns a route that visits all the nodes exactly once.

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 - 从一个点出发，经过多点，到达终点

http://docs.pgrouting.org/latest/en/TSP-family.html#tsp

### 例子

http://docs.pgrouting.org/latest/en/pgr_dijkstraVia.html#pgr-dijkstravia

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).

## 参考

http://pgrouting.org/

《聊一聊双十一背后的技术 - 物流、动态路径规划》

http://docs.pgrouting.org/latest/en/TSP-family.html#tsp

Tags:

Updated: