干货丨数学规划视角下的分仓优化解题思路

2022 年 8 月 04 日
本文字数：4746 字
阅读完需：约 16 分钟

分货作为供应链管理的重要环节，在电子消费、食品饮料、服装鞋帽、美妆日化等行业中的问题日益突出，尤其是大型企业，往往拥有成百上千的 SKU 和遍布各地的门店及仓库，分货不合理常常导致断货和库存积压并存，影响整体营销效果。新消费时代，市场需求复杂多变，分货难度加剧，人工分货很难保证各类产品在多个门店或仓库的存货量，借助智能决策技术优化分货策略成为越来越多企业的选择。

从运筹学角度看，分货问题是典型的混合整数规划问题，在求解优化的过程中，需要将业务逻辑进行翻译构建数学模型，再对数学模型进行求解，以下针对仓库向门店分货这个场景，介绍具体的求解优化步骤。

一、问题描述

常规的分货问题描述如下：假设有 M 个大仓，N 个门店。设第 i 个大仓的分货限额为 $S_{i}, i = 1, 2, \dots, M$ ，需要将 $S_{i}$ 分配给各个门店，第 j 个门店分得 $X_{(} i, j), i = 1, 2, \dots, M, j = 1, 2, \dots, N$ ，使得：

m i n O B J

s . t . i \sum X_{(} i, j) \leq S_{i}, i = 1, 2, \dots, M

这里的 $O B J$ 是某种可以衡量分货策略好坏的函数，分货策略越好，该函数值越小。举个简单的例子， $O B J$ 可以是该分货策略的预期缺货量，那么显然，缺货量越小，说明分货策略越好。当然，在实际生产决策中，衡量分货策略好坏往往是从多个维度来考量，诸如现货率、补货次数、补货周期等核心优化指标均要纳入考虑。

对于约束来说，除了上面所展示的，还有其他一系列业务相关约束，例如大仓优先级、最小分货单元限制等，在后续的介绍中，会说明如何将这些约束补充进去。

二、构造模型

构造模型，其实就是将业务目标和业务约束翻译成数学模型的过程。在复杂的分货场景下有很多的业务规则，为了满足这一系列的业务规则，需要设置合理的目标函数和约束。下面，我们从初始的目标函数（初始为 0）和约束（初始约束为 $\sum_{i} X_{(} i, j) \leq S_{i}$ ）开始，一步步将各个业务规则加入到模型中去。

业务规则 1：尽可能满足门店的需求

对于每个门店来说，通过对消费者需求的预测，会生成一个期望达到的库存水平。大仓给门店分货的时候，需要尽可能满足门店的期望。因此，假设门店 j 的期望库存水平为 $〖 T a r ﷩ j 〗 (〖 T a r 〗_{j} \geq 0)$ ，当前库存水平为 $〖 I n v 〗_{j} (〖 I n v 〗_{j} \geq 0) ，〖 X ﷩ i, j 〗$ ， $〖 X ﷩ i, j 〗$ 为大仓 $i$ 分给门店 $j$ 的分货量， $S j \geq 0$ 为门店 j 取得分货量后扔未满足的量，那么，显然可以得到当前库存水平+分货量+未满足量=目标库存水平，即

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} = 〖 T a r 〗_{j}

当然，这个结论还有个不太严谨的地方：如果 $〖 I n v 〗_{j} + \sum_{i} X_{(} i, j)$ 已经超过 $〖 T a r 〗_{j}$ ，那么这个式子就无法满足了。因此将上述式子改成

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} \geq 〖 T a r 〗_{j}

同时，目标函数中，增加对 $〖 X s 〗_{j}$ 的惩罚，即

O B J = (\sum i ﷩ ﷩ 〖 X s 〗_{i})

这样， $〖 X s 〗_{i}$ 越小越好，那么当 $〖 I n v 〗_{j} + \sum_{i} X_{(} i, j)$ 能够不低于 $〖 T a r 〗_{j}$ 的时候， $〖 X s 〗_{j}$ 能达到最小值 0。于是，当前模型变成了：

m i n i \sum 〖 X s 〗_{i}

s . t . i \sum X_{(} i, j) \leq S_{i}, i = 1, 2, \dots, M

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} \geq 〖 T a r 〗_{j}, i = 1, 2, \dots, M, j = 1, 2, \dots, N

这样的模型是不是已经足够满足我们的要求了呢？可以考察一下这样的情况，假设目标库存水平是 100，当前库存水平是 80，上游大仓的供货能力非常充足，那么对于分货量来说，分货 20 的时候，未满足量为 0；分货 30 的时候，未满足量也是 0。换句话说，分货量不低于 20 的时候，都能达到目标函数的最优解。但是从业务的角度来说，显然分货 20 是更加合理的，因此需要对分货量也增加惩罚：

m i n 〖 p e n a l t y_{o} r d e r i \sum j \sum X_{(} i, j) + p e n a l t y_{s} l a c k i \sum 〖 X s 〗_{i} 〗

s . t . i \sum X_{(} i, j) \leq S_{i}, i = 1, 2, \dots, M

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} \geq 〖 T a r 〗_{j}, i = 1, 2, \dots, M, j = 1, 2, \dots, N

这样，分货量 Xi 在尽量满足门店目标库存水平的前提下，尽可能越小越好。其中 $p e n a l t y_{o} r d e r$ 和 $p e n a l t y_{s} l a c k$ 是对两个惩罚项的权重。通俗来讲，每分货 1 个单位，会有 $p e n a l t y_{o} r d e r$ 的惩罚分数，每未满足 1 个单位，会有 $p e n a l t y_{s} l a c k$ 的惩罚分数。显然， $p e n a l t y_{o} r d e r$ 要远低于 $p e n a l t y_{s} l a c k$ ，这样才能避免，为了降低分货量的罚分，宁愿不满足门店目标库存水平的情况发生。

到这里，就建立了整个模型的雏形，或者说，最基本的业务目标——在大仓分货能力的限制下，尽可能满足下游门店的目标库存水平——已经达成了。后面会针对其他业务规则，对该模型继续进行补充。

业务规则 2：大仓优先级

对于每个门店，分给这个门店货物的大仓是存在优先级的（这在业务上一般和距离、物流等因素相关），在分货过程中，希望尽可能从优先级最高的大仓进行分货，如果优先级最高的大仓没货，才从其他大仓分货。为了实现这个业务规则，假设 $〖 w h_{r} a t i o ﷩ i, j 〗$ 为大仓 $i$ 对门店 $j$ 的优先级。该值越小，说明优先级越高。那么结合优先级，将模型做如下改动：

m i n 〖 p e n a l t y_{o} r d e r (\sum i ﷩ ﷩ j \sum 〖 〖 w h_{r} a t i o 〗_{(} i, j) X_{(} i, j) 〗) + p e n a l t y_{s} l a c k i \sum 〖 X s 〗_{i} 〗

s . t . i \sum X_{(} i, j) \leq S_{i}, i = 1, 2, \dots, M

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} \geq 〖 T a r 〗_{j}, i = 1, 2, \dots, M, j = 1, 2, \dots, N

可以看到，优先级高的大仓往门店分货的分货量获得的惩罚低一些，反之，优先级低的大仓往门店分货的分货量获得的惩罚会高一些。

业务规则 3：最小分货单元

在分货场景中，一般会有分货的最小单元，这个最小单元往往和商品的箱规有关系。例如一箱移动电源，里面有 20 件，分货的时候不能拆箱，那么分货量必须是 20 的倍数，这就是最小分货单元的概念。为了满足这个规则，添加如下约束：

m i q ∙ 〖 X o ﷩ i, j 〗 = X_{(} i, j), i = 1, 2, \dots, M, j = 1, 2, \dots, N

其中 $m i q$ 为最小分货单元， $〖 X o 〗_{(} i, j)$ 为引入的辅助变量，必须是非负整数。可以这么理解，是以箱为单位的分货量， $〖 X ﷩ i, j 〗$ 是以件为单位的分货量。通过这个约束保证了 $〖 X ﷩ i, j 〗$ 为 $m i q$ 的整数倍。

3.代码实现

通过第 3 节的介绍，最终获取模型

m i n 〖 p e n a l t y_{o} r d e r i \sum j \sum 〖 〖 w h_{r} a t i o 〗_{(} i, j) X_{(} i, j) 〗 + p e n a l t y_{s} l a c k i \sum 〖 X s 〗_{i} 〗

s . t . i \sum X_{(} i, j) \leq S_{i}, i = 1, 2, \dots, M

〖 I n v 〗_{j} + i \sum X_{(} i, j) + 〖 X s 〗_{j} \geq 〖 T a r 〗_{j}, i = 1, 2, \dots, M, j = 1, 2, \dots, N

m i q ∙ 〖 X o 〗_{(} i, j) = X_{(} i, j), i = 1, 2, \dots, M, j = 1, 2, \dots, N

下面使用 COPT 来实现。

from coptpy import Envr, COPT

"""问题参数"""# 大仓和门店列表WH_LIST = ["wh1", "wh2"]STORE_LIST = ["store1", "store2", "store3"]# 大仓总量WH_CAPACITY = {"wh1": 100, "wh2": 300}# 门店目标库存水平STORE_TARGET_INV = {"store1": 100, "store2": 80, "store3": 120}# 门店库存水平STORE_INV = {"store1": 50, "store2": 20, "store3": 30}# 大仓优先级PRIORITY = {    ("wh1", "store1"): 0.9,    ("wh2", "store1"): 0.1,    ("wh1", "store2"): 0.9,    ("wh2", "store2"): 0.1,    ("wh1", "store3"): 0.05,    ("wh2", "store3"): 0.95,}# 最小分货单元MIQ = 6# 惩罚系数PENALTY_ORDER = 1PENALTY_SLACK = 100
"""创建模型"""# 创建模型env = Envr()model = env.createModel("xiaomi")
# 生成变量x_dict = {}        # 分货量x_slack_dict = {}  # 分货之后的缺货量x_int_dict = {}    # 为了满足最小分货单元的辅助变量for i in WH_LIST:    for j in STORE_LIST:        x_dict[i, j] = model.addVar(vtype=COPT.CONTINUOUS, lb=0, name=f"order_{i}_{j}")        x_int_dict[i, j] = model.addVar(vtype=COPT.INTEGER, lb=0, name=f"order_int_{i}_{j}")for j in STORE_LIST:    x_slack_dict[j] = model.addVar(vtype=COPT.CONTINUOUS, lb=0, name=f"order_slack_{j}")    # 设置目标函数obj = PENALTY_ORDER * sum([sum([PRIORITY[i, j] * x_dict[i, j] for j in STORE_LIST]) for i in WH_LIST])obj += PENALTY_SLACK * sum([x_slack_dict[j] for j in STORE_LIST])model.setObjective(obj, sense=COPT.MINIMIZE)
# 增加约束for i in WH_LIST:    # 每个大仓的分货总量不能超过限制    model.addConstr(sum([x_dict[i, j] for j in STORE_LIST]) <= WH_CAPACITY[i], f"le_capacity_{i}")for j in STORE_LIST:    # 每个门店补货之后的库存水平要尽可能超过目标库存水平    model.addConstr(STORE_INV[j] + sum([x_dict[i, j] for i in WH_LIST]) + x_slack_dict[j] >= STORE_TARGET_INV[j], f"target_inventory_{j}")for i in WH_LIST:    for j in STORE_LIST:        # 每个大仓发给每个门店的分货量要是最小分货单元的倍数        model.addConstr(MIQ * x_int_dict[i, j] == x_dict[i, j], f"miq_{i}_{j}")
"""模型求解"""model.solve()for i in WH_LIST:    for j in STORE_LIST:        # 获取大仓i发给门店j的分货量        print(f"{i} -> {j}: {x_dict[i, j].x}")

复制代码

执行代码之后，得到分货结果：

wh1 -> store1: 0.0

wh1 -> store2: 0.0

wh1 -> store3: 90.0

wh2 -> store1: 54.0

wh2 -> store2: 60.0

wh2 -> store3: 0.0

4.总结

基于运筹优化技术实现智能分货的关键是算法、建模和求解，在具体实践过程中，算法设计是第一步，也是很关键的一步，需要深入业务场景，对业务逻辑进行深度梳理和拆解，这将为后续的算法工作打下良好的基础。完成了业务逻辑的清晰梳理及后续的建模，COPT 的建模编程过程就会非常顺畅。

为了便于理解，本文对分货场景进行了很多简化，实际的分货优化算法和模型要复杂得多，考虑的因素也更加丰富，例如门店库容上下限、补货门店数的限制、物流因素的影响、不同门店的分货紧急程度等等。而且，商品 X 门店的组合数量会很庞大，这也是人工分货越来越难以满足实际需求的原因。不过，再复杂的业务逻辑也是由一个个简单的逻辑搭建起来的。

除了算法和模型之外，实际应用中求解规模也更加庞大，值得一提的是，目前求解器 COPT 可以支持高效求解上亿量级的问题。在前文提到的某著名电子消费品牌的应用案例中，由于该企业的商品 X 门店的组合数量达到百万级别，数据量达到上亿级别，单台服务器无法支撑如此庞大的运算。在实施过程中，该企业使用了 COPT 的浮动授权+spark 分布式集群+Azkaban 平台相结合的技术框架，最终实现了日维度上小时级别的分货问题求解。

分货项目上线后，该企业的多项业务指标都取得了明显改善，其中门店现货率平均提升 8%，补货次数平均减少 0.15 次，周转天数平均降低 10 天，出货量也大幅提升，为全年 GMV 带来了数千万的增长。据该企业反馈，分货项目得到了内部各个层面的高度认可，是该企业目前唯一一个正在线上运行的 AI 项目。

头部企业的实践数据表明，基于优化算法和 COPT 的智能决策解决方案，正成为企业在新消费环境下实现增长的重要方式。而且，智能决策不仅能够解决分货难题，在供应链诸多环节，比如生产排程、物流运输、库存优化等，都有巨大应用价值。

更多求解器应用案例，可在 CORIDM 教学平台了解

CORIDM（全称 Center for Operation Research and Intelligent Decision Making）是杉数科技推出的运筹与智能决策的案例教学平台，集成了多个经典运筹学问题以及多个行业多个领域的真实案例，并且提供一站式的 Jupyter Notebook 编程环境，旨在为教授和学生带来“理论结合实践”的案例教学/学习体验。

1、内嵌 Python 编程/COPT/运筹优化等基础知识介绍。用户可以在平台中学习各种基础知识，为解决工业界的实际问题做充足的准备；

2、汇聚零售、消费、制造、物流、航空等多个行业的智能决策案例。对于每个案例，平台提供了详细的案例介绍、解决方法和数学模型、实现代码、总结拓展等，提供了充足的学习资源，能够让学习者充分掌握每个案例的内容和思想；

3、提供开箱即用的 Jupyter Notebook 编程环境。所需的 Python 第三方包包括 COPT 求解器已经部署完成，用户不需要自行安装任何软件即可运行代码；

为了帮助用户更好地应用 CORIDM 平台，我们建立了企业微信社群，届时将不定时在群内发布课程/案例更新信息，方便用户进行交流与问题反馈。大家可以通过下方二维码加入求解器 COPT 群交流（QQ 群 811049651）或 CORIDM 交流群。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/e64302642a8990e78a86db3e8】。文章转载请联系作者。

杉数科技

关注

服务逾20个行业的超100家龙头企业 2021.04.07 加入

杉数科技，是中国领先的人工智能决策优化技术服务企业，通过中国首个自研商用求解器COPT，为企业打造从数据到决策的端到端决策产品平台，帮助客户解决一系列业务场景中的决策优化难题，进一步助力企业降本增效。

发布

暂无评论

创作场景