菜鸟网络算法专家朱礼君：物流优化问题在大数据时代被赋予新的意义​ | CCF-GAIR 2017

2017年7月7日至9日，全球人工智能与机器人峰会CCF-GAIR大会在深圳成功举办。本次由CCF中国计算机学会主办、雷锋网与香港中文大学（深圳）承办。来自全球30多位顶级院士、近300家AI明星AI企业，齐聚智能科技产业盛会。

菜鸟网络高级算法专家朱礼君在CCF-GAIR 2017大会上发表了演讲，主题是“大数据时代的物流优化问题”，主要讲解菜鸟网络当中的物流发展情况。朱礼君毕业于美国马里兰大学，获得物理学博士学位，先后就职于Goldman Sachs、亚马逊、Facebook等公司，于2014年回国加入阿里巴巴，领导菜鸟网络仓配供应链的算法团队。

以下是朱礼君演讲速记全文整理，雷锋网在不改变原意的基础上做了精编：

我来自菜鸟网络，我将分享大数据时代的物流优化问题，我们在做物流优化的时候碰到了很多问题。物流其实是一个非常古老的行业，可以说有上千年的历史，但是在这个大数据时代，我们发现很多传统的运筹学优化问题，在大数据时代被赋予了很多新意义，我们在这方面做了很多研究，碰到了很多有意思的问题，在运行的过程中也学到了很多的经验与大家进行分享。

菜鸟网络是传统行业和物流行业的融合

首先介绍一下菜鸟网络，菜鸟网络是一个物流平台，协同物流合作伙伴为消费者和商家提供物流服务，包括快递、仓配网络、跨境、末端网络，还有农村物流网络。值得一提的是这里面很多节点，像仓库以及配送，最后一公里等，我们用的还是社会上的物流资源，是我们合作伙伴的资源，但是菜鸟网络在这里面会起到全局优化的作用。

刚才说到我们的一个特点就是传统行业和物流行业的融合，因为物流行业是一个非常传统的行业，但是我们是一家互联网公司，是一家数据公司，所以数据是核心，技术是核心，很多的传统物流优化的问题在互联网时代的确是被赋于了很多新的意义，而且在大数据和算法是这里面的核心。

物流优化问题在大数据时代被赋予的新意义

在大数据时代，我们的物流优化问题被赋于了哪些新的意义呢？经过我们的研究发现，首先我们对很多物流优化问题的计算性能要求远远大于以前，之前我们不太在乎优化计算资源的使用的，因为以前的优化是今天算了明天再用，现在是实时的，所以对算法有很大的挑战。

另外，机器学习和人工智能被提到很高的高度，在物流领域以前用的是传统运筹优化的理论和算法，在大数据时代，这两者需要得到更好的有机融合。还有一点也是我们最近在研究的方向，就是怎么用机器学习的思想来求解传统物流优化问题，这也是在学术界上非常有挑战的一个新的方向，我们在这个过程中也有一些经验。

物流算法应用案例

下面分享一下我们在菜鸟网络做过的一些物流算法应用的案例。

第一个问题是供应链仓储配送网络的优化问题，这是非常传统的问题，我们有一些客户在全国或者全世界有一个区域的分布，我们到底要选哪些仓库布点，把货囤到哪些仓库，从供应商那里运到仓库，最后再运到用户哪里，这里的核心是我们选择哪个仓库，每个仓库负责哪个区域的用户，这是传统的问题。

为什么我们认为在现在这个大数据时代有它的新的意义呢？在阿里的电商平台上，商家其实都是负责自己的货，之前他会用自己的仓储网络，我们会对每个商家做优化，比如说优化以后，有些货可以放到菜鸟仓库里，帮它配送，它会覆盖一些范围。

举个例子，深圳的一个商家以前可能在深圳有仓库，北京的用户他就需要远程发货，但是菜鸟在北京有仓库，我们就可以推荐这个商家用我们的仓库囤在北京附近货。这里面需要考虑的一些优化的目标非常多。除了成本以外，还会考虑时效，次日达的体验对用户来说非常重要，还有铺货成本，就是从供应商运到仓库大概要多少钱，一般我们会用混合规划的模型来解决这个问题，所以这里面要求非常快，我们专门设计一些算法来解决这个问题，我们有成千上万的商家，对每个商家都要单独求解，这样用传统优化的算法会有一定的局限性。

当商家选了我们的仓库之后，我们要告诉他们怎么分仓，我在北京的仓库要放多少货，上海的仓库要放多少货，这个问题看似简单，其实不然，就算我根据历史的数据，用机器学习的模型预测出北京的销量是多少，上海的销量是多少，这还是不够，因为机器学习的模型是有非常多的不确定性因素，它预测的未来销量会有很大的波动，我们也知道特别在中国的电商会有很多的促销，这个波动会变得更大，我们如何把这些波动考虑进去，使得我们在一些不确定的环境下，都能保证我补货的量比较合适，不会有缺货的情况出现，也不会有滞销的情况出现。所以要考虑铺货的成本、仓储的成本，然后要考虑周期性补货，到底是一个星期一次，还是两个星期一次，还是一个月一次是最优化。最重要的一点是要考虑销量的波动性，因为销量非常不稳定。

然后整个补货量确定之后，我们建立这样一个模型，用鲁棒优化的算法来计算每个仓库大概要补多少量，这个算法也是对每一件商品、每一个商家都是个性化计算的，所以这也是一个难点。

在仓储领域，我们知道在仓库里面，用户下了订单以后，仓库里面会有仓库的工作人员，在仓库的货架走一圈，把用户下的订单都拣过来，再打包发给用户。这里面非常重要的问题就是任务怎么切分和路径怎么优化。任务切分就是哪个订单应该派给哪个人，路径优化是怎么派给这个人，这两个问题是相互融合的，它是一个类似于车辆路径规划的问题。这里面的难点就是，特别是像电商这样的平台，订单是不断下发的，我们需要知道到底在什么时候我要做一个决定，哪些订单把它大爆发给一个工作人员，让他去货架上拣，所以这是一个需要实时做决策的问题，它对计算性能的要求也非常高，因为仓库里的工作基本上是连轴转，中间不会停，因此需要迅速计算出下一个任务到底要发给谁，然后订单也是不断下发，这是一个非常动态的问题，所以用一些传统的运筹优化算法解这种问题比较难。

箱型推荐问题

在仓储领域还有一个比较有意思的问题，可能大家会觉得这个问题看上去比较简单，其实不然，就是箱型推荐问题。比如说用户在这个网站上买了8件商品，一个用户买8个东西或者10个东西，这是很正常的，这些东西有它的长宽高、重量，我知道我仓库里备的箱子的大小和它能承重多少，问题是在订单下发的那一刻，我要知道这些商品要怎么垒，然后放到哪个箱子里，或者最大的箱子也放不下，我要放到哪几个箱子里，这个问题为什么这么重要呢？如果能一个箱子装下，它就是一个包裹，而如果我把它分成了两个包裹，它就会需要两个包裹运输，增加了配送的费用，而且这个箱子的包材也有浪费，所以这个算法可以发挥空间很大。这个问题在学术界是一个传统的三维装箱问题，这是一个非常难的问题。它的约束是物品累积在一起的时候，它的长宽高不能高于那个箱子的长宽高，这是大家都能想到的约束条件。一般的传统的做法是用构造性的算法求解，就是我去尝试各种不同的摆放形式，或者不同的摆放顺序，然后我们在这里面需要做一些语言启发算法，就是把一些启发式的算法整合起来，做一些分层的算法设计。假设你有100个商品，一个复杂的算法很可能是算不过来，因为我们需要很短的时间内把这个计算出来，在订单下发的过程中就计算出来，如果你没有计算出来，后面就会卡住，所以这个算法的挑战很大。

我们把这个问题解完了以后，后来自己考虑了一下，这里有一个很重要的约束，就是商品累积在一起，它的长宽高不能高于这个箱子的长宽高，然后我们就自己问自己，这个约束是一定要的吗？其实不然。因为我们可以根据历史的一些数据来重新分析一下每个仓库它到底要怎么样准备它的箱子，这其实是一个新问题，我们提出了一个新的问题，在历史上，传统的学术界没有做过，因为现在电商积累了这么多的商品数据、订单数据，我知道每一个仓库发货的时候，用户喜欢把什么东西买在一起，然后订单里面的那些组成的商品成分是什么，它们的长宽高是什么，有一个分布，那个分布我知道，我的确可以从数据的角度反推出来最优的箱子的形状是什么，然后我们就做了这个事情，这也是一个非常有意思的问题，刚才说到，假设我给定箱子长宽高以后，我要解这个问题，其实是一个非常难的问题。在这里我们根本不能够用传统优化算法里面的求梯度，用梯度下降的方法去做，因为你根本算不出它的梯度是什么，所以我们做了一些无梯度的算法。

因为这个问题比较特殊，它对这个箱子的长宽高没有太多约束，所以我们就可以做一些无梯度的优化算法，把每个箱子的长宽高的参数空间做一些切分，然后看最后总成本的函数大概是多大，然后会平衡全局的搜索和局部的搜索，找到一个最优解，这样做对成本也是非常大的节约。这里给我们一个启示，在物流行业很多时候你把一个算法做好了非常好，但是你要找到这里面你可以打破的约束可能更重要。

我们更进一步研究这个问题，因为传统的优化问题一般用的方法就是运筹学里的一些方法，比如说整数规划的问题，或者是一些启发式的算法。但是现在人工智能、深度学习、机器学习都是非常火的领域，的确有一些新的思想可以用在传统的问题里面。像在机器翻译这个领域，以前我们用的都是一些传统的机器学习方法，后来有人提出来用深度神经网络的方法，用LSTM的网络结构做机器翻译，后来也有一些学术上的言怎么把这种LSTM的网络结构用在解TSP的问题，我们就尝试了把这种网络结构用来解箱型推荐的问题。这里面的目标是说，我们要预测商品放进去的时候那个顺序到底怎样，使得它最后的面积最小，这的确是我们要解决的问题。传统的优化的方法就是不停地去试顺序到底是怎么样的，然后找到一个顺序。用机器学习或者深度学习的方法，我就直接预测出那个顺序，当然这里面会牵扯到很多数据，我们会用历史数据，这里输入的数据是物品的长宽高，输出的数据是它的顺序的数据，中间有一些模型跟机器翻译的模型网络结构非常像，当然我们做的时候也是用它的历史数据训练，做下来有5%的提升。虽然这个运筹优化还是比较古老的领域，但是在人工智能这个时代，机器学习和深度学习的算法的确可以用。

车辆的路径规划问题

在物流这个行业有一个非常重要的问题是车辆的路径规划问题。这个问题的定义其实非常简单，就是我们在地理上有一些需要去服务的点，要配送的包裹，或者是需要揽收的货物，它在地理上分布在不同地方，我需要从一个总的中心派几辆车，分别去揽收，或者分别去派送这些货物或者是包裹，这个问题体现在两个层面：

第一，怎么派活，哪些点的服务要派给哪辆车，用什么样的车。

第二，每辆车要怎么走，它的路径要怎么优化，这个跟仓库里面的拣货优化路径类似，这一大类问题是车辆路径规划问题。它有很多变种，比如说CVRP，就是有的车有限重。还有VRPTW，就是它有一个时间窗的约束。还有VRPPD，你去一个地方拿东西，然后再去另一个地方配送。还有一些其他组合，所以问题其实非常多，但是总的框架还是比较类似，无非是说我要派一些车去一些服务点，然后每辆车怎么走，这个问题在数学上抽象起来还算比较清晰。

传统的方法大概两类：

第一，有一些精确的解法，这些算法一般在超过100个服务点的时候很难在优先的时间里面解出来；

第二，传统的算法里面还有很多近似算法，像ALNS、VNS，这些都是流域搜索的算法，还有基因算法。现在的一些比较前沿的研究是如何把这些优化算法与深度学习的一些技巧联合起来。

我们自己开发了一个车辆路径规划非常强大的引擎。因为刚才提到这是物流行业经常出现的问题，我们从算法的层面来说，这里面最重要的一个点是用了机器学习里的一个思想。每一个我要优化的问题它会有不同的约束，比如在农村，约束车的数量不变，如果外卖，可能会有时间窗，所以每一类问题的约束还是多种多样的，我要是单独做一个算法还好，但是我要算法适应各种不同的约束，就非常难。而且我们知道机器学习、强化学习里面会有一些自适应的方法，我们会根据这个问题的特殊的结构识别出来我到底要怎么解决这个问题，这里我们用的是比较传统的Bandit Learning思想，各种问题会有一些不同的解法，有一些算子，我会试一下，看看两两交换、三三交换，能不能把这个解做得更好，把一些解做一个变换，看看能不能做得更好。不同的问题，不同的策略会使它更快的收揽，所以我们会去试，比如说这次好，下次会再试一下其他方式，比如说两两交换不好，我可以试一下三三交换，这样算下来，每个个体会找到特定的算子，到底什么样的算子、算法最优。

我们的应用案例也很多，像一些生鲜配送的应用、农村淘宝、城市门店配送、仓库拣选路径优化。应用的场景很多，同一个算法引擎可以用到很多场景中，原因就是因为它有自适应的学习过程。

大数据智能分单

下面分享我们做的大数据智能分单。传统物流的情况是说我们需要把包裹收上来以后，按照全国的流向去分，比如说我会按北京、上海、广州流向去分，以前是人在分的，如下图，有一个人在看快递地址，然后把它放到对应的口，全国可能有200多个口，人工分拣起来很难。未来我们肯定希望做到自动化，自动化比较重要的一个点就是数据化，首先我们需要把这个地址数据化，然后把它编码。以前是人工会写一个码，我会看这个地址。现在菜鸟电子面单，在商家发货的时候，会写上对应的码，操作员只需要看这个码就行了，非常方便，因为识别一个码比识别一个手写的地址更简单。

一个地址应该去哪个站点配送呢？快递公司有多规则去分，比如说深圳福田区的一个网点它到底要服务哪一个区域，它有一些很复杂的规则，这些规则你很难把它数字化，我们用了一个什么样的方法呢？我们用的是大规模机器学习方法，我不知道你的规则什么样，也不需要描述，我把它挖过来，这是机器学习的非常简单的应用，原来你是怎么学习的我不知道，我只要有历史数据，我就可以通过机器学习的挖掘把它利用出来。这里面会用到一些分词、地理围栏的特征，还有规则的特征，我们用大数据的模型学习，最终把订单都分到它对应的点。

据雷锋网了解，中国有很多物流提供商、很多快递公司，也有很多配送公司都有各自的优劣，每个公司在各自的区域优势不一样。

如上图，左边公司和右边公司，它的配送的时间有差距，可以看见比如说在北方，右边那个公司就没有左边这个公司好。

一个商家要发货的时候，它对每一条线路都要做一个选择，比如说商家如果在杭州，杭州到上海需要谁来发，杭州到广州、北京、武汉分别用谁来发，下面又有很多的配送公司，这是一个组合优化的问题，我怎么样对每一条线路，用什么样的配比分配我的订单最终最优化，这个事情用人做非常难，而且简单粗暴，他不会细到每条线路怎么分，但是交给算法来做，就会很精细。我们做了一个引擎，考虑时效、服务、成本等等，把所有的因子考核到一起，求一个最优的分配方案，然后自动地为这个商家提供一个智能发货的解决方案。

我刚才提到很多算法，我们是一家互联网公司，以技术为核心，我们希望通过整合社会化物流，提升整个中国的物流水平。积累下来的技术，希望能够开放，给整个社会上的物流公司使用，能够提升整个中国社会的物流水平。如路径规划的算法的引擎，我们已经在跟多个合作伙伴对接，刚才提到的箱型推荐的算法已经开放出来了，还有地址库，地址怎么分类，地址的聚合的服务，标准化的服务，还有只能分单的算法，对每个配送公司怎么去分他的订单，这些算法我们都对外开放，提供给所有物流合作伙伴。以该方式来提升整个中国物流的效率。

未来发展方向

从技术的方面来讲，我们觉得未来的发展方向是这样的：第一点是从Model-driven的方法到Data-driven的方法。刚才说到传统的物流优化一般用的是运筹优化的模型，运筹优化一般会有一个目标函数，比如成本，然后我有约束，比如当日达订单比例是多少，这个仓库订单不能超过多少，这辆车装的东西不能超过多少，这些约束列好以后，需要把它求解，这是一个以模型为中心解决问题的方法。

但是在互联网时代积累了非常多的数据问题。

一类问题可能我们解了很多，它们有一点不一样，但是有很多地方是一样的，比如说农村配送，我每天要配送的村点其实不会变，但是它的量会变，所以我昨天求解的路径规划和今天求解的路径规划应该是有很大的关联，而传统的模型驱动的方法，我把这个关联性就丢掉了，我昨天的解没有用。我解了同样的一类问题几次以后，我应该是可以总结归纳出一些方法，为明天求解同样的问题或者类似的问题会有帮助，这是采用Data-driven的方法解决问题。我们也用一些深度学习或者是机器学习的方法做这方面的研究，这的确是一个非常让人激动得方向，它的确是把传统的领域注入了一些新的活力。

第二类是算法一定要产品化。算法做得再深，不考虑各种各样的边角料的情况肯定不行，特别是物流行业，我要应用到实操有很多环节需要不断地打磨。就像刚才提到的路径规划的算法，在运行过程中得到非常多的反馈，那些反馈我们又会加回去。我们把算法平台化，不会为单独一个问题解一个算法，因为问题实在太多，单独为每个问题建模，在可扩展性上会遇到很大问题。刚才也提到大部分的算法已经对外开放，所以未来也会继续在这方面努力把我们的算法能力，把我们人工智能方面的能力对外开放，提升物流行业的智能化。

雷峰网原创文章，未经授权禁止转载。详情见转载须知。