多车型绿色车辆路径问题优化模型

何东东，李引珍

(兰州交通大学 交通运输学院，兰州 730070)(*通信作者电子邮箱liyz01@mail.lzjtu.cn)

0 引言

能源与环境问题已成为全球的热点议题。人类活动产生的二氧化碳(CO2)是温室气体的主要来源，也是气候变化和极端天气出现的主要源头。国际能源署(International Energy Agency, IEA)称，2017年全球能源相关二氧化碳排放量增长1.4%，达到325亿吨的历史最高点。这一增长率相当于增加4.60亿吨的二氧化碳排放量，等同于1.7亿辆汽车的排放量。

另一方面，运输行业不仅是能源消耗较大的产业，而且是碳排放大户，据世界资源学院的统计，交通运输行业的二氧化碳排量占全球总排量的20%。实施绿色运输已经成为减少碳排放的必然趋势。自文献[1]建立了带时间窗且以碳排放和距离为目标的运输车辆综合优化模型，分析了不同交通条件下速度优化对模型的影响之后，文献[2]将碳排放和燃料消耗的最小化作为优化目标，建立EVRP(Emissions Vehicle Routing Problem)的模型和算法，对不同拥堵水平下EVRP的解进行了比较和分析。文献[3]同时考虑经济和环境因素，将二氧化碳排放量、燃料消耗、旅行时间等纳入到车辆路径规划中，从而求得经济环保的车辆路径，提出了污染路径问题(Pollution Routing Problem, PRP)。文献[4-6]对污染路径问题(主要是以二氧化碳排放量和油耗量为目标)的模型和算法进行了拓展和创新研究，并对绿色车辆路径问题进行了评述。文献[7]拟合了一个关于燃料消耗率(Fuel Consumption Rate, FCR)和车辆总重量之间的线性表达式，并提出了考虑FCR的有限容量车辆路径问题(FCR considered Capacitated Vehicle Routing Problem, FCVRP)模型，确定并讨论了导致燃料消耗变化的因素。文献[8]建立购买或销售碳排放权的混合整数规划多车型车辆路径问题模型，采用禁忌算法获得的解表明碳排放量可以显著减少且不用牺牲碳交易所带来的收益。文献[9]将燃料成本、碳排放成本和车辆使用成本纳入传统VRP问题中建立最低碳排放模型，构造RS-TS(Route Splitting Tabu Search)算法，通过数值实验揭示了距离、燃料消耗、行程时间和其他参数之间的关系。文献[10]考虑驾驶员小时成本、燃料成本、客户地理位置、车队组成(单一车型与多车型)，以及取货或者送货等一系列子问题，利用LANTIME禁忌搜索算法对算例求解表明，以不同成本作为求解目标得到不同的车辆路径。近年来国内对此类问题的研究也日益增多，文献[11-20]构建了不同目标函数下的低碳、低油耗、低成本的车辆路径问题模型，并设计了相应的算法进行求解，如禁忌搜索算法、遗传算法、粒子群算法、极线扫描算法，也都取得了很多成果。从以上研究可以看出绿色车辆路径问题成为现阶段研究的热点。

为降低物流配送过程中车辆产生的废气污染，本文提出了带时间窗的多车型绿色车辆路径问题(Green Multi-type Vehicles Routing Problem with Time Windows, G-MVRPTW)模型，且以能耗、碳排放和司机工资最小为目标建立了相应的模型,并设计了改进的禁忌搜索算法求解该问题。通过数值实验验证了所提模型和算法的有效性和可行性，为低碳运输及管理提供决策支持和方法指导。

1 问题的描述

本文研究的G-MVRPTW可描述为：一个配送中心D具有M种类型的车辆，其相应车型的载重量为Qm(m={1,2,…,M})，各种类型的车辆数有km辆。不同类型的车辆从配送中心出发对若干个客户点进行服务，设每个客户点的需求量不超过车辆的载重，即：maxdi≤Qm，每条子路径的客户需求总量不超过车辆载重，车辆完成任务后返回配送中心。求解满足客户需求且以能耗、碳排放和司机工资为总成本最小的情况下，通过模型和算法来寻找环境友好型绿色路径，以达到承运人经济成本和政府环保要求之间的均衡。

2 模型的建立

2.1 能源消耗和碳排放量计算

计算车辆油耗量需要依据多种因素，本文参考文献[21-24]不断通过对比分析研究取得的综合油耗率模型，并结合文献[3]的研究：当车辆速度v<40 km/h时，发动机系统决定了燃油消耗量；当车辆速度v≥40 km/h时，车辆牵引功率Pt决定了燃油消耗量。因此本文假定车辆在距离为Dij的弧(i,j)上以运行速度vij≥40 km/h为客户进行配送，则在弧(i,j)上燃料的消耗量Fij的近似计算式为：

Fij≈Pt(Dij/vij)/q≈

(1)

研究表明，车辆的碳排放量与油耗量成正比，则弧(i,j)上的CO2的排放量为：

Eij=ε×Fij

(2)

上述模型式(1)～(2)中使用的具体参数及取值如表1所示。

表1 模型式(1)、(2)参数Tab.1 Parameters of model formula (1) and (2)

2.2 数学模型

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

∀i,j∈V0,m∈M,C是一个很大的正整数

(11)

ei≤ti≤li;∀i∈V0

(12)

(13)

(14)

∀i,j∈V且i≠j,m∈M

(15)

模型说明：式(3)是只考虑总里程最小的传统车辆路径的目标函数；式(4)是本文G-MVRPTW模型的目标函数；约束条件式(5)～(6)表示每个客户只被一辆车访问一次；式(7)表示车辆从车场出发完成任务最后回到车场；式(8)为节点平衡方程；式(9)表示每个客户的需求被满足；式(10)为送货时车辆载重约束；式(11)～(12)为时间窗约束；式(13)为消除子回路约束；式(14)～(15)分别是决策变量和非负约束。

3 算法设计

多车型绿色车辆路径问题是VRP的子问题，而VRP为非确定性多项式(Non-deterministic Polynomial, NP)难问题。考虑到所求解问题的NP特性及其规模，精确算法(分枝定界法、割平面法等)无法避开指数爆炸问题，只能求解小规模VRP问题，难以求得最优解[25]；而模拟退火、禁忌搜索、遗传算法、蚁群算法和神经网络等通用启发式算法已被用于求解VRP问题，也取得了很好的效果。文献[26-27]较为全面的综述和分析表明，禁忌搜索是求解VRP及其变型问题的有效算法，因此，本文设计了改进的禁忌搜索算法求解G-MVRPTW模型。

3.1 初始解

根据客户点时间窗的最迟开始服务时间li的大小，对客户编号进行升序排序；如果最迟开始服务时间相同，则比较li-ei的大小，较小的排在前面，如得到客户以1～9顺序排列。对于车辆的分配，由于maxdi≤Qm，且研究表明：多用一辆车所带来的固定费用总是超过其因总行驶距离缩短或速度优化等所带来的节省，所以首先使用大容量的车进行装载，当该车辆的声誉装载量无法满足下一个客户需求时，将此时的装载容量∑di与次大型车的车容量Qm进行比较，如果∑di≤Qm，则换到次大型车，同时次大型车还可以继续向下作类似比较；否则，采用原大容量车型；从而达到选取最适合车辆，使得装载率最高，提高车辆使用率。当某种车型的车辆使用数超过车辆拥有数时，选取下一种车型，直到所选有客户点被分配。根据上述方法，将客户1分配给第1辆车，可得第1辆车的配送路径0-1-0，并判断添加客户2到第1辆车能否满足约束条件，若满足则配送路径为0-1-2-0；否则将客户2分配给第2辆车，得到第1、2辆车的配送路径为0-1-0-2-0。依此类推，直到所有客户均都被分配，从而得到一个初始可行解0-1-2-6-0-3-5-8-0-4-7-9-0。

3.2 邻域结构

解的质量和算法的搜索速度很大程度上依赖于邻域结构的设计，本文根据编码的特点设计了3种邻域结构：

1)插入算子Insertion。随机从子路径A选取一个点插入到子路径B中，生成邻域解，但是在插入到B时，必须使得子路径的客户号序列是递增的，这样可以保证访问顺序满足最迟开始服务时间li的约束。如0-1-2-6-0-3-5-8-0-4-7-9-0第2条子路径中的客户5，插入子路径1的可能位置为012560，而051260则不满足最迟开始服务时间的约束。随后评估所有的可能性后选择向当前迭代最优的方向进行移动。在下面算子中，同样需要遵循子路径内客户序号递增规则。

2)交换算子Swap。随机选取两条路径中的两点进行交换插入生成邻域解。

3)混合算子Hybrid。在一次迭代中随机选择算子1)或者2)。

3.3 解的评价

本文算法利用带有惩罚机制的解的评价将算法设计为可接受导致不可行解的变换，产生可行解和不可行解的混合，以便通过不可行解的过渡，对邻域空间进行充分搜索，找到更好的可行解，避免过早陷入局部最优。因此，解的评价参考文献[28-29]，改进为：

(16)

其中：P1、P2只表示每个目标的优先级，即P1≫P2，是定性的概念，不赋予任何具体数值；K是最少子路径数(即最小车辆数)；Z(r)、E(r)分别是子路径r上的总费用值和超出载重部分；p为每条不可行路径的惩罚权重。若一个解是可行的，则E(r)=0。p∈[50，2 000]，开始时等于200，并通过一个自调整参数来加权，每隔10次迭代测试一次。若前面的10个解是可行的，则将其除以2；若所有的10个解都是不可行的，则将其乘以2。这种机制由文献[30]提出，可以产生一种可行解和不可行解的混合，有利于减少早熟的可能性。

3.4 禁忌表

禁忌表主要由禁忌对象和禁忌长度组成。本文构造了一个N×N的矩阵作为禁忌表，以记录禁忌对象的禁忌情况。如果进行了3.2节中1)～3)操作，则将被操作客户点i和j的禁忌情况存入矩阵的元素(i,j)中，禁忌长度采用文献[30]的随机禁忌长度，取值为[lmin,lmax]的随机整数。

4 数值实验结果及分析

4.1 实验设置

本文算例的测试数据采用随机生成，客户需求量是区间[1，9]内随机产生的整数(吨)，客户信息见表2，其中，设定客户点0为配送中心。

表2 客户信息表Tab.2 The information of customers

客户之间的距离矩阵D是[2，26]的随机整数(km)，见表3；每两个客户点之间的速度矩阵V为[12，23]的随机整数(m/s)见表4；车辆类型及相关参数见表5。表3～4中，D和V都是对角矩阵。

表3 客户间距离矩阵 kmTab.3 Distance matrix between customers km

表4 客户间速度矩阵 m/sTab.4 Speed matrix between customers m/s

表5 不同车辆类型相关参数Tab.5 Relative parameters of different types of vehicles

4.2 模型的计算结果及分析

4.2.1 算法性能分析

针对改进的禁忌搜索算法的性能，本文以模型的总成本最小为优化目标，通过Java编程，用本文改进的禁忌搜索算法和传统禁忌搜索算法进行数值实验，分别运行10次，实验统计结果如表6所示。表6中，平均偏差=(平均解-最优解)/最优解，最大偏差=(最劣解-最优解)/最优解。分别记录某一次传统禁忌搜索算法和改进的禁忌搜索算法求得最优解时的解的变化如图1所示。由表6和图1可知，改进的禁忌搜索算法能在很短的时间得到最优解，并表现出明显的优势，收敛性能也有所提升，验证了改进算法的可行性和有效性。

图1 不同算法收敛效果示意图Fig.1 Schematic diagram of convergence effects for different algorithms表6 不同算法求解数值实验统计结果Tab.6 Statistical results of different algorithms for solving numerical experiments

算法最优解平均解平均偏差/%最大偏差/%未得到最优解个数平均计算时间/s传统禁忌搜索算法755.633784.8773.8719.99413.170改进的禁忌搜索算法755.633778.9323.0811.2728.122

4.2.2 结果分析

采用禁忌搜索算法分别求解以最小走行距离、最小油耗和碳、最小司机工资(即为最短服务时间，由模型可以看出司机成本与旅行总时间有关，旅行总时间=司机工资/单位时间司机工资)、最小总成本为优化目标，得到的路径安排如表7所示。

由表7可得：作为不同的运输参与者可以选用不同的路径方案。如：从政府节能减排的角度出发，则S2最小油耗和碳排放是政府的最佳选择；对于承运人追求的就是总成本最小，则S4最小总费用是承运人的最佳选择。如若涉及物流外包的情况，则对于物流提供方，S1最短走行距离或者S3 最短服务时间便是其最佳选择，因为物流提供方希望租出去的车辆走行越短的距离并且用尽量短的时间完成运输任务，这样可以再为下一个有运输需求的客户服务，获得更大的收益。

表7 不同目标最小化算得的车辆路径方案明细Tab.7 Details of vehicle routing schemes with minimization of different targets

同时可以看出：司机成本占总成本约60%，因此本文在算法构建时尽量减少车辆数的使用的做法是正确的，同时验证了多用一辆车所带来的费用总是超过其因总行驶距离缩短或者速度优化等所带来的节省。另一方面，油耗和碳的成本占总成本的40%左右，而二氧化碳成本占比非常不明显，大约在3%(40%×0.5/(6.5+0.5)≈2.86%)，并且本文设定的二氧化碳排放成本是190 元/吨，大大高于目前50～60 元/吨的碳价；同时也说明了作为发展中国家，国家鼓励产业发展，因此不能制定太高的碳价，因此碳价普遍偏低，目前的碳价不会显著影响企业的物流运输安排，因此很少有运输企业在运营过程中考虑环保因素。但是为了有效控制温室气体排放，推进绿色低碳转型发展，参与和引领全球气候治理，政府可以适当调高碳价，让碳成本在总成本中占比提高，从而让运输企业将碳排放成本考虑到总的运输成本中去，才能有效地让运输行业减少二氧化碳的排放。从更长远的情况来看，政府将来一定会加大节能减排的管控，则对于运输行业来讲，新能源车辆投入运输市场进行配送将是新的趋势。

分析由表7各项指标得到的结果，得出以下结论：

1)路径最短的不一定能耗越小。

考虑以走行距离为目标的车辆路径安排S1比以低碳为目标S2的路径总长减少了约14.9%，但是能耗和碳的成本却增加了约13.3%，类似的可以对比S4。走行距离减少了但油耗和碳成本却增加的原因在于油耗和碳成本不仅与走行距离有关，还与载重量、行驶速度有关。

2)吨公里数更能反映油耗和碳成本。

S1的第5条子路径(简称S15，下同)和S36采用同型车，装载率、平均速度大致相同(18.96 m/s、18.68 m/s)的情况下，S36的旅行距离是S15的88/42=2.1倍，但是二氧化碳和油耗的成本却是92.626 9/58.345 3=1.6倍，则偏差率ξ=|1.6-2.1|/1.6=31.3%，相差较大，所以用走行距离来衡量油耗和碳成本存在很大的偏差。本文引入吨公里数这个指标，得到S36与S15的吨公里数相比为2 419/1 564=1.55，则偏差率ξ=1.6-1.55|/1.6=3.1%，更加接近油耗和碳成本的比值，这时的偏差可认为是速度平方的差引起的。因此引入吨公里数这个指标更能反映油耗和碳成本。

3)优化运输组织，提高车辆的利用率。

注意到S13、S32、S43的司机工资所占总成本的比例非常高，分别为88.99%、90.8%、91.59%，而油耗和二氧化碳则仅仅为10%左右，其主要原因是车辆的装载率较低，且同时服务的客户数比较少，则从承运人节省运输成本及优化运输组织出发，可以提前制定运输计划，如三天为一个时段集中配送，尽量减少单车单客运输或单车少客运输，提高车辆的利用率；同时，对于不可避免的单客户，如果载重量允许，则尽量选择小型车辆配送，因为调整与车型相关的参数βm和自重wm可减少成本。

4)车型的影响。

为了说明单车型和多车型的区别，本文采用最小总成本为目标得到3种单一车型的对比结果，如表8所示。

表8 不同单一车型的结果对比Tab.8 Result comparison of different single type of vehicles

由表8可知：采用单一车型B时，得到802.883 5元的最低总成本。若从油耗和碳角度考虑，A型车的吨公里数比B少21.1%，比C少55.2%，以及车型的影响，导致A型车油耗和碳成本较B、C两类车分别低5.3%和48.4%，因此应选用载重量较小的A型车进行配送，但此时的车辆使用数最多，总成本比B高6.2%。若从最短走行距离和最短旅行总时间(旅行总时间=司机工资/单位时间司机工资)考虑，C型车的走行距离分别比A、B两类车少26.0%和8.1%，C型车的旅行总时间分别比A、B两类车少10.0%和0.08%，因此应选择载重量大的C型车进行运输，但此时的油耗和碳成本较高，总成本也比B高19.5%。综上对A型车和C型车的分析，则很容易理解采用B型车时得到总成本最低，因为B型车属于中型车，同时继承了A和C的优势，因此总成本是单一车型中最低的。另一方面，对比表7可知,采用单一车型的总成本普遍比采用混合车型的高，因此可以得出：运输企业采用混合车型进行运输比采用单一车型运输更加节约成本。

5 结语

本文以VRPTW为基本模型，引入了基于载重、速度、距离的碳排放计算方法，建立了G-MVRPTW模型，然后设计了改进的禁忌搜索算法。数值实验验证了所提模型和算法对于带时间窗的城市绿色多车型车辆路径安排的可行性和有效性，可以得出如下结论：

1)以模型的综合成本最小为目标与传统的以走行距离、旅行时间为目标得到的路径安排有所不同，虽然以综合成本最小为目标将导致走行距离增加或者旅行总时间增加，但是不会增加运输企业的经济负担，即此时的总成本仍然是最小的。

2)目前我国的碳价较低，当前的碳交易机制不会显著影响运输企业的车辆路径安排，因此政府需要适当调高碳价才能在运输行业有效地实现节能减排；在将来，新能源车投入运输市场将是新的趋势。

3)吨公里数更能反映油耗和碳排放成本。

4)优化运输组织，提高车辆的利用率。尽量减少单车单客运输或单车少客运输，或者是选用轻型车进行单客户配送。

5)运输企业采用混合车型进行运输比采用单一车型运输更加节约成本。

本文只研究了闭合式车辆路径问题，虽然文中也提到物流外包，但并没有研究开放式车辆路径问题(OVRP)，由于OVRP的车辆不需要返回配送中心；同时对于取货的OVRP，车辆也不需要统一从配送中心出发，则可以减少更多的油耗和碳成本，也将更加节约运输时间，所以研究开放式绿色车辆路径问题将是下一步研究的内容。