环境与成本兼顾视角下的多车型HFGVRPTW 研究

王 莉 （湖南工商大学 智能工程与智能制造学院，湖南 长沙 410205）

0 引 言

近年来，对绿色车辆路径选择问题（Green Vehicle Routing Problem，GVRP）的研究因其对环境和社会的有利影响而日益受到重视。世界能源理事会报告指出，全球运输部门的主要能源是石油产品，特别是汽油、柴油、燃料油和喷气燃料，其排放的二氧化碳总量在2010—2050年期间将从16%上升至79%，而排放量增加与车辆移动量及燃油消耗量有直接联系，并且在大多数情况下与车辆移动量成正比。因此减少车辆运输过程中的车辆数、油耗量和碳排放量对未来全球环境的改善具有深远影响。

郭红霞等[1]以网络运营成本最低为优化目标，建立了网络条件下公路港多车型甩挂调度优化模型，并设计了基于动态规划法、节约里程法和改进模拟退火算法的两阶段启发式算法对模型求解。何小年等[2]将车辆使用费用分为固定费用和以油耗为主的可变费用，构建了以最小化油耗为目标的多车型车辆路径问题模型，然后运用禁忌搜索算法对其进行求解。路世昌等[3]以碳排放最小化为优化目标，设计了两阶段启发式算法进行求解。赵志学等[4]以油耗碳排放成本最低为优化目标，设计了一种融合模拟退火算法的混合差分进化算法求解。赵静等[5]以物流配送总成本为目标函数，采用改进粒子群算法求解。程元栋等[6]以冷链配送总成本最低为目标建立数学函数模型，并采用改进的遗传算法求解。

梳理国内外文献可知，诸多学者从不同角度对GVRP进行了探索，并形成了日益丰富的研究成果，但是以下方面仍需进行深入研究：已有文献中很少同时考虑多车型和时间窗，这与货物配送的实际情况不符。配送中心通常配备有多种车型，且服务的客户多集中在城市，这些客户对货物送达时间有要求。已有研究虽然考虑了总成本最小化，但也只是将油耗量或碳排放量转化为了经济成本，而较少关注环境本身的影响，不利于节能减排。为此，针对上述问题，本文提出了车辆油耗量与配送成本最小化的双目标优化模型，并采用动态规划算法结合遗传算法的混合启发式算法求解，解决了多车型带时间窗绿色物流的车辆分配和物资配送问题。

1 问题描述及定义

1.1 问题描述

本文研究的问题可描述为：某配送中心拥有多种不同车型的配送车辆，要求在时间窗和车辆资源有限的条件下，设计科学合理的配送计划，使车辆油耗量和总成本最低。

本文中定义模型的假设条件有：配送中心每种车型的车辆数有限；配送中心无容量约束；配送中心与客户点、客户点之间的距离已知，且车辆的行驶速度不变，为车辆的油耗最优速度；每辆车只执行1次配送任务，可以在不同时刻出发，完成任务后即回到配送中心；每位客户只能访问一次且只能被一辆车访问；每位客户的货物量不超过车辆最大容量；考虑的时间为运输时间、车辆服务时间和车辆等待时间，物资装卸载时间不予考虑。

1.2 符号与变量定义

符号：G=（V，A）为配送网络。V表示节点集，V={p|p=0，1，...，P}，其中0表示配送中心，v′=v{0}表示客户集合。qi为客户i（i∈V′）的货物量。A为连接顶点的弧集，A={（i，j）|i，j∈A，i≠j}，dij为路段Aij的距离。U为配送车型集合，U={u|u=1，...，M}，Qu为车型u的额定容量，μu为车型u的净重，Zu为车型u的车辆数。SQ为所有车型额定容量集合。Qmax=max{Q1，Q2，...，QTY}表示所有车型的最大容量。Ku={k|k=1，...，Zu}为车型u的配送车辆集合，总车辆集合为K={K1，K2，...，KM}。lukij表示车型u的第k辆车在路段Aij上的载重，vf表示车辆的油耗最优速度。sti为客户i的服务时间，[Bi，Ei]为客户i的服务时间窗。saik为车辆k到达客户i的时间，sbik为车辆k到达客户i的等待时间，如果saik＜Bi，那么sbik=Bi-saik；否则sbik=0。scik为车辆k离开客户i的时间。Ff表示总油耗，fukij为车型u的第k辆车在路段Aij上的油耗量。UC表示总成本。Pu为车型u的车辆固定发车成本，Ru为车型u的车辆单位时间租用费用，Wu为车型u车辆单位时间的人力成本，ccik为车辆k在路段Aij上的惩罚成本。

ζ表示燃油空气质量比，K表示典型柴油的热值（kJ/g），N表示发动机排量（升），V发动机转速（rev/s），ψ为换算系数（g/L），ε表示车辆传动效率，ω表示柴油机效率参数，g为重力加速度（m/s2），θ为道路坡度，Cr表示滚动阻力系数，Cd表示空气阻力系数，As为车辆锋面面积（m2），ρ为空气密度（kg/m3）。

决策变量：xuk为0—1变量，当车型u的第k辆车被使用时该值为1，否则为0。yij为0—1变量，若路段Aij被配送车辆访问，该值为1，否则为0。zik为0—1变量，客户i由车辆k服务时该值为1，否则为0。

2 模型构建

根据油耗计算相关理论，油耗会受多种因素共同影响，其中速度和载重是影响油耗的两个最重要的因素。Barth等人在2005年提出了综合模式排放CMEM模型。指出车型为u的第k辆车在路段Aij上的油耗量为：

式（2）为目标函数1，表示车辆配送过程中最小的油耗量。式（3）为目标函数2，表示车辆最低的配送总成本最低。式（4）表示每种型号的每辆车只能服务每位客户一次。式（5）表示每种型号的每辆车最多只能使用一次。式（6）表示所有从配送中心出发的车辆最都要返回配送中心。式（7）表示配送车辆只能从客户点的一个方向往另一个方向单向行驶。式（8）与（9）表示客户时间窗约束。式（10）表示车辆离开客户的时间为到达客户的时间、等待时间、服务时间的总和。式（11）表示车辆到达下个客户点的时间为车辆离开上个客户点的时间与该车辆在两客户点之间的路段上行驶时间的总和。式（12）—式（14）表示车辆容量约束。式（15）表示变量的取值约束。

3 算法设计

本文研究的HFGVRPTW是一个多目标优化问题，属于NP-hard问题。传统求解多目标优化问题的方法主要包括两种：一种是将多个目标转化为单一目标，再分别进行优化，求解速度快；另一种是将多目标优化问题作为整体进行求解，以期得到更优解。本文基于第二种方法，设计了一种动态规划算法结合遗传算法的混合启发式算法来求解上述模型。

3.1 参数初始化及适应度函数

3.1.1 参数初始化

设定配送中心地址坐标DZ、客户点数量CN、客户点坐标CD、车型数量TY、车型集合U、车型额定容量集合SQ、动态规划算法最大循环次数N、遗传算法最大循环次数Gen_max、交叉概率pc、变异概率pm、以及CMEM计算模型中ζ、K、N、V、ψ、ε、ω、g、θ、Cr、Cd、As、ρ的初始值。令当前遗传算法的循环次数itre=1。

3.1.2 适应度函数

本文采用加权法对目标函数O1和O2进行处理，并将其作为适应度函数。定义λ1和λ2分别为目标函数O1和目标函数O2的权重，λ1+λ2=1，如此一来，原本的多目标问题就转变成了单目标问题，即：

3.2 种群编码及种群结构调整

3.2.1 种群编码

种群中每一条染色体上都包含若干子串。子串1为自然数编码，长度为m×n×p，其数值表示m车型的n辆车配送p个客户点的情况；子串2为实数编码，长度为m×n×p，其数值表示车辆n运输物资到客户点j的时间。因此，染色体的总长度为2×m×n×p。

3.2.2 种群结构调整

随机产生的染色体可能会导致客户的需求量超过车辆最大载重量或车辆到达时间超过时间窗的情况发生，产生非法解，因此需对种群结构进行调整，具体过程可参照2.4。

3.3 适应度计算

为评价模型种群中个体的优劣性，根据式（16）对每个染色体的适应度进行计算，适应度最大的染色体为最优染色体，其中的个体为最佳个体。

3.4 遗传操作

为了保证算法具有较强的全局搜索性、较高的搜索精度和较快的收敛速率，本文采用遗传算法进一步优化动态规划算法的全局最优解。选择操作采用精英选择，交叉操作采用顺序交叉法，变异操作采用逆转变异法。

3.5 算法结束

用进化代数，记录当前染色体和个体。如果满足要求，则终止算法输出最优结果；否则返回3.2继续运行。

4 算例仿真分析

4.1 参数设置

算例采用Solomon数据库中的C103算例作为本文的测试数据，其中各算例都有100位客户与一个配送中心。将配送中心坐标设为（40,50）。拥有2种配送车辆，其最大车辆数、净重、额定容量、运营成本、租车费用和人力成本的具体情况如表1所示。两种车型的行驶速度均为50 km/h，惩罚成本均为10元/分，车辆在客户点的服务时间为10分钟。油耗量CMEM计算模型中各典型参数值如表2所示。

表1 车辆数据

表2 CMEM 模型的典型参数

为了求解测试算例，本文设计的混合式启发式算法在Windows7、CPU为1.90 GHz、内存为4G的微机上采用Matlab R2014a编程来实现。算法参数设置如下：N=50，gen_max=500，pc=0.9，pm=0.01，λ1=0.8，λ2=0.2。

4.2 算例仿真结果分析

4.2.1 车型分配及车辆行驶路径结果分析

将算法运行10次，平均运行时间为201.8s，说明该算法的收敛性较好，能满足物流管理工作的时间需要。车辆分配方案与计算结果如表3所示。

由表4可知：a.并未将所有车辆完全使用，只使用了7辆3.5吨的车，5.5吨的车也只使用了6辆，原因是3.5吨车辆的油耗量和车辆使用成本等都低于5.5吨车辆，而在本算例中客户点需求量都比较接近，因此优先安排3.5吨车辆进行配送；b.不同车型车辆配送的客户点数量没有较大差别，100个客户点中由3.5吨车辆和5.5吨车辆分别配送其中的50个客户点。原因是客户点的需求量都不是很大，时间窗比较接近，应尽可能由同一种车辆完成配送。但是在本算例中3.5吨车辆的油耗量和车辆使用成本等都低于5.5吨车辆，因此在油耗量和成本均为最小化的双目标下，通过减少使用载重5.5吨的车辆数来降低配送中产生的油耗量和总成本。

表4 车辆分配及配送路线决策结果

4.2.2 不同最大车辆数约束条件下的车型分配及车辆路径规划

为了比较最大车辆数约束对HFGVRPTW的影响，本文通过设置不同的最大车辆数对净重为3.5吨和5.5吨的两种车型进行仿真实验，计算结果见表4，适应度值变化情况如图1所示。

图1 不同最大车辆数约束条件下的适应度值

由表4和图1可知，最大车辆数约束条件对不同车型的油耗量和总成本有显著影响。当最大车辆数为10、15时，所有车辆都投入使用，意味着每辆车的行驶距离和行驶时间会延长，油耗量和总成本也会增大；当最大车辆数为20、25和30时，虽然并未使用所有车辆，但是由于每辆车配送的客户数减少，投入使用的车辆反而增多，同样导致产生的油耗量和总成本更大；车辆使用率对油耗量和总成本有显著影响。最大车辆数为20时，车辆使用率仅为65%，产生的油耗量和总成本明显低于车辆数最大时的结果。因此在车辆数充足的前提下降低车辆使用率可有效减少油耗量和总成本；在不同的最大车辆数约束条件下，不同车型车辆配送的客户点数量无较大差别，原因是载重3.5吨车辆的油耗量和车辆使用成本等都低于载重5.5吨的重型车，因此优先使用载重3.5吨车辆进行配送。

5 结 论

为降低物流配送成本、满足绿色物流的配送需求，本文构建了异构车型带时间窗的HFGVRPTW数学模型，并设计了动态规划算法结合遗传算法的混合启发式算法进行求解。实验结果表明相对于单车型车辆，选择多车型进行配送，其油耗量和配送成本都会降低，更有利于绿色物流配送；当客户点的需求量和时间窗比较接近时，在车辆数充足的前提下，降低车辆利用率可有效降低油耗量和总成本；如果只考虑环境目标，会导致总配送成本增加；而如果只考虑经济目标，会导致环境进一步恶化。因此实现节能减排需要综合考虑环境目标与经济目标。