外卖配送路线规划的底层逻辑——迪克斯特拉算法

几何图形学里，圆的面积要大于方形。方形常见于建筑、家具设计等领域，因其稳定性和规则性受到广泛使用；圆常见于钟表、轮胎、饼干等圆柱形物体，因其均匀性和流畅性也被广泛使用。

某个未知面积数的地区，需派遣若干人入驻管辖，并要求以最少的人数能够彻底覆盖掉区域内的所有范围，不准出现遗漏某个角落。方形因其稳定性和规则性，无疑更优于圆形。

现实生活中，城中村、各大小区居民楼，实行的是网格化集中管理；依照两点距离，直线最短的原理，铺设、修筑的道路、桥梁、铁路大多也是以方形为主。简单点讲，国内城市的主干线、支线路段大都是以方形包围了城市里的各种建筑物，只有路况较为复杂特殊的山路才以圆形包围。

一

外卖配送路线规划的底层逻辑是以迪克斯特拉算法为主，该算法的主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

骑手在接单大厅看到的外卖订单、或是系统自动派发给的订单，都是先以骑手所在的位置为起始点，根据Dijkstra算法遍历后，再把订单推送展现在附近距离最近的骑手接单大厅里、或是自动完成接单。

骑手每变动一次位置，或是外卖订单的送餐地址发生改变，Dijkstra算法都会重新遍历一次，再重复上述工作。

当运力充足时，骑手与外卖的关系为一对N；运力供给紧张时，关系则变成N对N，其原因：每一笔外卖都有配送时效要求，当配送运力出现不足且外卖在不断爆单时，就需要更多的骑手去完成配送，而每位骑手背单上限却有着具体数量要求。要想快速提高配送时效，明显N对N关系更为适用。

二

下面先以圆形为例，设圆的上下左右4个边界点分别为A、B、C、D，骑手所在的中心点为O。

图表1 方形与圆形范围比较

绝大多数人认为，几何学里圆的面积大于方形。所以外卖和网约车行业以司机和骑手所处位置半径O点，来推送圆圈2.5公里内的所有订单给司机与骑手，一来可以保证接单距离在圆心O点出发都是同等距离，二来可以提高骑手的接单成功率。

针对第1点，这其实是一种完全错误的观点。外卖大厅里的订单，是在Dijkstra算法遍历后，以订单上商家所处的位置与骑手当时所在位置之间相差的距离，在算法设定误差最短路径范围内，自动推送到骑手所在的接单大厅里，让他可以看见该笔订单。并不是说，当某位骑手所处实时位置，距离推送该笔订单上取餐商家位置最近时，才会在接单大厅里看到该笔待接手的外卖单。

这种最短路径的误差值存在，既可以提高算法的运行速度，也能提高接单大厅推送的外卖订单接单的成功率。简单来讲，接单大厅里推送给骑手的外卖订单，不会只有一名骑手看到相同的订单，而是符合Dijkstra最短路径误差范围内的N名骑手。就好比A骑手率先看到某笔订单，因对配送佣金单价多少产生了几秒犹豫，在这几秒钟的犹豫时间内，被B成功接手。也有这种情况，B和C也同时看到了该笔订单，但C的抢单速度比B快了0.0001秒，被C成功抢夺。这些都是因允许范围误差的存在，所以才出现的现象。

所以，不管使用什么图形来规划接单范围，都不能保证骑手从半径出发，接到的外卖订单都是同等距离。为了让读者更直观地理解，我们可以用图表1来论证。把方形与圆形未重叠的4个边界点的面积看做是最短路径允许的误差范围，只要骑手进入这个未重叠的面积区域，就可以看到从ABCD四个边界点地址分别推送的外卖订单。依照Dijkstra算法最短路径原理，进入方与圆未重叠区域的任意坐标，都能拥有抢单资格，但骑手之间相互所处的坐标位置不同，距离4个边界点地址的距离也就各不相同，所以圆并不能保证，接单距离在圆心O点出发都是同等距离。

之所以讲以上东西，是因为地形与接单范围图形也有着直接的利害关系，至于到底有何种联系，以后有机会再讲讲。