外卖配送路线规划的底层逻辑——迪克斯特拉算法
几何图形学里,圆的面积要大于方形。方形常见于建筑、家具设计等领域,因其稳定性和规则性受到广泛使用;圆常见于钟表、轮胎、饼干等圆柱形物体,因其均匀性和流畅性也被广泛使用。
某个未知面积数的地区,需派遣若干人入驻管辖,并要求以最少的人数能够彻底覆盖掉区域内的所有范围,不准出现遗漏某个角落。方形因其稳定性和规则性,无疑更优于圆形。
现实生活中,城中村、各大小区居民楼,实行的是网格化集中管理;依照两点距离,直线最短的原理,铺设、修筑的道路、桥梁、铁路大多也是以方形为主。简单点讲,国内城市的主干线、支线路段大都是以方形包围了城市里的各种建筑物,只有路况较为复杂特殊的山路才以圆形包围。
一
外卖配送路线规划的底层逻辑是以迪克斯特拉算法为主,该算法的主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。
骑手在接单大厅看到的外卖订单、或是系统自动派发给的订单,都是先以骑手所在的位置为起始点,根据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点出发都是同等距离。
之所以讲以上东西,是因为地形与接单范围图形也有着直接的利害关系,至于到底有何种联系,以后有机会再讲讲。