微信精选

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

2018-01-11 13:51

  我们选取了目前在这一方面做得比较优秀的几个企业,看看他们是怎样通过算法来得到最短的配送距离?

  美团外卖调度中关键难点之一——订单分配

  在过去一年多时间里,美团配送团队在机器学习、运筹优化、仿真技术等方面,持续发力,深入研究,并针对即时配送场景特点将上述技术综合运用,推出了用于即时配送的“超级大脑”——O2O即时配送智能调度系统。

  系统首先通过优化设定配送费以及预计送达时间来调整订单结构;在接收订单之后,考虑骑手位置、在途订单情况、骑手能力、商家出餐、交付难度、天气、地理路况、未来单量等因素,在正确的时间将订单分配给最合适的骑手,并在骑手执行过程中随时预判订单超时情况并动态触发改派操作,实现订单和骑手的动态最优匹配。

  同时,系统派单后,为骑手提示该商家的预计出餐时间和合理的配送线路,并通过语音方式和骑手实现高效交互;在骑手送完订单后,系统根据订单需求预测和运力分布情况,告知骑手不同商圈的运力需求情况,实现闲时的运力调度。

  在这一套调度流程中会遇到一个关键问题——订单分配,下面就方案架构和关键要点来分析一下:

  外卖订单的分配问题一般可建模为带有若干复杂约束的DVRP(Dynamic Vehicle Routing Problem)问题。这类问题一般可表述为:有一定数量的骑手,每名骑手身上有若干订单正在配送过程中,在过去一段时间(如1分钟)内产生了一批新订单,已知骑手的行驶速度、任意两点间的行驶距离、每个订单的出餐时间和交付时间(骑手到达用户所在地之后将订单交付至用户所需的时间),那么如何将这批新订单在正确的时间分配至正确的骑手,使得用户体验得到保证的同时,骑手的配送效率最高。

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

外卖配送场景下一个配送区域上众多骑手的分布示意图

  美团外卖每天产生巨量的订单配送日志、行驶轨迹数据。通过对配送大数据进行分析、挖掘,会得到每个用户、楼宇、商家、骑手、地理区域的个性化信息,以及有关各地理区块骑行路径的有效数据,那么订单智能分配系统的目标就是基于大数据平台,根据订单的配送需求、地理环境以及每名骑手的个性化特点,实现订单与骑手的高效动态最优匹配,从而为每个用户和商家提供最佳的配送服务,并降低配送成本。

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

  即时配送订单分配问题的优化目标一般包括希望用户的单均配送时长尽量短、骑手付出的劳动尽量少、超时率尽量低,等等。一般可表达为:

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

  除了要考虑时间、地段等约束外,有时还需要考虑部分订单只能由具备某些特点的骑手来配送(例如火锅订单只能交给携带专门装备的骑手等)、载具的容量限制等。

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

  即时配送大数据平台实现对骑手轨迹数据、配送业务数据、特征数据、指标数据的全面管理和监控,并通过模型平台、特征平台支持相关算法策略的快速迭代和优化。

  机器学习模块负责从数据中寻求规律和知识,例如对商家的出餐时间、到用户所在楼宇上下楼的时间、未来的订单、骑行速度、红绿灯耗时、骑行导航路径等因素进行准确预估,为调度决策提供准确的基础信息;而运筹优化模块则在即时配送大数据平台以及机器学习的预测数据基础上,采用最优化理论、强化学习等优化策略进行计算,做出全局最优的分配决策,并和骑手高效互动,处理执行过程中的问题,实现动态最优化。

  达达-京东到家——路径规划和派单算法

  在10.22号举办的《中国python开发者大会》上,新达达配送算法团队负责人廖瑞奇首次分享了达达-京东到家在路径规划和派单算法方面的一些实践经验。

  1)路径规划

  在达达平台上,一个骑士可能会同时配送多个订单,如何规划骑士的配送路线,使得骑手的送货距离最短,优化骑士的配送效率,是平台要解决的一个核心问题。

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

  对于单个骑手的路径规划问题,是一个典型的TSP问题: 

评测:美团、新达达、58速运、菜鸟的路径优化算法对比

评测:美团、新达达、58速运、菜鸟的路径优化算法对比