基于碳排放量对城市道路车辆路径规划研究

温喜梅，朱兴林，刘泓君

(新疆农业大学 交通与物流工程学院，新疆 乌鲁木齐 830052)

随着城市经济的快速发展，人民生活水平逐渐提高，物流配送已成为居民生活中的重要部分。但由于交通基础相对薄弱以及城市交通管理经验不足等方面的原因，出现了城市交通压力不断扩大、物流配送效率低的现象，严重影响了城市居民的物流配送需求。同时，随着人们节能减排、绿色物流意识的不断加强，在考虑碳排放量的同时确定最优车辆配送路径也非常有必要，具有实际意义。

物流配送的整个系统相对来说比较复杂，车辆路径规划问题(Vehicle Routing Problem，VRP)的研究也引起了越来越多学者的关注。宋芹[1]建立了车辆路径规划及使用者均衡的双层优化模型，通过验证结果表明模型的有效性，可较好地解决交通堵塞问题。Zhu等[1]发现车辆的行驶距离与碳排放量具有一定的关系。唐金环等[3]考虑到配送时间和碳排放量的限制，发现两者因素对路径具有一定的影响，建立多目标规划模型进行求解。Xiao等[4]研究了碳排放量、成本、距离三者之间的关系以及对路径规划的影响，从三个方面对配送路线进行了对比分析。杨龙[5]在考虑燃油消耗的情况下对路径问题进行了研究，首先分析了油耗的影响因素，在不同因素影响下，根据算例分析利用改进蚁群算法对模型求解。除了文中考虑的因素之外，也包含道路情况及多车型问题。

对于VRP的求解算法大多采用混合算法[6]。邓红星等[7]利用JOPT算法对模型求解，并对规划后的路径与原路径进行对比，结果表明该算法的有效性。刘娜等[8]在保障湖北社区居民生活的前提下，以SOM(Self-Organizing Maps)算法与遗传算法求解路径规划问题，结果证明遗传算法比SOM算法更加精确。邓红星等[9]以配送肉类为例，考虑保鲜度问题构建随机需求的最小成本模型，利用改进遗传算法对模型仿真求解。管卫利[10]、何敏[11]主要介绍了VRP模型及算法，考虑到遗传算法和蚁群算法的各自不足，利用遗传算子的改进蚁群算法对模型求解，但文中缺少对各控制参数影响性能的研究以及在实际运输过程中会出现道路拥堵、红绿灯等情况。孙伟等[12]以保证产品新鲜运输为目标构建数学模型，利用化学反应算法对算例求解，确定最优分配及成本。若采用其他算法与化学反应算法进行比较分析，则结果更具有说服力。顾蕾[13]对车辆路径规划的求解算法——包括遗传算法、快速探索随机数等方法进行综述，并分析各自存在的缺陷，进一步对算法进行改进和融合，构造新的混合算法，新算法优于传统的标准算法。

本文针对城市道路交通存在的现实问题及城市内多区域的需求问题，在对物流配送系统规划车辆路径时考虑碳排放成本和惩罚成本等，以最大程度地减少物流成本，建立混合整数规划模型、利用化学反应算法对模型进行求解，从而确定配送的最优路径。

1 城市道路交通现状及存在的问题

为满足不同类型的交通工具需求，城市道路多由机动车道、非机动车道和公共汽车优先车道组成。根据城市道路设计规范及相应功能可将城市道路分为快速路、主干道、次干道和支路四大类，每一类的设计速度均不相同[14]。以机动车为例，当大城市人口≤200万人时，快速路设计的行驶速度一般为60～80 km/h，当城市人口数>200万人时，属于特大城市，此时设计时速取最大值为80 km/h，在中等城市内快速路不存在；在大城市人口≤200万人时主干路设计的行驶速度为40～60 km/h。同理，特大城市的主干路设计时速取最大值60 km/h，中等城市设计的速度为40 km/h；次干路与支路设计时速分别为40 km/h和30 km/h。随着现有城市道路规模的不断扩大，人民生活需求也不断增加，带来了一系列新的交通矛盾问题。

1.1 城市道路拥堵问题

随着城市化进程的加快，城市人口越来越多，道路的通行能力达到饱和，从而造成供需之间的不平衡，出现拥堵现象。截至2019年6月，全国机动车数量达到3.4亿，其中的汽车数量占比为73.5%；拥有机动车驾驶证约为4.2亿人，其中汽车驾驶人占比约为90%[15]。城市道路空间有限，交通工具复杂，尤其是在早晚高峰时段，行驶速度降低，拥堵时间较长。因此，确定合适的路径将节约一定的时间，对出行计划更有利。

1.2 城市道路环境污染问题

目前，我国雾霾污染问题越来越严重，而造成雾霾天气的主要原因之一就是车辆排放的尾气污染物，而其中的机动车排放污染占了较大比例。在城市道路出现拥堵时，将会降低车辆行驶速度，在浪费时间的同时也增加了车辆的燃油消耗，造成环境污染，因此，需采取一定的措施并提倡坚持绿色出行、环保的理念。在城市内可大力发展城市公共交通，在保障绿色环境的同时进一步提高了城市交通的利用率，缓解交通压力。

城市配送服务已成为提高居民生活质量的必要保障，也是物流配送中的最后、最关键的“一站”。合理的配送路径不仅关系着配送效率高低，也影响城市道路的拥堵和环境污染等问题。因此，在考虑绿色出行的前提下如何确定最优的配送路径，是当前研究的重点。

2 问题描述及模型构建

2.1 问题描述

由于车辆行驶受限以及运输成本等原因，目前的配送主要分为两级配送模式，首先在市郊某处建立规模较大的储备仓库，然后利用车辆配送至城市内的各个配送中心，再由城市内的各个配送中心点对各区域的客户负责配送，以满足客户需求，如图1所示。

图1 城市内多配送中心配送模式

若城市物流配送系统共有m个配送中心服务点，n个需求客户。每辆车的最大载重不超过Q，行驶最远距离不超过L。

配送方案的假设条件：

1)每个配送中心的车辆数目固定；

2)车辆从配送中心出发，根据路线进行配送，并最终回到原配送中心；

3)一辆配送车辆可服务多个客户，但每个客户仅被一辆车服务一次；

4)每辆车的容量与行驶距离有限。

为建立该问题的数学模型，对符号定义如下：

2.2 符号定义

2)参数。qi：客户i的需求量(0

3)决策变量。xijk：如果车辆k经过(i,j)时的值为1，否则为0；fijk：配送车辆k经过(i,j)时的货物装载量；ρij：车辆行驶在任意两点i和j之间路径的燃料消耗率；Fij：车辆经过路径(i,j)时的燃料消耗量；Eij：车辆经过路径(i,j)时的碳排放量。

2.3 车辆碳排放量

已有研究成果表明，车辆的碳排放量与燃料消耗量具有正相关关系，因此，可利用燃料消耗量刻画其碳排放量。根据Suzuki[16]单位行驶里程(km)的燃料消耗量为

(1)

由于在实际的物流配送中，两点之间的行驶里程为dij，因此，可得到车辆经过路径(i,j)时的燃料消耗量Fij为

(2)

根据碳排放量与燃料消耗量之间的关系，得到车辆的碳排放量模型为

Eij=ξFij.

(3)

2.4 软时间窗约束

所谓软时间窗，可理解为在客户理想的时间段内进行配送，这时客户的满意度为最高。当车辆在早于时间段开始或车辆到达时间晚于可接受的时间段内时，客户的满意度会有所降低。如图2所示，在[ai,bi]时间段内进行配送时，客户满意度为最高；在tbi内接受服务，客户的满意度有所降低，直至满意度为0。

图2 客户满意度

满意度降低的同时也会产生一定的等待费用或赔偿费用，给车辆司机及配送中心造成一定损失，都要接受相应的惩罚，惩罚成本与时间关系如图3所示。

图3 惩罚成本函数图像

惩罚成本函数通常为随着时间而变化的函数，软时间窗的惩罚函数如式(4)所示

(4)

2.5 模型建立

根据上述符号定义、碳排放量及惩罚成本计算方法，以最小化物流成本为目标建立模型

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

qjxijk≤fijk≤(Q-qi)xijk∀(i,j)∈E,k∈K,

(14)

xijk∈{0,1} ∀i,j∈N,k∈K,

(15)

fijk≥0 ∀i,j∈N,k∈K.

(16)

其中，目标函数(5)为使总的物流配送成本达到最小，主要包括固定成本、碳排放成本和时间惩罚成本3部分。限制条件中：式(6)为每个配送中心的配送车辆总数一定；式(7)为每个客户只能被一辆车服务；式(8)为保证车辆行驶路径具有一定的连续；式(9)和式(10)分别为车辆的容量和里程的限制；式(11)和式(12)为车辆k是否得到使用；式(13)和(14)为车辆配送的载重限制条件；式(15)为0～1变量xijk的约束；式(16)为变量的非负限制。

3 模型求解

目前，求解VRP问题所采用的智能优化算法中容易出现收敛速度慢、局部最优的缺点，无法在短时间内得到最优解。化学反应优化算法CRO(chemical reaction optimization, CRO)是模拟化学反应中分子进行碰撞达到最终稳定状态，即分子势能达到最低[17]。针对提出的问题及CRO的算法特点，采用两部编码法和矩阵编码法两种方式，采用基于贪婪搜索策略的种群初始化方法，进一步设计四种化学反应算子。

3.1 解的表达

3.1.1 两部编码法

在两部编码法中，每个解的编码由两部分组成，如图4所示。其结构为：配送车辆服务的客户数量+客户服务顺序序列。如图3所示，配送中心1中的配送车辆1服务两个客户，服务顺序为：客户4→客户7，路线为：配送中心1→客户4→客户7→配送中心1，依次类推，可得到所有配送中心配送车辆服务的客户及客户服务顺序。

图4 两部编码

3.1.2 矩阵编码法

矩阵编码法采用矩阵的形式进行编码，如图5所示。具体说，将多配送中心看作多个单配送中心单独进行考虑，然后分配车辆，设计行驶路线。如配送中心1中的配送车辆1为客户4、7提供配送服务，配送路线为：配送中心1→客户4→客户7→配送中心1；同理，配送中心2的配送车辆1为客户6、客户9、客户11提供物流配送服务，因此，配送路线为：配送中心2→客户6→客户9→客户11→配送中心2。

图5 矩阵制编码

3.2 算法步骤

3.2.1 初始化阶段

步骤1：算法参数的初始化。CRO的参数设置[18]如表1所示。

表1 化学反应算法的参数设置

步骤2：种群的初始化。为提高解的质量，减少求解时间，以贪婪搜索策略初始化种群个体。首先，根据客户与各配送中心的距离，分配客户到最近的配送中心；其次，根据配送中心的客户安排配送车辆；最后，调整每辆车所服务的客户先后顺序。

3.2.2 单分子无效碰撞

单分子无效碰撞是指单个分子撞击容器壁而得到一个新分子的过程，即ω→ω′，采用随机插入算子的方法。假设基因序列为：1|4|7|2|5|8|3|6|9|，选中基因2，基因序列变成1|4|7|5|8|3|6|9|，然后将基因2插入到另一位置，假设插入到基因3之前，那么得到新的基因序列为：1|4|7|5|8|2|3|6|9|。

3.2.3 分解反应

分解反应是指当一个分子撞击到容器时，分子分解为多个分子(默认分解为两个分子)。采用交换算子产生新分子的算子，对处在两个不同位置的基因进行交换。

3.2.4 分子间无效撞击

3.2.5 分子合成反应

与化学反应中的合成反应类似，化学反应优化算法中多个分子合成一个新的分子。具体来说，随机从父代1和父代2中选择相同的一个基因，将选中的基因与其后的基因距离进行比较，将势能较少一组基因中的其后基因放入到选中基因位置，确定合成路径下的一个顾客，重复上述过程直到合成后包含所有顾客。

4 实例分析

以乌鲁木齐市社区蔬菜直销点的配送中心为研究对象，确定最优路径并为社区需求点提供服务。已知在此区域内4个配送中心服务点坐标以及48个社区需求点编号[19]，每个配送中心均有3辆车，每天早上6点开始准备配送工作，车辆的平均行驶速度为40 km/h，每辆车最大载重为4 t、最大行驶距离为100 km，并将车辆提前到达的时间惩罚成本μ1和时间窗之后到达的单位惩罚成本μ2设置为10元/h、50元/h，碳排放系数转换因子ξ为3.096。在此基础上根据模型目标确定最优路径规划，配送中心和客户信息如表2、表3所示。

表2 配送中心信息

表3 客户信息

参考Suzuki[16]的仿真数据取值，令ρ0=1，ρ*=2；同时，由于每升燃料消耗释放2.32 kg的碳排放量[20]，设单位碳排放费用Ccarbon为0.1万元/kg、0.3万元/kg，因此，配送车辆每天的固定成本为500元[21]。

为使车辆运输缩短距离，配送中心原采用节约法对车辆路径进行规划，此种方法规划的路径着重于行驶距离的长短，而忽略了配送时间、客户满意度及碳排放量对环境的影响研究，不符合节能减排、绿色物流思想。

4.1 CRO算法求解

为验证贪婪搜索策略的有效性，并对比两种编码方式的优劣。基于化学反应算法的基本框架，本文采用3种求解算法求解模型。

如表4所示，在编码方式上，算法CRO1采用两部编码法，算法CRO2和算法ICRO(Improve Chemical Reaction Optimization)采用矩阵编码法。初始化阶段，ICRO采用提出贪婪搜索策略，而CRO1和CRO2均采用随机初始化方式。

表4 3种算法的详细信息

通过求解确定CRO1和CRO2的配送车辆数为9，ICRO的配送车辆数为8，部分配送顺序：A→1→10→2→34→19→A；B1→48→35→41→38→44→B1和B2→42→39→40→21→B2；C1→46→47→30→24→32→C1；……； D3→3→5→13→21→D3。其中，B1和B2代表配送中心B使用2辆车进行分别配送，C1，C2等同理。

将3种算法的求解结果和CPU耗时汇总，如表5及图6所示。

表5 3种算法求解结果对比

结果分析:表5和图6表明，CRO1和CRO2的求解结果相差不大， CRO2求解比CRO1求解多1.4%，而CPU时间降低了17.5%；ICRO算法相比前两种求解方法，在最值及CPU时间方面上均表现出优势，其主要原因在于初始化的处理方式不同，CRO1和CRO2的车辆配送为9辆，ICRO使用车辆数为8，这也与成本分析相对应，ICRO减少了一辆车的成本开支。可以看到，在CPU时间上3个算法求解结果依次递减，这也说明贪婪搜索策略相比随机初始化的求解效率高，总体较好。

图6 3种CRO算法比较

4.2 优化路径前后对比

将配送中心的初始路径与优化后的配送路径进行距离和碳排放成本对比，结果如表6、表7及图7所示。

表6 优化路径前后对比(Ccarbon=0.1万元/kg)

图7 优化前后碳排放成本与距离比较

4.3 结果分析

1) 考虑碳排放成本的车辆路径优化与最初的配送距离相比，由57.82 km增加到了60.73 km，但优化后的碳排放成本有一定减少。

2) 分别对不同单位的碳排放成本Ccarbon=0.1、Ccarbon=0.3进行对比，当单位碳排放成本逐渐增加时，优化路径后成本减小的效果十分明显。

3) 优化后的路径距离虽然有所增加，但总的碳排放成本有所降低，符合绿色出行。同时，当单位碳排放成本逐渐增大时，碳排放成本所占比例会逐渐增大，因此，降低碳排放量将减少成本支出，具有一定意义。

5 结 语

针对城市多区域配送问题，本文以乌鲁木齐市社区蔬菜直销点的配送中心为研究对象，主要研究碳排放量对车辆路径规划问题的影响，从而确定配送中心的最优配送路径。以碳排放量和时间为约束，建立以碳排放成本、惩罚成本等总成本最小化模型，采用化学反应优化算法对问题模型进行求解，得到优化的配送路径，并将优化前后的路径距离、碳排放成本进行对比。经实例分析与计算，结果表明，虽然车辆行驶的距离有一定增加，但可降低燃料消耗、减少碳排放成本，实现绿色出行的概念。同时，验证了CRO相关算法及模型的可行性与有效性，为降低燃料成本和低碳物流配送规划问题提供方法指导。