低油耗多车型车辆路径问题及算法

仝凌云 王琳

摘要 为了解决以低油耗为优化目标的具有固定车辆数的多车型车辆路径问题，从低碳环保角度出发，建立以固定发车费用和油耗费用为优化目标的数学模型，并提出了一种融合邻域搜索算法的混合模拟退火算法，解决了传统模拟退火算法全局搜索能力差的缺点。模型中的油耗费用考虑了车辆车载率和行驶里程，算法中客户采用自然数编码方式，首先采用前向插入算法产生初始解；然后在解变换过程中融合了3种邻域搜索算子即互换、逆转、插入操作生成新解；最后通过实例对算法性能进行测试。通过与其他算法的计算结果对比验证了模型的实用性与算法的有效性。

关 键 词 车辆路径问题；多车型；低油耗；模拟退火算法；邻域搜索算法

中圖分类号 TP301.6 文献标志码 A

0 引言

2015年4月环保部发布的源解析结果表明机动车已成为天津市第二大气污染来源[1]；世界经济合作组织（Organization for Economic Co-operation and Development， OECD）在 2003 年《配送：21 世纪城市货运的挑战》报告中指出：货车对美国、日本等国家主要城市造成的城市污染占总量的40%～60%，但货物运输仅占城市交通总量的10%～15%；2014 年我国快递业务量达到 140 亿件，同比增长52%[2]。因此，本文在研究城市配送车辆路径规划问题时改变传统的对车辆行驶距离最短的研究，而使用车辆的油耗费用和固定费用作为优化目标，希望可以实现降低能源消耗和减少空气污染的目标。

自1959年Dantzig和Ramser初次研究车辆路径问题（VRP）[3]，多年来，学者们对VRP的多种变形问题进行了研究，研究结果大多集中在单车型的研究[4-6]。然而在生活中运输公司有多种车型，且车辆数一定。因而研究具有固定车辆数的多车型VRP（Heterogeneous Fixed Fleet Vehicle Routing Problem， HFFVRP）更贴近现实情形。目前，对于HFFVRP的研究成果比较少，马建华等[7]用变异蚁群算法实现了以最快完成作为最优目标的多车场多车型VRP；潘雯雯等[8] 建立需求可拆分的多车型车辆路径问题混合整数规划模型，并以路径优化和路径改进相结合的两阶段算法求解；Subramanian 等[9]提出自适应记忆规划求解多车型VRP；Taillard[10]提出了一种列产生启发式算法求解具有固定车辆数的多车型车辆路径问题。

这些文献虽然比单车型更符合实际，但是在研究中仅仅以旅行最短时间或者最短距离为最优化目标，欠缺考虑车辆调度对油耗的影响，可能会给物流企业造成财产损失，也不符合国内节能减排的大趋势。

一些学者意识到车辆运输对环境的影响[11]，开始把目标转向以最小油耗、最少碳排放为目标的车辆路径问题。葛显龙等[12]构建了以车辆固定费用和油耗费用最小为优化目标的数学模型，并用量子遗传算法求解；李进等[13]运用禁忌搜索算法求解了以油耗和碳排放费用为最小的车辆路径问题，并证实求解结果相比以往的车辆调度更加经济与环保；李长征等[14] 建立了碳排量最小的车辆路径优化模型，并用改进的遗传算法求解，取得了较好的结果；Abdullah-Konak等[15] 开发了一个精确的动态规划算法来确定碳排放最少的车辆路径。

综合分析现有文献在研究问题方面有以下不足之处：1）配送中心大多由混合车辆组成，不同的车辆类型其车辆固定成本和油耗必定不同，但目前大多研究仅考虑单一车型；2）计算油耗时忽略了车辆载重对油耗的影响。

随着HFFVRP的研究成果不断增长，其求解方法也层出不穷。作为典型的NP-hard难题，目前大多数研究者把精力放在怎样构造高质量的求解算法上，如遗传算法[16]、蚁群算法[17]、分支定界算法[18-20]及禁忌搜索算法[21]等，且均取得了一些较好的效果。其中模拟退火算法（Simulated Annealing，SA）思想最早是由Metropolis等提出的，因为同时具备较强的鲁棒性、隐含并行性及通用性[22]等优点深受研究者的青睐。钱晓明等[23] 采用禁忌搜索中的禁忌表对模拟退火算法进行改进；Atiye Ghorbani等[24]将帝国主义竞争算法与模拟退火算法结合求解车辆路径问题。王超等[25]设计的并行模拟退火算法用于求解同时送取货和带时间窗的车辆路径问题，求解30个大规模算例的结果可以作为该类问题的新基准；Yu等[26]在传统模拟退火算法基础上融合3种局部搜索算法用来求解选址-路径问题。尽管如此，模拟退火算法仍然有求解问题规模有限、算法运行时间长等缺点，所以本文对算法做进一步改进，在算法解变换产生新解的过程中融合了3种邻域搜索算法（交叉、变异、逆转操作），增加了算法中解的多样性，加快收敛。

本文研究配送中心采用固定车辆数的多种车型，以车辆使用的油耗费用和固定费用之和最小为目标的车辆路径问题。为了解决上述车辆路径问题，本文首先引入了油耗的计算方法，构建了以油耗和固定发车费用之和为优化目标的数学模型；而后设计了融合3种邻域搜索算法的混合模拟退火算法求解该问题；最后通过与禁忌搜索算法、遗传算法和量子遗传算法对比验证本算法的有效性和可行性。

1 问题描述

本文研究了单一配送中心调派多种车型的车辆对若干个客户派送商品，每一个顾客的位置和商品需求量已知，每一次派送都需要从配送中心发车，完工后返回配送中心。目标是在油耗及车辆固定费用的情况下，找出满足客户货物需求的总运输费用最小的路径安排。配送过程中，采用具有车辆数限制的最优的车辆类型。约束为：所有车辆在行驶过程中不能超载；每一个顾客都被服务且只能被一辆车服务一次；配送中心有多种车型且每种车型数量有限。

符号与决策变量为：1）[G=V，A]为配送网络；2）[V]为节点集，[V=0，1，2，…， N]，其中0表示配送中心，[1，2，…，N]表示客户；3）[A]为弧集，[A=][（i，j）|i，j∈V，i≠j]；4）[dij]为弧[i，j]的距离；5）[M]表示配送中心的车辆类型数，以[m][m∈M]表示具体车辆类型；6）[Qm]为车型[m]的容量，[m=1， 2， …， M] ；7）[nm]为车型[m]的数量；8）[Fkm]为车型[m]、车辆[k]发车的固定成本，[k∈（1，nm）]；9）[pmijk]表示车型为[m]的车辆[k]在段弧[（i，j）]上车辆的实载率；10）[qmijk]表示车型为[m]的车辆[k]在段弧[（i，j）]上车辆的装载量；11）[qi]为节点[i]的需求量；12）[xmijk]为0或1变量，[xmijk=1]表示车型为[m]的车辆[k]经过弧[（i，j）]，否则为0。

2 模型建立

2.1 车辆油耗的计算

影响车辆油耗的因素十分复杂，一般将影响因素分为3大类：车辆因素、环境因素、人为因素[27]，具体因素如表1 所示。本文研究的是多车型车辆路径问题，侧重不同车型的载重对油耗的影响。油耗可以通过车辆实载率和行驶里程求得。车辆的碳排放量与油耗量成正比，耗油量大的车辆通常排放更多的碳，通常1 L燃油（汽油）会产生2.32 kg的CO2[28]。实载率[pmijk]有效反映车辆在运输过程中是否被有效利用，主要考虑车辆的容量与在弧[（i，j）]上的装载量两个方面，第[m]种车型车辆[k]在弧[（i，j）]的实载率为：[pmijk=qmijkQm]。假设车辆的油耗正比于运输量，[em1]是[m]车型空载时的单位距离油耗成本，[em2]是满载时的油耗成本，弧[（i，j）]运输距离中第[m]种车型车辆[k]油耗成本为：[emijk=em1+pmijkem2-em1]，若运输距离为[dij]，则该车在弧[（i，j）]上运输的总油耗成本为：[Cmijk=dijem1+pmijkem2-em1][12]。

2.2 模型

本文研究的问题为具有固定车辆数的多种车型，每种车型具有不同的油耗费用和固定费用。因此在优化整个配送网络时，还需要选择具有车辆数限制的合适的车辆类型，以尽可能减少油耗和车辆的固定费用之和。低油耗多车型车辆路径问题模型为

[minz=m=1Mk=1nmi=0Nj=0Ndijxmijkem1+pmijkem2-em1+ m=1Mk=1nmj=0NFmkxm0jk ]， （1）

[s.t.]

[pmijk=（j=0Nqjxmijk-i=1j-1qixmijk）Qm ∀i， j]， （2）

[j=1Nk=1nmxm0jk=i=1Nk=1nmxmj0k ∀i，j，k，m]， （3）

[j=0Nk=1nmm=1Mxmijk=1 ∀j，k，m] ， （4）

[i=0Nk=1nmm=1Mxmijk=1 ∀i，k，m]， （5）

[i=1Nqij=0Nxmijk≤Qm ∀i，j，k，m] ， （6）

[j=1Nk=1nmxm0jk≤nm ∀m]， （7）

[xmijk=0，1 ∀i，j，k，m]。 （8）

式（1）为目标函数，表示总费用之和最小，包括油耗费用和固定发车费用；式（2）表示车型为[m]的车辆[k]在客户[i]到客户[j]的实载率；式（3）表示每辆车的配送线路的起点和终点都必须是配送点；式（4）～式（5）表示每个客户都被访问并且保证客户仅被一辆车访问一次；式（6）为每辆车的装载能力约束；式（7）为每种车型的车辆数限制；式（8）为决策变量约束。

3 设计求解算法

模擬退火算法是在初始阶段设置某一初温和降温速率。随着温度参数的持续下降，结合Metropolis抽样过程在解空间随机寻找目标函数全局最优解的一种智能优化算法。其物理退火过程和相应的算法操作与之对应：1）加温过程与算法的设置初温对应；2）等温过程与算法的Metropolis抽样过程对应；3）冷却过程与控制参数的降低对应。但基本的模拟退火算法在求解大规模问题的最优解时运行的时间难以承受。为避免基本模拟退火算法的缺点，本文设计了一种新的混合算法，在模拟退火算法解变换过程中融合了3种邻域搜索算法。邻域搜索算法扩展了当前解的搜索空间，减小了算法陷入局部最优的可能性，提高了算法的稳定性，使得算法能够在较短的时间内求得问题的最优解。下面将分别介绍混合模拟退火算法的实现过程。

3.1 编码

采用自然数编码方式，车辆数[k]已知，配送站用0表示；客户由（1，2，…，[i]，…，[n]）表示。多车型VRP解的编码形式为（0，[i11]，[i12] ，…，[i1s]，0，[i21]，[i22] ，…，[i2t]，0，[ik1]，[ik2] ，…，[ikn]，0）。例如编码（0，1，2，3，0，4，5，0，6，7，8，0，9，10，0）是指由4辆车完成进行10个客户货物配送的路径安排，4条路径分别如下。

路径1：配送站→1→2→3→配送站；

路径 2：配送站→4→5→配送站；

路径 3：配送站→6→7→8→配送站；

路径4：配送站→9→10→配送站。

3.2 改进的模拟退火算法的实现

3.2.1 求初始解

首先设置控制参数：降温速率[q]、初始温度[T0]、结束温度[Tend]和确定每个[T]时内的迭代次数即链长[L]，本文采用多车型前向插入算法[29]生成初始解。具体步骤如下：

步骤1 构造一条从配送中心发车并返回配送中心的初始空路径，对当前路径，选择未被分配路径的顾客插入到空路径中，优先考虑距离配送中心最远的且未分配路径的顾客作为潜在顾客并试探插入当前路径；

步骤2 在路径中随机选择满足车辆容量约束插入点插入；

步骤3 重复步骤2直到当前路径的配送需求超过车辆的配送能力为止；

步骤4 重复步骤1～3直到所有客户都被插入到路径中为止，此时形成一条新路径。

根据文献[13]的结论，小车型（6 t）比大车型（16 t）油耗低，所以在车型的选择上除了满足装载约束，要优先考虑使用小车型。

3.2.2 邻域搜索算法产生新解

为增强算法的搜索能力，本算法采用混合邻域结构，即随机互换、逆转、插入操作对初始解进行邻域搜索。3种操作分别标号为1、2、3，在[1，3]中随机产生整数[α]，则对当前最优解进行操作[α]。下面将简要介绍这些邻域搜索算法。

1）互换操作。互换操作首先随机选择当前路径中的任意两个客户点，然后交换这两个客户点的位置，最后要检测通过互换操作得到的新路径是否满足车辆载重等约束条件，如果满足则新路径产生。互换操作通过改变同一条路径或者不同路径中两个不同客户的位置来降低总费用。具体互换过程如图1所示。

2）逆转操作。逆转操作即2-opt操作，该方法首先通过选择操作选出一条路径中任意两个客户点，然后通过将两客户间所有客户的排列顺序逆转来减少路径总成本。每接受一次2-opt操作，都要根据约束条件重新安排车辆，将新的路径成本与当前最优值比较，假如该路径的成本减少，则改进的路径被保留；否则，保留当前最优值。具体逆转过程如图2所示。

3）插入操作。插入操作首先通过选择操作选择一条路径中任意两个客户点，然后将某一客户点插入到另一客户点后由此产生新路径。这种插入操作可以很好的避免算法早熟的现象，保证最优路径可以迭代到下一次，同时可以使算法更快的向最优解收敛，防止算法陷入局部最优。具体插入过程如图3所示。

3.2.3 解的评价

解的评价关键是惩罚不可行的解。如果某条路径中配送总量超过车辆装载能力[Q]，则该路径方案不可行。该算法设计为暂时不可行解，可行解中夹杂不可行解，以便通过不可行解的过渡，对邻域空间进行充分搜索，找到更优的可行解，避免过早陷入局部最优。首先计算[Xnew]中每辆车的实际装载量[Cu]；然后判断车辆是否超载，[Cv=max（CuQ -1，0）]，若[Cv]非零则车辆超载，并求出[Cv]的平均值[Cvmean]；最后将[βCvmean]与目标函数式（1）一起求最小，其中[β]为惩罚因子。

3.2.4 Metropolis准则

若运输总成本函数为[zX]，则当前解的运输总成本为[zX1]，新解的运输总成本为[zXnew]，总成本之差[dz=zX1-zXnew]，则Metropolis准则为

[P=1 ， dz<0 ，exp（-dzT） ， dz≥0 。] （9）

如果[dz<0]，则以概率1接受新的路径；否则以概率[exp（-dz/T）]接受新的路径。

3.2.5 降温

利用降温速率[q]进行降温，即[T=qT]，若[T

改进的模拟退火算法的流程图如图4所示。

4 仿真

4.1 测试问题

为了验证构建模型和设计的改进的模拟退火算法对于求解多车型车辆调度问题的有效性，本文对文献[12]的算例进行求解。所用车辆车型分别为6 t、8 t、16 t，每种车型有4辆，相关数据如表2所示[12]。

算例规模为30个客户，所有车型车辆不受行驶距离和行驶时间的限制。配送中心坐标为（41 km，70 km），客户的信息见表3。要求合理安排配送车辆的配送路线，使完成配送任务的总运输费用最少。

4.2 参数设置

本文的模擬退火算法参数设置如下：降温速率[q=0.95]、初始温度[T0=1 000]、结束温度[Tend=10]以及确定每个[T]时的迭代次数即链长[L=500]。算法是基于MATLAB R2017a 软件编程实现的，电脑的配置为内存4 GB，Windows10专业版操作系统，处理器Intel（R）Core（TM）i5-3337U CPU @ 1.80 GHz。

4.3 算法比较

改进的模拟退火算法与遗传算法[30]、禁忌搜索算法[30]和量子遗传算法[12]进行对比分析。从油耗、距离、运行时间等方面进行对比，结果如表4所示。

表4对比了4种不同算法的优化结果和计算时间。表5为本文算法以费用为最优目标的车辆路线，图5为相应的路径图和迭代图。由表4可以看出，本文算法的油耗费用优于其他算法，能够显著提高解的质量。运输距离虽然比量子遗传算法增加52.05 km，但是油耗费用减少了13.4%。由图5可以看出算法基本能在450代以内找到问题的最优解，将算法最高迭代次数设置为600代，运行时间为99.42 s，运行时间比遗传算法、禁忌搜索算法和量子遗传算法分别减少了57.15%、50.25%、36.89% ，表明本文算法在提高解质量的同时也大大提高了算法的求解效率。以上分析说明了本文算法在求解多车型以配送总费用最小为优化目标的车辆路径问题是有效的。

5 总结

研究低油耗的固定车辆数的多车型车辆路径问题可以帮助企业找到适合自身需求的车辆调度，有助于其总成本和碳排放的下降，同时也符合我国建设资源节约型、环境友好型社会的目标。本文模型考虑了车辆的实载率和运输距离与油耗之间的关系，在此基础上，建立了以固定发车费用和油耗费用为优化目标的数学模型。由于该模型是NP-hard问题，改进了模拟退火算法对模型进行求解，算法使用前向插入启发式算法生成初始解，在解变换产生新解的过程中融合了交叉、变异、逆转操作3种邻域搜索算法。通过相关实例的应用和对比，表明本文提出的算法在提高解质量的同时也大大提高了算法的求解效率，从而指导物流企业如何合理安排不同型号载运车辆。

参考文献：

[1] 郭薇. 全国环境监测工作会议召开[J]. 中国环境报，2014，4（1）：11-20.

[2] 俞明健. 城市货运交通问题与城市地下物流[J]. 交通与运输，2017，33（3）：1-3.

[3] DANTAIG G B，RAMSER J H. The truck dispatching problem[J]. Institute of Management Sciences，1959，6（1）：80-91.

[4] NAZIF H，LEE L S. Optimised crossover genetic algorithm for capacitated vehicle routing problem[J]. Applied Mathematical Modelling，2012，36（5）：2110-2117.

[5] MORETTI B R，AMAEAL A V，Arne L. Adaptive granular local search heuristic for a dynamic vehicle routing problem[J]. Computers and Operations Research，2009，36（11）：2955-2968.

[6] MÜLLER J. Approximative solutions to the bicriterion vehicle routing problem with time windows[J]. European Journal of Operational Research，2010，202（1）：223-231.

[7] 马建华，房勇，袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法[J]. 系统工程理论与实践，2011，31（8）：1508-1516.

[8] 潘雯雯，郭海湘，周光勇，等. 基于两阶段算法的需求可拆分多车型车辆路径问题[J]. 中国管理科学，2016，24（S1）：55-61.

[9] SUBRAMANIANA，PENNAP H V，UCHOA E，et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem[J]. European Journal of Operational Research，2012，221（2）：285-295.

[10] TAILLARDE D . A heuristic column generation method for the heterogeneous fleet VRP [J]. Operations Research，1999，33（1）：1-14.

[11] DEKKER R，BLOEMHOF J，Mallidis I. Operations research for green logistics-An overview of aspects，issues，contributions and challenges [J]. European Journal of Operational Research，2012，219（3）：671-679.

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

[13] 李进，傅培华. 具有固定车辆数的多车型低碳路径问题及算法[J]. 计算机集成制造系统，2013，19（6）：1351-1362.

[14] 朱长征，李艳玲. 碳排量最小的车辆路径优化问题研究[J]. 计算机工程与应用，2013，49（22）：15-18.

[15] XIAOY Y，KONAK A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. Journal of Cleaner Production，2017，167：1450-1463.

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

[17] 郭海湘，潘雯雯，周欣然，等. 基于单车场多车型车辆路径问题的混合求解算法[J]. 系统管理学报，2017，26（5）：824-834.

[18] CHENG C，YANG P，QI M Y，et al. Modeling a green inventory routing problem with a heterogeneous fleet[J]. Transportation Research Part E：Logistics and Transportation Review，2017，97：97-112.

[19] 揭婉晨，杨珺，杨超，等. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践，2016，36（7）：1795-1805.

[20] PESSOAX A，SADYKOV R，UCHOA E. Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems[J]. European Journal of Operational Research，2018，270（2）：530-543.

[21] BRANDAO J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J]. Computers & Operations Research，2011，38（1）：140-151.

[22] 史峰. MATLAB智能算法30个案例分析[M]. 北京：北京航空航天大学出版社，2011：178-187.

[23] 钱晓明，孙颖，刘建，等. 基于混合模拟退火算法求解电表配送车辆路径问题[J]. 计算机集成制造系统，2017，23（11）：2553-2560.

[24] GHORBANI A，AKBARI JOKAR M R. A hybrid imperialist competitive-simulated annealing algorithm for a multisource multi-product location-routing-inventory problem[J]. Computers & Industrial Engineering，2016，101：116-127.

[25] WANG C，MU D，ZHAO F，et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows[J]. Computers and Industrial Engineering，2015，83：111-122.

[26] YU V F，LIN S W，LEE W，et al. A simulated annealing heuristic for the capacitated location routing problem[J]. Computers and Industrial Engineering，2010，58（2）：288-299.

[27] DEMIR E，BEKTAS T，LAPORTE G. A review of recent research on green road freight transportation[J]. European Journal of Operational Research，2014，237（3）：775-793.

[28] COE E. Average carbon dioxide emissions resulting from gas-oline and diesel fuel[R]. Seattle，Wash，USA：United States Environmental Protection Agency，2005.

[29] 穆東，王超，王胜春，等. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统，2015，21（6）：1626-1636.

[30] 邢文训，谢金星. 现代优化计算方法[M]. 北京：清华大学出版社，2009：101-120.

[责任编辑 田 丰]