油耗最小化多车型车辆路径问题研究

何小年 彭琼

摘  要： 研究最小化油耗的多车型车辆路径问题，将车辆使用费用分为固定费用和以油耗为主的可变费用。建立了该问题的数学模型，运用禁忌搜索算法进行模型求解。算法采用随机选择车型产生初始解，设计三种Or-opt邻域结构，利用罚函数接受导致不可行解的变换。通过案例测试验证了模型的正确性和算法的有效性。结果表明，采用最小化油耗为目标比最小化距离为目标更加经济和环保。

关键词： 多车型车辆路径问题; 最小化油耗; 禁忌搜索算法; Or-opt算法

中图分类号：TP391          文献标志码：A     文章编号：1006-8228（2019）02-09-04

Research on the multi-type vehicle routing problem with minimizing fuel consumption

He Xiaonian， Peng Qiong

（School of Information and Electrical Engineering， Hunan International Economics University， Changsha， Hunan 410205， China）

Abstract： The Multi-type Vehicles Routing Problem with Minimizing Fuel Consumption （MVRPMFC） is researched; And the use costs of vehicles are divided into the fixed cost and the variable cost arising mainly from fuel consumption. The MVRPMFC is modeled mathematically; and Tabu Search Algorithm （TSA） is used to solve it. According to TSA， the initial solution is generated with the random selection of the vehicle type， three kinds of mixed neighborhood structure are designed for Or-opt， and the penalty function is used to accept the transformation which leads to infeasible solution. The experiment shows the model is correct and the TSA is effective; and minimizing fuel consumption as a goal is more economical and environmentally friendly than minimizing the distance.

Key words： Multi-type Vehicle Routing Problem; minimizing fuel consumption; Tabu Search Algorithm; Or-opt

0 引言

降低燃油消耗，能有效減少汽车尾气排放，同时降低配送成本。本文在经典车辆路径问题（Vehicle Routing Problem，VRP）的基础上，研究最小化油耗的多车型车辆路径问题（Multi-type Vehicle Routing Problem with Minimizing Fuel Consumption， MVRPMFC）。MVRPMFC综合考虑不同型号车辆的配合使用，在安排车辆路径时考虑最小化油耗约束，以配送成本最小化和尽可能降低碳排放为目标。

近年来，国内外在配送的碳排放约束方面的研究并不多。李淑琴等设计模拟退火算法求解了带时间窗的环保多车型车辆路径问题[1];段凤华等人应用基于最佳插入和交换的混合邻域禁忌搜索算法求解带碳排放约束的异型车辆路径问题[2]。葛显龙等研究了考虑碳排放因素的带时间窗的多车型车辆路径模型，设计了混合遗传算法求解[3];李进等提出了考虑车辆运量和速度的能耗计算方法，建立了非满载运输方式下的低碳路径LCRP模型，设计了基于路径划分的禁忌搜索算法RS-TS[4]。

1 MVRPMFC问题描述与数学模型

假定在一个物流网络中，N={0，1，2，…，n}为节点的集合，节点0表示车场，节点1，2，…，n表示客户，Qk：k型车的容量。在车场有容量异型车队K，假定车队规模固定，每辆车只可行驶在一条线路上，每个客户需求为正。问题是在客户需求、车辆容量、车辆固定成本、空载与满载时的油耗既定的情形下，确定车辆配送路线，以最小化固定运输成本，以及可变油耗成本的总成本，其中可变油耗成本与车辆运输量、运输距离和车载率密切相关。

为构建数学模型，做如下符号说明。k：车辆类型，k=1，2，…，Mk表示k型车的数量;qi：客户i的需求量;dij：客户i和j之间的距离，距离矩阵视为对称，即dij=dji;车型为k的车辆m从客户i行驶到客户j，则xijkm=1，否则xijkm=0;客户i的货物由车型为k车辆m服务，则yikm=1，否则yikm=0;pijkm表示车型为k的车辆m从客户o行驶到客户j的实际载重量;Fkm表示车型为k的车辆m的固定使用费用。

因此，MVRPMFC数学模型为：

满足： ⑴

⑵

⑶

⑷

⑸

⑹

目标函数表示运营成本、碳排放交易成本和违反时间窗惩罚成本的总和。约束⑴表示车辆装载能力的限制，约束⑵限制了每种车型数量，约束⑶表示每个客户只由一辆车访问一次，约束⑷表示进入和离开一给定客户点的车辆数相同，约束⑸表示车型为k的车辆m在客户i到j的实载率，约束⑹表示每一辆车都从车场出发，最后都回到车场。

2 求解MVRPMFC的禁忌搜索算法

2.1 初始解

本算法初始解设计为：以随机方式生成客户点的排列，然后再随机从异型车队中选一辆车，在客户点排列中最左端选择一个客户分配给该辆车，如此循环，直至该车不再能完成其后的最左端客户装载任务。随后，又从异型车队中随机选一辆车作为当前车辆，将剩余客户点集中最左边的客户点安排给该车。依次循环，直到所有的客户点都服务完毕。

2.2 邻域结构

本文使用Or-opt方法，Or-opt方法是k-opt中的一种，k-opt通过每次交换条k边来改进初始解。目前都认为3-opt算法是一种比较有效的算法[5]，Or-opt方法是Or提出将一段路径（1个、2个、3个连续的顶点）在另外两个顶点间重新定位，相当于一个受约束的3-opt交换。本文根据Or-opt将一段路径（1个、2个、3个连续的顶点）在另外两个顶点间重新定位，设计了Or-opt-1，Or-opt-2，Or-opt-3三种交换的组合，以随机的方式选择其中一种应用于当前解。下面对可行变换加以说明，其中带下划线者为所挑选的顶点。

在同一线路或不同两条线路中随机挑选两个顶点（客户点或车场），随机的执行下列三种变换之一。

⑴ Or-opt-1，将一段路径1个顶点在另外两个顶点间重新定位，例如：

⑵ Or-opt-2，将一段路径2个顶点在另外两个顶点间重新定位，例如：

⑶ Or-opt-3，将一段路径3个顶点在另外两个顶点间重新定位，例如：

2.3 解的评价

对MVRPMFC类型的车辆调度问题需要优化的目标为运输成本（可变成本和固定成本）。为了充分对解空间进行搜索，算法接受导致不可行解的变换。违反了车辆装载能力限制时，其不可行性的程度可以通过引入一个罚值而将该约束条件包含到目标函数中去进行度量，即。其中K是该解中所使用的车辆数（线路数），T（r）为车辆r的行驶费用，C（r）为在线路r上超出车辆载重量的部分，而p*是惩罚系数。若一个解是可行的，则所有线路上的C（r）都等于零。p*∈[0.0001，10000]，p*开始时等于1，并通过一个自调整参数来加权：每隔10次迭代测试一次，若前面的10个解都是可行的，则将其除以2;若所有的10个解都是不可行的，则将其乘以2。这种机制可以产生一种可行解和不可行解的混合，有利于减少陷入局部最优的可能性[6]。

2.4 禁忌表

禁忌表用于记载最近的5～10（随机挑选）次迭代中解的变换特征。可以构造一组（n+1）×（n+1）阶矩阵来记录禁忌情况。若点i和j被挑选来进行以下三种变换：Or-opt-1，Or-opt-2，Or-opt-3三种交换，则将其禁忌情况存入矩阵的元素（i，j）中。在每一次迭代时，都必须将上一步所进行的变换填入到禁忌表中，而表中的其他元素相应地减1直到等于零为止。

2.5 终止准则

当总迭代步数达到一个给定值，或在给定的连续迭代步数内当前的最好解没有改变时，则终止搜索。

3 算例测试与比较

3.1 算例一

本文提出的禁忌搜索算法已用Delphi编程。为了测试算法的计算效果，采用文献[5]算例，所有车型车辆不受行驶距离限制，要求合理安排配送车辆的配送路线，使完成配送任务的总油耗最少。以距离为优化目标和油耗为优化目标分别利用本文算法对文献[5]进行求解，经过20次运算结果中最优解见表1。

本文以距离为优化目标固定费用为600，可变油耗费用为1112.35，总费用为1712.35;以油耗为优化目标固定费用为620，可变油耗费用为958.27，总费用为1578.27。

表1中结果表明：虽然以距离为优化目标总距离比以油耗为优化目标要短，但是以油耗为优化目标总费用比以距离为优化目标的总费用节约了134.08，节约了7.83%。

3.2 算例二

采用文献[7]的算例，文献[7]中没有考虑车辆的固定成本，本文假设三种车型的固定费用分别为60，100，150。以距离为目标，20次运算结果中取最优解如表2所示。以距离为优化目标，可变油耗成本为11749.21，固定费用为300，总费用为12049.21;以油耗为优化目标结，可变油耗成本为11363.37，固定费用为300，总费用为11663.37。

注：表2中标“☆”文献[7]中两条路径的配送量都超出了3种车型中最大车型的容量的限制。

文献[7]以距离为目标的动态求解的最优线路成本为393.22，线路油耗为9977.7;以油耗为目标的动态求解最优解油耗成本为9070.9，运输总路程为443.3。本文以距离为优化目标线路油耗为11749.21;以油耗为优化目标线路总油耗为11363.37。

结果比较表明：文献[7]结果虽然比本文结果总成本要优，但是以距离为优化目标和以油耗为优化目标两种情况中都有一条线路上的配送量超出车辆装载量的限制。本文所得到的解是可行的，以距离为优化目标虽然距离比以油耗为优化目标的距离要短，但是以油耗为目标比以距离为优化目标线路总油耗节约了3.28%。

4 结论

以随机选择车型、从三种邻域变换中随机选择一种、禁忌长度在一定数值区间随机选取的方式，设计求解MVRPMFC问题的禁忌搜索算法混合邻域变换，并且借助罚函数实现搜索过程中对不可行解的试探，以跳出局部最优点。研究表明，如果针对物流行业开发新的合适的智能配送管理系统，并普及应用，对运输配送业开征碳税，并不会增加行业成本。相反，碳税的开征可促进运输配送领域提升其智能化程度，这不仅可以促进其效率和效益的提升，还可以缓解能源供给压力、实现低碳物流、绿色物流，促进物流业转型升级。

参考文献（References）：

[1] 李淑琴，杨斌，赵磊，易宣齐.需求帶时间窗的环保多车型组合配送路径优化[J].广西大学学报（自然科学版），2003.2：388-394

[2] 段凤华，符卓.带碳排放约束的异型车辆路径问题及其禁忌搜索算法[J].铁道科学与工程学报，2015.12（4）：941-948

[3] 葛显龙，谭柏川，吴宁谦.基于碳交易机制的带时间窗车辆路径问题与算法研究[J].管理工程学报，2018.32（4）：141-148

[4] 李进，傅培华等.低碳环境下的车辆路径问题及禁忌搜索算法研究[J].中国管理科学，2015.23（10）：98-106

[5] 葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2013：125-133

[6] 符卓.开放式车辆路径问题及其应用研究[D].中南大学，2004.

[7] 熊浩，胡列格.多车型动态车辆调度及其遗传算法[J].系统工程，2009.27（10）：21-24