基于 CO2排放的车辆路径优化模型及其算法研究

张得志，钱奇，李双艳，靳方平

（1.中南大学 交通运输工程学院，湖南 长沙 410075；2.中南林业科技大学 交通运输与物流学院，湖南 长沙 410004）

基于 CO2排放的车辆路径优化模型及其算法研究

张得志1，钱奇1，李双艳2，靳方平1

（1.中南大学 交通运输工程学院，湖南 长沙 410075；2.中南林业科技大学 交通运输与物流学院，湖南 长沙 410004）

物流不仅是能源消耗大户，同时也是 CO2排放的重要来源。在分析配送车辆燃油消耗和 CO2排放因素的多种车辆类型车辆路径问题特点的基础上，构建其相应的优化模型，并给出基于遗传算法的启发式求解算法。最后，针对该模型和求解算法进行数值算例仿真，研究结果显示：路径最短的路线不一定是能耗最小的路线；与传统基于路径最短的车辆路径对比，基于 CO2排放的车辆路径总行驶里程较长，但其综合成本较低；遗传算法是解决绿色车辆路径问题的一个有效的求解算法。

物流能耗；CO2排放；车辆路径；优化模型；遗传算法

物流活动包括货物运输，存储，库存管理，物料搬运，以及所有相关的信息管理过程。物流的目标是协调这些活动，以最小的成本满足客户的需求。过去，这种成本纯粹定义为货币成本。考虑到环境压力的上升，企业必须更多的考虑物流活动的外部性，这其中涉及到气候变化、空气污染、噪声、振动和事故等。

根据2010年能源交通报告，2008年美国交通运输业所排放的二氧化碳占二氧化碳总排放量的31.05%，超过工业、商业及居民的二氧化碳排放总量，是最大的二氧化碳产生源。根据欧洲环境局2011年发布的TERM2011报告，2009年在欧盟27个国家中，运输（包括国际海运）占全部温室气体排放总量的24%，其中，公路运输占温室气体排放总额的 17%［1］。而在物流活动中，公路运输占到了80%以上。由此可见，发展低碳经济必须要首先优化交通运输。实现低碳运输的一个方法就是优化运输线路，减少碳排放。因此，本文侧重于研究公路运输在组织车辆路径的过程中，如何减少CO2排放，减少对环境的危害。绿色车辆路径研究的目的就是研究减少运输外部性的方法，在经济、社会、环境目标之间取得更加持续性的平衡。

车辆路径问题（Vehicle Routing Problem，VRP）最早由 Dantzig和 Ramser［2］于1959年提出，之后产生了这一问题的许多变种，例如多车型车辆路径问题［3-5］、多 车 场 车辆路径 问 题［6-7］、开 放 式车辆路径问题和动态车辆路径问题等［8-10］。

上述经典的车辆路径研究文献中，其目标函数大多是最小化运输成本或者运输距离，其中，运输成本一般包括 2个方面的内容，其一为车辆的启动成本，包括车辆的使用费、折旧、司机工资等；其二为车辆的行驶费用，一般文献中设定为行驶距离的线性函数。但是随着社会的发展，“绿色物流”的概念逐渐深入人心，在考虑行驶成本的同时，有必要考虑 CO2排放对社会的作用。因此，我们需要综合考虑油耗和 CO2排放对车辆路径的影响。

王明阳等［11］建立了带油耗的单车场开放式车辆路径问题。另外，国家发改委和财政部已经形成了“中国碳税税制框架设计”的专题报告，表示我国碳税将在未来若干年内推出。考虑到碳税的计费依据是二氧化碳排放量，根据《2006年 IPCC国家温室气体清单指南》提供的方法，二氧化碳排放量的计算公式为：单位化石燃料二氧化碳的估算值=低位发热量 ×碳排放因子 ×碳氧化率 ×碳转换系数，本文采用的碳税成本为每 20元/t［12］。

因此，本文在车辆路径问题的研究中同时考虑油耗和碳排放两个因素，构建基于 CO2排放的车辆路径优化模型，并对比分析了考虑 CO2排放外部成本的车辆路径优化和传统车辆路径优化，探索适应绿色车辆路径优化的规律和管理启示。

1 问题描述与数学建模

1.1 问题描述

本研究同时考虑油耗和碳排放的单车场多车型闭合式绿色车辆路径问题。问题的描述如下：只有1个车场，车场中有 L种不同类型的车辆（每种车辆足够多），每种车辆具有不同的容量、固定成本、单位燃油消耗、碳排放因子。该车场服务 N个客户点，每个客户点的坐标位置已知，需求量已知。配送车辆从车场装上货物出发，为 N个客户送货，要求每个客户只由1辆车为其完成送货任务，车辆将货物运送完毕后回到车场。被派出完成配送任务的配送车辆，其总费用由 3部分组成：车辆的固定成本、燃油消耗费用和车辆排放 CO2的外部成本。该问题的优化目标是：在综合考虑车辆运行费用（含固定成本和变动成本）与碳排放的环境成本情况下，如何合理配置车辆及安排各车辆配送线路，使得总成本最小。

1.2 数学建模

符号及决策变量说明：

N=［0，1，2，…，n］表示客户点；其中0表示车场，1到 n表示可用车辆的类型；kl表示第 l型车的数量；ql表示第l型车的容量；sij表示客户点 i和j之间的距离；di表示客户点 i的需求量；c表示单位体积的油价；fl表示第 l型车辆的单位油耗；tl表示第 l型车辆的排放因子；gl表示第 l型车的固定使用成本；λ表示单位 CO2排放外部成本。

目标函数可以表述为如下：

相应的约束条件为：

在上述模型中，公式（1）是目标函数，表示车辆燃油成本、车辆使用固定成本、车辆的碳排放成本；公式（2）确保每条线路的载重量不超过车辆的容量要求；公式（3）表示对于每个顾客，有且仅有1辆车为它服务；公式（4）表示到达每个客户只有 1辆车；公式（5）表示离开每个客户只有 1辆车；公式（6）表示离开车场的车辆和回到车场的车辆相等，即所有车辆从车场出发，最后又回到车场；公式（7）和公式（8）表示0-1整数约束，分别表示车辆访问顺序与车辆选择。

1.3 求解算法分析

对于多车型车辆路径问题（Fleet Size and Mixed Vehicle Routing Problem，FSMVRP），由于基本的VRP是NP完全问题，因此，FSMVRP也是NP完全问题。另外，由于 FSMVRP中的车辆类型不同，因此，FSMVRP比基本 VRP的求解更加困难和复杂。FSMVRP的研究还处于初步阶段，目前尚没有求解该问题的精确算法。因此本文采用遗传算法求解。

遗传算法（Genetic Algorithm，GA）最初由美国Michigan大学 J.Holland教授于1975年首先提出，它是一种概率搜索算法，具有内在的隐并行性和更好的全局寻优能力；能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

1）染色体结构

遗传算法以编码的方式将解空间映射为遗传空间，将可能的解编码为一个向量，称为一个染色体或者个体。因此，解的编码方法很大程度上决定了解空间的搜索方向。本文采用客户与虚拟物流中心共同编码的方法来表示一个可能的解。例如（以10个城市为例）：

表示1辆车从配送中心出发，依次服务第 1，3，5号客户后返回配送中心，然后另 1辆车从配送中心出发依次服务第2，6，8，4号客户后返回，第3辆车从配送中心出发依次服务第7，9和10号客户后返回。

2）初始种群

初始种群的生成方法是在客户随机全排列的两端及中间插入若干数量的虚拟配送中心，即生成一个若干车辆服务全部所有客户的初始解，因为随机生成的解，必然有一部分是不符合约束条件的，因此，需要根据车辆载重能力修正初始解，直到所有初始解满足条件位置。

3）适应度函数

由于目标函数是基于车辆固定成本、燃油消耗成本和 CO2排放成本构成的综合成本最小；因此，简单起见，适应度函数可以取目标函数的倒数。

4）遗传算子

选择算子：采用保存最佳策略的轮盘赌法来选择个体。

交叉算子：由于编码的特点决定染色体组间无序（车辆的前后顺序）、组内有序（车辆的访问顺序），因此，若采用传统的部分匹配交叉，可能会破坏解的优良特性。因而，本文利用参考文献［13］中提供的交叉方法。具体过程为：①如果染色体交叉点处有0，就直接采用部分匹配交叉的方法；②如果染色体交叉点处没有0，就将交叉点向后移动直到出现0，再采用部分匹配交叉的方法。

变异算子：采用2点交换作为染色体变异的算子。随机选择染色体的2点，交换这2个点位上的基因。若染色体中出现连续的0，表示变异向良好的方向，减少了所使用的车辆数。

5）终止条件

因为遗传算法是随机搜索算法，很难找到一个明确的终止条件。为简单起见，本文设置一定的进化代数T（一般T∈［100，1 000］），作为算法终止的条件。

6）算法实现步骤

步骤1：初始化运行环境，配置变量；

步骤2：构造染色体，生成初始解空间，并进行约束检查，对不符合约束条件的解进行修正；

步骤3：计算初始解的适应度；

步骤4：gen=1，对群体进行选择、交叉、变异操作，对最终生成的子代进行约束检查，使之全部成为可行解；将子代插入父代中，形成新的父代；

步骤5：当 gen小于指定的终止代数，返回步骤4，继续执行；否则，评价最后的解，当取得最小的目标函数值即满意解，算法结束。

2 算例分析

2.1 实例计算

假设某一配送中心为30个客户配送货物，各个客户的需求量及坐标见表 1及图 1所示。车场坐标为（11，11），该配送中心共有 3种类型配送车辆，每种类型车辆足够用，各种车辆的运行参数如表2所示。如何合理安排配送车辆的行驶路线，使得包括车辆购置固定成本、燃油费和 CO2排放费用等综合配送成本最小。

表1 客户的坐标位置及需求量Table1 Coordinates and demands of customers

图1 客户位置示意图Fig.1 Location of customers

表2 3种车辆的运行参数Table2 Operation parameters of three kinds of vehicles

2.2 结果分析

针对算法的性能，记录其在1 000代中的最优解以及均值如图 2所示，由图 2可以看出，算法具有较好的收敛性和稳定性。

图2 收敛效果示意图Fig.2 Convergence effect

1）仿真结果分析

其中一次的运行结果如下：总成本3 865.8元，碳排放量1 020.1 kg，路径长度2 197.3 km。共需要7辆车，其中，4辆20 t的车，3辆30 t的车。每辆车的容量为20，30，19，30，18，20和30 t。每辆车的路径 长 度 为 334.166 6，264.859 8，355.512 7，246.739 5，300.977 2，262.701 3和 432.343 8 km。车辆路径图如图3所示。

图3 车辆路径示意图Fig.3 Vehicle routing

若只考虑行车路径最短，得出的结果如下：路径长度为1 741.4 km，碳排放量为1 403.1 kg。完成配送需要4辆车，即载重50 t的车4辆。每辆车的装载量为 50，39，48和 49 t。路径长度分别为320.841 1，333.444 3，554.653 6和542.111 5 km。车辆路径示意图如图4所示。

图4 车辆路径示意图Fig.4 Vehicle routing

2 组数据对比如表3所示。

表3 2种结果对比分析Table3 Contrast of two kinds of results

由上面的数据可以看出，当只考虑路径最短时，需要4辆车来完成，总路径长度为1 741.4 km。碳排放量为 1 403.1 kg。当考虑燃油消耗以及碳排放成本时，需要 7辆车来完成，路径长度为2 197.3 km，碳排放量1 020.1 kg。

上述数据说明，当只考虑路径最短时，需要尽可能的利用载重量较大的车，本例中使用了4辆50 t的车。当考虑燃油消耗时，由于大车的燃油消耗率过高，导致车辆燃油消耗以及碳排放成本升高，因此利用载重量较小的车来配送成本更低。

由此可以发现，路径最短的路线不一定是能耗最小的路线。在本案例中，由于大型车辆的燃油消耗高于中型车辆，因此在优化过程中，就选择了利用中型车辆来完成配送以减轻成本。如上表中的分析，后者比前者的路径长度增加了 26.18%，然而，碳排放量却减少了27.3%。

为了更好的说明这个问题，现在将多车型问题改写为单车型问题，分 3种车型分别讨论：

1）当只考虑50 t车型时，总成本 5 117.2元。路径长度1 808.6 km，碳排放量1 724.1 kg，车辆装载分别为37，40，34，50和25 t。

2）当只考虑30 t车型时，总成本 4 580.5元。路径长度2 156.8 km，碳排放量 875.9 kg，车辆装载分别为21，28，18，30，16，22，25和26 t。

3）当只考虑20 t车型时，总成本 3 696.9元。路径长度2 652.8 km，碳排放量717.9 kg，车辆装载分别为13，10，20，18，17，11，18，6，19，19，19和16 t。

以上3种类型的对比分析如表4所示。

表4 单一车辆仿真结果分析Table4 Analysis of simulation results of a single vehicle

以上的数据充分说明了当考虑最短路径时，应当充分使用载重量较大的车辆来进行运输，但如果考虑能耗问题的话，由上面的分析可以发现大型车辆由于单位距离能耗过大，导致最短的运输路径并没有对应于最小的能源消耗。因此，在考虑能耗时，应当综合优化，充分考虑各种车辆的能源消耗率以及固定成本等因素。

3 结论

1）考虑了车辆运行过程中CO2排放的外部成本，最优车辆路径与传统的基于距离或者时间最短的车辆路径不一致。

2）基于 CO2排放的车辆路径优化结果中，其最优路径与车辆属性、车辆行驶速度和装载量密切相关。

3）当只考虑路径最短时，需要尽可能的利用载重量较大的车；当考虑燃油消耗时，由于大车的燃油消耗率过高，导致车辆燃油消耗以及碳排放成本升高，因此利用载重量较小的车来配送成本更低。

4）将车辆的碳排放水平设为静态，这与实际运作情况存在一定的差异。未来进一步的研究应该考虑基于时变速度的车辆 CO2排放问题，以便更科学的调度配送车辆，以获得最佳时间和最佳配送路线。

［1］Vicente.Laying the foundations for greener transport：transport indicators tracking progress towards environmental targets in Europe［R］.European Environment Agency，Copenhagen，Denmark，2011.

［2］Dantzig G B.The truck dispatching problem［J］.Management Science，1959，1（6）：50-53.

［3］陈锋.带时间窗约束的多类型车辆路径问题的改进节约算法［J］.科学技术与工程，2012，20（24）：6082-6086.CHEN Feng.The improved saving method of vehicle routing problem with time window［J］.Science Technology and Engineering，2012，20（24）：6082-6086.

［4］Duhamel，Lacomme，Prodhon.A hybrid evolutionary local search with depth first search split procedure for the heterogeneous vehicle routing problems［J］.Engineering Application of Artificial Intelligence，2012，25（2）：345-358.

［5］陈萍，黄厚宽，董兴业.求解多车型车辆路径问题的变邻域搜索算法［J］.系统仿真学报，2011，23（9）：1945-1950.CHEN Ping，HUANG Houkuan，DONG Xingye.Variable neighborhood search algorithm for fleet size and mixed vehicle routing problem［J］.Journal of System Simulation，2011，23（9）：1945-1950.

［6］党立伟，孙小明.多车场车辆路径问题及混合遗传算法［J］.科学技术与工程，2012，20（8）：1816-1820.DANG Liwei，SUN Xiaoming.Multi-depot vehicle routing problem with hybrid genetic algorithm［J］.Science Technology and Engineering，2012，20（8）：1816-1820.

［7］刘冉，江志斌，耿娜，等.半开放式多车场车辆路径问题［J］.上海交通大学学报，2010，15（11）：1539-1545.LIU Ran，JIANG Zhibin，DI Na，et al.The half open multi-depot vehicle routing problem［J］.Journal of Shanghai Jiaotong University，2010，15（11）：1539-1545.

［8］钟雪灵，王雄志.开放式车辆路径问题的混合算法［J］.计算机仿真，2011，28（8）：207-210，232.ZHONG Xueling，WANG Xiongzhi.Hybrid algorithm for open vehicle routing problem［J］.Computer Simulation，2011，28（8）：207-210，232.

［9］李相勇，田澎.开放式车辆路径问题的蚁群优化算法［J］.系统工程理论与实践，2008，28（6）：81-93.LI Xiangyong，TIAN Peng.Research on ant colony optimization algorithm for the open vehicle routing problem ［J］.Systems Engineering-Theory&Practice，2008，28 （6）：81-93.

［10］熊浩，符卓，鄢慧丽.动态车辆路径问题的隐分区灵活分批策略［J］.同济大学学报（自然科学版），2013，41（5）：676-681.XIONG Hao，FU Zhuo，YAN Huili.Virtual partition and flexible batch strategy of dynamic vehicle routing problem［J］.Journal of Tongji University（Natural Science），2013，41（5）：676-681.

［11］王明阳，陈鑫，张丽华.带油耗的单车场开放式车辆路径问题研究［J］.物流科技，2012（10）：18-21.WANG Mingyang，CHEN Xin，ZHANG Lihua.Research on a single depot open vehicle routing problem with fuel consumption［J］.Logistics Sci-Tech，2012 （10）：18-21.

［12］田丽娜.碳税政策下运输成本与碳排放的关系研究［C］//第六届中国智能交通年会暨第七届国际节能与新能源汽车创新发展论坛，北京：2011：3-7.TIAN Lina.Relationship of transportation cost and cabron emissions under the cabron tax policy［C］//The sixth sessionh of the china intelligent transport annual meeting and the seventh session of the internation alenergy souing and new energy antomoble forum on innovatoon and development，Beijing：2011：3-7.

［13］谢金星，刑文训.现代优化计算方法［M］.北京：清华大学出版社，1999.XIE Jinxing，XING Wenxun.Modern optimization methods［M］.Beijing：Tsinghua University Press，1999.

（编辑 蒋学东）

Research on an optimization model and its algorithm for vehicle routing problem based on CO2emission

ZHANG Dezhi1，QIAN Qi1，LI Shuangyan2，JIN Fangping1

（1.School of Traffic and Transportation Engineering，Central South University，Changsha 410075，China；2.College of Transportation&Logistics，Central South University of Forestry and Technology，Changsha 410004，China）

Logistics is not only the major part of energy consumption，but also an important source of CO2emissions.When considering the characteristics of energy consumption and CO2emission factors in vehicle routing problem with multiple vehicles，the corresponding optimization model was constructed，and a heuristic algorithm was given based on genetic algorithm.Finally，numerical simulation was performed for the model and solution algorithm.The results show that the shortest route is not always the least energy consumption route.When compared with the traditional shortest path vehicle routing，vehicle routing based on CO2emissions has a longer path length，but with a lower comprehensive cost.Genetic algorithm is an effective algorithm to solve the green vehicle routing problem.

logistics energy consumption；CO2emission；vehicle routing；optimization model；genetic algorithm

F275.5

A

1672-7029（2015）02-0424-06

2014-10-29

国家社科基金资助项目（11CGL032）；国家自然科学基金资助项目（71271220）

张得志（1976-），男，湖南祁东人，副教授，博士，从事物流系统优化研究；E-mail：dzzhang@mail.csu.edu.cn