张大力[2]
【摘要】
本文以某电商仓配企业在分拣设备开发过程中面对的储位分配问题为背景，介绍了电商管理实际问题中对于智能算法设计的需求，讨论了如何通过线上订单分析优化问题的结构，进而提升智能算法的运行效率。
“1分钟的时间能做什么事情呢？读150个字，跳绳120下，发一下呆……对于物流企业的一间仓库来说，1分钟可以发出1 200个包裹，也可以分拣6 250件商品。没错，就是这个速度！”2021年3月12日的《央视新闻》栏目报道了最近上海发网供应链管理公司研发的电商仓库自动分拣系统。这套分拣系统是如何高效率地代替人工的，相信大家都已经从众多的媒体报道中知道了，每一套高效的物流设备背后都有一个神奇的算法！我们行研院智能物流团队作为这一神奇算法的研究者，当然需要回答“神奇算法在哪里？”
想要知道神奇算法在哪里，我们得先知道所面对的问题在数学世界里是什么样的。而这套分拣系统的关键在于如何选择SKU（库存量单位）放入线边[3]工站，“有N个订单，组成这些订单的是K个SKU，应该选中哪Q（小于K）个SKU放入分拣线工站？”目标当然是N个订单中能在线边分拣得越多越好。
我们智能物流团队走出的第一步是选择一种最简单的分拣线型，即单线—单工站的情形（见图1）：
图1 最简单的分拣线型
而它类似于0—1装箱问题，在数学世界里是这个样子的：
这里xi表示SKU是否被放入工站，只能取值0或者1。当你为由这个0—1变量而产生的求解难度惴惴不安的时候，不用担心，我们通过对它的拉格朗日松弛问题求对偶，让一个只有连续决策变量的线性规划问题代替了它。在这个新问题中，其他都没有变，只是xi可以取0和1之间的任何值了。
针对这个问题，确定了问题的决策变量、优化目标、约束条件，建立了优化模型，并应用了经典的拉格朗日松弛算法进行求解，经过严密的证明推理，发现了拉格朗日松弛子对偶问题的对偶即为原混合整数规划模型的线性松弛模型。单纯借助拉格朗日松弛算法，在不需要借助商用求解器的情况下，对于订单数有3万的大订单集合，可以达到85%的拣选率，且完成时间在3分钟之内。
在3分钟内知道10万订单如何分解！当你为上面的结果欢欣鼓舞的时候，其实你还没有面临发网的困境，但从表1中可以看出，随着订单量的增加，已有算法的求解时间将呈现出指数型的增长。真实世界里的怪兽比你想象中的要庞大，发网的分拣线可不止一条线路、一个工站。我们面对的问题是这样的（见图2）：
表1 订单装箱问题的规模与最优解性质
图2 发网的分拣线
如图2所示，这里有6个工站，拣选订单的货框除了在面对面的工站无法传递之外，可以从第一列从左到右流通到最后一列。这样我们又得回答上面那个问题：“有N个订单，组成这些订单的是K个SKU，应该选中哪Q（小于K）个SKU放入分拣线工站？”不过现在是“应该选中哪Qi个SKU放入第i个工站？”
小小一变，让我们对问题的回答超级困难，课本上的方法相继败北。若继续用拉格朗日松弛算法，结果发现算法始终无法收敛，上下界更新得像蜗牛一样慢；Benders分解算法收敛更加缓慢。“神奇算法在哪里？”一张张订单给了我们一点灵感，每一张订单都是有父母姊妹的（见图3）。(www.xing528.com)
图3 订单家谱
这是一张订单们的家谱，深灰色订单如果被满足，箭头所指的浅灰色订单就会被满足。“若订单k中的SKU集合是订单p中的SKU集合的父集合，则若订单p无法被拣选，那么订单k也不能被拣选”，这样我们就有了新的算法来解决问题——从这个谱系的结构中找到关键的订单，转化成相应的有效不等式（cut）添加进算法进行求解。添加的原理如图4所示。
图4 添加的原理
当我们将这些有效不等式药水添加进算法后，在相同的求解时间内，有效提升了订单拣选数量（见图5）。
图5 添加有效不等式后的订单拣选量变化图
在数值实验的过程中，虽然添加有效不等式的效果较好，但是对于部分超大的订单集合，例如11万的订单集合，直接使用求解器求解是无法在发网给定的时间窗内给出可行的布局方案的，需要更进一步改进算法。这时我们想到了前面利用的SKU domination cuts，SKU之间的domination关系一定程度上反映了各SKU的价值，基于这个发现进一步设计了基于SKU价值分析的贪心启发式算法。此启发式算法在设计时不仅考虑了SKU的价值信息，还充分考虑了拣选区的布局结构。设计的构造式启发式算法不但可以有效求解储位分配问题，还可以解决储位分配过程中的负载均衡问题，同时指导日常的储位调整。
“神奇算法已经找到了吗？”远远没有！第一，就算是加入了这些药水，算法还没有我们期望得快；第二，发网新的问题又来了——如何在最大化订单拣选量的同时，让每个工站干的活尽量一样多？
问题虽然还没有完全被我们解决，但相信大家都已经知道问题的答案了！“神奇算法在哪里？”——神奇算法就在实际问题的结构里。行研院智能物流团队在为发网设计这一储位分配算法的过程中，也是经历了课本中一个一个算法使用无效的绝望后，才隐约看到了神奇算法的影子！
当然，如果你能和这些创造出算法世界中各类问题的人们站在一起就更棒了，我们有幸成为这样的算法研究者，和上海发网共同建立的联合研究中心也让我们能够把培养出的算法配置在这一条条的分拣线上。
【注释】
[1]原文发表于上海交通大学行业研究院官方微信公众号《安泰研值》2021年5月6日。
[2]上海交通大学中美物流研究院副研究员、上海交通大学行业研究院智能物流行研团队负责人。
[3]线边指生产线、流水线的边上。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
