新冠肺炎主要通过环境扩散，而消毒杀菌可以有效控制病毒的传播．在疫情防控过程中，须要把消毒杀菌作为首要工作来看待．因此，减少消杀过程中的时间和经济成本就显得极为重要．带容量约束的弧路径问题(CARP)首先由文献[1]提出，作者同时证明CARP为NP-hard问题．对于该类问题，部分国内外研究者尝试采用精确算法进行求解，如文献[2]的割平面算法和文献[3]的分支定价算法等．而大多数研究者往往采用启发式方法进行求解，如文献[4]的免疫拉马克算法、文献[5]的路径扫描启发式算法及文献[6]的混合元启发式算法．多车场带容量约束的弧路径问题(MDCARP)在CARP的基础上考虑了多个车场．根据对终点的选择，可将该问题分为封闭式和开放式．封闭式的MDCARP要求服务车辆最后返回到起点车场，这也是MDCARP的主要研究方向．文献[7]将MDCARP转化为多个标准的CARP，采用了模因算法进行求解．文献[8]考虑了非对称MDCARP，利用分支定界算法进行求解．文献[9]利用混合遗传算法对多目标MDCARP进行了求解．文献[10]设计了求解多目标MDCARP问题的模因算法．而开放式的MDCARP对服务车辆的最终目的地不做要求．文献[11]利用近似算法实现对开放式MDCARP的求解．开放式的MDCARP是国内外较少研究的领域，也是本研究的主要方向．本研究基于社区疫情防控的消杀作业路径优化问题的特征提出了用于消杀面型任务的作业工艺，建立了问题的整数规划模型，并且设计了基于模拟退火算法的启发式算法对问题进行求解，最后通过计算实验说明了算法的有效性．1 问题建模1.1　问题描述社区疫情防控的消杀作业路径优化问题可以描述为给定一个路网图，路网图中有一个或多个起始点(即车场)．有一组具备相同容量的消杀车辆分别从任意起始点出发，在不超出自身容量的前提下，对路网图内的路段进行消杀，直至满足了所有路段所需的消杀次数，再返回到任意起始点．消杀车辆的消杀路径长度有一部分为仅经过不消杀距离，是消杀车辆为了从当前的消杀任务前往下一个消杀任务所消耗的距离，而每个路网图实际消杀所消耗的距离是固定的，因此本研究的优化目标即是最小化所有消杀车辆总的仅经过不消杀的距离．1.2　数据预处理路网图中的各路段都包含主道路，且可能包含须要消杀的特殊区域．根据主道路宽度及特殊区域的长度和宽度，通过设置消杀车辆的单次消杀宽度，可计算得到各个路段所需的消杀次数，同时根据特殊区域的有无，将路段分为普通路段和特殊路段．各消杀车辆在消杀的过程中都存在单次消杀宽度，该宽度可根据实际须要消杀的路段宽度进行调整，但不得超过该消杀车辆的消杀宽度上限．后面所称“单次消杀宽度”均指消杀车辆的消杀宽度上限．普通路段即为不带有特殊区域的路段，其所需消杀次数为主道路宽度与单次消杀宽度的比值向上取整，即：消杀次数= 主道路宽度/单次消杀宽度．当消杀社区等场所时，可能会遇到含有公园等平面型的特殊区域的路段，如图1所示(虚线以下为主道路，虚线以上为特殊区域)．对于此类路段的处理，将特殊区域及与等长的主道路单独分离出来，作为一段独立的路段进行处理，将这种路段称为特殊路段，两边多余出来的路段则作为普通路段处理．10.13245/j.hust.240364.F001图1特殊路段处理示例图本研究针对如图2所示四类不同长宽的特殊区域设计了四种不同的作业工艺，其中：A类的宽度与单次消杀宽度的比值向上取整为偶数；B类的长度与单次消杀宽度的比值向上取整为偶数；C类的长度与单次消杀宽度的比值向上取整为1；D类的宽度与单次消杀宽度的比值向上取整为奇数，且长度与单次消杀宽度的比值向上取整为大于1的奇数．含有A，B和C类特殊区域的特殊路段的消杀次数即为主道路消杀次数，而含有D类特殊区域的特殊路段的消杀次数时须要在主道路所需消杀次数上加一．10.13245/j.hust.240364.F002图2各类特殊区域作业工艺示例图对于A类和D类的特殊区域，可能会在消杀特殊区域的过程中对主道路进行额外的消杀，如图3所示，那么就可以在之后对主道路的消杀中少消杀对应宽度的主道路．10.13245/j.hust.240364.F003图3多余消杀现象示例图1.3　建模1.3.1　对特殊路段的预处理消杀特殊路段的特殊区域和主道路的需求量不同，因此将特殊路段化为两条起始点和长度相同的弧．其中一条的需求量为消杀主道路的需求量，所需消杀次数为该特殊路段的消杀次数减1，称为普通弧；另外一条的需求量为消杀特殊区域及部分主道路的需求量，所需消杀次数为1，称为特殊弧，对于特殊弧不考虑仅经过不消杀．同时将普通路段称为普通弧．普通弧和特殊弧统称为消杀弧．表1展示了建模过程中所用到的相关变量和参量的符号及含义说明．10.13245/j.hust.240364.T001表1模型涉及符号及含义说明符号含义说明G连通图，G=(V,E,A)K消杀车辆集合，K=1,2,…,k,…C消杀容量上限V顶点集，i,j∈VVC起始点集，VC⊆VE普通弧集，E=(i,j)i,j∈V,i≠jA特殊弧集，A=(i,j)i,j∈V,i≠jxijk消杀车辆k对普通弧(i,j)仅经过不消杀的次数yijk消杀车辆k对普通弧(i,j)消杀的次数bijk消杀车辆k对特殊弧(i,j)消杀的次数qij普通弧(i,j)消杀需求量，qij=qjipij特殊弧(i,j)消杀需求量，pij=pjilij普通弧(i,j)长度，lij=ljiλij普通弧(i,j)所需消杀次数，λij=λjifik消杀车辆k的消杀路径中i点的净流量zijk消杀车辆k若消杀或经过普通弧或特殊弧(i,j)则为1，否则为0S用于消除子回路约束的临时顶点集合，无实际含义ukS用于消除子回路约束的临时决策变量，无实际含义bkS用于消除子回路约束的临时决策变量，无实际含义1.3.2　最优化目标与约束min∑k∈K∑(i,j)∈Elijxijk；(1)∑(i,j)∈Eqijyijk+∑(i,j)∈Apijbijk≤C(∀k∈K)；(2)∑k∈K(yijk+yjik)=λij(∀(i,j)∈E)；(3)∑k∈K(bijk+bjik)=1(∀(i,j)∈A)；(4)∑(i,j)∈E(xijk+yijk)-∑(i,j)∈E(xjik+yjik)+∑(i,j)∈Abijk-∑(i,j)∈Abjik=fik(∀k∈K,∀i∈V); (5)fik=0(∀i∈V\VC,∀k∈K)；(6)∑i∈VCfik=0(∀k∈K)；(7)-1≤fik≤1(∀i∈VC,∀k∈K)；(8)-1≤fik+fjk≤1(∀i,j∈VC,i≠j,∀k∈K)；(9)∑i,j∈Szijk≤S-1+V2ukS(∀S⊆V\VC,S≠∅,∀k∈K); (10)∑i∈S∑j∉Szijk≥1-bkS(∀S⊆V\VC,S≠∅,∀k∈K); (11)ukS+bkS≤1(∀S⊆V\VC,S≠∅,∀k∈K)；(12)ukS,bkS∈{0,1}(∀S⊆V\VC,S≠∅,∀k∈K)；(13)xijk∈N(∀(i,j)∈E,∀k∈K)；(14)yijk∈N(∀(i,j)∈E,∀k∈K)；(15)bijk∈{0,1}(∀(i,j)∈A,∀k∈K)．(16)式(1)为模型的最优化目标，即最小化所有消杀车辆全程仅经过不消杀的总距离；式(2)为容量约束，即每个消杀车辆的消杀用药量不能超过容量；式(3)和(4)表示每条弧的所需消杀次数都须要得到满足；式(5)～(9)为各个节点的净流量约束；式(10)～(13)为消除子回路约束；式(14)～(16)为决策变量的取值范围．2 算法设计本研究的问题可以退化为经典的CARP，而CARP是已被证明为NP-hard问题的经典问题．考虑到模拟退火算法(SA)可以有效解决NP-hard问题[12-14]，因此本研究基于模拟退火算法进行以下算法设计．图4为模拟退火算法的流程图，图中：f(x)为解x的目标函数值；xold为当前解；xnew为新解；∆f为新解和当前解目标函数值之间的差值；θ为当前温度；k为降温系数．10.13245/j.hust.240364.F004图4模拟退火算法流程图2.1　生成初始解首先，对普通弧和特殊弧进行编号，并生成一个空二维数组．数组的每一行对应一个消杀车辆，其列长上限为一个消杀车辆在满足容量约束的情况下最多可消杀的消杀弧数量，可以缩小列长以提高运算效率．数组的每个元素为该行对应消杀车辆所消杀的弧编号，从前往后为该消杀车辆的消杀顺序．然后，随机选择一个未满足所需消杀次数的消杀弧编号并随机填充在数组一个仍待填充的单位，判断填充后的解是否满足容量约束，若满足则填充成功，该消杀弧的所需消杀次数减1；否则填充不成功，重新选择一个消杀弧编号进行填充．如此反复，直到所有消杀弧的所需消杀次数得到满足，数组中未被填充的地方填充0元素(0元素无实际意义，仅为方便后续产生新解)．若在填充过程中，任意未满足消杀次数的消杀弧编号填充进数组都会使容量约束无法满足，则重新开始生成初始解．最后得到的初始解如图5所示．10.13245/j.hust.240364.F005图5初始解示例图2.2　产生新解本研究设计的模拟退火算法产生新解的方法为随机选择将数组中的两个元素进行互换，但所选的元素不能相同且互换之后产生的新解必须满足容量约束条件，否则互换没有意义，须要在当前解的基础上再进行一次互换，直到满足条件为止．2.2.1　两个非0元素互换如图6所示，两个非0元素进行互换会产生两种效果．如图6(a)所示，相当于将两个消杀车辆所须消杀的消杀弧进行互换；如图6(b)所示，相当于将同一个消杀车辆所须消杀的弧的顺序进行调换．10.13245/j.hust.240364.F006图6两个非0元素互换示例图2.2.2　非0元素与0元素互换如图7所示，非0元素与0元素进行互换会产生三种效果．如图7(a)所示，相当于将一个消杀车辆的一个消杀弧转移到另一个消杀车辆中；如图7(b)所示，相当于改变某个消杀车辆的消杀顺序；如图7(c)所示，相当于在两个相邻的消杀弧之间创造出新的填充空间方便之后新解的生成．10.13245/j.hust.240364.F007图7非0元素与0元素互换示例图2.3　更新当前解2.3.1　目标函数本研究设计的模拟退火算法的目标函数即为最小化所有消杀车辆仅经过不消杀的总距离．首先利用Floyd算法求得各个节点之间的最短距离和走最短距离须要经过的节点，然后将消杀弧之间的距离用各点之间的最短距离表示．具体方法如下．如图8所示，假定起始点集为{1，2}，消杀车辆须要依次消杀弧(1，5)，(3，4)和(6，7)，用dij表示点i与点j之间的最短距离．首先比较d11，d15，d21和d25的大小，若d11最小，则该消杀车辆由节点1出发，从节点1开始消杀弧(1，5)，目标函数值加上d11．接着判断d53和d54的大小，若d53d54，则该消杀车辆由节点3开始消杀弧(3，4)，目标函数值加上d53．以此类推，直到最后一个消杀弧，若是从节点6开始消杀弧(6，7)，则比较d71和d72的大小，若d72d71，则该消杀车辆最终回到点2，目标函数值加上d72．10.13245/j.hust.240364.F008图8求解目标函数示例图2.3.2　接受新解规则在生成新解后，通过计算∆f，以Metropolis准则选择接受新解的概率，即p=1  (∆f0);exp(-∆f /T)  (∆f≥0).2.4　最优解条件当每个θ下的迭代次数完成后，通过令θ←kθ实现降温并重置迭代次数，直到降温到最低温度θmin．此外，可以设置一个值，当连续没有被接受的新解数量超过该值，输出最优解．3 计算实验本研究利用随机生成的小规模、中规模算例及现实中的某学校教学楼一层和宿舍区两个大规模算例进行计算实验，并分别与CPLEX求解器和贪婪算法对比，以验证模型的正确性和算法的有效性．使用三元组(P,N,Q)表示一组算例，其中：P为节点数；N为普通弧数量；Q为特殊弧数量．3.1　消杀量设置根据文献[15]的研究，对于普通弧和特殊弧的单次消杀需求量计算式分别为Wn=0.3lb；Ws=0.3lb(t/b+1)(φ∈φA),0.3l(t+b)(φ∈φB),0.3l(t+b)(φ∈φC),0.3lbt/b(φ∈φD),式中：Wn为普通弧单次消杀所需药量；Ws为特殊弧消杀所需药量；l为主道路长度；t为特殊区域宽度；b为单次消杀宽度；φ为特殊区域尺寸；φA，φB，φC和φD分别为A，B，C和D四类特殊区域尺寸集合．在后面的计算实验中，单次消杀宽度都设置为2 m．3.2　参数设置三类规模的算例的计算实验算法参数设置如表2所示．10.13245/j.hust.240364.T002表2算法参数设置参数小规模算例中规模算例大规模算例初始温度10100100最低温度0.10.10.1迭代周期数4 0004 0004 000降温系数0.950.980.98最大连续不被接受新解数1×1042×1052×1053.3　小规模算例计算实验结果对小规模算例(8，13，8)设计了三对不同的消杀车辆数和容量上限，每对参数下开展了10次计算实验，与CPLEX进行比较．如表3所示，表中：最优优化率表示模拟退火算法的最优解与CPLEX最优解的偏差；平均优化率表示模拟退火算法的平均结果与CPLEX最优解的偏差．10.13245/j.hust.240364.T003表3小规模算例(8，13，8)计算实验比较结果消杀车辆数容量上限/L模拟退火算法CPLEX最优优化率/%平均优化率/%最优结果/m平均结果/m平均求解时间/s求解结果/m求解时间/s485.012.012.029.212.00.4700575.042.042.068.442.081.5300665.066.068.447.266.03 600.0004由实验结果可以看出：对于小规模算例的前两组实验，模拟退火算法可以在较短时间内得到精确最优解．对于第三组实验，CPLEX求解器在限制时间里只能得到解的上界为66 m，而模拟退火算法可以在较短的时间内得到较优的解，且与CPLEX求解器的上界解相同或近似．3.4　中规模算例计算实验结果对中规模算例(11，14，5)设计了三对不同的消杀车辆数和容量上限．每对参数下开展了10次计算实验，与CPLEX进行比较，如表4所示．10.13245/j.hust.240364.T004表4中规模算例(11，14，5)计算实验比较结果消杀车辆数容量上限/L模拟退火算法CPLEX平均优化率/%最优结果/m平均结果/m平均求解时间/s求解结果/m求解时间/s412569.076.2320.887.03 60012.45100111.0111.0375.2153.03 60027.4690111.0115.0505.2199.03 60042.2由实验结果可以看出：对于中规模算例，CPLEX求解器无法在限定时间内解得精确解，而模拟退火算法可以在较短时间内得到比CPLEX求解器更优的解，平均优化率在10%~50%之间．3.5　大规模算例计算实验结果对两个大规模算例(24，23，9)和(43，44，6)分别设计了四对不同的消杀车辆数和和容量上限．每对参数下开展了10次计算实验，并将实验结果与贪婪算法进行比较，如表5和表6所示，表中平均优化率表示算法的平均结果与贪婪算法最优解的偏差．10.13245/j.hust.240364.T005表5某学校教学楼一层算例(24，23，9)计算实验比较结果消杀车辆数容量上限/L模拟退火算法最优结果/m模拟退火算法平均结果/m贪婪算法结果/m平均优化率/%9120742.0749.802 186.065.710110848.4857.482 656.067.7111001 000.61 000.602 684.662.712901 128.61 138.122 822.859.710.13245/j.hust.240364.T006表6某学校宿舍区算例(43，44，6)计算实验比较结果消杀车辆数容量上限/L模拟退火算法最优结果/m模拟退火算法平均结果/m贪婪算法结果/m平均优化率/%96001 030.951 138.714 446.7074.4105501 066.351 333.355 200.9074.4115001 199.551 377.984 621.3570.2124501 484.551 666.154 572.1063.6由实验结果可以看出：本研究设计的模拟退火算法较贪婪算法的平均优化率在60%~80%之间，且随着消杀车辆的增加和容量上限的减少，仅经过不消杀距离在总距离中的比例会增加．4 结语本研究对社区疫情防控的消杀作业路径优化问题进行了研究，针对各类特殊区域设计了四种作业工艺并建立了问题的数学模型，设计了基于模拟退火算法的启发式算法对问题进行求解．通过计算实验发现，算法求解小规模算例可以在较短时间内取得与精确解近似或相同的解，平均偏差率在4%以内；求解中规模算例可以在较短的时间内取得比CPLEX求解器更优的结果，平均优化率在10%~50%；对于大规模的算例，取得的结果较贪婪算法平均低了60%~80%．实验结果表明本研究对解决社区疫情防控的消杀作业路径优化问题有一定的价值．在未来的研究中，将考虑使用其他智能优化算法以提高算法的收敛能力，同时将考虑多车型、需求可拆分等方向，对问题进行深入研究．