考虑仓库作业能力限制的器材年度供应任务分配

张育铭，刘世伦，王 兵，金 峰

（陆军装甲兵学院 装备保障与再制造系，北京 100072）

0 引言

陆军装备维修器材（下称“器材”），是装备保障工作的重要物质基础。器材及时足量供应，是完成装备维修、恢复部队战斗力的重要保证。陆军现行的器材供应保障分为年度供应和临时供应两部分，其中以年度供应为主、临时供应为辅。年度供应由部队提出器材需求，主管单位汇总后将供应任务分配至储供基地、战役仓库等仓储供应点位。

为提高器材供应保障效益，学者从不同角度开展了广泛研究。田尧，等[1]针对军事物流基地配送策略展开研究，考虑配送能力，以配送费用、储备费用、惩罚费用最低为优化目标，通过Lingo求解，提升配送效率，降低配送成本。贾琦，等[2]考虑超储器材调剂供应，以总成本最小、时间最短、闲置率最低为目标，采用改进人工鱼群算法进行求解，得到最优供应方案。李浩[3]针对器材库存补充供应优化，考虑器材保障经费、供应点位库存、仓储布局等因素影响，结合器材消耗量预测方法和库存限额确定方法，构建了队属仓库阶段性需求确定和供应点位阶段性供应方案确定模型，以保障成本和保障率为优化目标，设计了两阶段粒子群优化算法求解。杨帆[4]在建立需求确定模型的基础上，针对确定性任务下的器材供应问题，构建了二阶段供应模型，采用改进灰色遗传算法对模型进行求解；针对不确定任务的器材供应问题，构建了滚动多阶段供应模型，采用改进的动态粒子群算法进行求解。

在年度供应保障任务分配中，传统做法是采用就近分配原则，即部队的需求优先由距离最近的仓库来供应。但仓库建设规模、库存容量、力量结构和硬件设施条件各不相同，其作业能力也有较大差距。就近分配容易造成有的仓库供应任务扎堆，导致器材发出时间迟滞，进而影响整体保障效果。而现有文献中未发现将仓库作业能力纳入供应保障任务全局进行研究。因此，考虑仓库作业能力的限制，如何最优地分配器材年度供应保障任务，是值得研究的问题。

器材供应保障任务分配具有排序与调度问题特征，可看做具有处理集限制的同类机排序与调度问题，Leung，等[5,6]持续对处理集限制的调度问题进行研究，综述了相关问题的研究成果。Ebenlendr，等[7]针对此类问题的一个特例，设计了一个近似求解算法。本文参考排序与调度的相关原理，考虑仓库作业能力限制，建立陆军器材年度供应保障任务分配模型，并进行算例实验分析。

1 问题描述和模型假设

本文考虑年度器材供应保障任务的分配问题，在器材需求、库存和位置布局已知的情况下，优化仓库向部队的器材供应任务。仓库受作业能力和库存限制，整体目标追求最短送达时间和最低成本的加权最优。

1.1 问题描述

考虑M个仓库向G个部队供应器材J类，其中第m个仓库位中第j类器材的库存水平为qmj，各类器材总库存数量为Q；第g个部队总需求数量为sg，第j类器材需求数量为dgj，器材需求总数量为D。时间以T表示，单位为天。仓库作业能力W指一天内作业总体能力数值，不同仓库作业能力各不相同，每类器材规格参数为vj，该数值越大，表示需要的仓库作业能力和运输成本越高。仓库和部队具有部署位置L，运输时间为LTmg，同距离Rmg正相关，运输时间系数为kt；运输费用LC同器材数量、规格和距离正相关，系数为kc。各部队需求分配计划至各仓库，以各部队最大完成供应时间Dmax和运输成本LC的加权和最小为优化目标。符号公式见表1。

表1 符号公式说明

1.2 模型假设

根据上述问题描述，提出如下模型假设：

（1）器材需求和库存状况已知，总库存满足部队器材需求，不同仓库对同类器材的作业能力相同，作业准备时间、装卸载时间忽略不计；（2）不考虑库存持有成本，忽略备货作业过程中产生的其他费用，运输费用同器材总规格和运输距离正相关，不考虑零担、整车运输费用差异和固定费用；（3）仓库可以在作业能力范围内同时完成多类多件器材的备货，单件器材不允许跨天作业；（4）仓库完成一个部队的全部作业任务即可进行运输；（5）作业和运输时间单位为天，不满1天分别按照1天计算。

2 模型构建

本问题为具有处理集限制的同类机排序与调度和运输成本的组合优化问题。按照传统排序与调度理论，需要对所有器材需求在仓库进行作业顺序排序。考虑到器材年度供应保障任务器材类别相对集中的特点，弱化单件器材拣选先后顺序，构建了一个基于器材类别的供应保障任务分配模型。并实现了传统器材任务分配的最短距离优先分配(SDFA，Shortest Distant First Assignment)算法，作为对比分析的参照。

2.1 基于器材类别的供应保障任务分配模型

定义如下决策变量：

pgjmt∈{0 ,1}，表示第m个仓库第t天进行第g个部队的第j类器材备货，反之为0。

xgjmt∈N，表示第m个仓库第t天进行第g个部队的第j类器材件数备货。

由上述变量，构建混合整数规划模型的约束条件。

其中，式（1）表示仓库作业能力限制，任何时刻进行备货的器材作业能力需求不能超过仓库作业能力。式（2）表示满足需求约束，必须满足所有部队所有器材需求。式（3）表示库存限制，分配器材供应任务不能超过该单位库存。式（4）表示最大任务完成时间，为最后一个部队完成收货的时刻。式（5）表示运输成本。

可以看到，在约束条件构建中存在一个0-1决策变量同整数变量乘积的二次约束pgjmtxgjmt，对于此形式二次规划问题的求解是非常困难的。为解决此问题，引入决策变量bgjmt∈[0 ,U]，U为xgjmt中的最大值，使得bgjmt=pgjmtxgjmt。得到改进后的混合整数规划模型约束。

其中，式（6）-（10）为式（1）-（5）决策变量对应替代后的约束条件。式（11）-（14）为约束决策变量bgimt和xgimt、pgimt的关系。式（11）、式（12）对约束变量bgimt的上界，式（13）约束变量bgimt的下界，三个约束是紧约束，保证了bgimt=pgimtxgimt。以最大完成任务时间和运输成本的加权和最小为优化目标，完成供应分配模型构建。

2.2 SDFA算法

在实际工作中，传统的器材任务分配是按照距离优先准则进行就近分配，为了检验最优任务分配与传统任务分配效果的差别，这里给出传统的距离优先分任务分配（SDFA，Shortest Distant First Assignment）的实现算法，其基本思路是：首先计算仓储点、部队间的距离矩阵，对距离进行排序，首选安排距离最近仓库、部队组合的器材分配，按照距离远近依次分配，最终完成全部器材需求分配。完成计划分配后，仓库以远距离优先安排备货的原则进行作业排班，计算最大完成时间和运费。伪代码见表2。

表2 SDFA算法伪代码

3 模型分析

首先考察一种简化的情况，以分析模型的适用性。

考虑2个仓库，4个部队，1类器材需求，库存充足，仓库作业能力各不相同，4 个部队围绕作业能力较大仓储点分布。布局如图1所示，图中点位连接线为路径和运输时间，令仓储点库存为TM=(+∞,+∞)T，器材需求为TD=(10,20,30,40)T，仓储点到部队的运输时间矩阵为，仓储点作业能力W={20,10}，器材规格V={5}，运输成本系数kc=0.01。根据最短距离优先算法，以横向代表仓库、纵向代表部队，易得完成供应的时间为26，运输成本为5。以算法计算的时间、成本值对两个变量进行无量纲处理，并调整模型中权重θ1，θ2，通过COPT求解器求解模型的精确解。表3为SDFA算法和模型求解供应保障计划时间、成本对比表，表中时间减少和成本增加均为同SDFA算法得到的时间、成本数值，不同权重对应分配计划见表4。

图1 供需点位布局示意图

表4 供应保障任务

从结果可以看到，通过调整权重θ1,θ2的取值，可以得到不同权重下的最优任务分配策略，模型求解较SDFA算法在供应完成时间上有明显改进。传统就近分配原则，造成了供应任务积压在01仓库，如果给临近的02仓库分担一些任务，可有效缩短供应时间。但舍近求远难免会产生运输成本的增加，实际工作中需要在时间和成本中做出权衡。

4 算例实验

下面结合陆军器材年度供应保障业务，生成不同规模算例进行实验，通过python调用COPT求解器进行求解，运行环境为Intel(R) Core(TM) i7-9700F 3.00GHz CPU，32.0 GB RAM。参考业务实际，构建3个仓库，15个部队，100类共计30 000 件器材需求，仓库作业能力各不相同，点位在1 000×1 000范围内分布。

4.1 基本信息

仓库器材类别、数量、作业能力和部署位置见表5。库存器材基础数量指与部队器材需求相等的库存数量。

表5 仓库信息表

部队需求器材类别、数量和部署位置见表6。

表6 部队基本信息表

器材数量和作业能力需求见表7。器材的规格代表了器材的尺寸大小，分为5类：极小件、小件、中间、大件和极大件，对应不同运输成本和作业能力消耗，分别为1,10,50,100,200。

表7 器材需求总量和规格参数

4.2 结果分析

设置相同器材类型布局下三种库存数量（对应器材种类为基础数量的库存、2倍基础数量的库存、数量不限的库存）和所有仓库全品种器材不限库存4种情况进行器材分配求解，按照第3 节求解方法，θ1，θ2分别取0.8 和0.2，kc=0.001，进行求解分析。表8为四种情形SDFA算法和模型求解的完成供应时间和成本。

表8 计算结果

从结果上看，基础数量库存时，算例的可优化空间很小；随着库存数量和品种的增加，SDFA算法的供应完成时间呈先增后减的趋势，运输成本呈大致下降趋势，表明就近分配原则主要起到了节约运输成本的效果，但容易造成仓库作业任务积压而导致供应时间变长；模型算法求解的供应时间得到明显缩短，同时不可避免的会引起运输成本的小幅上涨。另外，在本算例中两倍基础数量库存情况下已经达到较好的供应时效，提高器材数量和品种的储备，对降低运输成本略有改善，但不会进一步缩短供应任务完成时间；考虑到现实中增加库存带来的采购成本和库存持有成本增加，增加库存来换取运输成本的降低是不可取的。

图2展示的是两倍库存情况下的SDFA算法和模型求解的任务分配流向图，箭头的粗细代表器材数量，不同线型箭头代表不同仓库的器材供应，可以看出仓库2作业压力较重，模型优化了任务分配后，将部队11、15、9、1的就近保障任务由仓库1和仓库3进行分担，减轻了仓库2的作业压力，提高了保障任务整体时效。

图2 流向图

5 结语

本文考虑仓库作业能力限制对陆军装备维修器材年度供应保障任务的影响，构建了兼顾任务完成时间和运输成本的供应保障任务分配模型，并通过算例与传统就近分配方式进行对比。结果表明：

（1）传统就近分配方式，能够得出运输成本较低的方案，但容易导致作业任务积压，使任务完成时间变长；（2）最优任务分配模型能够以较小的运输成本涨幅得到任务时效的显著改善，从而提高整体供应保障效益；（3）仓库保持较高的库存量和较全的库存品类可以提供更丰富的任务分配方案，对降低运输成本有一定效果，但由于仓库作业能力的限制，对改善整体任务完成时间的效果有限。