基于循环神经 络架构的大规模供应链 络的仿真和优化

导读：很多大规模供应链 络中包括成千上万、甚至几十万种原材料、中间产品和最终产品。这些 络面临着十分复杂的生产和库存管理问题。本 告将介绍一种基于循环神经 络架构的供应链仿真和优化算法，大大提升仿真和优化的速度，可以很好地解决大规模供应链 络的库存管理优化问题。

全文目录：

01

背景介绍

在过去很长一段时间里，AI 有着突飞猛进的发展。商业中比较常见的应用包括：推荐、自然语言处理、图像识别、强化学习相关等。

那么到底是什么推动了 AI 技术大踏步的前进？我们会发现其背后的主要原动力就是摩尔定律。

摩尔定律提到基本上每两年，集成电路上可以容纳的晶体管数目都会翻一番，年化增长率为 40%，以汽车为例，如果按照摩尔定律的速度发展，1970 年的大众甲壳虫现在只卖一美分且时速能达到每小时 5000 公里。如果说工业革命带来了机械力的提升，那么摩尔定律则带来了计算力的提升。

在供应链管理当中，做算法的人更多的是关注供应链建模与优化，包括物流 络的规划、人员的排班、配送路径优化、库存管理、生产计划和需求预测等问题。传统所用的一些建模和优化的方法，比如非常常见的线性规划，混合整数规划，或者在仿真这块，比较常见的是离散事件仿真等等，这些工具目前无法非常充分利用并行计算的大规模计算。

例如最有名的优化问题求解器 Gurobi 和 CPLEX 只能支持最多 32 核，但实验室里普通的服务器就有 48 核，这样的计算能力，没有办法很好地利用起来。所以，在供应链建模与优化这个领域 ，如何把人工智能各种各样的算法运用起来，或者与传统的运筹学算法运用起来，将摩尔定律带给我们的强大算力很好地利用，这是一个亟待解决的问题。

本团队这几年一直在尝试把一些人工智能的方法和供应链领域的建模和优化进行联合。

目前也提到了一些方法把人工智能的技术应用到供应链管理当中，比如需求预测等等，但在这个层面上，把人工智能和供应链管理结合起来的方法，其实是找供应链管理当中的某一个应用场景，用人工智能的方法来解决，还是在用人工智能的方法解决供应链管理上的问题，并没有通过供应链管理提出新的问题，给出新的人工智能的方法，因此需要更多去考虑这两者如何能够更深层次的结合。

本团队在过去一段时间中，都在尝试一些人工智能技术的一些底层方法，比如深度学习等很多工具，其最大优势就是可以很好利用强大的计算能力，那么有什么办法能够把这样的计算能力同样放到供应链管理当中来呢？下面将分享一些本团队最近做的工作。

—

02

本团队的工作

这是一个很经典的供应链管理问题——库存优化问题。在生产系统中，BOM 也就是物料清单，指要生产出来的产品中的原材料、半成品、最后的成品以及他们之间的生产关系和装配关系。在生产管理中，很重要的问题就是库存，特别是需要安全库存。我们无法知道未来某个时候的订单量具体是多少，可能存在一些波动，因此在供应链管理当中，会通过安全库存的方法，对冲掉所带来的波动。因此这个重要的问题就变成了求安全库存问题，在 BOM 所形成的 络中，安全库存到底应该放在哪些产品上。

这是本团队给国内某知名的头部制造商做过的项目，这个 BOM 中节点超过五十万个， 络当中的链接超过了 400 万条。在这样 BOM 中相对活跃的节点有 5 万个，这些活跃节点的链接大概有 50 万条；且该 络中的 络结构还有各种各样的回路， 络结构复杂。另外此供应链在任何一个时间点的库存价值，差不多有 200 亿人民币。从公司的角度，他并不想把库存管理问题分成一个个产品类，因为所有的产品中，要共享很多中间的产成品和原材料。因此，从公司的角度，想站在一个宏观的角度同时去解决这么多产品所组合起来的大规模库存管理问题。

在研究这样一个库存策略优化问题时，关键问题在于安全库存应该放在哪，如果每个产品都有安全库存，那么管理起来比较困难，因此我们希望安全库存最后只放在比较少，比如 5% 的产品上。第二个需要解决的问题是，决定了放在这个节点上后，到底应该放多少。这个问题本身是一个超大规模的优化问题，如果这个问题本身规模不大，比如 100 个节点，那么文献当中已经有一些方法能够解决了，尽管这些方法本身比较慢，但基本上几个小时还是能够找到解的。但 50 万个节点的 BOM 中，主要的挑战来自于计算能力不足或者计算时间太长。

传统的供应链领域解决方法，比如随机服务的模型，或者保证服务模型，他们都有各自所带来的问题，且对这个 BOM 络结构有一定的要求，比如需要生产关系是一个串行或者是一个装配系统 ，如果一旦存在环的情况，那么传统的模型将不可用。又如保证服务模型还要把这样一个随机问题转化成一个确定性问题，在转化的过程中，可能也会带来各种各样的难点。

本团队因此选择了另外一类方法——仿真方法，这种方法对一般的 络结构都ok，并不需要是什么装配系统，但是仿真方法遇到的最主要的问题是会比较慢。因此，本团队想仿真这样一个库存系统。在企业生产管理，尤其跟库存管理相关的生产计划是以天为作业单位的。

综上，以天为单位，以一个 Base Stock Policy 进行库存管理，计算 Inventory Positions，产出上游订单，同时接受已完成的订单交付，满足外部需求，更新当前的 Inventories 和 Backlogs。在生产环节，会根据今天的订单，根据原材料情况 ，根据不同材料是否齐套来决定当天的生产量。依照此仿真流程，进行 100 天的仿真，将仿真得到的成本加和起来，这样就知道策略在未来 100 天的成本。且需要仿真多次，通过大数定理或中心极限定理来估算期望成本。想要解决这个问题，我们的变量是库存位置和库存量，安全库存放在什么地方、应该放多少。我们的目标有两条，最主要的目标是希望库存成本比较低；第二个目标是希望安全库存的位置相对比较少，便于管理。

当前问题的难度是规模变得太大之后算力不够。传统的仿真模型背后的优化方法是Glasserman 和Tayur 在 1995 年的时候提出来的。首先建立一个仿真模型，然后进行梯度计算。在传统的仿真优化领域，大家是用 IPA 去算梯度。当有了梯度后，和神经 络训练是一样的，可以用随机梯度下降方法去求解。所面临的主要的问题，是仿真模型计算复杂度是 Tn^2，n 为 BOM 中 络节点的个数。

本团队在机器上一次性最多只能跑大概 5000 个节点，因为要计算目标函数，只跑一次是不够的，但仿真一次大概要一个小时，计算梯度的话时间就更长。如果仿真和梯度计算这么慢，无法支持去解决这样一个优化问题。所以当前目标为如何把运行时间降到一个可接受的水平，能够在几个小时之内，至少解决 5 万个节点的库存优化问题。

循环神经 络是一个随着时间变化的神经 络，因此利用循环神经 络一般是来解决具有持续性的问题，比如语音识别、机器翻译等领域。在训练循环神经 络时，也有一个目标函数用来优化循环神经 络当中的权重。在循环神经 络领域，哪怕是千万级别的循环神经 络的结构也能解决。因此基于上述思路，供应链管理问题也是一样，通过反向传播的方法去计算梯度，然后使用随机梯度下降的方法去解决优化问题。

从结构上来，做库存优化和循环神经 络的训练模式是很像的。从结构上看，这都是一个多阶段的问题，在此过程中参数的变化都是以某一种连续函数的方式在发生变化。在优化过程中，两者想要优化的内容不同，循环神经 络想要优化神经 络的权重，而在库存管理当中，想要优化的是安全库存的量。但优化方法都是一样的，都是用随机梯度下降法。在此过程中，我们没有用循环神经 络去做任何训练，只是用到循环神经 络背后的计算工具，所以我们并不是简单地把循环神经 络拿到这个问题上来训练数据。

为什么循环神经 络可以解决大规模的问题？总结下来有三点：

利用 BOM 的邻接矩阵，将整个仿真过程转化为矩阵/向量运算。通过 TensorFlow，将 络表示为邻接矩阵，这样可以很方便的通过一行代码并行化，甚至在 GPU 上运行。但在张量化的时候，是一个 50 万 x 50 万的 络，对内存的要求也比较高。为了解决这个问题，我们发现在生产系统中， 络本身是非常稀疏的。

因此，我们用稀疏矩阵技术减小内存消耗，另外考虑到平均出度来表示 络的稀疏度。在数据中看到一个非常有趣的现象，平均出度相当于是个常数，不会随 络大小变化。在生产 络中，这个度是指一个部件或者半成品当中有多少一阶段的产品装配其中，该数字不随 络大小变化，说明对于一类产品，该数字是有上限的。通过这个邻接矩阵和稀疏矩阵，大大降低了对内存的要求。

为了让计算变得更快，要构建计算图。通过反向传播的方法去计算梯度。在供应链管理当中，大家都用 IPA 方法，其实 IPA 和 BP 所计算出来梯度是一样的。BP 采取的是一种反向模式，计算会快很多。因此，本团队把反向传播的思想借鉴过来，去对仿真模型构建了计算图，同时对计算图做了一个定制化的反向传播计算梯度的算法。

最后一步采用了 L1-正则化的方法，在之前的目标函数加上 L1-正则项，求解带 L1-正则项的优化问题来选择库存放置的位置，基于上一步的结果，固定特定位置为 0，若为 0 的话，这个地方就不安排安全库存。受到高斯回归领域 Relax Lasso 算法的启发，提出了两阶段优化算法。

第一阶段是采用随机版的快速迭代阈值收缩算法进行求解，第二阶段采用随机梯度下降算法来求解。

上图是本团队的数值仿真结果，时间复杂度由之前的 Tn^2降为 Tn。举例来说对 1万个节点的问题，传统的仿真方法要 200 多分钟，现在用本团队的算法，只用1.48s，计算性能提供了 8600 倍。通过 Tensorflow 框架去构建计算图，然后用反向传播去算梯度，这里使用了CPU ，因为用 GPU 的加速没有取得明显效果。第二步在计算梯度的时候，以前用的是IPA，现在通过用稠密矩阵用 BP 算法，计算性能又提升了 2300 倍。对 1 万个节点，大概 5.68 秒就能够计算出来。

最后，给大家展示一下库存优化结果，左边是 Stage 1，左边这一列是计算成本，这里面有四个不同的图，它对应于四个不同的规模。右边是库存位置，可以看到库存位置 降得很快。然后本团队又进行了 Stage 2，相比 Stage 1 还是有 2% 到 3% 的提高，5 万个节点基本上都能在两个小时左右解决，50 万维的节点大概需要一天。

总结：

本团队主要对库存优化问题和循环神经 络做了类比，两者有相似之处，因此想到可以通过循环神经 络解决供应链管理中的大规模问题。同时，通过 Tensorflow 这样高性能的计算工具，降低了建模、优化和大规模并行化所带来的障碍。在实验中发现，通过我们的方法，无论在仿真还在梯度计算的方面，运行速度都提高了数千倍。该方法可进一步拓展到更大或者其他一些大规模排队 络的建模和优化中，包括交通 络和服务 络等。

今天的分享就到这里，谢谢大家。

｜分享嘉宾｜

洪流

复旦大学管理学院&大数据学院 教授

洪流教授本科毕业于清华大学，博士毕业于美国西北大学。现任复旦大学特聘教授、弘毅讲席教授、大数据学院副院长和管理科学系系主任；曾任香港城市大学管理科学讲座教授，香港科技大学教授和金融工程实验室主任等。研究主要集中在随机运筹学、数据科学、供应链管理、风险管理等领域，在国际顶尖期刊上发表学术论文五十余篇。目前担任INFORMS仿真分会主席、中国管理现代化研究会风险管理专委会主任和中国运筹学会金融工程和风险管理分会副理事长。咨询过的公司包括华为、可口可乐、香港航空货运站、交通银行、进出口银行等。

｜DataFun新媒体矩阵｜

｜关于DataFun｜