基于拆分运输的低碳车辆路径优化

2018-07-17李双艳王忠伟张得志

铁道科学与工程学报 2018年7期

李双艳，王忠伟，张得志

(1. 中南林业科技大学交通运输工程与物流学院，湖南长沙 410004；2. 中南林业科技大学林业工程博士后流动站，湖南长沙 410004；3. 中南大学交通运输工程学院，湖南长沙 410075)

车辆运输过程会耗费大量的能源，产生大量碳排放。从运作管理角度，优化车辆路径安排降低其排放是现代物流运输企业改善运输环境绩效的必要手段，也是实现绿色、高效物流的一个重要方法。对于低碳车辆路径问题，Tajik等[1]给出考虑总油耗和温室气体排放有时间窗约束的取货车辆路径模型。ZHANG等[2]采用二氧化碳排放与载重函数关系进行环境车辆路径问题的建模。Demir等[3]分别对有时间窗和无时间窗约束的污染路径问题(PRP，Pollution Routing Problem)建立数学模型，并分析车辆装载量和总费用的关系。李进等[4]建立碳排放交易机制下的物流配送路径优化模型，指出与仅考虑经济成本的模型相比，碳排放限额交易机制能够有效促使企业减少碳排放，但可能会带来企业成本的上升。唐金环等[5]以城市货的为例，建立考虑旅行时间和碳排放量的多目标车辆路径问题模型。陈玉光等[6]构造基于准时送货与最小化耗油的配送车辆路径模型，给出最小油耗及最小越界时间惩罚帕累托解集。杨培颖等[7]以最小碳排放量为目标，对现实接送机场服务运作中的车次分配与调度问题进行优化求解。低碳车辆路径问题是NP-Hard问题，很难由精确算法获取最优解，一般采用启发式算法进行求解，Bektas等[8]建立排放污染路径问题(Pollution-Routing Problem)的数学模型，给出包含碳排放费用的运输优化方法。Kramer等[9]研究低排放的车辆路径问题的元启发式求解方法。降低运输过程碳排放与提高车辆运输效率是密切相关的。而拆分运输是提高车辆装载率和运输效率的模式之一。拆分运输允许多条路径访问同一个需求点，并且由这几条路径来共同承担该点的需求。因此也就放宽了一般 VRP 问题中对于车辆容量要大于需求点送货或取货需求量的要求。需求可拆分的车辆路径问题(Split Delivery VRP)最早由 Dror等[10]提出。Archetti等[11]提出局部搜索算法，并验证当任务点需求量较大时 SDVRP得到的结果明显优于VRP。刘新宇等[12]对需求可拆分车辆路径问题的研究进行了总结，说明需求可拆分的取送货车辆路径问题研究的必要性。基于拆分运输的低碳车辆路径问题具有实际的应用前景。如生物质电厂的生物质燃料运输、一日多配的快递包裹运输等。但对拆分运输模式下低碳车辆路径问题研究还很欠缺。本文在国内外研究的基础上，采用拆分需求运输的方式，建立多车多次，单点多次的低碳车辆路径优化模型，设计符合拆分约束的重定位禁忌搜索算法求解算法。分析车型和拆分对运输碳排放的影响，给出可执行的运输减排建议，从而促进低碳运输和低碳物流发展。

1　问题描述

本文研究的拆分运输低碳车辆路径问题是车辆路径问题的一个扩展，其优化目标是运输过程中的总碳排放量最小，而不是距离最小或时间最短。由于车辆碳排放与车辆载重及距离均相关。因此该类车辆路径问题中，需求点访问的顺序、需求点的载/卸货量都是决策变量。如图1，将拆分运输的最小碳排车辆路径问题定义在有向拓扑图中，车场安排一定数量、固定类型车辆通过有向网络到各个需求点进行货物集派，然后返回。各需求点的运输可以进行拆分，车辆在每次集派时，其装载重量不能超过其最大载重，决策目的是确定每辆车辆的行程路径及每个需求点集派货物量，以最小化拆分运输的碳排放。

图1　拆分运输车辆路径问题示意图Fig.1　Schematic diagram of split delivery vehicle routing problem

2　数学模型

2.1　符号定义

输入参数：dij表示节点i和j之间的车程距离；k表示特定燃料的碳排系数；m表示参与运输的车辆数；C表示车辆的最大载重量，所有车辆最大载重量相等；qi表示收购站点 i的需要运输的货物重量；a表示车辆单位周转量油耗系数，单位：L/(t·km)；b表示车辆空载油耗量，单位：L/km。

决策变量：Xvij表示从i到j的有向路段是否属于车辆v行驶路段，为0-1变量；Yvij表示从i到j的有向路段上车辆 v的装载量，为连续变量；Zvij表示从i到j的有向路段上车辆v的剩余装载量，为连续变量。

根据英国交通部对油耗与载重量关系的研究,车辆的油耗与载重可以简化为线性关系：

其中：Q为货物载重；a为车辆的油耗系数；b为车辆空载油耗。这样对于一定类型的车辆，若已知载重量，可以根据对应的油耗技术参数，计算单位里程的油耗量，然后乘以碳排放系数和行驶里程，得到碳排放量 F (Q ) = k (a Q + b )d。

2.2　模型表示

构建对应的车辆路径数学模型，目标函数(1)为非线性函数，包含了车辆载重和行驶路段长度的积。

约束式(2)表示每辆车必须从1点发出，(3)表示每辆车必须回到1点，(4)表示到达每个点的车辆数大于等于1。(5)表示每个点发出的车辆数必然等于到达的车辆数。(6)表示从1点出发时所有车辆的载重量总和为零，即空载。(7)表示任何回到1点的车辆载重量的边界约束。(8)表明对每个节点而言，所有发出车辆的载重和与流入车辆的载重和之差为该点的取货量qi，即拆分约束。(9)表明对于每辆车而言，在每个路段上的载重量和剩余载重量和必然为CXvij。(10)是每条路段上的车辆装载量约束。该模型针对集货问题，配货问题模型与之对称。

3　求解算法

3.1　算法流程

Lensatr等[13]证明了几乎所有类型的VRP均为NP一难问题。因此，拆分运输低碳车辆路径问题也是NP-hard问题。其优化目标碳排放量是车辆运输距离和车辆载重二类变量的非线性函数。需要求出各个站点的拆分量及其分派的车辆，所有车辆的路径。该问题决策变量有2类，求解变量较传统的车辆路径问题有所增加，求解复杂度高。为了在有限的时间内求解出“可接受”的最佳近似解，采用元启发算法进行求解。将求解过程分为2个阶段。第1个阶段解采用贪婪插入法生成初始可行解。第2阶段采用禁忌搜索迭代优化初始解。当允许拆分生物质收集点的收集量分派给不同车辆时，车辆的利用率会增大。最少车辆需求为M。

算法流程如下。

Step 1：初始化，车辆剩余装载容量为 C，收集站点i的秸秆量为qi；

Step 2：将收集站点按照秸秆数量大小降序排序；

Step 3：车辆到排序最前的收集站装载秸秆；

Step 4：根据贪婪插入方法在路线中依次添加其他收集站点装载秸秆，更新车辆剩余装载容量和收集站点的秸秆量值；

Step 5：判断车辆的剩余装载容量是否为0，若是，使用车辆数增加1，并跳至Step 6。否则，跳到Step 4；

Step 6：判断车辆全部使用否，即使用车辆数是否为M，若是则循环结束，否则，跳到Step 2；

Step 7：重定位算子产生的候选解；

Step 8：进行选优、禁忌和解禁操作，并更新禁忌表和最优解；

Step 9：满足终止条件，算法停止。

3.2　重定位算子

生物质收集具有大批量，节点密集的特点，必须进行拆分收集。在产生候选解过程中应考虑车辆容限和收集序列。对应设计2类重定位算子，一类是部分重定位操作，另一类为整体重定位操作。假设i为路径r1中的一个节点，车辆在该点的装载量若为δi,r1。将该收集任务重新分配给r2，其分配量为，当r2路径对应的车辆剩余容量小于δi,r1，则原收集任务部分转派给r2，重新定位i到r2，派量为 Qr2- Lr2。否则，原收集任务全部转派给r2，重新定位i到r2，派量为δi,r1，如图2所示。在进行候选解选优时，根据目标函数进行计算，包括距离和路段载重对碳排放的影响。

图2　重定位算子Fig.2　Relocation operation

4　实例仿真

4.1　仿真数据

为了研究上述优化模型及其算法的有效性，以湖南省衡阳祁东县凯迪生物质发电厂为例，计算其收集运输的最小碳排路径。祁东凯迪生物质发生物质发电厂项目座落在湖南省祁东县经济开发区工业园，由武汉凯迪控股投资有限公司投资建设，占地面积250亩，总建设规模为2×12 MW机组，配2台48 t/h生物质锅炉。生物质发电厂年燃料需求量27.611 4万t，年运行300 d，年运行时间7 200 h，日需求量为 920.48 t，燃料来源是祁东县所管辖的乡镇。祁东县辖19个镇、4个乡，各个乡镇设燃料收购站点。根据交通路网数据可获得各乡镇之间的运输距离。运输车辆的类型根据运输生物质的重量确定，生物质发电厂对生物质需求量大，各收购站点的燃料重量都超过了 18 t，且多数站点燃料重量大于 30 t，甚至高达 74 t，因此要选用大吨位的牵引拖车进行运输。根据车辆空载等速燃料消耗量、综合燃料消耗量，可以得出不同的车型的油耗相关系数见表1。不同的车型车辆油耗系数a和空载油耗b不一样，见表1。仿真采用MATLAB7.2数值仿真软件编程，在3.20 GHz 主频、1.96 G 内存、Windows 7操作系统平台进行运算。

4.2　结果与分析

采用型号ZZ4251N3241C的牵引拖挂车运输生物质燃料时，仿真结果如表2和图3所示。为了验证基于拆分运输的低碳车辆路径模型和算法的有效性，同时计算了拆分运输下距离最优的结果，即表3中情形2。说明低碳车辆路径模型和距离最小车辆路径模型的不同。情形1为基本情形，是以碳排量为优化目标。情形2是以行驶总距离为优化目标。而情形3以碳排量为优化目标，但油耗系数a扩大10倍。情形4也是以碳排量为优化目标，其中空载油耗b扩大10倍。以车型1为例，在情形1下得出的仿真收集路线及其收敛情况如图3和图4。

表1　车辆技术参数Table1　Technical parameters of delivery vehicles

图3　情景1下的需求拆分的车辆路径安排Fig.3　Vehicle routing with split demand under scenario 1

图4　情景1算法收敛曲线Fig.4　Algorithm convergence curve under scenario 1

表2　情形1下拆分收集运输安排Table2　Vehicle schedule with split demand under scenario 1

表3　ZZ4251N3241C车型生物质燃料运输的不同优化目标的对比分析Table3　Comparative analysis of optimal solutions for different optimal objectives based on ZZ4251N3241C vehicle

仿真还对其他2种车型进行了优化。表4是3种不同载重的牵引拖挂车对应的总碳排和总运输距离的优化结果对比。3种车载重分别为24.2，27.2和33 t。其载重量逐渐增大，空载油耗b也随之增大，而油耗系数a则逐渐减小，最少需要的运输次数减少。

表4　3种车型优化计算结果对比Table4　Comparative analysis of optimal solutions for different vehicle types

对不同车型，统计各收集站运拆分次数的情况如图5所示。对最小容量的车型ZZ4251N3241C，在情形1下，其被分割次数最多的是收集站3，情形2下，分割次数最多的是收集站3，10和11。情形3和4下，其被分割次数最多的是收集站3。即路径优化目标的拆分频次比碳排优化目标的要多。

在情形 1下，ZZ4181N361GD1(车型 2)和ZZ4259M28CCC1B(车型 3)分割次数最多的是收集站为3，10和11。且单次完成收集运输的客户点数相比容量小的车型(车型1)减少。可见随着车载容量的提升，分割点增多且有向生物质发电厂靠近的趋势。

综上可分析得出：1) 碳排总量和运输总距离为优化目标的2种情况对比。发现两者碳排总量区别不大，为4.248%，距离变化则更小，不到1%，这是因为油耗因子都比较小的原因。而情况1下车辆的载重量更为平均，载重均方差为8.01。情况2的则为23.35。

2) 单位油耗系数a和空载油耗b影响分析。分别增大单位油耗系数和空载油耗 10倍的结果见表3，其碳排相对基本情形(1)的变化为 233.11%和663.44%，显然空载油耗变化对碳排的影响更大。增大空载油耗系数时，各个车辆载荷也更为平均，车辆的载重方差为7.52。而增大单位油耗系数时，车辆的载重均方差为 12.90，且其优化结果的行驶距离和碳排都会有所增加。以上结果表明碳排优化决策使车辆路径安排趋向载重均衡，而距离最短优化决策不具有此特点。

3) 路径点访问顺序分析。对于多点服务路径而言的，在每条路径中，距离生物质发电厂最短的客户点安排在最后访问。如路径[0, 10, 12, 1, 0]，其中各个点距离生物质发电厂的距离为12.6，37.7，7.1 km。再如路径[0, 18, 21, 0]，其中各个点距离生物质发电厂的距离为56.9，51.9 km。这是因为在集货运输过程中，载重量是不断增加的，是递增的，为了降低碳排，会形成重载短程现象。即把距离短客户点的安排靠后。也就是说在同一条路线不同的访问顺序(顺时针、逆时针)的油耗存在差异，最短路不存在该特点。

4) 拆分特点分析。从结果可见，距离生物质发电厂较远的且集货量小于车载容量的收购站点，运输是单趟完成的，不进行拆分。如收购站点编号为20，21，22的点距离生物质发电厂的距离分别为72.8，51.9和69.7 km。其货物量分别为19.66，19.81和18.26 t，均小于车载容量。根据结果，可以发现20和22号收购站的集货单次完成，21号收购站的集货分2次拆分完成。

5) 随着车辆载重的增大，单位距离碳排减小，空载碳排增大，碳排放总量减小，行驶总距离也减小。如车型1和车型3的碳排总量相差128.36，减小了20.59%。载重量越大的车型碳排量越小，环保性能也越好。