基于低碳排放的应急物流车辆路径优化

张静怡，司夏萌，张 虹

（北京信息科技大学 信息管理学院，北京 100192）

0 引言

近年来，各类突发事件给人们的生命安全带来了严重的威胁。例如，近年在全国各地频繁发生的洪涝灾害、四川地区的地震灾害以及在全世界肆虐的新冠疫情等。这类事件会给人们的生命健康带来严峻的威胁，其影响也蔓延到社会与经济层面，给社会稳定与经济持续发展造成危害。突发事件发生时，为了减少人员伤亡与财产损失，救援工作对物流的需求极为迫切。因此，有必要组织好应急物流工作，对应急物流车辆路径优化问题进行研究，在应对突发事件时具有十分重要的意义。

目前，已有众多学者对应急物流配送路径优化进行研究。宋英华，等[1]以时间窗惩罚成本最小与驾驶员心理成本最小为目标，建立了双目标应急物流配送车辆路径问题的整数规划模型，并通过加权遗传算法进行了求解；Li，等[2]以运输时间最短、受灾点满意度最大为目标，建立了应急物流配送路径优化模型，采用快速非支配排序遗传算法求解模型；吕伟，等[3]在软时间窗与硬时间窗的综合约束下以总延迟时间最短、软时间窗惩罚成本最小、硬时间窗不满足数最少为目标，建立了应急物流车辆配送路径模型，首先预处理路网数据，然后建模并利用遗传算法求解模型；杨潇，等[4]基于需求分级构建了应急物流系统定位-路径优化模型，并通过改进遗传算法进行求解，得到了最优选址和路径方案；康斌，等[5]以最小化最晚车辆服务结束时间、最小化需求未满足率为目标，建立了应急物流配送路径优化模型，通过优先邻点交叉算子改进遗传算法对模型进行求解；赵建有，等[6]通过K-means聚类算法选择配送中心并划分受灾点，以救援时间最短、救援费用最小以及受灾点紧迫度排序指数最大为目标，构建了应急车辆路径优化模型，并通过改进的布谷鸟-蚁群组合算法进行求解；彭大江，等[7]引入三角模糊数刻画模糊需求，提出了模糊需求下的应急物流中心选址-路径模型，并通过基于Q-学习的超启发式算法求解模型；Jiang，等[8]以配送时间最短、配送成本最低、未满足需求量最低为目标建立应急物流调度模型，通过鲁棒优化方法进行求解；Oruc，等[9]提出了一个双目标优化模型，旨在通过提供受影响地区的损害信息来最大化评估道路所增加的总体价值并最大化评估节点的总利润，可以有效地寻找救援线路；李慧，等[10]综合考虑道路拥挤情况、救援物资储备、患者和医院的地理位置、车辆空闲情况等多维因素，实现了基于改进弗洛伊德算法的救护车应急救援路径规划。

总结已有研究文献可知，当前对应急物流车辆路径优化的研究多以时间最短、路径最短、成本最低、需求满意度最大为目标构建数学模型，较少考虑到配送过程中的碳排放对环境所产生的影响。基于此，本文综合考虑配送成本、需求满意度与碳排放量，建立了基于低碳排放的应急物流车辆路径优化模型。

1 相关理论

1.1 节约算法

节约算法又称C-W 算法，是将运输问题中的两条路径合并形成一条路径，大幅缩短合并之后的运输距离，直到达到一辆车的最大载重限制后，再对下一辆车进行优化。节约算法通常用来获取车辆路径优化问题的初始解，以满足受灾点的物资需求与配送车辆的载重限制作为前提条件，将运输路径最短的配送方案作为应急物流车辆路径优化问题的初始解。

1.2 遗传算法

遗传算法是模仿生物界选择和遗传的机理形成的一种基于种群的随机全局搜索与优化方法。在遗传算法中，一条染色体代表问题的一个解，根据设置的适应度函数，计算每一条染色体的适应度值，通过选择操作保留适应度较高的染色体，并通过交叉、变异等操作保持种群的多样性，在进行一定次数的迭代后解码，就得到了问题的最优解。

遗传算法具有全局搜索能力强、收敛速度快等优点，但遗传算法通过随机方法产生初始解，搜索的难度更大，且局部搜索能力也存在不足。

1.3 大规模邻域搜索算法

大规模邻域搜索算法是一种主要基于“破坏”和“修复”思想的算法，首先通过破坏算子从目前的解中移除若干需求点，再通过修复算子，将被移除的需求点再度插回已被破坏的解中，从而获得更高质量的解。

2 问题描述

本文研究中需要解决的应急物流配送路径优化问题如下：多个配送中心，多个受灾点，已知各配送中心与各受灾点的位置、各配送中心的仓库容量、车辆的最大载重量，各受灾点的需求量可以用三角模糊函数表示，要求每个受灾点仅由一辆车进行配送，且车辆在完成配送任务后返回配送中心。在时间、空间和资源的约束下，建立车辆路径优化模型，使配送车辆的固定成本、运输过程中产生的成本、未满足需求量的惩罚成本以及碳排放成本之和最低。图1为应急物流车辆路径优化问题的示例图。

图1 应急物流车辆路径优化问题示例图

3 基于低碳排放的应急物流车辆路径优化模型

3.1 模型已知条件

（1）假设每个受灾点仅由一辆车配送物资；

（2）假设配送车辆的初始位置在某一配送中心，且在物资配送完毕后返回该配送中心；

（3）假设配送车辆均为同一型号，其最大载重限制相同。

3.2 符号说明

D：配送中心节点集合{i|i=1，2，…，m}；

N：需求点集合{i|i=m+1，m+2，…，n}；

V：车辆集合{k|k=1，2，…，r}；

c1：车辆的固定使用费用；

c2：车辆的单位运输费用；

c3：未满足需求的单位惩罚成本；

oi：受灾点i最乐观的需求量；

li：受灾点i最有可能的需求量；

pi：受灾点i最悲观的需求量；

Qi：受灾点i的需求量；

dij：点i到点j的距离；

μ：车辆满载时的燃油消耗率；

μ0：车辆空载时的燃油消耗率；

Mk：车辆k能负载的最大重量；

Mijk：车辆k从点i行驶到点j的载重量；

Gi：配送中心i的最大容量；

τ：碳排放量与燃油消耗量之间的转换系数；

3.3 模型建立

考虑到应急物流的特殊性与环境保护思想，为了在降低运输成本的同时尽量满足受灾点的物资需求，并减少碳排放，本文以车辆的固定成本、车辆运输过程中产生的成本、未满足需求的惩罚成本以及碳排放成本之和作为目标函数构建模型。

（1）配送车辆的固定成本

（2）配送车辆的运输成本

（3）未满足需求的惩罚成本。在突发事故中，受灾点的需求量具有不确定性。因此，为尽量满足受灾点的需求，保障救援工作的顺利进行，本文参考文献[11]，利用三角模糊函数，通过最乐观需求、最可能需求和最悲观需求来估计需求量Qi。它们之间的关系见式（3）、式（4）。

采用加权法将三角模糊数转化为某个数值，受灾点i的需求量Qi可以通过式（5）计算得到。

由于车辆和配送中心的容量限制，车辆运送到受灾点的应急物资数量可能会低于预计需求。因此，当受灾点的需求没有得到满足时，将会产生一定的配送惩罚成本。惩罚成本可以表示为:

（4）碳排放成本。应急物流运输过程中的碳排放量与燃油消耗呈线性相关，而燃油消耗受到车辆行驶速度、车辆载重量、道路坡度、行驶距离等多种因素的影响。本文参考文献[12]计算燃油消耗量，可以用以下公式表示：

碳排放成本可以表示为：

（5）目标函数：

约束条件：

式（10）表示各配送中心配送的物资总量不超过配送中心的容量；式（11）表示每个受灾点仅由单独一辆车提供一次配送服务；式（12）表示每辆车在配送中心出发且仅服务于一个配送中心；式（13）表示每辆车在应急物资配送完毕后重新返回配送中心。

4 混合遗传算法设计

为了提高遗传算法的搜索效率，利用节约算法得到遗传算法的初始解。针对遗传算法在局部搜索能力上的缺陷，采用大规模邻域搜索算法中“破坏”与“修复”的思想，构造出一种混合遗传算法，用以求解本文中的应急物流车辆路径优化问题，混合遗传算法的流程图如图2所示。

图2 混合遗传算法流程图

（1）编码。采用整数编码的方法，假设受灾点数目为n，配送中心最大车辆使用数目为k，则染色体长度为n+k-1，染色体可表示为(1，2，…，n+k-1)的形式。

（2）种群初始化。采用节约算法构造问题的初始解，高质量的初始解可以在一定程度上降低遗传算法的搜索难度，假设h是标记第几大距离节约值的位置，则具体步骤如下：

步骤一：将每个受灾点的配送任务分配给一辆单独的车执行；

步骤二：将每两条路径融合并计算距离节约值，将距离节约值依据从高到低的顺序排列；

步骤三：更新距离节约值，融合节约值最大的两条路径，判断该路径上车辆的载重量是否符合车辆容量限制，若不符合，则使h=n+1，执行步骤四，否则重复执行步骤三；

步骤四：融合距离节约值第h大的两条路径，判断是否存在某条路径上仅有一个受灾点的情况，若存在，则重复执行步骤三，否则输出每辆车所途经的受灾点的序号。

通过节约算法得到初始配送方案后，进行种群的初始化。先把初始解按编码方式转换为个体，然后将种群的所有个体全部赋值为初始解转换的个体。

（3）适应度函数。应急物流模型中的目标函数f由配送车辆的固定成本、运输成本、未满足需求量的惩罚成本以及碳排放成本之和组成，由此可知，目标函数越小则结果越符合要求，而选择操作通常保留适应度值较大的个体，因此将适应度函数设为目标函数的倒数，即令：

（4）选择操作。利用二元锦标赛选择法进行选择操作，操作过程就是比较两个个体，然后选择适应度值更大的个体进入子代种群。若种群数目为NIND，则循环NIND次，每次循环随机选出两个个体，在二者中选择出适应度值更大的个体。由于新选择出的NIND个体中可能有重复个体，所以只保留重复个体中的一个个体，然后删除其他重复个体。

（5）交叉操作。首先在两个父代染色体上随机选择两个交叉位置，然后截取两个交叉片段，交错移动到两个父代个体之前，最后删除第2个重复的基因位，构成两个子代个体。这种交叉方式有利于维护种群的多样性。具体操作如图3所示。

图3 交叉操作流程

（6）变异操作。在父代染色体上随机选择两个变异位置，交换两个位置上的基因，得到变异后的子代个体，具体操作如图4所示。

图4 变异操作流程

（7）局部搜索操作。运用大规模邻域搜索算法中“破坏”与“修复”的思想，即通过破坏算子按照相似性计算公式（15）从目前的解中移除若干受灾点，然后通过修复算子将被移除的受灾点插回让目标函数值增加值最少的位置。

破坏算子：按照式（15）、式（16）移除若干受灾点。

式中，为将cij标准化后的值，范围在区间[0，1]；cij为i与j之间的距离；vij表示i与j是否在同一条路径上，如果在同一条路径上则为0，否则为1。由式（15）可知，两个受灾点相互之间的距离越近，则R(i，j)越大；两个受灾点如果位于同一路径上，则R(i，j)最大。

破坏算子的伪代码见表1。

表1 破坏算子伪代码

修复算子：修复算子的伪代码见表2。

表2 修复算子伪代码

（8）终止条件。达到最大迭代次数MAXGEN时，停止迭代，输出问题的最优解。

5 算例分析

5.1 算例说明

本文引用文献[13]中应急物流路径问题的分布数据，见表3、表4。存在3个配送中心与20个受灾点，各节点的位置信息已知，各节点之间的距离通过平面坐标的欧氏距离简化表示。混合遗传算法的参数设置见表5。

表3 配送中心相关数据

表4 受灾点相关数据

表5 参数表

5.2 算法比较

利用MATLAB R2018b编程软件，根据分布数据信息，分别运用遗传算法与混合遗传算法求解基于低碳排放的应急物流车辆路径优化模型。

遗传算法与混合遗传算法的优化过程如图5、图6所示，求解得到的最优配送方案路线如图7所示。

图5 遗传算法的优化过程

图6 混合遗传算法的优化过程

图7 混合遗传算法得到的最优配送方案路线图

遗传算法与混合遗传算法的优化仿真结果对比见表6。

表6 仿真结果

5.3 结果比较

通过对比遗传算法和混合遗传算法的优化过程可知，利用节约算法求初始解，利用大规模邻域搜索算法改进局部搜索操作的混合遗传算法在迭代次数为42 次时达到最优解，而遗传算法在迭代次数为60次时达到最优解，因此本文中的混合遗传算法相较于传统的遗传算法具有更好的收敛性。对比遗传算法与混合遗传算法的优化结果可知，混合遗传算法在运输距离、总成本、碳排放成本上都取得了更好的结果。

6 结语

本文基于低碳绿色的思想，针对灾害发生前提下的应急物流路径优化问题进行研究，以配送车辆的固定成本、运输成本、未满足需求量的惩罚成本以及碳排放成本之和最小为优化目标，构建了基于低碳排放的应急物流车辆路径优化模型，并通过混合遗传算法对模型进行求解。最后利用MATLAB软件分别通过遗传算法与混合遗传算法进行仿真，并对比分析二者的结果。由对比结果可知，混合遗传算法具有更好的收敛性，且在运输距离、总成本、碳排放成本上均获得了更好的结果。因此，基于低碳排放的应急物流车辆路径优化模型具备实用性且混合遗传算法具有较高的求解效率，可为应急物流车辆路径优化问题的应对提供参考。

不过本文对于各受灾点需求量的预测方式过于简单。而在现实生活中，由于次生灾害、信息的滞后性等因素，受灾点的需求量呈现出更大的不确定性，配送车辆在运输过程中的交通条件也存在很多不确定因素，这些因素都会对应急物流车辆路径优化的结果产生影响。因此，未来可更深入研究考虑更多不确定因素的应急物流车辆路径优化问题。