一种“效率-公平-运力”多维权衡的需求可拆分配送方法

王建伟，刘旭旭，付鑫*，杨洋，崔梦妍

(1.长安大学，运输工程学院，西安 710064；2.北京航空航天大学，a.交通科学与工程学院，b.车路协同与安全控制北京市重点实验室，北京 100191）

0 引言

自然灾害和重大社会公共事件等各类突发事件所引发的人员伤亡、财产损失及环境恶化等问题日益显著。当突发事件发生后，综合考量各类救灾目标需求，将各类应急物资配送至受影响区域可降低由突发事件造成的损失。在研究应急物资配送问题时，已有研究多选择以配送总耗时最少[1]或路程最短[2]为目标函数，将配送效率最优作为应急物资配送首要目标，以降低灾害影响。而当面临多受灾点情景时，各个受灾点间的配送差异性也需受到关注。随着“人道物流”的提出，有学者将配送公平性作为应急物资配送的切入点。Cook 等[3]考虑供应物资的不确定性，在两阶段人道主义供应链构建背景下，通过将最小化未满足需求作为目标，把配送公平性融入应急物资配送路径优化问题中。曲冲冲等[4]则同时考虑配送效率与配送公平性因素，建立多目标规划模型以解决大规模地震后应急物资配送问题。除需要考虑配送效率与配送公平外，突发事件还具有不确定性[5]，可能会发生路网损害、运力不足等情况，因此，决策者将有限运力、可用运输资源最少纳入影响因素范围具有必要性。吴珂等[6]将使用车辆数最小为优化目标，构建应急配送车辆调度模型，以保证应急物资在时间窗范围内到达受灾点。上述研究虽然在目标设定上存在差异，但其均假设每个受影响点只能被车辆访问一次，并且各点物资需求量小于单车最大载重量。然而，在突发事件发生后，会产生多个受影响点短时间内产生不同规模与类型物资需求，在真实救援场景中，各受影响点物资需求量往往超过单一车辆运输规模，若仍要求每个受影响点只能由一辆救援车辆提供运输服务，则会导致模型适用性受到影响。因此，有必要将需求可拆分这一约束条件引入应急物资配送问题研究。

与传统车辆路径问题相比，需求可拆分车辆路径问题一般允许需求点需求量大于单车容量，可将各需求点物资需求根据车辆剩余载重量进行拆分，使其被多车多次访问[7]，更加符合应急物资配送实际情况。Zhang等[8]将需求可拆分问题引入海上应急物流问题中，以解决运输网络不确定情况下的应急物流作业问题。Bortfeldt等[9]建立了一个三维装载约束下的需求可拆分车辆路径问题，通过3种算例证明拆分交付不仅在一维装载下更优，在三维装载约束下得到的结果也更有益。需求可拆分车辆路径问题可以提高车辆利用率，降低使用车辆数，这一特点对于应对突发事件后大量物资运输需求或者可用运输资源受限问题具有更好适用性。

综上所述，为考量多目标场景下的应急物资配送问题，本文在模型构建时拟加入需求可拆分条件，并且为探究效率、公平、运力等因素对应急物资配送方案的影响程度，扩大应急物资配送模型的适用范围，以配送时间最短、加权时间攀比值最小和使用车辆数最少为目标函数，构建在有限运力条件下，权衡“效率-公平-运力”多维需求的可拆分应急物资配送模型，并设计改进的蚁群算法求解模型。

1 问题描述与模型建立

1.1 问题描述

本文研究问题为：突发事件发生后，单种物资、单种车型、单供应点、多需求点、带时间窗、多目标的需求可拆分应急物资配送问题，模型假设如下：

(1)仅有一个物资供应点，且该供应点物资储备量已知；

(2)各需求点物资需求量已知；

(3)物资供应点物资储备量等于各需求点总需求量；

(4)各需求点最多被访问2次；

(5)不考虑道路损毁等意外影响，且路网节点、路段距离和通达性已知；

(6)配送车辆型号大小相同，车辆最大载重量均为45 t；

(7)车辆完成服务后应返回物资供应点；

(8)各受灾点仅有右时间窗约束(即最晚到达时间)，当车辆到达时间超出右时间窗时不能提供服务；

(9)各需求点的卸货时间默认为30 min。

1.2 参数定义

本文模型符号说明如表1所示。

表1 模型符号说明Table 1 Notations description

1.3 模型构建

本文总目标主要包括配送时间、加权时间攀比值和车辆使用数这3 部分。目标函数为总目标最小化，即

式中：Z1为配送过程耗时最短，表示配送效率，Z2为以各需求点物资依赖度作为权重Γi的加权时间攀比值最小，加权时间攀比值反映了由物资匮乏时长差异引发的不公平感，表征配送公平性，；Z3为车辆使用数最少，表征运力，w1、w2、w3为权重，三者均为正数且由决策者偏好决定，其对配送方案的具体影响见3.3节。

约束条件为

式(2)和式(3)表示各点最晚到达时间计算方法，其中，T0v=0，每个点最多被访问2 次；式(4)表示各点最晚到达时间不能超过右时间窗；式(5)表示入度均衡和出度均衡，且车辆在1次行程中至多只能途经某需求点1 次；式(6)表示避免子回路约束，其中，N为I的一个真子集；式(7)表示车辆容量限制；式(8)表示所有车辆为某需求点运送物资之和等于该需求点的物资需求量，其中，di表示点i的物资需求量；式(9)表示车辆只有访问某需求点才能对其服务，其中，dj表示点j的物资需求量；式(10)表示w1,w2,w3取值范围，三者均为正数且由决策者偏好决定；式(11)表示各变量类型与范围。

2 求解算法设计

2.1 蚁群算法的改进

需求可拆分车辆路径问题为一类非确定性多项式(Non-deterministic Polynomial,NP-hard)问题，本文使用蚁群算法求解模型。为加快蚁群算法搜索速度，避免求解结果陷入局部最优，主要从选择拆分点、信息素更新和引入变邻域搜索算子这3方个面改进蚁群算法，且当解持续不变时，初始化信息素，以增加随机性，具体操作步骤如下：

Step 1 初始化蚁群参数，迭代次数F=1。

Step 2 随机生成各搜索路径初始点。

Step 3 根据时间窗和车辆剩余载重量确定可访问点集合，并根据状态转移公式选择下一访问节点。

Step 4 计算目标函数值，并选出最优解。

Step 5 对最优解进行变邻域搜索，得到新解，并判断新解是否优于最优解，若是更新最优解。

Step 6 判断F代最优解是否等于F-1 代最优解，若是，调整ρ。

Step 7 判断是否连续20代最优解相同，若是，初始化信息素；否则，更新信息素。

Step 8 判断迭代次数是否达到最大迭代次数Fmax，若是，输出当前最优解；否则F=F+1，并转至Step 2。

2.2 选择拆分点

本文定义拆分点为需求量大于车辆剩余载重量的点。针对拆分状态，将每个需求点进行0-1 标记，0为未被拆分，1为已拆分。在进行拆分点选择时，若存在拆分状态标记为1 的需求点，则将其从可访问点中剔除。

2.3 信息素更新

在每次迭代结束后，对所有路径进行信息素更新，但只允许目标函数值最小的蚂蚁释放信息素，并为其增加一个奖励值[10]，信息素更新方式为

式中：εij(F+1) 为F+1 代的点i与点j间信息素浓度；ρF+1为F+1 代的信息素挥发因子；Δεij(F,F+1) 为两代间信息素改变量；Q为信息素常量；Rbest为最优路线所包含的所有弧；Lbest为最优路线的长度；Lnow为当第F+1 代最优路线的长度。

为加快前期信息素积累速度，自适应改变信息素挥发因子，当两次迭代所得最优解相同时，减小信息素挥发因子；否则，信息素挥发因子为常数ρ。信息素挥发因子公式为

为避免算法陷入局部最优，增加选择多样性，当连续20 次迭代所得的最优解均相同时，对信息素矩阵进行初始化操作。

2.4 变邻域搜索算子

本文采用插入算子、逆转算子和交换算子搜索邻域解[11]。假设原始解R=(1,2,3,3,4,5,4)，i=2，j=6，插入算子是将第1 个位置i对应的受灾点插入到第2 个位置j对应的需求点后面，得到新解R1=(1,3,3,4,5,2,4)；逆转算子是将i、j间的所有需求点进行逆转操作，得到新解R2=(1,5,4,3,3,2,4)；交换算子是交换i、j对应需求点，得到新解R3=(1,5,3,3,4,2,4)。

3 实例分析与讨论

3.1 案例描述

在建模基础上，本文根据2008年汶川地震开展实例验证。将成都市(编号为0)作为物资供应点，为汶川县、北川县等12个区域进行急救医药包运输。各地区伤亡人员情况如表2所示，假设人均4 个急救医药包[12]，每个医药包重量0.5 kg，生成各受灾点需求量，根据所罗门算例中的c101 数据生成各点右时间窗。提取在线开放街区地图中四川省主干路网(本文指高速公路，一级公路和二级公路)作为各点间原始路网数据，使用改进Dijkstra算法求得各点间最短距离，并简化为拓扑结构，如图1所示。

表2 汶川地震各地区伤亡人员情况Table 2 Casualties of Wenchuan earthquake in various regions

图1 各点间最短路路网拓扑简图Fig.1 Topology diagram of shortest road network between points

3.2 案例求解与算法比较

使用Matlab R2018a 编写算法代码，相关参数设置如下：蚂蚁数量m=50，最大迭代次数Fmax=100，转移控制参数r0=0.95，初始信息素挥发系数ρ=0.3，信息素重要程度因子ι=1，启发函数重要程度因子ϖ=5，时间窗重要程度因子ξ=3，物资依赖度重要程度因子ψ=1，更新信息素浓度的常数ς=10，此时假设决策者无明显偏好，即w1、w2、w3取值均为1 3，车辆行驶速度为v=50 km·h-1。使用改进的蚁群算法对案例随机求解10 次，最优解配送路线方案如表3所示，算法收敛曲线如图2所示。

表3 改进蚁群算法最优解配送路线方案Table 3 Improved ant colony algorithm optimal solution distribution route scheme

为验证改进算法性能，应用传统蚁群算法在相同条件下对模型随机求解10 次，算法最优解收敛曲线如图2所示。利用最优解、平均值、标准差、平均偏差率(C1)、优化率(C2)对比两种算法，结果如表4所示。其中，为平均值，Zbest为最优值，Zbest-IACO为改进蚁群算法最优值，Zbest-ACO为传统蚁群算法最优值。

图2 算法所得最优解收敛曲线对比Fig.2 Comparison of convergence curves of optimal solution obtained by traditional ant colony algorithm and improved ant colony algorithm

表4 算法求解结果对比Table 4 Comparison of solution results of traditional ant colony algorithm and improved ant colony algorithm

通过对比传统算法与改进算法的最优解收敛情况可知，传统蚁群算法迭代40 次后陷入局部最优，改进蚁群算法可通过邻域搜索跳出局部最优，得到更优解，如图2所示。值得一提的是，虽然在2.1 节蚁群算法改进中存在更新信息素的操作，但更新信息素仅仅是增加获取更多解的比例，由于在每次迭代过程中仅记录目前为止蚁群得到的最优目标函数值及其配送路线(当第n+1次迭代的最优解劣于第n次迭代的最优解时，算法的最优解仍为第n次迭代的最优解)，因此图2中改进蚁群算法最优解收敛曲线在第20次到第70次之间保持平稳。

由表4可知，改进算法的最优解和平均值均小于传统算法，且优化率为负数，可见改进算法求解质量更好，不易陷入局部最优，并且改进算法的标准差和平均偏差率均小于传统蚁群算法，表明改进后算法的稳定性有所提升。

3.3 不同场景下算例结果分析

(1)三目标场景

3.2节中，效率、公平、运力这3个子目标函数权重w1,w2,w3的初始取值均为1/3，为探究子目标函数权重对模型结果的影响，对w1,w2,w3从[0,1]区间以0.1为间隔分别取值，并进行排列组合，即针对3 个权重中每一权重的任一取值，都对另外两个权重值以0.1 为间隔进行穷举，形成所有组合可能。最终得到66种权重组合，在相同实验环境下，根据所有权重组合使用改进蚁群算法求解10 次，观察各权重组合最优值绘制目标函数值随子目标函数权重变化情况，结果如图3所示。

图3 目标函数值随子目标权重变化散点图Fig.3 Scatter plot of change of objective function values with sub-target weights

通过分析各权重组合下目标函数最优解可知：①整体而言，子目标函数权重变化对目标函数值影响显著，目标函数值与公平权重和运力权重呈反比关系，与效率权重呈正比关系；②同时考虑3 个目标函数时，各子目标函数权重满足效率权重在0.3以内、运力权重在0.6以上、公平权重在0.7以上中任意一条件，均能使最终目标函数值取得较好水平(0.15以内)。因此，在同时考虑效率、公平和运力时，决策者应慎重考虑各子目标函数权重。

(2)双目标场景

为探究更广泛场景下子目标函数权重的影响，在相同实验条件下，对任两个子目标选取不同权重值，比较不同决策权重下各子目标的变化，结果如图4所示。

图4 双目标前提下各子目标函数值随权重变化图Fig.4 Variation of each sub-objective function value with weights under premise of double objective

通过分析双目标场景下，使用车辆数随运力权重变化情形可知，当决策者仅考虑双目标且具有明显运力偏好时(运力权重大于0.9)，配送时间与加权时间攀比值均会急剧增加，然而，使用车辆数却不会发生减少，如图4(b)和图4(c)所示。因此在仅考虑双目标且运力已作为目标函数之一时，决策者一味追求运力最小并不能达到预期目标。

在仅考虑双目标且效率已作为目标之一时，若效率权重已超过0.4，随着效率权重增加，配送时间会收敛于约371 min 处，但车辆数或加权时间攀比值却会急剧增加，如图4(a)和图4(c)所示。由此可知，在仅考虑双目标前提下，当效率权重超过0.5时，配送时间将对权重变化无反应。因此，决策者应均衡考虑权重分配，赋予效率过高权重，不仅不能显著降低配送时间，反而会导致车辆数或加权时间攀比值大幅增加。

在仅考虑双目标且公平已作为目标之一时：当公平权重小于0.4，加权时间攀比值对于权重变化非常敏感；当公平权重处于[ ]0.4,0.9 时，加权时间攀比值会随着权重增加减缓降速；当公平权重超过0.9后，加权时间攀比值不再降低，如图4(a)和图4(b)所示。进一步分析公平权重变化对配送时间和车辆数的影响，当公平权重处于[0 .3,0.7]时，配送时间和车辆数不随公平权重的变化而变化，如图4(a)和图4(b)所示。因此，在已考虑公平的双目标模型中，当决策者倾向提高配送公平性时，将公平权重控制在[0 .3,0.7]为较优选择。

(3)决策者具有明显偏好场景

特别的，当w1,w2,w3的组合排列为时，决策者在决策时使用综合策略，无明显偏好；当w1,w2,w3的组合排列为(1,0,0)时，决策者在决策时使用高效策略，倾向配送时间使用最短，此权重组合适用于突发事件爆发初期，各需求点均对应急物资产生迫切需求，且各需求点受影响程度相差不大，运力充足阶段；当w1,w2,w3的组合排列为(0,1,0)时，决策者在决策时使用公平策略，倾向配送公平最优，此权重组合适用于突发事件爆发初期，各需求点均对应急物资产生迫切需求，且各需求点受影响程度差异明显，运力充足阶段；当w1,w2,w3的组合排列为(0,0,1)时，决策者在决策时使用经济策略，倾向使用最少运力，此权重组合适用于突发事件爆发中后期，各需求点的应急物资需求得到一定满足，且各需求点受影响程度差异不明显阶段，此时减少使用车辆数可降低配送成本。不同决策者偏好下各子目标最优解如表5所示。

表5 不同决策者偏好下各子目标的最优解Table 5 Optimal solutions under different decision maker preferences

对比不同决策者偏好下各子目标函数值可知，效率、公平、运力这3个子目标相互悖反，理想状态下，增加1 辆车可使效率提高6.54%，公平提高16.00%，增加运力投入可以显著提高配送方案的效率与公平。理想状态下，效率提高1.00%，公平降低0.99%，当运力不变时，效率与公平之间近似呈现1∶1的反比例关系。因此，在应急物资配送过程中，应尽可能增加运力投入来提高配送效率与公平。

4 结论

本文得到的主要结论如下：

(1)本文所建模型与算法可用于求解需求可拆分应急物资配送方案生成，可根据不同需求调整模型求解。与传统算法相比，改进后算法可有效摆脱局部最优，寻优性和稳定性表现更好。

(2)当同时考虑“效率-公平-运力”多维目标时，决策者应慎重考虑各子目标函数权重，效率权重应控制在0.3 以内，否则会造成目标效益显著失衡。

(3)当仅考虑双目标且决策者分别偏好效率、公平、运力时，各目标权重的合理偏好为，效率[0 .0,0.4]，公平[0 .3,0.7]，运力[0 .0,0.9]。

(4)在需求可拆分应急物资配送模型中，效率、公平和运力这3个子目标相互悖反，增加运力投入可以显著提高配送方案的效率与公平，当运力不变时，效率与公平之间近似呈现1∶1反比关系。