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

2 minute read

背景

小长假,带着一家人出去旅行,计划好了去几个地方,如何设计旅行线路是最优的?(里面还涉及到路费,路途时间等因素)。

pic

又比如 拼车,餐饮配送,包裹取件、配送,都包含最佳路径计算的共性在里面。

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.

详情

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

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

拼车的问题更加复杂一些,

从一个点出发(司机位置),经过多点(所有拼车乘客的上车地点),再去到多点(拼车乘客的下车地点)。

拼车的问题可以分为两个阶段来解决,

第一个阶段,从司机位置到接上所有拼车乘客。

第二个阶段,从最后一个乘客上车地点,到达所有乘客的下车地点。

两个阶段的规划需求是一样的,从一个点出发,经过多点,到达终点。

详情

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

Flag Counter

digoal’s 大量PostgreSQL文章入口