带时间窗的装备维修器材生产路径建模与优化
2020-08-05滕尚儒何成铭
滕尚儒，何成铭，丛 彬
(1.陆军装甲兵学院 装备保障与再制造系， 北京 100072； 2.陆军装备部信息保障室，北京 100072)
装备维修器材供应保障是装备保障工作的重要组成部分，其基本职能是弥补器材供需之间在空间上和时间上的不一致，以保证平时和战时器材供应的不间断[1]。其主要任务涉及生产和库存计划的制定、运输方式和运输工具的合理选择以及配送路径规划等问题。研究合理地制定生产、库存及配送计划，使得供应链上总成本最低，该优化问题被称为生产路径问题(production routing problem，PRP)。
相对于传统战争，信息化条件下的战争强度大，装备损伤多，部队用户对器材的需求主要体现在器材供应的数、质、时、空四个方面，其中，“时”即时间。物流对配送时间上的要求主要体现在两个方面：一是对配送运输时间的有效性要求。从目前物流发展的现状分析，这是一种时间段要求，即通常要求在规定的时间段内完成相应的配送运输保障任务；二是对配送运输时间的精确性要求。供应链对各个环节的衔接具有严格的时间要求，当这种要求达到较高水准时，配送运输的送达时间就必须做到精确，也就是说配送与物流体系中其他环节在时间上要达到精确协接。
在器材供应保障过程中，给每个部队用户增添时间窗约束以进行配送服务，涉及的VRP就衍变成了VRPTW(vehicle routing problem with time windows，VRPTW)。VRPTW是基本VRP的扩展问题，是在VRP的基础上考虑每个客户对配送时间的具体要求，该时间窗是由客户要求的最早服务时间和最晚服务时间所确定的一个服务时间区间。根据能不能违反时间限制这一标准，可以进一步将时间窗进行细分：能够以一定惩罚为代价进行违反的时间限制为软时间窗；必须严格执行的时间限制称为硬时间窗。
国内外学者对于此类带时间窗的优化问题已做出诸多的研究，Zografos等[2]提出了一个基于GIS决策支持系统的路径构建算法，有效地解决了带时间窗的双目标车辆路径优化问题。Shen等[3]探究在时变条件下多时间窗约束的危险品运输网络优化问题，并结合动态规划法与灰色关联分析法进行求解。赵达等[4]提出了一种修正的节约算法来求解带硬时间窗的随机需求库存路径优化问题，能够在较短计算时间内最小化配送成本和用车数量。赵崇远[5]针对有时间窗的车辆调度问题，建立了含有时间惩罚函数的数学模型，并用遗传算法和节约启发式算法求解。
论文研究了部队用户(需求)硬时间窗约束下的装备维修器材PRP，各需求点只在指定时间窗内接受服务，同时还考虑了车辆最早离厂和最晚进厂时间。首先针对问题特征构建一个以总成本最小为目标的混合整数线性规划(mixed integer linear programming，MILP)模型，同时提出3个有效不等式来改进该模型，之后在CPLEX平台上求解随机生成的45个算例，验证了优化模型和不等式的有效性。
1 问题分析与建模
现代作战战场情况复杂，对器材供应的时效性要求较高，器材供应时间不能过早也不能过晚：过早可能暴露作战企图，还容易给部队造成累赘；过晩可能造成供应间断，影响部队修复通用装备，贻误战机。精确保障要求下的器材供应保障工作强调器材交付时间的准确性，即在一个合理的期限内将部队所需的器材送达目的地，确保部队用户能够及时得到器材保障。
因此研究装备维修器材PRP，就必须充分考虑部队用户对器材交付时间的要求，同时也能够反映器材供应保障工作的总体服务水平。
1.1 问题描述
假设用有向图G=(N,A)表示配送网络，其中，N={0,1,…,n}表示节点集，A为弧集。节点0表示器材承制单位，其库存能力记为U0，最大生产能力记为C。器材承制单位可生产单品种器材，物流服务商可提供一组容量为V的同类型车辆K={1,2,…,|K|}。图G中分布有一组部队用户R={1,2,…,n}，每个部队用户i∈R的最大库存能力为Ui，在规划周期T={1,2,…,|T|}内，对器材的需求具有时变性和确定性[6]。该生产路径问题网状结构可用图1概略描述。
图1 生产路径问题网状结构示意图
所考虑的时间窗是一个部队用户与物流服务商协商好的、由部队用户的最早和最晚可接受服务的时间确定的一个时间区间[ET,LT]，ET表示最早可到达时间，LT表示最晚必须到达时间。当器材交付时间超出[ET,LT]时，其惩罚值等于一个非常大的正值，表示硬时间窗的限制，超出时间窗的服务视为无效服务，将其作为不可行解，从而每阶段部队用户只能在该时间窗内接受服务。
综上，带时间窗的装备维修器材PRP是指在规定时间窗内满足各部队用户需求的前提下，对生产计划、库存计划、配送计划进行整合，以最小化生产、库存和运输总成本。每阶段的主要决策内容包括：
1) 器材承制单位生产多少；
2) 给每个部队用户交付多少；
3) 如何为给定的交付计划规划运输路径。
为了简化建模过程，在上述保障过程描述的基础上，做出如下几点假设和说明：
1) 器材承制单位在车辆离厂前已完当前阶段成生产任务；
2) 每辆车在完成每次配送任务后返回器材承制单位；
3) 每阶段每辆车至多执行一次配送任务；
4) 为节约卸货时间，每阶段每个部队用户仅能由同一车辆为其提供一次服务。
1.2 符号说明
引进参数如表1所示。
模型中的变量如表2所示。
表2 模型中的变量
1.3 模型构建
综上所述，可用如下MILP模型表示带时间窗的装备维修器材PRP优化决策模型，记为P1。
(1)
约束条件：
(2)
(3)
(4)
pt≤Ytwt,∀t∈T
(5)
(6)
(7)
(8)
(9)
(10)
(11)
∀i∈R,j∈R{j},k∈K,t∈T
(12)
(13)
(14)
(15)
(16)
(17)
pt≥0,∀t∈T
(18)
(19)
(20)
wt∈{0,1},t∈T
(21)
(22)
(23)
(24)
(25)
(26)
其中，目标函数(1)由生产、库存和运输成本3部分组成；式(2)-式(4)确保器材承制单位和部队用户之间的库存守恒；式(5)确保器材承制单位每阶段的生产量不超过其最大生产能力和部队用户未来阶段的总需求量；式(6)限制了器材承制单位和部队用户的最大库存；式(7)确保车辆在配送过程中的实际载货量不超过其最大允许装载量；式(8)表示如果车辆访问了某部队用户，交付给该部队用户的器材量不能超过其未来阶段的总需求量；式(9)表示每个部队用户至多被一辆车访问；式(10)表示车流量守恒，即车辆到达一个节点后必须从该节点离开；式(11)确保每辆车每阶段至多执行一次配送任务；式(12)确保了车辆访问各部队用户时间的一致性；式(13)和(14)确保了车辆从器材承制单位出发时间和返回时间的一致性；式(15)-式(17)确保了部队用户在规定的时间窗内接受服务，并限制了车辆从器材承制单位出发和返回时刻；式(18)-式(26)界定了决策变量的取值范围。
2 有效不等式
有效不等式是区别于原问题约束的，并且主问题中整数变量满足的关系不等式。其加入可以对主问题的解空间进行有益的限制，能够减少由主问题得出的整数解对于子问题不可行的情况，加速算法的收敛，并起到改进初始下界的作用。这些有效不等式通常是基于问题结构提出，对于不同的问题有不同形式的有效不等式。由于加入了时间窗约束，所构建的模型中包含了更多0-1变量和连续变量，可行域较大，通过CPLEX优化求解器可求得小规模实例最优解且求解的时间较长。
(27)
(28)
∀i∈R,t∈T,t (29) 式(27)表示在调用车辆k之前，车辆k+1不能离开器材承制单位，该不等式确保了编号靠前的车辆被优先调用；式(28)表示如果阶段t部队用户i∈R由车辆k访问，那么车辆k-1也一定访问过同一阶段编号在i之前的部队用户；式(29)表示如果某部队用户在区间[t+1,τ]内未被访问，那么阶段t结束时的该部队用户的库存量足够必须能够满足其在[t+1,τ]内的总需求量。 目标函数(1)和式(2)-式(29)构成了改进后的模型，记为模型P2。 为检验提出模型和不等式的有效性，本章以随机生成的45个实例来测试上述两个模型。所有实例测试实验均在Windows 10，CORE CPU 2.4 GHz，8 GB RAM下用Visual Studio 2010和CPLEX Version 12.6.0进行。 表3 参数生成规则 为验证原模型P1和改进后的模型P2的求解效果，论文选定45个随机实例进行实验计算，其中包括9组不同规模问题，每组问题下生成5个实例。对比实验采用表4的符号定义来评价模型P1和P2。 表4 对比实验分析的符号定义 实验结果如表5，其中，4-8列统计了CPLEX优化求解器在5个实例上运行后各个评价指标的均值，求解时间限制在7 200 s。这里需要注意的是，如果分支规模超出内存容量，计算便会终止。 分析表5中各列数据可以发现： 表5 小规模实例计算结果 1) 实例1，实例2，实例3和实例4表明，CPLEX可以求得包含10个部队用户、多至10个阶段，和20个部队用户、多至3个阶段的小规模实例的最优解，平均求解时间在105.32 s以内； 2) CPLEX在求解包含20个部队用户和6个阶段的实例时，可获得其中2个实例的最优解，但计算时间较长。随着实例中部队用户数和阶段数的增加，CPLEX计算时间的增幅较大； 3) 从包含30个部队用户和3个阶段的实例7中可以看出，上下界的偏离程度平均达到了35.44%，说明求解此类带时间窗约束的优化决策问题的复杂度较大； 4) 从LB2列可以看出，在测试实例上，改进后的模型P2提供的下界比起LB1列，平均有所增大，表明引入的不等式在求解此类问题时的有效性。 图2给出了模型P1与P2提供的下界之间的差值，其中横坐标x表示实例编号，纵坐标y表示差值，即LB2-LB1。 图2 测试实例得出的下界差值曲线 从图2可以看出，在45个测试实例中，有23个实例的最优值无法通过CPLEX获得，其中有20个实例的差值为正，实例35的差值最大，达到了773。这主要是因为改进后模型的约束更紧，在线性松弛之后的多面体更接近原整数可行解的凸包，使用分支定界法时分枝和剪枝相比初始模型更加有效。综上，所提出的有效不等式有助于CPLEX优化求解器生成更好的下界。 为带时间窗的装备维修器材PRP提出了一个MILP模型，并引入3个有效不等式来改进该模型。通过数值仿真实验发现，CPLEX优化求解器只能求得小规模实例的最优解，且求解的计算时间随着部队用户数目和规划周期的增加大幅增长，改进后的模型提供的下界比起初始模型平均有所增大，表明引入的不等式在求解此类问题时的有效性。 由于该问题的复杂性，CPLEX求解的计算时间随着部队用户数目和计划时域的长度的增加大幅增长。实际情况中，问题规模可能更大，需要进一步开发高效的求解算法求解该类问题。3 模型求解
3.1 实例生成
3.2 结果分析
4 结论
