天下武功，唯快不破——快递中的寻路算法

前几天双 11 下的单，都已经收到包裹了吧？

为什么 2016 年双 11 的快递来得比以往都及时？今天，就来给大家分享一下物流与背后的数据库技术。

物流行业是被电子商务催生的产业之一。

快件的配送和揽件的调度算法是物流行业一个非常重要的课题，直接关系到配送或揽件的时效，以及物流公司的运作成本。

好的算法，可以提高时效，降低成本，甚至可以更好的调动社会资源。

本文将以物流行业为例，给大家分析一下 PostgreSQL 与 Greenplum 在地理位置信息处理，最佳路径算法，机器学习等方面的物流行业应用方法。

物流的要素分析

物流做的事情很简单，寄件，送件（但是后面蕴藏着很多高精尖的黑科技呢，比如怎么调度，怎么获得最佳路径）。

物流环节的要素有几个，都与位置有关。

• 寄件人

• 揽件员（揽件人通常不是直接将货收到仓库，而是网点。所以网点到仓库也是需要调度的，本文未涉及。）

• 调度方法与配送差不太多。

• 货物

• 仓库

• 运输工具

• 派件员

• 收件人

我们这里先从简单的入手，假设现在只关心位置信息，剖析一下从寄件到收到包裹，整个过程串起来，看看背后的技术。

1. 寄件

货物从寄件人到揽件员，通常是预约的操作，而且寄件人可以直接去网点办理寄件，所以没有太多的算法在里面。

如果派件和揽件混合在一起的话，可以用 KNN 算法来解决，再结合派件点路径调度，选出最佳的揽件人。

例如，寄件人当前位置，与快递员调度的下一个位置，进行 KNN 运算，因此 B 来揽件是成本最低的。

2. 货物在仓库之间流转的物流调度

假设上图为仓库的位置，两个仓库之间如果开通了线路的话，就以线段连接起来。

每个仓库负责一个区域，这个区域是一个几何的图形。

通过寄件人和收件人的位置，与仓库的区域进行点面判断，找出寄件人的仓库与收件人的仓库。

快件为点，仓库为面，寄件时根据寄件人填写的寄件和收件信息转换为寄件和收件两个经纬度，通过这两个经纬度与快递公司的仓库表进行点面包含的判断匹配，就可以找出快件对应的起点和终点的仓库。

点面判断。

有了源和目标就可以通过 pgrouting 提供的各种最佳路径算法算出每件货物的最佳路径。

本文后面会有 demo 来讲解如何使用 pgrouting 计算最佳路径。

仓库之间的货车的工作就简单了，装满就走或分波次(考虑到时效) 的原则，负责好两个直连节点的来回运输，并不是一辆车完成整个货物的从起点到终点的运输。

例如负责 A 和 B 之间线路的货车，只在 AB 之间跑运输。

3. 货物从终点仓库到网点的物流调度

货物在抵达目标仓库后，首先要将货物分拣到派件的网点。

其实也是一个点面判断的过程，网点覆盖的派件范围为面，快件则为点，点面判断找出对应的网点。

从仓库到网点，也可以使用仓库建流转的原理，计算出最佳线路。货车只负责2个网点之间的货物流转即可。

4. 派件

进入派件的流程，也就是货物在抵达收件人手中的最后一公里要做的事情。

为了更好的实现派件调度，需要对快件进行聚合操作，根据位置进行聚合。

原理和前面类似，还是要做点面判断，只是目标更加精确，例如精确到小区或者很小的区域。

派件除了要考虑快件的目的地（聚合后的），还需要考虑快件的体积，重量，以及快递员的运货能力（体积与重量） 。

假设一个网点当前收到的快件覆盖了以下需要派送的点（聚合后的），同时每个点的货物体积总和如数字所表示。

路径规划与前面不一样的地方，这里规划的是多个点作为目标。

多点目标的最佳路径，用意是确保相邻目标的连续性，确保切分不同网点的快件后，拿到快件的人跑的依旧是相邻的点。

例如中心是网点的位置，其他点是目标位置，目标位置的数字是体积，假设每个快递员一次运输的体积是 7000，虚线是一个快递员拿到的一趟的快件。

这种方法确保了每趟的快件是连续的。

多点目标的最佳路径规划，在本文后面的部分也会有 DEMO。

地址转换成坐标

如何将地址转换成坐标，不在本文的讨论范围，很多做导航的公司都可以输出这个能力。

但是作为快递公司，还有一种方法可以获得精确的坐标信息，例如快递员的手持GPS终端，收件时扫个条码，同时上报位置信息。

有了一定的基数后，通过文本分析和机器学习，也可以输出地址转坐标的能力。

如果基数非常庞大，可以选择基于 PostgreSQL 的 Greenplum 数据仓库，进行文本分析与机器学习(支持 MADlib 库，支持R，python，java)。

PS：

Greenplum 支持文本分析，支持地理位置信息处理，支持 MADlib 机器学习库，还支持 R 语言自定义函数，python 函数，支持分布式并行计算。

最重要的是它开源，绝对是有文本和地理位置分析需求的用户最好的选择。

你可以使用熟悉的 R、Python、Java 自定义数据库端的 UDF，满足灵活的业务需求。

路径规划

以仓库之间的数据流转为例：

需要用到 PostgreSQL 数据库的 PostGIS 与 pgrouting。

首先是基础数据的录入，即道路数据，用来表示开通了运输航线的仓库之间的线段数据，以及线段的属性信息。

1. 生成拓扑

有了道路信息还不够，要生成最佳路径，首先要生成合法的拓扑，否则怎么生成路径呢？

生成拓扑前，需要添加两个字段，用来存储线段的首尾编号。

调用 pgr_createTopology 生成拓扑，也就是生成线段的首位编号的过程

例如，ABC 三条线段，其中 B 线段的两端都没有和 AC 完全吻合，误差分别为 1 米和 10 米，所以需要设置容错。

生成线段，实际上就是设置 source 和 target 的 ID，设置完后，可能就变成这样的了。

 

2. 生成最佳路径

我们知道道路是有坡度，有弯度的，还有颠簸程度，是否单行线，过路费，拥堵程度，怎么送货效率最高，不能只看路程。

想象一下你打车去机场的场景，如果时间比较紧的话，就要靠司机了。

一个优秀的出租车司机是会帮你选择最佳路径的，算上拥堵费，绕路其实可能更省。

pgrouting 支持的最佳路径算法很多

你可以根据不同的算法，输入当时每条路段相关的因素（例如坡度，弯度，颠簸程度，是否单行线，过路费，拥堵程度 数字化的 weight 系数），生成最佳路径。

支持的内置算法如图

 

小结

小结一下物流配送都用到了哪些技术：

1. 根据寄件人和收件人地址转换成坐标，需要用到公共的转换库，当基数达到一定程度后，可以自建转库。

自建地址和坐标转换库，需要用到机器学习的技术，PostgreSQL 与 Greenplum 都支持 MADlib 库，对于 Greenplum 的 R 用户，可以使用 Greenplum 进行隐式的并行数据挖掘，处理大数据量的挖掘很有帮助。

2. 根据寄件人和收件人的坐标，与快递公司仓库覆盖的的电子围栏进行点面判断， 找到匹配的仓库。

3. 得到最佳运送路径，规划算法参考 pgrouting 的手册以及 workshop

4. 根据寄件人或收件人的坐标，以及最后一公里的网格信息进行点面聚合，得到配送位置。

5. 聚类算法

如果小区信息在数据库中存储的不是面，而是点，那么派件的点面判断，可以用 PostgreSQL 或者 Greenplum 的 K-Means 聚类算法，将快件与小区进行聚合，达到同样的目的。

根据指定的种子数组，即网点覆盖的小区或写字楼等组成的点值数组，生成聚类数据（即目标包裹），从而实现最后一公里的高效率配送。

PostgreSQL 在地理位置处理的领域一直处于非常领先的地位，用户群体也非常的庞大，PostGIS 和 pgrouting 只是这个领域的两个插件。

PostGIS 和 pgrouting 在阿里云的 RDS PostgreSQL 数据库都有提供，想要了解更多可以点此。