装备维修器材供应保障是装备保障工作的重要组成部分，其基本职能是弥补器材供需之间在空间上和时间上的不一致，以保证平时和战时器材供应的不间断[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所示。
表1 模型参数
符号说明cij(i, j)∈A之间的运输成本τij车辆由出发点i至目标点j的行驶时间at阶段t∈T的单位生产成本bt阶段t∈T的生产准备成本C器材承制单位的生产能力gii∈N的初始库存量Dti阶段t∈T部队用户i∈R需要的器材量Ui节点i∈N的库存能力hi器材在节点i∈N产生的单位存储成本ei部队用户i∈R接受服务的最早时间e0车辆从器材承制单位出发的最早时刻li部队用户i∈R接受服务的最晚时间l0车辆返回器材承制单位的最晚时刻si为部队用户i∈R提供服务所需要的时间
模型中的变量如表2所示。
表2 模型中的变量
符号说明pt阶段t器材的生产量wpt0-1变量,若阶段t器材承制单位启动生产,则wpt=1,否则其值为0Iti阶段t结束时部队用户i持有器材量ykti阶段t车辆k给部队用户i交付的器材量zkti阶段t车辆k为部队用户i提供服务的时刻vkti0-1变量,若阶段t部队用户i被车辆k访问,则vkti=1,否则其值为0εkt阶段t车辆k离开器材承制单位的时刻λkt阶段t车辆k到达器材承制单位的时刻xktij0-1变量,若阶段t车辆k从点i行驶到点j,则xktij=1,否则其值为0
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 有效不等式
为改进模型P1，先引入有效不等式的概念。在整数规划问题中：Min{eTs|s∈S}，其中
若对于任意s∈S，都有kTs≤t0成立，则称不等式kTs≤t0是有效不等式。
有效不等式是区别于原问题约束的，并且主问题中整数变量满足的关系不等式。其加入可以对主问题的解空间进行有益的限制，能够减少由主问题得出的整数解对于子问题不可行的情况，加速算法的收敛，并起到改进初始下界的作用。这些有效不等式通常是基于问题结构提出，对于不同的问题有不同形式的有效不等式。由于加入了时间窗约束，所构建的模型中包含了更多0-1变量和连续变量，可行域较大，通过CPLEX优化求解器可求得小规模实例最优解且求解的时间较长。
通过分析问题的结构，针对该模型中变量
和
特点，本节在Archetti等[7]和Coelho等[8]研究的基础上，提出以下3个有效不等式对模型P1进行改进：
(27)
(28)
∀i∈R,t∈T,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。
3 模型求解
为检验提出模型和不等式的有效性，本章以随机生成的45个实例来测试上述两个模型。所有实例测试实验均在Windows 10，CORE CPU 2.4 GHz，8 GB RAM下用Visual Studio 2010和CPLEX Version 12.6.0进行。
3.1 实例生成
测试实例中，部队用户数量n设置为10，20，30和40，阶段数|T|设置为3，6和10。对包含10个部队用户的实例，车辆数|K|设置为1；对包含20，30和40个部队用户的实例，车辆数|K|设置为2。器材承制单位和部队用户位置对应于有向图G中节点i的坐标，记为(Xi,Yi)，从U[0,1 000]中随机产生；运输成本cij用节点i和j之间的欧氏距离表示；在规划周期开始时，令初始库存
为0；时间窗的参数设置参考文献[9]提出的参数生成规则，车辆离开器材承制单位的最早时刻e0和最晚到达时刻l0分别设置为0和1 200；为部队用户提供服务的时长从区间[60,120]中随机生成。参数生成的详细规则见表3。
表3 参数生成规则
参数生成方式描述cij=(Xi-Xj)2+(Yi-Yj)2τij=cij/10Dit从U[30,210]中随机生成C=β(∑i∈R∑t∈TDit)/|T|,其中β从U[2,4]中随机生成U0=βC,其中β从U[1.5,2]中随机生成Ui=βimaxt∈T{Dit},其中βi从U[2,3]中随机生成,i∈Rhi从U[0.5,1.5]中随机生成at从U[4,7]中随机生成bt =βC,其中β从U[0.3,0.5]中随机生成 V=1.25(∑i∈R∑t∈TDit)/|K|/|T|,其中g从U[1.5,2]中随机生成si U[60,120]eimax{β1-β2/2,e0+τ0i},其中β1从U[e0+τ0i,l0-τi0-si]中随机生成,β2=β3(l0-e0),其中β3从U[0.125,0.25]中随机生成limin{β1+β2/2,l0-τi0-si},其中β1从U[e0+τ0i,l0-τi0-si]中随机生成,β2=β3(l0-e0),其中β3从U[0.125,0.25]中随机生成
3.2 结果分析
为验证原模型P1和改进后的模型P2的求解效果，论文选定45个随机实例进行实验计算，其中包括9组不同规模问题，每组问题下生成5个实例。对比实验采用表4的符号定义来评价模型P1和P2。
表4 对比实验分析的符号定义
符号说明UBCPLEX求解P1得到的最优值的上界LB1CPLEX在有限计算时间内寻得P1的最优下界值LB2CPLEX在有限计算时间内寻得P2的最优下界值GapGap=(UB-LB1)/LB1×100%TimCPLEX求解的计算时间NCPLEX求得最优解或已知最优解的实例数量
实验结果如表5，其中，4-8列统计了CPLEX优化求解器在5个实例上运行后各个评价指标的均值，求解时间限制在7 200 s。这里需要注意的是，如果分支规模超出内存容量，计算便会终止。
分析表5中各列数据可以发现：
表5 小规模实例计算结果
No.n|T||K|UBLB1LB2Gap/%Tim/sN1103115 88615 88615 8860.000.32526136 54736 54736 5470.004.125310173 54273 54273 5420.0034.2354203235 78635 78635 7860.00105.32556277 46568 67968 75012.791 756.8426102162 024154 994155 3214.544 869.3607303238 45628 39328 67935.441845.410862112 545105 220105 3216.964 789.9609403265 76455 27755 36618.975 132.320
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优化求解器生成更好的下界。
4 结论
为带时间窗的装备维修器材PRP提出了一个MILP模型，并引入3个有效不等式来改进该模型。通过数值仿真实验发现，CPLEX优化求解器只能求得小规模实例的最优解，且求解的计算时间随着部队用户数目和规划周期的增加大幅增长，改进后的模型提供的下界比起初始模型平均有所增大，表明引入的不等式在求解此类问题时的有效性。
由于该问题的复杂性，CPLEX求解的计算时间随着部队用户数目和计划时域的长度的增加大幅增长。实际情况中，问题规模可能更大，需要进一步开发高效的求解算法求解该类问题。
[1] 唐卫民,陈卓,王昕.国防动员需求工作的矛盾分析及对策思考[J].国防,2017(01):33-35.
[2] ZOGRAFOS K G，ANDROUTSOPOULOS K N.A heuristic algorithm for solving hazardous materials distribution problem[J] European Journal of Operational Research,2004,152(2):507-519.
[3] SHEN Xiaoyan,XIE Chengjiang,LIU Haoxue，et al.Model and algorithm for routing and scheduling problem in hazardous materials transportation network[J].Journal of Networks,2013,8(5):1027-1034.
[4] 赵达,李军,马丹祥,等.求解硬时间窗约束下随机需求库存—路径问题的优化算法[J].运筹与管理,2014,23(1):26-38.
[5] 赵崇远.基于遗传算法的边防连队运输保障车辆调度问题研究[D].长沙:国防科技大学,2008.
[6] ADULYASAK Y,CORDEAU J F,JANS R.Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems[J].INFORMS Journal on Computing,2014,26(1):103-120.
[7] ARCHETTI C,BERTAZZI L,LAPORTE G,et al.A branch-and-cut algorithm for a vendor-managed inventory-routing problem[J].Transportation Science,2007,41(3):382-391.
[8] COELHO,LEANDRO C,LAPORTE G.Improved solutions for inventory-routing problems through valid inequalities and input ordering[J].International Journal of Production Economics,2014(155):391-397.
[9] COELHO,LEANDRO C,LAPORTE G.Optimal joint replenishment,delivery and inventory management policies for perishable products[J].Computers & Operations Research,2014(47):42-52.