人工智能与即时物流: 达达-京东到家的算法实践

在10.22号在上海举办的中国python开发者大会(Pycon China)上，来自达达物流算法团队的廖瑞奇首次分享了达达-京东到家在动态定价、路径规划和派单算法方面的一些实践经验。以下内容根据分享内容整理而来：

背景介绍

作为国内领先的即时物流信息服务平台，达达在仅使用众包配送员的情况下，实现了多个领域订单的高质量即时配送，订单来源不仅包括京东到家的生鲜商超订单，也包括来自外卖平台的餐饮订单、京东商城订单，以及远距离的同城快送订单。

在这一过程中，有很多问题都必须依赖人工智能相关的技术来解决。相关技术的使用，有效提升了达达平台的运行效率，为平台带来了巨大收益。本文将会分享达达在动态定价、路径规划和订单指派相关的一些实践经验，以及我们在实践过程中的一些思考。

动态定价

达达平台一方面连接着各种不同来源的配送需求，一方面连接着数以百万计的众包配送员。 平台是否能够高效运转，很大程度上取决于我们能否平衡运力的供给与需求。当骑士太多，订单太少时，就会出现供大于求，骑士流失；当订单太多，骑士太少时，则会出现供不应求，服务体验变差。

那么什么时候会出现供需不平衡呢？供需不平衡可能在多个维度出现，包括空间维度、时间维度和订单维度。

• 空间维度的供需不平衡： 在达达平台上，我们会绘制每个区域的供需热力图，来评估空间维度的供需不平衡： 

• 时间维度的供需不平衡：因为天气、节日、早晚高峰等因素，不同时间点，订单的需求会发生巨大变化（比如下雨天大家都喜欢叫外卖）。同样的，运力的供给也有一定的分布规律（比如过年期间工作状态的骑士会变少） 

• 订单维度的供需不平衡： 即使物流配送服务的非标准化程度非常高，任何两个订单之间，都有多维度的差别，这些差别会影响该订单的配送难度和供需状况，迫使我们预估订单维度的接单难度 

正是因为存在着以上维度的供需不平衡，我们才需要在考虑多维度因素的情况下，使用价格手段来调节供给和需求。这就要求我们做到千单千价：完全实时的动态定价，通过定价来平衡骑士利益、用户体验和平台利益。

在这一过程中，我们使用了多方面的技术，来实现多个维度的供需预测和定价。 

路径规划

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

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

由于TSP是一个NP-hard问题，没有多项式时间内的确切解法。为了解决这个问题，我们使用了启发式算法中的遗传算法，来快速获取骑士的较短配送路线，并且能够同时得到规划后的路线的最终配送距离。在待规划点超过10个以上的情况下，算法的运行时间也能保持在几毫秒，同时保证极高的准确性。 

有了这个基础算法，我们就可以判断订单间的顺路情况，以及某个订单是否适合由某个骑士来配送。

订单指派

在达达平台上，我们同时有订单的抢单和派单机制，来实现合理的订单分配。 

在订单分配的过程中，我们不仅需要考虑顺路情况、配送效率等，也要考虑骑士的接单偏好、配送能力、活跃状况，以及订单分配的公平性等因素。简单来说，订单指派是一个有限制的多目标优化问题，不仅需要考虑平台效率，也要考虑骑手的心理因素、运营的稳定性等。 

目前，使用派单和抢单结合的方式，达达平台上绝大多数的订单，都能在发出后1分钟以内实现订单的合理分配。

总结

在达达，我们面临的算法问题是全新的，这一领域里很少有现有的实践经验可以借鉴。传统互联网算法的输入和目标是相对比较清晰的，而在线下线下结合的领域，则往往面临的是复杂的输入和多目标优化问题。

同时，问题的非标准化程度和复杂程度也要高于其它同类公司。以顺路判断为例，滴滴/uber在拼车时最多只需要考虑2单间的顺路情况，而外卖配送则可能同时配送5单以上订单。同时，即时物流配送相对于打车也有更强的时效要求和订单差异。 

挑战同样也意味着机遇，这一领域的算法优化往往能带来巨大的价值。随着人工智能技术的快速发展和新零售的崛起，物流领域正面临着巨大的变革，达达-京东到家也在其中扮演着重要角色。 我们期待对这一领域感兴趣的同学加入我们，一起在这一激动人心的算法领域里探索和创新。

作者简介：廖瑞奇，新达达配送算法团队负责人, 在机器学习、物流算法、计算广告等领域有着丰富的实践经验。2016年初加入达达，从0到1建立起达达的算法团队。目前主要负责订单指派、动态定价、路径规划等相关工作。