0 引言
近年来，新冠疫情的持续反复对物资运输提出了新的要求，为风险区域客户提供物流服务成为各物流供应商面临的难题。按照常态化疫情防控政策要求，车辆为风险区域客户运输物资后，物流供应商需对车辆进行严格消杀，同时对司机进行健康监测，导致运输成本增加。另外，物资运输车辆行驶路线也是影响运输成本的重要因素。物资运输路径优化是物流网络优化的重点之一，能通过合理安排物资运输车辆行驶线路，将位于风险区域与非风险区域的客户分开派送，有效降低运输成本，因而成为研究热点。
近年来，国内外学者对物资车辆配送路径优化进行了广泛研究。物资车辆路径优化模型，又名车辆路径模型（Vehicle Routing Problem, VRP），由Dantzig和Ramser于1959年首次提出[1]。在此基础上，部分学者从城市路网层面入手，在物资车辆配送路径优化模型中考虑了交通拥堵、城市地形、区域限行、车辆速度实时变化等实际城市路网运行状况，增加了模型在现实城市路网中的实用性，如王安等[2]针对城市交通拥堵状态，用行驶时间替代行驶距离，构建了考虑交通拥堵的物资配送路径优化模型；王川[3]在模型目标成本中考虑了城市地形导致的额外车辆油耗因素，提高了物资配送路径优化模型成本计算的准确性；袁强[4]在模型约束中考虑了城市区域限行，解决了物资运输路径优化问题在区域限行状况下的应用问题；范厚明等[5]和侯登凯等[6]分别从时空距离和时变路网两个角度出发，研究了物资配送路径优化模型在运输车辆速度实时变化环境中的应用。
综上，当前关于物资配送路径优化模型的研究主要聚焦于城市路网、客户需求、实际应用等方面，将物资配送路径优化模型用于解决农村电商、危废回收、应急物资运输等实际问题，但尚无关于物资配送路径优化模型在常态化疫情防控环境下的应用研究。从实际操作层面来看，常态化疫情防控政策直接影响车辆消杀频率与司机防疫调度，进而影响物流供应商的综合运输成本。因此，本文在疫情常态化防控背景下，基于已有研究，将客户按照所在区域进行分类，综合考虑服务时间窗、多车型服务车队及疫情防控对物流运输造成的额外成本因素，以最小化由物流供应商运输、防疫和违背时间窗惩罚组成的综合运输成本为目标，构建物资运输路径优化模型，并针对问题结构设计相应的启发式求解算法，以期为疫情防控政策下的物流运输路径优化提供理论支撑。
1 问题描述与模型构建
1.1 问题描述
本研究提出的物资运输路径优化问题以经典的运输路径优化模型（VRP）为基础，同时考虑常态化疫情防控对运输路径优化造成的影响。根据疫情防控需求，本文将物流供应商的客户分为两种类型：位于疫情风险区域的客户（简称“风险客户”）和位于非疫情风险区域的客户（简称“非风险客户”）。为防止货物运输导致交叉感染，切断传染链，针对风险客户，需使用专用车辆并指定司机进行派送，司机在派送过程中全程封控不下车，车辆在抵达客户点后，由客户对车辆和物资进行消杀后再卸货。运输完成返回后，对司机进行严格核酸检测和健康监测，对运输车辆实行彻底消杀，这些都额外增加了运输成本。
因此，常态化疫情防控下物资运输路径优化问题属于带软时间窗的单配送中心、多车型、多类型需求的静态运输路径优化问题。该问题中，已知客户节点位置、货物需求量及是否位于风险疫情区域；物流供应商有一个配送中心、若干客户（风险客户与非风险客户）及不同型号的车辆（运输成本各不相同）；每个客户的服务时间窗不同，同时有且只有一辆运输车为其服务。相应的路径优化问题可以描述为：在满足车辆容量、时间窗与车型等约束的前提下，尽可能合理规划车辆运输线路以使运输总成本最低。
与传统物资配送运输路径优化问题相比，本研究根据客户分类，对各类型客户的适配车型进行单独判断，并优化车辆运输路线，因此在模型构建与求解上更加复杂，如表1 所示。
表1 问题比对 |
| 传统运输路径优化问题 | 常态化疫情防控背景下的 运输路径优化问题 | |
|---|---|---|
| 客户类型 | 单一类型 | 多类型 |
| 车辆类型 | 单车型 | 多车型 |
| 服务时间窗 | 无时间窗 | 软时间窗 |
| 目标成本 | 运输成本 | 运输成本+防疫成本+ 时间窗惩罚成本 |
1.2 模型假设
本文模型构建基于以下假设：
（1）已知网络内所有节点的需求量、地理位置及时间窗，且各值不会改变；
（2）单个客户需求总量不会超过车辆荷载上限；
（3）已知网络内的成本参数（包含不同车型的运输成本、司机健康监测人工成本等）；
（4）所有车辆从配送中心出发，在运输任务完成后又驶回配送中心；
（5）假设车辆在路网中匀速行驶，不考虑道路拥堵或车辆事故等特殊因素。
1.3 模型建立
1.3.1 模型目标函数
模型目标函数由物流供应商运输成本和违背时间窗惩罚成本两部分组成：
式（1）中：Z为总成本（元）； 为常态化疫情防控下的运输成本（元）； 为配送过程中，因违背客户要求的最佳配送时间窗范围而导致的惩罚成本（元）。
疫情风险会产生额外的运输成本，且不同车型产生不同的附加成本。本文将运输成本分为两部分，第一部分将启用第k种类型车辆产生的额外防疫成本加入该车辆从配送中心出发行驶到第一个客户所产生的行驶成本，即 ；第二部分为除去第一部分以外的行驶成本，即 。对二者求和后，可得到常态化疫情防控下的运输成本：
式（2）中： 为启用第k种类型车辆产生的额外防疫成本（元/车）； 为第k种类型车辆的单位行驶成本（元/km）； 为配送中心和第j个客户之间的行驶距离（km）； 为路径决策变量，若物资运输车辆从i点行驶到j点使用第k类车辆，则取 =1，否则取 =0； 为第i个客户和第j个客户之间的行驶距离（km）；N为网络内所有的节点集合；0表示网络内唯一的配送中心；K为网络内不同类型的车辆编号集合，车辆被集中分为两大类，其中奇数编号车辆为风险客户服务，偶数编号车辆为非风险客户服务，且编号大小顺序按荷载重量划分，每个车型荷载重量不同，按编号升序排列 ， 表示第k种类型车辆的标定荷载（t）。
1.3.2 惩罚成本
由于疫情防控原因，车辆不一定能在客户最期望的时间范围内准时到达，有可能为客户带来一定的损失，如工厂停工费、货物存储费、货物贬值费等，其中部分需由物流供应商承担。因此该部分费用需划入物流供应商的运输总成本中，在线路规划时综合考量，即惩罚成本，如图1 所示。惩罚成本一般和延误时间相关，延误时间越长，成本越高。当物流供应商的配送时间远远超出客户可接受的时间范围，可能导致客户完全无法接受，故惩罚成本是无穷大的。
风险客户和非风险客户对时间的敏感程度不同，相比非风险客户，风险客户对时间敏感程度相对宽松，因此在货物非准时到达时惩罚成本也不同，如图1 所示。客户的时间惩罚成本 可以使用分段函数表示：
式（3）中： 为第i个客户提前送达的惩罚成本（元）； 为第i个客户提前送达的单位惩罚成本（元/h）； 为配送车辆到达第i个客户的时间（h）； 为第i个客户延迟送达的惩罚成本（元）， 为第i个客户延迟送达的单位惩罚成本（元/h）。
通过对式（3）变形得到时间窗惩罚成本：
1.3.3 模型约束
模型的主要约束如下：
每个客户有且仅有一辆与其分类相符的车型为其提供服务，且在运输过程中只能提供一次服务：
任意运输线路的行驶起点与终点均为配送中心：
每辆运输车在到达任意客户卸货后，须继续向下一客户行驶：
每条运输线路装载的货物总重量不得超过所选车型k的最高荷载：
式（9）中： 为第i个客户的物资需求量（t）。
若客户i和客户j均为风险客户或非风险客户，则客户i和客户j可以由同一辆车进行配送，且使用车型k：
式（10）中： 为判断参数，当第i个客户可由车型k提供运输服务时，取 =1，否则 =0。
货物到达客户i的时间 须在可接受时间范围内：
配送车辆到达客户j的时间 是到达前一个客户点i的时间、配送车辆在第i个客户卸货所消耗的服务时间、配送车辆从第i个客户行驶到第j个客户所消耗的运输时间之和，即：
式（12）~式（13）中： 为配送车辆在第i个客户卸货所消耗的服务时间（h）； 为配送车辆从第i个客户行驶到第j个客户所消耗的运输时间（h）；v为车辆的平均运行速度（km/h）。
车辆从配送中心驶出的时间点 被约束为0：
车辆的路径决策变量为二元0-1变量：
2 算法求解
常态化疫情防控下物资运输路径优化模型是经典运输路径优化模型（VRP）的延伸与拓展，属于典型的NP-hard问题。此类问题很难使用精确算法在可接受的时间范围内对实际规模案例进行求解，因此需设计与问题结构相匹配的启发式算法对问题进行求解。由于遗传算法与变邻域搜索算法在路径优化问题求解中表现出的强鲁棒性与搜索能力，本文针对研究问题特点设计了与问题结构相对应的遗传算法对问题进行求解，如图2 所示。
根据图2 ，所建遗传算法先对所有网点数据进行预处理，建立大染色体。然后，生成初始解，并判断其是否满足时间窗约束，再根据每条运输线路不同运量赋予不同车型并进行适应度函数评估。接着，根据路径特点对运输路径进行交叉与变异，在遗传操作后新生成的染色体会再次进行约束判断与适应度函数评估，使用精英保存策略保留适应度函数排名前10%的解并直接进入下次迭代，进而加速算法收敛。最后，判断算法终止条件，待算法收敛后，停止运算，并输出最优结果。
2.1 解的编码与构造
根据问题结构，本文遗传算法染色体构造设计示意如图3 所示。为了降低不可行解的生成概率，提高算法效率，染色设计按照风险客户和非风险客户分为两类。运输路径选择实数编码，染色体最尾端为路径分割点，用来标记与识别不同的物资配送线路。以图3 的非疫情风险区域客户的运输路径为例，其包含两条物资配送线路，分别为0-7-10-0和0-8-12-11-9-0。针对所得运输路径分别计算车辆荷载，进而匹配车型，计算适应度函数。
2.2 交叉与变异
在交叉中，为了降低不可行解的生成概率，所设计遗传算法两部分染色体分开进行交叉变异操作。本研究设计的部分匹配交叉方式如图4 所示。该方式可保证在路径优化问题中，即使所选的两个父代完全相同也能生成新的不同子代，进而防止搜索陷入局部最优，加快算法的收敛速度[16]。部分匹配交叉中，第一步分别在两部分染色体中随机选择交换区域，并对路径分割点进行交换；第二步将交换区域内部的基因分别交换放置在各自染色体的前端，生成新的染色体；第三步对新生成的子代染色体进行筛选，根据新加入的交换基因，搜索并删除与新加入基因重复的基因，从而形成全新的子代染色体。
针对变异操作，本研究采用基因翻转变异，分别随机选取父代染色体中包含的疫情风险区域客户和非疫情风险区域客户两部分模块中的基因进行调换，从而直接生成新的子代染色体，如图5 所示。
3 算例分析
3.1 模型验证及算法性能测试
为验证模型并测试针对该模型所设计的遗传算法的适用性和计算性能，本研究使用LINGO软件和所设计的遗传算法分别求解一系列不同规模的算例，并比对二者的计算结果。Solomon标准算例是经典的VRP算例，提供已知的客户点位置、需求量、时间窗、服务时间等参数，且有3种不同的客户点分布：随机均匀分布（R型）、随机集中堆分布（C型）、随机均匀+集中堆混合分布（RC型），均表示客户在地理位置上的不同区位分布模式。目前，Solomon算例已被广泛应用于各种路径优化问题研究，相比于单个实际案例，Solomon算例包含的类型更全面，更具普适性，能充分证明模型在不同运输网络中的适用性[17]。因此，本研究采用Solomon标准算例对模型和算法进行验证。所设计遗传算法在配置2.5GHz CPU, Intel Core i7处理器、内存16GB的计算机上采用MATLAB 2019b编码实现，运行时间上限设置为10 800s。根据问题规模的不同，遗传算法的输入参数（如种群规模、交叉概率、变异概率、算法终止迭代次数等）通过多次实验数据计算获得，且所有计算结果均为运行10次的平均值。
分别采用LINGO和本文设计的遗传算法求解不同类型（R型、C型与RC型）与不同规模（10客户、25客户、50客户、100客户）算例，对应的运行结果与运行时间如表2 所示，其中遗传算法与LINGO软件的运算结果差值百分比 由式（16）计算得到：
式（16）中： 为由遗传算法运行求得的最优目标函数值； 为由LINGO求得的最优目标函数值。
表2 不同算例运行结果与运行时间比对 |
| 客户 （分布类型 及数量） | 运行结果 | 运行时间 | |||
|---|---|---|---|---|---|
| LINGO | 遗传算法 | LINGO /s | 遗传算法 /s | ||
| R10 | 8 872.3 | 8 872.3 | 0 | 667 | 13 |
| R25 | 24 963.4 | 24 963.4 | 0 | 7 586 | 241 |
| C25 | 24 545.4 | 24 545.4 | 0 | 6 804 | 198 |
| RC25 | 24 462.8 | 24 882.2 | 1.5% | 8 653 | 260 |
| R50 | 73 430.6 | 69 854.4 | -4.9% | 10 800 | 843 |
| C50 | 75 412.2 | 70 252.6 | -6.8% | 10 800 | 787 |
| RC50 | 74 871.1 | 68 685.3 | -8.3% | 10 800 | 824 |
| R100 | — | 242 382.1 | — | — | 2 341 |
| C100 | — | 238 453.2 | — | — | 2 564 |
| RC100 | — | 240 983.9 | — | — | 2 867 |
由表2 可知，针对部分小规模算例（R10, R25, C25），利用本文所建遗传算法求解可得问题的最优解，与LINGO求得的精确解相同，只有在求解RC25客户算例时，产生1.5%的差异。在运行速度方面，遗传算法的计算时间远远短于LINGO的计算时间。当算例规模到达50客户时，LINGO软件已经无法在规定的时间范围内计算出算例的最优解，只能在10 800s内给出算例的可行解，此时遗传算法求得的解明显优于LINGO得到的解。当算例规模增加到100时，LINGO已经无法在时间限制内给出一个合理的可行解，此时遗传算法依然能在可接受的时间范围内给出不同类型算例的优化解。这也说明本研究所设计遗传算法对不同规模与不同类型算例的求解精度与效率均较高。
3.2 输入参数敏感度分析
为分析不同模型输入参数对常态化疫情防控背景下物资运输路径优化的影响，选取客户位置混合分布的RC50客户算例作为基准算例，计算生成本研究的分析算例，其中包含38个风险客户，12个非风险客户和6种配送车型。配送车型参数如表3 所示。模型其他相关基准参数参照湖州市某物流企业成本数据估算得到，如表4 所示。
表3 模型车辆计算参数 |
| 车辆 编号 | 车辆荷载/t | 防疫成本 /（元·车-1） | 单位距离运输成本 /（元·km-1） | |
|---|---|---|---|---|
| 疫情风险客户服务车型 | 1 | 4 | 2 000 | 50 |
| 3 | 8 | 3 500 | 70 | |
| 5 | 12 | 5 000 | 90 | |
| 非疫情风险客户服务车型 | 2 | 4 | — | 50 |
| 4 | 8 | — | 70 | |
| 6 | 12 | — | 90 |
表4 模型基准计算参数 |
| 输入参数 | 取值 |
|---|---|
| 车辆平均行驶速度/（km·h-1） | 45 |
| 非疫情风险客户提前送达的单位时间惩罚成本/（元·h-1） | 200 |
| 非疫情风险客户延迟送达的单位时间惩罚成本/（元·h-1） | 400 |
| 疫情风险客户提前送达的单位时间惩罚成本/（元·h-1） | 100 |
| 疫情风险客户延迟送达的单位时间惩罚成本/（元·h-1） | 300 |
（1）车辆平均行驶速度分析
不同城市对道路车辆的行驶速度管控政策可能不同，因此在保证其他参数不变的前提下，在一定范围内调整车辆平均行驶速度来观察其对所建模型的影响。输入参数平均车辆行驶速度的变化对模型部分输出参数（网络内的配送车辆数、车辆平均荷载、车辆平均装载率）的影响如图8 所示。
由图8 可知，当车辆平均行驶速度增大时，网络内所用配送车辆数逐渐减少，车辆荷载逐渐增大。这说明当车辆可以提升运行速度为客户服务时，物流供应商倾向于使用荷载更大的车型、更少的车辆来降低运输成本。另外，当车辆平均行驶速度增大时，网络内车辆装载率逐渐增加，但当速度增大至65km/h并持续增加时，装载率保持收敛。这主要因为受限于网络内客户需求和时间窗，当网络内所用车辆数过少时，无法装下所有客户需求的货物同时无法在合理时间内为客户提供服务，因此即使车辆平均速度持续增大，网络内部所用的车辆数及每个车辆的装载率也无法发生变化。
（2）时间窗长度影响分析
不同区域和不同类型的客户对配送时间窗的要求可能不同，故在保证其他参数不变的前提下，在一定范围内调整网络内所有客户的时间窗来观察其对所建模型的影响。输入参数时间窗变化对部分模型输出参数（运输成本、时间惩罚成本和网络内使用的配送车辆数）造成的影响如图9 所示。可以看出，当客户的服务时间窗放宽后，网络内所用配送车辆数逐渐减少，导致运输成本小幅下降。同时，时间窗的放宽也大幅降低了系统内的时间惩罚成本。
（3）防疫成本影响分析
不同物流供应商的防疫成本可能不同，故在保证其他参数不变的前提下，在一定范围内调整防疫成本以观察其对所建模型的影响。输入参数防疫成本对模型部分输出参数（配送车辆数、车辆平均荷载）的影响如图10 所示。可以看出，当防疫成本逐渐增加时，为了降低其给总成本造成的影响，物流供应商倾向于在网络内投放更少但容量更大的运输车辆。
4 结语
为解决常态化疫情防控背景下的物资运输路径优化问题，本文构建了综合考虑物流供应商的防疫成本、多客户类型、服务时间窗与多车型等因素的物资运输路径优化模型，并针对问题结构设计了一种结合部分匹配交叉与精英保留等遗传策略的遗传算法对模型进行求解。通过与LINGO软件的精确计算结果比对，发现所设计的遗传算法在求解不同类型与不同规模的算例时，均具有较高的计算速度与计算精度。本文拓展了传统物资运输路径优化模型在常态化疫情防控环境下的应用，为物流供应商科学选择运输方案提供了方法。然而，由于城市道路运行情况的复杂性，本文在模型构建中未考虑交通拥堵、车辆速度实时变化等实际情况，在未来的研究中将进一步完善模型，提高模型在现实城市路网中的实用性。