写点什么

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

作者:杉数科技
  • 2022 年 8 月 04 日
  • 本文字数:4746 字

    阅读完需:约 16 分钟

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

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


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

一、问题描述

常规的分货问题描述如下:假设有 M 个大仓,N 个门店。设第 i 个大仓的分货限额为,需要将分配给各个门店,第 j 个门店分得,使得:



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


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

二、构造模型

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

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

对于每个门店来说,通过对消费者需求的预测,会生成一个期望达到的库存水平。大仓给门店分货的时候,需要尽可能满足门店的期望。因此,假设门店 j 的期望库存水平为,当前库存水平为为大仓 分给门店的分货量,为门店 j 取得分货量后扔未满足的量,那么,显然可以得到当前库存水平+分货量+未满足量=目标库存水平,即


当然,这个结论还有个不太严谨的地方:如果 已经超过 ,那么这个式子就无法满足了。因此将上述式子改成


同时,目标函数中,增加对的惩罚,即


这样,越小越好,那么当能够不低于的时候,能达到最小值 0。于是,当前模型变成了:




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





这样,分货量 Xi 在尽量满足门店目标库存水平的前提下,尽可能越小越好。其中 是对两个惩罚项的权重。通俗来讲,每分货 1 个单位,会有的惩罚分数,每未满足 1 个单位,会有的惩罚分数。显然,要远低于,这样才能避免,为了降低分货量的罚分,宁愿不满足门店目标库存水平的情况发生。

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

业务规则 2:大仓优先级

对于每个门店,分给这个门店货物的大仓是存在优先级的(这在业务上一般和距离、物流等因素相关),在分货过程中,希望尽可能从优先级最高的大仓进行分货,如果优先级最高的大仓没货,才从其他大仓分货。为了实现这个业务规则,假设 为大仓对门店的优先级。该值越小,说明优先级越高。那么结合优先级,将模型做如下改动:




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

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

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


其中 为最小分货单元, 为引入的辅助变量,必须是非负整数。可以这么理解,是以箱为单位的分货量, 是以件为单位的分货量。通过这个约束保证了的整数倍。


3.代码实现

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





下面使用 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
用户头像

杉数科技

关注

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

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

评论

发布
暂无评论
干货丨数学规划视角下的分仓优化解题思路_运筹优化_杉数科技_InfoQ写作社区