烟草工业企业多仓库发货的货源平衡与调度优化模型

杨 军，罗 卫，何 哲，熊世进，陈永锋

（湖南中烟物流有限责任公司，湖南 长沙 410000）

1 研究背景

中国是目前世界上最大的烟草生产国和消耗国之一，中国烟草年营收额1万亿元，纳税超过9 000亿元。每年巨大的营收背后，是庞大的物流压力，因此建设现代化的供应链物流体系，已经成为烟草工业企业提高经营效率，减少物流成本的重要方式之一。同时，为了更精准地响应到货点的服务需求，更合理地选择配送线路，更快速地完成物流配送，导致烟草工业企业对整个供应链的管理和把控有着非常高的要求。因此，一个高效率低成本的物流供应体系，是烟草工业企业提高客户满意度，增强自身核心竞争力，保持企业健康稳定发展的重要手段之一。

烟草工业企业的整个生产供应环节其实和大多数企业没有太大区别（如图1），然而在实际运营的细节上，却存在着许多不同：

（1）企业在全国通常只有几个发货点，而需求点则多达数百个且遍布全国。

（2）物流公司拥有多种车型，每种车型具有不同的最大装载量，如果装载量不足，烟草公司需要向物流公司提供额外的补贴，从而造成巨大的成本浪费。

（3）由于每个发货点的生产能力以及供给量不同，为了成本最优，管理者经常会考虑在仓库之间进行货物的转运。

（4）一个发货点通常在配送中会通过拼车来降低运输成本。

图1 烟草工业企业生产供应环节

但是从目前的实际运营方式来看，烟草工业企业没有考虑如何系统高效地完成整个运输配送的过程。在传统模式下，企业的物流部门被动接收营销部门的发货需求编排发货计划。当指定的发货点货源不足时，再通过移库补充货源，因此经常会产生大量的移库成本，甚至由于移库不及时导致无法按时发货。此外，部分畅销的品类由于安全库存较低，当产生临时需求订单时，往往需要浪费大量人力处理，甚至出现由于发货点分配不合理导致无法按时发货的情况。

针对上述问题，本文构建了一个基于混合型整数线性规划的烟草运输调度模型，能够综合考虑到烟草工业企业运输的各个环节，计算得出最优的生产运输调度方案，在考虑企业各个发货点的生产能力的同时，以满足需求点的需求为原则，帮助企业制定发货计划和运输调度计划，实现成本的最优。

2 相关研究

对于烟草工业企业的物流运输调度问题，已经有相关学者做过一些研究。黄飞航等人（2014）[1]考虑了现在烟草工业企业物流仓库中普通存在的人工进行车辆调度的问题，设计了一个方法将排队管理系统应用到仓库管理中，从而提高仓库装卸货的效率。黄戈文等（2015）[2]融合了云计算、物联网、大数据、GIS、GPS 等设备，设计研发了一套基于云计算的烟草物流运输调度系统，能够对烟草配送的各个细节进行监控，从而达到提高物流效率、降低成本的效果。郭贤正等（2014）[3]基于烟草运输管理现有业务的瓶颈分析，提出了运输管理系统中智能车辆调度功能的设计方法，并总结了整个执行过程中全程可视化监控和管理的实现方法和实施经验。叶小龙等（2012）[4]针对烟草工业企业物流配送效率低成本高的缺点，提出了用配送中心选址方法以及配送网络的一般设计方法来改进整个供应链。

虽然已有部分学者研究过烟草工业企业的物流解决方案，现有大多数研究主要还是着眼于更加宽泛的物流运输领域以及车辆路径问题，Moons 等人（2016）[5]综合考虑了生产调度和车辆路径优化这两个经常被独立解决的问题，从而提高供应链的效率。谢天保等人（2010）[6]研究了在存在多个物流中心的前提下，各个物流中心相互协作以实现物流的协同配送问题。

在研究方法上，大多数研究采用的方法为目前广泛使用的各种算法。其中应用最为广泛的当属遗传算法。李军等（2000）[7]利用了最大保留交叉、交叉率和变异率自适应调整等技术，设计了基于自然数编码的遗传算法，研究了在车辆非满载的情况下满足货运需求的最短行车线路。王桢和黄磊（2016）[8]设计了一个两阶段优化遗传算法，第一个阶段为待发货订单指派最佳车辆，第二个阶段指定车辆的最佳配送方案，来解决在不同的订单发货区域的情况下，货车的装载和车辆路径的调度问题。廖良才等（2008）[9]将遗传算法的全局搜索能力和CW节约启发式算法的局部搜索能力结合了起来，用这种创新的混合遗传算法来解决物流车辆配送调度问题。其他算法比如禁忌搜索、粒子群算法、模拟退火算法等也有一部分学者研究。何小年和谢小良（2009）[10]设计了一种禁忌搜索算法来研究在车辆装载量存在约束的情况下的车辆路径问题，相比其他算法，该文提出的算法耗时短且结果也更优。徐杰和黄德先（2007）[11]通过使用粒子群算法和变异操作结合的求解方式来解决多目标下的带时间窗的车辆路径优化问题，减少了算法的无效迭代，提高了有效性。郑英和孟志青（2010）[12]使用了节约里程算法来解决烟草配送的问题。Bent 和 Hentenryck（2006）[13]针对带时间窗捡货送货的车辆路径问题，提出了一个两阶段的混合算法，第一阶段使用模拟退火算法对车辆数量进行优化，使得使用的车辆数达到最低，第二阶段使用LNS 方法对整个成本进行优化，使得在车辆数最少的情况下成本最低。Goel和Irnich（2017）[14]将驾驶员过度驾驶的情况考虑在内提出了一种分支定界法来求解这种车辆路径和驾驶员调度问题。

3 理论模型

3.1 问题背景

在传统模式下，企业的物流部门被动接收营销部门的发货需求编排发货计划，经常会产生大量的移库成本，甚至由于移库不及时导致无法按时发货，往往需要浪费大量人力处理，甚至出现由于发货点分配不合理导致无法按时发货的情况。要解决当前面临的上述困难，必须对现有物流运行模式进行调整优化，提升物流的协同效率和信息共享，由营销、物流、生产等供应链各环节的参与方紧密协同。因此本文提出了月计划的产销平衡工作新模式（如图2）。

在新模式下，对烟草工业企业的供应链来说，整个流程可以分为计划环节、生产环节、调度环节、配送环节。计划环节,指在每个月月末企业会收到下月需求计划，需要根据收到的订单以及各发货点的实际情况预排发货计划；生产环节，指企业根据制定的生产计划进行原材料的采购、加工和生产；调度环节，指生产完成之后，物流部门需要按照实际的需求重新制定发货计划，移库和回购计划；配送环节，指物流部门按照发货计划进行发货，按照运输计划和拼车计划将产品运送到到货点（如图3）。

为了帮助企业提升供应链效率，减少成本，本文提出了一个发货调度优化模型，其目标是在满足供需平衡的前提下实现运输成本的最优化，同时确保较高的车辆满载率，同时能够基于到货点的需求计划数据输出可供物流公司执行的具体发货计划和移库计划。

图2 月计划产销平衡工作流程图

图3 烟草工业企业生产物流调度配送过程示意图

模型在实际应用中，可以分为无货源计划约束和有货源计划约束两种应用场景。无货源计划约束指的是，基于下个月的需求计划为生产部门制定生产计划提供参考，在该场景下只需要考虑各发货点的可发货品规，而不需要考虑货源库存，同样以总成本最优的目标输出各发货点的货源需求；有货源计划约束是指，在有货源约束的前提下进行发货调度，所有的发货计划严格按照各发货点的库存情况进行发货，输出总成本最优和满载率较高的发货计划、移库计划以及货源补充建议。

该模型的主要挑战在于：（1）企业生产的产品品类较多，运输车辆具有多种车型，同时计划需要落实到计划期内的每一天，使得模型需要考虑的变量较多；（2）在调度过程中需要考虑各发货点的移库操作，移库可能进一步降低成本，但同时移库过程和移库后的货物搬运都需要占用配送时间；（3）在配送环节，到达不同的到货点时可能会有拼车的情况，拼车情况下的运费计算问题，以及配送环节的车辆选择问题，都是最终影响成本的重要因素。正是这些情况的存在，使得问题难度大大增加。

3.2 问题描述

本文模型考虑了多个发货点和到货点。每个发货点的发货数量有最大数量限制。每个到货点对烟草规格及数量需求不同，但不同规格烟草包装默认统一。物流公司可以使用多种车型，每种车型具有不同的最大装载量。各个到货点的月需求计划中，包括了到货点需要的产品品类、数量和需求时间。

在预排发货计划时，有货源计划约束场景下，模型需要考虑不同发货点之间的移库操作，移库的烟草规格和数量没有限制，移库货物到达仓库后变为可发库存有转换时间。

在制定运输计划时，模型需要考虑每个发货点对每个订单的发货时间、需要的运输车次以及发出的货物数量。发货运输过程中，多个到货点到货需求在时间允许的情况下，是允许拼车的，拼车能够节省因为车辆满载率不够而产生的补贴。拼车的业务规则如下：

（1）每个拼车线路从一个发货点出发，可以对多个到货点仓库的运输需求进行拼车（通常不超过2个需求点）。

（2）仅限同一个承运商及标段的到货点仓库之间进行拼载。

（3）单辆车辆产生的运费等于不同线路的单位运输成本与车辆载重，总运费等于各条运输线路上车辆运费加总。拼车线路的运费以所串连的多个到货需求中所指定最晚到货仓库的距离进行结算，但运输时间需要考虑多个到货仓库之间的距离，每增加一个拼车到货仓库需要增加额外的卸货时间。

3.3 模型构建

基于智能发货调度模型的目标、相关因素和约束条件，可以建立无货源计划约束和有货源计划约束场景下分别对应的线性规划模型的理论模型。

模型所需的符号和参数定义如下：

w：企业的发货点，w ∈W，W为所有发货点的集合；

l：到货点，l ∈L,L为所有到货点的集合；

p：烟草产品的产品规格和品类；

i：在配送过程中涉及到不同的车辆型号；

v：运输车辆的平均行驶速度；

SI：期初库存，发货点每月初剩余的上个月的库存余量；

dr：拼车线路，dr ⊆L 。

输入参数为：

Pwl=发货点w到到货点l的单位运输成本；

Pww'=发货点w到发货点w'的单位运输成本；

=在第td天发货点w到拼车线路dr的单位运输成本；

dwl=发货点w到到货点l的运输距离；

dww'=发货点w到发货点w'的运输距离；

=在第td天发货点w生产产品规格p的能力；

=第t天到货点l对于产品规格p的需求；

Cw=发货点w的库容；

INVwptd=在第td天末，发货点w剩余的产品规格p的数量；

tl=每个到货点要求的货物到达时间；

td=发货点发出货物的时间；

dt=路上所需的运输时间；

buffertime1=发货缓冲时间；

buffertime2=移库缓冲时间；

SIwp=发货点w的产品规格p的月初库容；

V[i]=车型i对应的装载量。

决策变量为：

=在第td天由发货点w生产的产品规格p的数量；

=在第td天由发货点w发往到货点l的产品规格p的数量；

=在第td天由发货点w移库发往发货点w'的产品规格p的数量；

trwlitd=在第td天由发货点w不拼车发往到货点l的车型i的数量；

tr_routewdritd=在第td天由发货点w拼车发往拼车线路dr的车型i的数量；

=在第td天由发货点w移库发往发货点w'的车型i的数量；

无货源计划约束下的运输调度模型为：

模型的目标为总运费最小化，因为运费与车辆的数量有关，因此运费最优的同时也考虑了车辆满载率最优，总运费包括了发货点到到货点的运费以及发货点到拼车线路的运费。约束（2）为运输时间约束，表示发货点w发往到货点l所需时间，包括实际运输时间和缓冲时间，发货过程中存在缓冲时间主要来自于驾驶员休息，天气原因等耽误运输的偶发事件；约束（3）为供需匹配约束，代表着各个到货点的需求必须被发出的产品满足；约束（4）为生产能力限制，发货点w当天生产产品p的数量小于等于其当天的生产能力上限。约束（5）-（11）对拼车的情况进行了约束。约束（5）保证拼车线路包含至少2个到货点；约束（6）表示当拼车线路上的某一到货点需求量为0时，此时此到货点不需要拼车；约束（7）表示当整条拼车线路上到货点需求均为0，则整条线路都不需要拼车；约束（8）表示当线路上存在拼车时，则拼车所用的车辆数量不为0；约束（9）保证了当到货点存在拼车线路时，不需要单独运往该到货点；约束（10）保证了不拼车的车辆装载容量大于等于目的地到货点的实际需求量；约束（11）保证了拼车线路上的车辆装载容量大于等于线路上所有到货点的实际需求量。

有货源计划约束下的模型仅在无货源计划约束下的模型基础上进行了改动。其目标函数如式（12）所示，总运费包括了不拼车的运货成本、拼车成本以及移库成本。

约束条件在无货源计划约束下的模型的基础上添加了以下几条：

约束（13）表示发货点间进行移库花费的时间，这里存在缓冲时间的主要原因来自于移库后通常要进行的装货、卸货、录入系统等操作；约束（14）保证了发货点当天库存等于前一天末库存和当天生产、移入数量之和减去当天发货、移出数量；约束（15）保证了td天末发货点w的库存不大于其库容并不小于0；约束（16）保证了移库使用的车辆装载容量大于等于总的移库产品数量。

4 模型求解

由理论模型可以看出，由于最终的决策变量既包括生产数量等浮点型数据，也包括整数型数据如车辆数，因此本文的问题可以归结为一个混合整数线性规划问题(MILP,Mixed Integer Linear Programming)。本文采用Python 下的第三方软件包Pyomo[15]结合Gurobi求解器对模型进行求解。具体的求解过程如图4所示。

图4 模型的求解过程示意图

由于本文的理论模型约束多、维度多、数据量大，导致算法时间复杂度和空间复杂度较高，求解难度大，因此本文通过以下两种方式降低了求解的复杂度：（1）在部分约束条件中应用了启发式算法的思想来使得求解空间缩小，以寻找近似的最优解：先允许一个较小的拼车距离，确定发货点的发货，再将允许拼车距离加大，在发货确定的情况下计算出运输安排；（2）对部分约束条件进行了McCormick envelopes转换使带有0/1变量的约束转换成线性约束，加快求解速度。

5 算例分析

为了评估模型的优化效果，本文算例使用的数据来自湖南中烟工业有限责任公司2017年11月的真实到货点需求数据等数据，将其输入模型进行优化计算，得到模拟的模型输出结果，包含运输总成本、发货计划明细、车辆总满载率和使用车辆总数等，将这些模型计算结果与该月份实际的运营数据进行比较，以评估模型的优化效果。

实际对比的数据涵盖湖南中烟工业有限公司下的7 个发货点，包含4 个位于湖南省长沙、常德、零陵、郴州的发货点，其余三个位于宁夏吴忠、吉林四平和河北保定。企业可以提供包括芙蓉王、白沙等共19 种品牌，各发货点期初库存和生产能力较为繁重。数据包括近400 个需求点，需求数量和时间、需求点与发货点距离信息各有不同。企业使用的装载车辆共有 3 种，装载量分别为 1 500 件，750 件，650件。车辆的平均行驶速度为50km/h。发货点与需求点的分布如图5所示，三角形代表发货点，圆点代表需求点。

在本文算例中，先以50km为拼车距离进行模型计算，即距离在50km之内的需求点的货物可以通过同一辆车进行拼车运输，由此确定出各仓库的发货日期和数量以及移库的信息，再以50km为拼车距离进一步计算出具体的运输路线、拼车安排。

本模型运算得到的部分具体调度明细如图6所示。本文将得到的结果与该企业实际运营数据进行比较，具体见表1。

图5 发货点和需求点分布情况

表1 模型运算结果与实际数据比较

从表1可以看到，在无货源计划约束的应用场景下，其单位运输成本下降了19.7%，出现成本大幅度下降的主要原因在于无货源计划约束不考虑货源库存。有货源计划约束模型与物流公司的实际运营情况比较贴近，因为该场景严格按照实际所提供的货源来安排发货计划，其模型计算模拟出来的发货计划成本可以与实际运输成本直接对比，用于评价模型的优化效果。从以上数据可以看出，单位运输成本下降了9.8%，下降的幅度也比较明显，另外发车次数也下降了8%，总满载率提高了1.79%。

从数据可以看出，本文提出的模型及算法，通过有效的供需匹配和拼车计划，能够帮助企业大幅降低运输成本，减少了发车次数，满载率也得到了提高，减少了不必要的装载空间浪费。

图6 部分调度明细

6 数值实验

在数值实验部分，本文对算例进行了扩展，通过改变是否拼车、车型组合、拼车距离，来观察决策变量是如何改变最优成本的。

（1）是否拼车。保持和算例相同的输入，本文对比了优化算法中允许拼车和不允许拼车两种情况，对比结果见表2，允许拼车使得11月的运输成本下降了3.87 个百分点，同时也大幅减少了需要使用的车次。允许拼车的策略能够充分利用运输工具的装载空间，从而大幅减少企业的运输成本。

表2 是否拼车对结果的影响

（2）车型组合（1 500件，750件，650件）。在这部分，本文对现有的三种车型进行排列组合，探讨不同车型组合对企业运输成本的影响（如图7）。本文将容量为1 500件、750件、650件的货车分别定义为A、B、C，测试的车型组合包括：只使用A，只使用B，只使用C，使用A 和B，使用A 和C，使用B 和C，使用A、B和C。

可以看到当仅能使用一种车型进行运输时（MN段），使用容量为1 500的货车成本最高，而使用容量为650 的车辆的运输成本最低，使用的车辆数最多，这是因为使用容量较大的货车导致车辆满载率降低，不仅运费较高，还有大量装载空间被浪费。

图7 车型组合对优化成本的影响

观察仅使用两种车型进行运输的数据（PQ段）可以发现，使用两种车型显然相比仅用一种车型更加节约成本，同样，当使用两种最小的车型进行联合运输时，运输成本是最低的。而使用三种车型进行联合运输时运输成本在该实验中达到了最低，多车型联合运输使得不同车辆能够进行互补，避免了空间的浪费，从而使装载空间利用率达到更高，进而节省了成本。

（3）最大允许拼车到货点间距离参数。保持和算例相同的输入数据，本文调整了模型求解中启发式算法对拼车距离的限制，在拼车距离分别为0、50km、100km、150km、200km、250km、300km时进行计算，得到结果如图8所示。可以看出，不拼车时，单位产品成本为8.026，满载率达到了77.92%；而当拼车距离达到300 时，单位产品成本降低到了7.02，满载率达到了84.85%。随着拼车距离的增大，优化算法提供的计划中单位产品成本在不断降低，但满载率在不断升高。这说明，由于拼车距离加大，有更多的需求点进入允许拼车范围内，从而算法能够搜寻到使运输成本越小的拼车计划，车辆的满载率得到提高，进而单位产品的运输成本得到降低。

图8 拼车距离对优化成本的影响

7 结论

本文针对烟草工业企业目前供应链存在的一些问题，在按时按量满足各个到货点需求等约束条件的基础上，以成本最优的目标建立了理论模型，可以为烟草工业企业提高运营的效率，提高服务满意度，对整个供应链可以进行更好的计划和把控，同时使用Pyomo构建了算法，获得了较好的求解效果。相比传统的关于物流调度优化方法的文章，本文主要突出解决了以下几个问题：（1）不仅仅只对物流调度的过程进行了优化，同时还对烟草工业企业每日的生产过程进行了优化，求解的结果包括每日每个仓库的生产量，为各个仓库的生产计划提供指导建议；（2）更多地关注模型本身，使模型更加符合实际的情况，模型求解也会更加贴近于最优解；（3）在数值实验里使用的数据来自于企业的真实数据，所以在实践中本文的模型可以取得较好的效果；（4）模型具有普适性，对多车型、多品类的供应链调度研究具有一定指导意义。

除了优点之外，本文的研究目前依然也存在一些问题：（1）模型的约束条件较多，如果数据规模很大，会导致模型过于复杂，求解起来耗时较高，会产生一定的困难；（2）寻求的是最优解，没有采用智能算法，虽然求出来的最终解较优，但是效率较低，在未来的研究中可以进一步完善。