人工分拣vs机器分拣表格（分拣自动派单的数学规划求解剖析）

人工分拣vs机器分拣表格（分拣自动派单的数学规划求解剖析）⑵形式：maximize(最大化，缩写为max.)：表示优化的方向是最大化目标，也可以是最小化(minimize 缩写为min.)。而优化的目标是后面的目标函数(objective function)：这里就是2x1 x2；⑴变量：用变量x1，x2来描述这个问题，跟用变量x，y，对描述问题本身没什么影响。但是从数学形式上来说，用x1，x2说明两个量都是同一类的变量(叫做决策变量)。进一步地，可以用一个向量x=（x1 x2）表示这些变量。此问题可描述为：设z=2x y，式中变量x，y满足下列条件:求z的最大值和最小值。先看求最大值，把这个问题写成线性规划的规范形式：这个看上去跟上面的描述区别不大，就是替换了x，y变量，增加了一些英文，还有一个莫名其妙的变换。下面说明为什么要整理成这样的形式：

这篇文章是想跟大家分享一下我们是怎么用数学规划处理分拣派单问题的。文章里用到的数学是简单的(对问题建模只用到了加减乘除，大于小于，最大最小。求解涉及的数学要复杂一些，我们在这里是直接调用求解器)。希望大家都能在这里找到感兴趣的东西。

1.概述

数学规划(Mathematical Programming)是用数学方法解决如何对有限资源进行分配和控制，得到最优的结果(例如最大化收益，最小化成本等等)。通常我们会对需求进行定性定量分析，建立恰当的数学模型描述该问题，设计合适的计算方法来寻找问题的最优解，探索研究模型和算法的理论性质，考察算法的计算性能等。由于很多数学问题难以直接给出显式解，最优化模型就成为最常见的选择。其被广泛运用于各种领域，包括交通(调度，路径规划)，物流(仓储，配送)，制造(生产计划，流程优化)，能源(设施布局，能源分配)，金融(资产配置，风险控制)，等等。 本文先简述了数学规划中一些重要的基本概念及方法，包括线性规划，整数规划，约束规划，以及求解器；然后针对物流中心仓分拣自动派单问题 - 即如何把待分拣的商品指派给合适的分拣员，作为一个约束规划问题来建模求解。

2.数学规划基本概念

2.1线性规划

我们看看这样一个操作：在图上画几条直线，围出一个区域打上阴影。拿一把直尺，摆成一定的角度，移来移去寻找最大值和最小值。这是中学数学里讲到的简单线性规划的图解法。

此问题可描述为：设z=2x y，式中变量x，y满足下列条件:

求z的最大值和最小值。先看求最大值，把这个问题写成线性规划的规范形式：

这个看上去跟上面的描述区别不大，就是替换了x，y变量，增加了一些英文，还有一个莫名其妙的变换。下面说明为什么要整理成这样的形式：

⑴变量：用变量x1，x2来描述这个问题，跟用变量x，y，对描述问题本身没什么影响。但是从数学形式上来说，用x1，x2说明两个量都是同一类的变量(叫做决策变量)。进一步地，可以用一个向量x=（x1 x2）表示这些变量。

⑵形式：maximize(最大化，缩写为max.)：表示优化的方向是最大化目标，也可以是最小化(minimize 缩写为min.)。而优化的目标是后面的目标函数(objective function)：这里就是2x1 x2；

subject to(缩写为s.t.)：表示这部分是约束条件(constraints)；

and：那就是and了。

⑶变换：是为了让这些方程变成形式统一的线性方程组(都有x1，x2和相应的系数)，然后就可以写成向量形式(写成向量也是为了能偷懒)：

而这里的目标函2x1 x2也可以写成向量形式:

综合以上，我们可以对线性规划问题做一个形式化描述：

线性规划问题可以用规范形式(canonical form)表示为：找到一个向量x，使得：

其中向量x就是问题要确定的决策变量构成的向量(包含了所有的变量们)，向量c和b是用问题中给定的条件构造的向量，其中c^T表示系数向量c和变量向量x做一个点积 (计算方法就是c1x1 c2x2 ...cixi)，得出来的目标值是一个标量(就是一个数字值)。规范形式是描述一个规划问题的通用形式，在相关内容中经常会看到。

所以，线性规划(Linear Programming，缩写为LP，也叫Linear Optimization，线性优化)是一个用数学模型得到最优的结果(最大化或者最小化)的方法，其中的要求(例如目标和约束)是用线性关系表示的。在实际应用中，线性规划问题可能会有茫茫多的决策变量(上百万)，和非常多的约束条件(成千上万)，需要用计算机和合适的算法求解。

2.2 整数规划

在有些问题中，变量不能取连续值，而必须取离散的整数值，典型的就是商品数量。如果我去苹果商店说要买0.5台苹果手机，店员很可能就会用一种充满关爱的眼神看我了。

从模型上来说，整数线性规划(integer Linear Programming，缩写为ILP)就是在线性规划的基础上，增加一个变量是整数的约束。但是在求解和结果上会很不一样。我们来看一下下面2个问题：

问题A(线性优化，Linear opt.)：

问题B(整数优化，Integer opt.)：

问题A和问题B的目标函数和约束都是一样的线性关系，只是问题B增加了变量是整数(integer)的约束。所以问题A是线性优化(linear optimization)，问题B是整数优化(integer optimization)。我们求出这2个问题的解，并在图上画出来。

线性优化的解是25，在点x=0，y=2.5；

整数优化的解是23，在x=3，y=2。

从上图中可以看到，整数优化的解(绿色)，并不是在可行域中(中间直角梯形围成的区域)离线性优化的解(红色)最近的整数点上。通常来说，线性优化问题的解，和相应的整数优化问题的解，会离得很远。因此，这两类问题需要不同的方法求解。

2.3 约束规划

有时候问题的目标函数不能表示成线性关系。例如对于一个排产问题，假设有张三，李四2个人一起生产一批水果手机。因为熟练程度不同，两人花的时间也不相同。张三生产1台要3分钟，李四生产1台要4分钟。优化的目标是尽快完成这一批手机的生产，那么张三和李四的生产任务要怎么安排？

假设任务分配是：张三生产x台，李四生产y台，规定两人必须独立完成各自的手机生产任务，那么这一批手机生产完成的时间是2人所花的时间中最长的一个，也就是max(3x 4y)。这是这个问题的目标函数，它不是一个线性函数，也就不能用整数线性规划的方法求解。

这种更一般的规划问题都可以归为约束规划(Constraint Programming，缩写为CP)，也有相应的求解方法。

2.4 优化问题求解器

我们借用OR-Tools的说明来整理一下上面提到的这三类优化问题和推荐的求解器：

类型	OR-Tools类型	缩写	求解器
线性规划	Linear Programming	LP	Glop
整数规划/混合整数规划	Mixed-Integer Programming	MIP	SCIP
约束规划	Constraint Programming	CP	CP-SAT

OR-Tools是Google提供的解决组合优化问题(combinatorial optimization)的开源软件包，组合优化问题是从一堆的可行解中找出问题的最优解。OR-tools包括了以下问题的求解器：

◇约束规划(Constraint Programming)

◇线性和混合整数规划(Linear and Mixed-Integer Programming)

◇车辆路径规划(Vehicle Routing)

◇图论算法(Graph Algorithms)

OR-Tools是用C 写的，可以用Python，Java，C#调用，使用起来也很方便。对于分拣派单这种规模不大的问题是够用的。当然，其在计算性能和问题规模上还比不上商用的求解器，在大规模和有时效性要求的问题上可能会不够用。

OR-Tools里的OR指的是operational research(缩写为OR，翻译成运筹学)。

线性规划推荐的求解器是Glop，全称是Google linear optimization，是Google自家的线性规划求解器。

混合整数规划(mixed-integer programming，缩写为MIP)是规划问题的决策变量中，有部分不要求是整数值。例如一个店铺里的商品，有按斤卖的(数量不一定是整数)，有按个卖的(数量一定是整数)。混合整数规划是整数规划的更一般的形式，推荐的求解器是SCIP。

SCIP全称是Solving Constraint Integer Programs，意思就是求解约束整数规划。这是德国柏林Zuse研究所(Zuse Institute Berlin，缩写为ZIB)开发的非商业求解器，用于求解混合整数规划(MIP)和混合整数非线性规划(mixed integer nonlinear programming，缩写为MINLP)

约束规划(CP)推荐的求解器是CP-SAT。SAT是satisfiability的缩写，意思是可满足性，说明这是基于可满足性的算法。

3.分拣自动派单问题：建模及求解

目前的分拣派单是这样一个问题：对一个B2C仓(例如9仓)的一个拣货组(例如6组休闲零食组)，在这天上班的有10多个员工，对应要分拣的有100多个商品。怎样在满足一系列条件的情况下，把这些商品分给这些员工，目标是让他们的绩效均衡。因为绩效是跟分拣的商品数和订单量相关的，能力强的员工在同样的时间内能分拣更多的订单，就能拿到更高的绩效。绩效均衡，是要能力强的人拿的更多，能力相近的人拿的相近。这里我们讨论的是一个商品只能分给一个员工的情况。

对一个规划问题建模，就是要确定三个要素：决策变量，约束条件，目标函数。

⑴决策变量：

分拣派单是一个指派问题，商品和员工之间的指派关系可以用一个矩阵来描述。

假设我们把5个商品指派给3个员工，指派关系是：

张三分到水果4，水果5；

李四分到水果6，水果7；

王五分到水果8。

这个指派关系可以用一张表来表示，就是：

这里用1和0分别表示是否有指派关系：1表示有指派，0表示没有指派。

但是在建模阶段，还没有求解之前，我们是不知道具体的指派结果的。所以建模的时候这张表中的元素都用未知量x表示，那就是：

x的下标用来区分不同位置：例如，x[0 0]就表示第0行，第0列相交的位置，也就是张三和水果4相交的单元格(计算机计数通常是从0开始的)。所有的x取值只能是0或1，这是在定义变量的时候就确定好的。

当这个表的结构确定好后，在接下来的过程中都不用改变人员和商品在表中的位置了，会变的只有其中x的值。这15个x组成了一的矩阵X（3 5），就是这个问题的决策变量矩阵：

⑵约束条件：

这一步就是要把实际业务中的条件和限制，转化成用数学描述的约束条件。首先要加上的约束，是一个商品必须分给一个员工，而且只能分给一个员工：

其次，一个员工能分拣的SKU数是有上限的，这里假设是2个(总共才5个商品):

实际问题中还有其它的条件和限制，也要转化成对应的约束。

⑶目标函数

我们再回顾一下问题的目标：能力强的人派更多的单量，拿更多的绩效。能力相近的则相近。

假设员工的能力值(一个给出的衡量工作能力和应得绩效的值)，商品的数量和绩效如下：

取这些值是为了方便说明，这样计算的结果都是整数。

原问题的目标要转化成数学描述，构造的目标函数要跟原问题的目标是一致的(或者说是等效的)。这里我们构造一个指标【约化绩效】，设计成当员工之间的约化绩效相等时，其真实绩效就与其能力值成比例。这个约化绩效的计算方法如下：

计算出来所有商品对员工的约化绩效如下表：

那么每个员工的约化绩效，就是其被指派的商品对应的约化绩效的和：

这里的rp指的是约化绩效(reduced pay，缩写为rp)，不是那个RP。同样，可以用一个向量rp表示三个员工的约化绩效：

所以问题的目标就转化为让员工的约化绩效的差别尽量小，也就是员工中约化绩效最大的，跟约化绩效最小的之间的差别尽量小。写成数学表达式就是：

我们把这个分拣派单问题写成规范形式(#后面是注释)：

这样对问题的建模就完成了。接下来就可以按这个模型写代码，用求解器求解了。

这个问题最优解的指派关系为：

对应的约化绩效为：

对应的真实绩效为：

这个结果看上去好像不是很美，员工的绩效和其能力值没有符合得非常好。这是因为约束了每个员工最多只能派到2个商品。在这个约束条件下，最优的结果就是这样了。

为了验证确实是约束的缘故，我们把员工商品数的约束放宽到3个(3个就相当于没有这个约束了。因为每人至少会有1个，那1个人最多也就3个)，那么问题的规范形式就是：

这个问题最优解的指派关系：

对应的约化绩效为：

对应的真实绩效为：

这个结果看上去员工的绩效和其能力值就符合的相当好了。

对于实际的分拣派单问题，其建模和求解是类似的。不过有了更多的商品和更多的人员(也就有了更多的决策变量)，更多的约束条件，这样求解出来需要更长的时间。

4.总结与展望

在本文中，我们先是简单看了一下数学规划中的线性规划，整数规划和约束规划。然后把一个分拣派单问题作为约束规划问题建模，并用求解器解出了最优解。这种基于数学规划的派单算法如今在B2C仓一个一个拣货组的推进，根据不同拣货组各自的特性，转化为相应的约束。目前已经用到了休闲零食，农副蛋蛋，蔬菜，水果这几个拣货组上。其效果也得到了业务方的认可，派单结果只需要根据当时情况做少量修改就可以使用，极大地提高了派单工作的效率和结果的公平性。数学规划在各个领域中都有广泛的应用，今后我们也会用来解决更多的优化相关的问题。