控制与决策  2020, Vol. 35 Issue (10): 2486-2496  
0

引用本文 [复制中英文]

刘长石, 申立智, 盛虎宜, 吕雄鹰, 瞿艳平. 考虑交通拥堵规避的低碳时变车辆路径问题研究[J]. 控制与决策, 2020, 35(10): 2486-2496.
[复制中文]
LIU Chang-shi, SHEN Li-zhi, SHENG Hu-yi, LYU Xiong-ying, QU Yan-ping. Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches[J]. Journal of Southwest China Normal University (Natural Science Edition), 2020, 35(10): 2486-2496. DOI: 10.13195/j.kzyjc.2019.0257.
[复制英文]

基金项目

国家社会科学基金一般项目(17BJL091)

作者简介

刘长石(1975-), 男, 副教授, 博士, 从事物流管理、应急管理等研究, E-mail: liuchangshi964@126.com;
申立智(1983-), 男, 讲师, 硕士, 从事物流信息管理等研究, E-mail: slzzx1983@163.com;
盛虎宜(1974-), 男, 研究员, 博士, 从事物流管理与服务管理的研究, E-mail: shenghuyi@163.com;
吕雄鹰(1968-), 女, 副教授, 硕士, 从事国际贸易与现代物流等研究, E-mail: 813290512@qq.com;
瞿艳平(1969-), 男, 副教授, 博士, 从事物流管理、品牌管理等研究, E-mail: 363538377@qq.com

通讯作者

盛虎宜, E-mail: shenghuyi@163.com

文章历史

收稿日期:2019-03-06
修回日期:2019-06-19
考虑交通拥堵规避的低碳时变车辆路径问题研究
刘长石 1,2, 申立智 2,4, 盛虎宜 3, 吕雄鹰 5, 瞿艳平 1     
1. 湖南工商大学 工商管理学院,长沙 410205;
2. 湖南工商大学 移动商务智能湖南省重点实验室,长沙 410205;
3. 电子科技大学 经济与管理学院,成都 611731;
4. 湖南工商大学 人事处,长沙 410205;
5. 湖南工商大学 经济与贸易学院,长沙 410205
摘要:针对时变路网条件下的低碳车辆路径问题, 首先, 分析车辆离散行驶速度与连续行驶时间之间的关系, 依据“先进先出”准则设计基于时间段划分的路段行驶时间计算方法, 引入考虑车辆速度、实时载重、行驶距离与道路坡度因素的碳排放计算函数; 然后, 在此基础上以所有车辆的碳排放量最小为目标构建低碳时变车辆路径问题数学模型; 最后, 引入交通拥堵指数, 设计交通拥堵规避方法, 并根据模型特点设计一种改进蚁群算法求解.实验结果表明, 所提出方法能有效规避交通拥堵、缩短车辆行驶时间、减少车辆碳排放, 促进物流配送与生态环境和谐发展.
关键词时变路网    碳排放    车辆路径问题    交通拥堵    
Research on low-carbon time-dependent vehicle routing problem with traffic congestion avoidance approaches
LIU Chang-shi 1,2, SHEN Li-zhi 2,4, SHENG Hu-yi 3, LYU Xiong-ying 5, QU Yan-ping 1     
1. School of Management, Hunan University of Technology and Business, Changsha 410205, China;
2. Key Laboratory of Hunan Province for Mobile Business Intelligence, Hunan University of Technology and Business, Changsha 410205, China;
3. School of Economics and Management, University of Electronic Science and Technology of China, Chengdu 611731, China;
4. Department of Personnel, Hunan University of Technology and Business, Changsha 410205, China;
5. School of Economic and Trade, Hunan University of Technology and Business, Changsha 410205, China
Abstract: In order to solve the low-carbon vehicle routing problem under time-dependent network, the relationship between discrete vehicle travel speed and continuous vehicle travel time is analyzed. According to the principle of "first in first out", the calculation method of road travel time across time periods based on time division is designed. The calculation function of carbon emissions is employed by considering vehicle speed, real-time load of vehicle, vehicle travel distance and road slope. The mathematical model of the low-carbon time-dependent vehicle routing problem(LCTDVRP) is established with the goal of minimizing the total carbon emissions. The traffic congestion index is employed to design the traffic congestion avoidance approach. An improved ant colony algorithm is designed according to the characteristics of the LCTDVRP model. The experimental results show that the proposed approaches can effectively avoid traffic congestion, shorten vehicle travel time, reduce vehicle carbon emissions, and promote the harmonious development of logistics distribution and ecological environment.
Keywords: time-dependent network    carbon emissions    vehicle routing problem    traffic congestion    
0 引言

自哥本哈根会议以来, 世界各国纷纷提出低碳、环保、绿色的概念.我国政府承诺到2020年单位国内生产总值二氧化碳排放比2005年下降40 % ~ 45 %.交通运输是重要碳排放源之一, 汽车(尤其是货车)尾气排放已成为我国大中城市污染的主要来源.因此, 应尽可能推进低能耗、低污染、低排放的公路物流运输, 使物流运输发展与生态环境保护相协调.

发展低碳公路物流的关键在于科学规划车辆行驶路线, 即求解物流运输的车辆路径问题(vehicle routing problem, VRP).已有许多学者分别以总行驶距离最短、总配送费用最小、总行驶时间最短为目标研究了VRP[1-4].这些文献具有一定参考价值, 但主要强调经济目标, 忽略了能源消耗与环境影响.随着研究的进展, 有些学者探讨了物流运输车辆的碳排放与能源消耗问题.文献[5]提出计算车辆碳排放与能源消耗的MEET模型.文献[6]比较分析了常用的6种碳排放与能源消耗模型.文献[7-8]综合考虑车辆速度、载重与道路状况等因素设计碳排放计算模型.这些模型具有科学性与合理性, 已经应用于许多文献.随后, 部分学者研究了以降低车辆能耗与碳排放为目标的低碳VRP.文献[9]以总成本最小为目标构建基于碳排放的多车型VRP模型.文献[10]建立以能耗最低与碳排放量最小为目标的VRP模型.文献[11-12]以车辆固定使用成本、油耗与碳排放成本之和最小为目标构建VRP模型.文献[13]分别以经济成本最小、环境成本最小、经济成本与环境成本之和最小为目标构建3种VRP模型.文献[14]以燃料排放成本与驾驶员工资之和最小为目标构建开放式VRP模型.文献[15]建立以燃料消耗最小为目标的低碳VRP模型, 设计两阶段邻域搜索算法求解.文献[16]在考虑道路坡度因素的基础上, 构建以车辆能耗最小为目标的低碳VRP模型.文献[17]考虑车辆能耗、碳排放和租车费用等因素, 以总配送费用最小为目标建立低碳VRP模型.文献[18]考虑车载量的实时变化及其对油耗与碳排放量的影响, 并给出市区小范围配送网络内的最优VRP决策.这些研究能有效促进节能减排.

由于城市早晚交通高峰、路段限速、交通管制与意外事故等原因, 城市交通路网具有时变特性.最近, 部分学者研究了时变路网条件下的车辆路径问题(time-dependent vehicle routing problem, TDVRP).文献[19]以系统总成本最小为目标构建TDVRP模型.文献[20]以最短行驶时间与最低油耗为目标构建TDVRP模型, 并设计不同交通拥堵场景进行实验.文献[21]以碳排放量最小为目标构建TDVRP模型.文献[22]以车辆行驶距离最短、油耗最小为目标构建TDVRP模型, 设计改进粒子群算法求解.文献[23]以总配送费用最小为目标构建TDVRP模型, 设计基于动态规划的启发式算法求解.文献[24]以碳排放量最小为目标构建TDVRP模型, 采用禁忌搜索算法求解.这些文献为后续研究提供有益借鉴.

已有成果为深入研究低碳物流运输问题提供了良好基础, 但仍存如下研究缺口: 1)已有研究大多关注TDVRP的数学模型与求解算法, 关于交通拥堵规避的研究文献相对缺乏.交通拥堵已经成为一种常见现象, 尤其在大中城市.交通拥堵导致车辆行驶时间延长、车辆能源消耗与碳排放量显著增加, 严重影响城市环境, 亟待系统深入研究. 2)已有文献采用的碳排放计算模型大都只考虑车辆速度、载重与行驶距离等因素, 较少考虑道路坡度因素. 3)已有研究大都假设所有车辆同时在0时刻从物流中心出发, 关于车辆根据需要在不同时刻出发的研究文献不多.尽管已有文献[25-26]将交通拥堵信息分为重复性拥堵和非重复性拥堵两种类型, 首先采用重复性拥堵信息规划车辆初始路径, 再根据接收到的实时交通信息调整车辆行驶路线; 文献[27]提出了4种交通拥堵规避策略; 文献[28]研究了基于车辆不同出发时间的TDVRP, 但都没有全部考虑.因此, 本文针对以上研究缺口, 探讨带交通拥堵规避方法的低碳时变车辆路径问题(low-carbon time-dependent vehicle routing problem, LCTDVRP)的数学模型与求解算法, 以期能为企业实施低碳物流提供决策参考.

1 问题描述

一个物流中心为多个客户提供配送服务, 客户地址、需求量、时间窗与服务时间已知, 客户需求量小于车辆容量.车辆装载量不能超过容量, 可以提前到达客户位置, 但必须等待至该客户最早服务时间才能配送.为明确本文适用范围, 提出如下假设:

1) 配送车辆为同一类型, 可以根据需要在不同时刻从物流中心出发, 完成任务后回到物流中心;

2) 交通路网具有时变特性, 配送车辆在不同时间段内以不同时速行驶;

3) 道路具有不同坡度;

4) 各客户有且仅有一辆车为其服务;

5) 当配送车辆遇到严重交通拥堵时, 在路上短暂停靠, 规避交通拥堵;

6) 车辆在行驶时间内产生碳排放, 在其余时间内发动机关闭, 不产生碳排放.

决策问题:如何制定配送计划, 满足客户需求并使得所有车辆的碳排放量最小?

2 数学模型 2.1 跨时间段的路段行驶时间计算方法

时变路网条件下的车辆速度不但与发车时间相关, 而且与道路状况有关.不同时间段内的车辆速度不同, 车辆行驶完路段(i, j)全程可能需要跨越多个时间段, 行驶时间难以直接计算, 需要合理处理.

已有VRP研究文献普遍采用车辆不停靠策略, 即车辆k在从节点i行驶到节点j的过程中, 无论遇到什么情况, 车辆k都处于行驶状态, 发动机不关闭.

Ichoua模型[29]认为车辆在足够短时间段内的实时行驶速度可以视作其在该时间段内的固定速度.已有许多文献依据“先进先出”准则采用Ichoua模型计算时变路网条件下的路段行驶时间[21.25].本文参考已有方法, 分析车辆离散行驶速度与连续行驶时间之间的关系, 依据“先进先出”准则设计采用车辆不停靠策略的路段行驶时间计算方法(如图 1): 1)将配送中心的工作时间平均划分为多个时间段; 2)不同时间段内车辆行驶在路段(i, j)上的行驶速度如图 1(a)所示; 3)不同时间段内车辆行驶在路段(i, j)上的行驶距离与行驶时间如图 1(b)所示; 4)图 1(a)图 1(b)的时间段一一对应, 图 1(a)各时间段内的行驶速度与图 1(b)所示的行驶距离具有关联关系, 根据图 1(a)各时间段内的车辆行驶速度与图 1(b)各时间段内的车辆行驶距离, 可以计算车辆在各时间段内的行驶时间, 从而得出车辆行驶完路段(i, j)全程的行驶时间.在图 1所示方法的基础上, 设计拥堵停靠策略下车辆行驶完路段(i, j)全程的总使用时间计算方法(如图 2):如果车辆在当前时间段内遇到严重交通拥堵, 车辆在路上停靠等待(发动机关闭, 速度为0);否则, 车辆按已有路径方案行驶.

图 1 采用车辆不停靠策略的路段行驶时间计算方法
图 2 拥堵停靠策略下车辆行驶完路段全程的总使用时间计算方法

H为时间段的固定时间长度; T={T0, T1, T2, …, TL}为物流中心的工作时间段集合; [TR-1, TR]为第R个时间段; tijkR为时间段R内车辆k在路段(i, j)上的行驶时间; hijkR为时间段R内车辆k在路段(i, j)上的停靠等待时间; sijkR为时间段R内车辆k在路段(i, j)上的行驶速度; FijkR为时间段R内车辆k在路段(i, j)上的行驶距离; Jij为路段(i, j)的距离, ; JijR为时间段R之后车辆k继续行驶完路段(i, j)全程需要行驶的距离.

假定车辆k从节点i的出发时间Dik属于时间段R, 即Dik∈[TR-1, TR], Rk为车辆k在时间段R内的可使用时间, Rk=HR-Dik.车辆k行驶完路段(i, j)全程的总使用时间tijk的计算步骤具体如下:

step 1:开始时间段的车辆行驶时间与停靠等待时间计算.

step 1.1:如果车辆在时间段R内遇到严重交通拥堵, 则车辆停靠, hijkR=Rk, FijkR =0, JijR =Jij -FijkR, 则转step 2;否则转step 1.2.

step 1.2: FijkR =sijkR Rk, 如果FijkRJij, tijkR =Jij/sijkR, 则转step 3;否则, JijR =Jij-FijkR, tijkR=Rk.

step 2:其余时间段的车辆行驶时间与停靠等待时间计算.

step 2.1:令ξ =1.

step 2.2:如果车辆在时间段R+ξ内遇到严重交通拥堵, 车辆停靠, hijkR+ξ=H, FijkR+ξ =0, JijR+ξ =JijR+ξ-1-FijkR+ξ, ξ =ξ+1, 则转step 2.2;否则, 转step 2.3.

step 2.3: FijkR+ξ =sijkR+ξH, 如果FijkR+ξ < JijR+ξ-1, tijkR+ξ=H, JijR+ξ=JijR+ξ-1-FijkR+ξ, ξ=ξ+1, 则转step 2.2;否则, tijkR+ξ =JijR+ξ-1/sijkR+ξ.

step 3:计算车辆k行驶完路段(i, j)全程的总行驶时间tijkx、总停靠等待时间tijks与总使用时间tijk. , , tijk=tijkx +tijks=.

2.2 符号与变量

符号: V为配送车辆集合; Q为车辆容量; C为客户集合; N为配送网络内的所有节点集合, N=0∪C, 其中0表示物流中心; di为客户i的需求量; gi为客户i的服务时间; [Bi, Ei]为客户i的时间窗; aik为车辆k到达节点i的时间; qik为车辆k到达节点i时的等待时间, 如果aik < Bi, 则qik =Bi-aik, 否则qik =0;cijkR为时间段R内车辆k在路段(i, j)上行驶单位距离产生的碳排放量.

决策变量: xijk为0-1变量, 当车辆k从节点i行驶到节点j时值为1, 否则为0; yik为0-1变量, 当节点i由车辆k服务时值为1, 否则为0.

2.3 数学模型

以所有车辆的碳排放量最小为目标, 构建LCTDVRP数学模型如下:

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)

式(1)为目标函数, 最小化所有车辆的碳排放量.式(2)表示每个客户必须且只能被服务一次.式(3)保证车辆到达与离开的是同一个节点.式(4)表示每辆车最多只能使用一次.式(5)表示路段距离与各时间段内的车辆行驶距离之间的关系.式(6)表示车辆行驶完路段全程的总使用时间与各时间段内的车辆行驶时间及停靠等待时间之间的关系.式(7)与(8)表示客户的时间窗约束.式(9)表示车辆到达客户时间、等待时间、服务时间与车辆离开客户时间之间的关系.式(10)表示车辆从上一个节点行驶到下一个节点之间的时间关系.式(11)表示车辆容量约束.式(12)表示变量的取值约束.

2.4 车辆碳排放量计算

MEET模型[5]适用范围较广, 已有许多文献采用MEET模型计算车辆碳排放量[6, 8].因此, 本文采用MEET模型计算车辆碳排放量, 具体如下.

时间段R内车辆k在路段(i, j)上行驶单位距离产生的碳排放率(kg/km)为

(13)

其中: e=(110+0.000 375v3+8 702/v), 表示车辆空载且以速度v (v=sijkR)行驶在坡度为0的道路上的碳排放率(g/km); Gij为路段(i, j)的坡度修正因子; ψijk为车辆k在路段(i, j)上行驶时的载重修正因子.

路段(i, j)的坡度修正因子Gij

(14)

其中ϖij为路段(i, j)的坡度(%).

车辆k的载重修正因子ψijk

(15)

其中γijk为车辆k在路段(i, j)上行驶时的实时载重与容量的比值, γijk∈[0, 1].

3 求解算法

VRP已被证明是NP-hard问题, 难以求得最优解, 通常采用启发式算法求出满意解.带交通拥堵规避方法的LCTDVRP更复杂, 求解更加困难.蚁群算法是一种启发式全局优化算法, 具有分布计算、信息正反馈和启发式搜索等特征, 能有效解决各领域的复杂组合优化问题[30].因此, 根据问题与模型的特点, 本文设计一种改进蚁群算法求解LCTDVRP, 思路如下: 1)设计一种交通拥堵规避方法; 2)将每只蚂蚁随机放置在各节点, 每只蚂蚁的行驶路径作为一个可行解; 3)考虑到车辆可能产生等待时间, 在蚁群算法的状态转移规则中引入等待时间因素.

3.1 交通拥堵规避方法

已有文献普遍采用车辆不停靠策略, 即车辆k在从节点i行驶到节点j的过程中, 无论遇到什么情况, 车辆k都一直行驶, 发动机都处于工作状态.在时变路网条件下, 如果车辆k在从节点i行驶到节点j的过程中遇到严重交通拥堵, 则采用车辆不停靠策略使得车辆k在交通拥堵时间段内以非常缓慢的速度行驶, 使得车辆k行驶完路段(i, j)全程的行驶时间成倍延长, 车辆油耗与碳排放量剧增.不停靠策略下车辆k行驶完路段(i, j)全程的车辆行驶时间、客户服务时间与车辆使用时间之间的关系如图 3所示.

图 3 采用车辆不停靠策略的车辆使用时间

随着交通技术与信息技术的发展, 综合采用人工智能、交通大数据与智慧停车等方法, 能有效识别并规避交通拥堵.例如2011年5月北京市发布了交通拥堵指数.该交通拥堵指数的最小计算时间单位是15 min(即每15 min发布一次), 取值范围为0 ~ 10, 一共分为5个级别.数值0 ~ 2对应“畅通”、3 ~ 4表示“基本畅通”、5 ~ 6表示“轻度拥堵”、7 ~ 8表示“中度拥堵”、9 ~ 10表示“严重拥堵”.交通拥堵指数的数值越高, 表明交通拥堵越严重.据此, 本文设计一种交通拥堵规避方法, 即如果车辆在路段(i, j)上行驶时, 车载设备接收到的交通拥堵指数表示当前时间段内路段(i, j)存在严重交通拥堵, 车辆在路段(i, j)上短暂停靠, 避开交通拥堵时间段, 发动机在停靠时间段内关闭; 否则车辆按已有路径规划方案继续行驶.车辆k采用交通拥堵规避方法行驶完路段(i, j)全程的行驶时间、停靠等待时间、客户服务时间与车辆使用时间之间的关系如图 4所示.

图 4 采用交通拥堵规避方法的车辆使用时间

对比分析图 3图 4可知, 相对于车辆不停靠策略, 当遇到交通拥堵情况时, 决策者采用交通拥堵规避方法能有效缩短车辆行驶时间, 但在某些路段上可能会增加车辆停靠等待时间, 车辆总使用时间将略有增加.基于节能减排视角, 交通拥堵规避方法能有效降低车辆油耗与碳排放、减少环境污染.

3.2 改进蚁群算法

改进蚁群算法的具体步骤如下.

step 1:初始化.初始化算法所有变量与参数, 令iter为当前迭代次数、max iter为最大迭代次数、bestcarbon为最优碳排放量.将物流中心工作时间平均分为L个时间段, 令iter=1.

step 2:构建可行解.

step 2.1:将M只蚂蚁随机放置在不同节点.

step 2.2:依次派出每只蚂蚁, 将当前蚂蚁m的所有未访问节点放入集合Wm, 令禁忌表tabum=∅.

step 2.3:令loadmk=Q为蚂蚁m的当前使用车辆k的初始装载量, Xk为车辆k的新增车辆标识, 且Xk =1.

step 2.4:采用跨时间段的路段行驶时间计算方法结合交通拥堵规避方法, 计算车辆k到达节点j (jWm)的时间ajk与等待时间qjk.

step 2.5:计算车辆k从当前节点i行驶到节点j的转移概率

(16)

其中: τij为信息素浓度; ηij为能见度, ηij=1/Jij; δμε分别为各种因子的重要性.

step 2.6:找出Pijm值最大的节点jmax, 如果该节点满足[Bjmax, Ejmax]与loadmk等条件, 则tabumi+1 =jmax, jmaxWm, loadmk=loadmk-djmax; 否则, 车辆k返回物流中心, tabumi+1=0, k=k+1, 转step 2.3.

step 2.7:如果Xk=1, 则计算车辆k的出发时间Sk, 令Xk =0.

step 2.8:如果Wmϕ, 则转step 2.4, 否则, m=m+1;如果mM, 则转step 2.2.

step 3:当前迭代结果计算.计算当前迭代的最优碳排放量carbonitermin, 如果carbonitermin≤ bestcarbon, 则bestcarbon=carbonitermin.

step 4:信息素更新.对本次迭代中最优路径的组成路段进行全局信息素更新, 即

(17)
(18)

其中: ρ为信息素挥发性, 0≤ρ < 1;Δτijm为蚂蚁m在路段(i, j)上信息素增加数量; A为常数; fm为蚂蚁m的碳排放量.

step 5:算法结束判断.如果iter≤max iter, iter =iter+1, 则转step 2;否则, 算法结束.

4 算例分析 4.1 实验设置

由于目前没有LCTDVRR的标准测试数据库, 采用Solomon的VRP数据库[31]中的算例C104、C105、C106、C107、C108、C109、R204、R205、R206、R207、R208、R209、R210、R211、RC202、RC203、RC205、RC206、RC207与RC208的客户坐标、需求量、时间窗与服务时间等数据作为本文测试数据.以上算例分为3种类型: C类型、R类型和RC类型算例的客户坐标分别属于集中分布、随机分布和混合分布(同时存在随机分布与集中分布).每个算例都有100个客户与一个配送中心.另外, 为符合测试要求, 补充如下数据:

1) 设定配送中心的总工作时间为960 min, 最早工作时间为7: 00 (即0时刻, 对应算例中配送中心的ready time, 即0 min), 最晚工作时间为23: 00 (对应配送中心的due time, 即960 min).

2) 考虑到北京市交通拥堵指数的最小计算时间单位是15 min, 设定本文每个时间段的时间长度为15 min.

3) 根据城市交通规律, 将8: 00 ~ 9: 00、18: 00 ~19: 00设为早晚高峰时间段, 其余时间设为普通时间段, 早晚高峰时间段的车辆行驶速度设定为20 km / h.

4) 令ϖ=0.1, 将[60 (1-ϖ), 60 (1+2ϖ), 60 (1-3ϖ)]设定为3种车辆速度.采用求余函数λ=bmod(R, 3), 当λ分别取值[1, 2, 0]时, 分别对应普通时间段内车辆的3种时变速度.

5) 将早晚高峰时间段的任意路段、在λ=0时间段内的车辆行驶路段的交通拥堵指数定义为9 ~ 10, 即“严重拥堵”.

6) 路段(i, j)的坡度ϖij设定为:如果i < j, 则ϖij =(i/j)/20;否则, ϖij=-(i/j)/20.

算法采用Matlab R2016a编程, 在处理器为1.8 GHz、内存为8 G的微机上运行.参考文献[28, 30]的方法, 将程序参数设置如下: Q=1 000单位、m=30、maxiter=600、τij=20、δ=2、μ=2、ε=1.5、A=20、ρ=0.15.

4.2 实验结果分析 4.2.1 交通拥堵规避方法的效果分析

为验证本文交通拥堵规避方法的有效性, 还采用Matlab R2016a编写了本文方法的遗传算法(GA)程序, 将本文带交通拥堵规避方法的改进蚁群算法(IACA)与文献[32]的蚁群算法(ACA)以及GA进行比较实验. ACA与GA都设定所有车辆在0时刻从物流中心出发, 且不带交通拥堵规避方法.设定GA的种群数量为200, 迭代次数为600.实验算例C107、C108与C109的客户坐标属于集中分布, 算例R208、R209、R210与R211的客户坐标属于随机分布, 算例RC205、RC206与RC207的客户坐标属于混合分布.实验结果如表 1所示.其中TCO2表示所有车辆的碳排放量(单位: kg), TTT表示车辆的总行驶时间(单位: min), TUT表示车辆的总使用时间(单位: min), TTD表示车辆的总行驶距离(单位: km).

表 1 IACA与ACA的计算结果

表 1可知:

1) IACA在所有算例都能取得TCO2的最优解.与ACA相比较, IACA的最高节约比率达到26.06 % (算例R211), 最低节约比率为3.18 %(算例R209), 平均节约比率为12.84 %.与GA相比较, IACA的最高节约比率达到57.77 %(算例C107), 最低节约比率为21.69 %(算例R209), 平均节约比率为36.64 %.说明交通拥堵规避方法确实能有效降低车辆碳排放.

2) IACA在所有算例都能求得TTT的最优值.与ACA比较, IACA最高节约比率达到17.06 %(算例R208), 最低节约比率为1.09 %(算例C109), 平均节约比率为9.56 %.与GA相比较, IACA的最高节约比率达到56.9 %(算例C107), 最低节约比率为1.36 %(算例R210), 平均节约比率为22.97 %.说明交通拥堵规避方法能有效缩短车辆行驶时间.

3) 关于TUT, IACA在大部分算例的计算结果都略高于ACA, 平均超过比率为8.91 %, 但IACA在所有算例的计算结果低于GA.这恰好表明了本文交通拥堵规避方法的理论分析:交通拥堵规避方法可能在某些案例下会使得车辆总使用时间稍有增加.

4) 从TTD来看, IACA在所有算例的行驶距离要稍微大于ACA的计算结果, 平均超过比率仅为3.46 %, 但IACA在所有算例都要低于GA.这恰好验证了文献[27, 33]中提出的路径选择优化方法:即如果车辆选择的最短路径遇到严重拥堵时, 车辆可以选择另外一条没有拥堵的次短路径, 从而避开交通拥堵, 缩短车辆行驶时间.说明本文设计的交通拥堵规避方法与文献[27, 33]设计的路径选择优化方法具有同样的优化效果.因此, 基于节能减排的视角, IACA优于ACA与GA, 能有效规避交通拥堵、缩短车辆行驶时间、减少车辆碳排放.

4.2.2 车辆路径规划结果分析

为验证本文IACA的稳定性, 采用算例RC208进行测试, 将程序运行10次, 每次求得的路径规划结果如表 2所示.

表 2 算例RC208的车辆路径规划方案

表 2中: CN为测试次数, VN为车辆使用数量(单位:辆), GT为所有车辆为规避交通拥堵在路上的停靠等待时间(单位: min), avg为平均值, CPUT为程序运行时间(单位: min), 其余符号的含义同表 1.

表 2可知:

1) 从TCO2来看, 最大值为529.81 kg, 最小值为493.57 kg, 平均值为518.01 kg, 浮动范围为[-2.28 %, +2.93 %]之内.说明IACA程序每次运行求得的目标函数值都比较接近, 算法具有稳定性.

2) 从GT的值来看, GT占车辆总使用时间(TUT)的比例最高达到21.55 %, 最低占16.51 %, 平均值为18.25 %, 说明本文设计的IACA为规避交通拥堵需要一定的停靠等待时间, 将使得车辆总使用时间有所增加.

3) 从CPUT来看, 最大运行时间为226.88 s, 最小运行时间为220.25 s, 平均运行时间为223.05 s.说明IACA能在较短时间内给出决策者满意解.

4) 在所有方案中, 最优车辆路径规划方案中的TTT、TUT、TTD与VN的值都不是最小值, 说明车辆碳排放受到行驶距离、行驶速度、车辆载重与道路坡度等多个因素的共同影响, 单独优化其中一个因素或者少数因素, 难以取得最优值.

算例RC208的最优车辆路径规划方案如图 5所示. 图 5(a)表示车辆行驶路线, 其中的菱形表示物流中心; 图 5(b)中, 带倒三角形的曲线与实线曲线分别为ACA与IACA求得的目标函数均值的适应度曲线.由图 5(a)可知, IACA使得配送车辆尽最大可能配送同一个区域的客户, 从而缩短车辆行驶距离、减少车辆行驶时间、降低车辆碳排放.由图 5(b)可知, IACA的目标函数值优于ACA的目标函数值; ACA大约在500代以后收敛, IACA大约在400代以后收敛.说明IACA比ACA具有更好的收敛性, 能有效解决早熟收敛问题, 在进化初期可以使种群具有多样性、在进化后期可以加快收敛速度, 实现决策目标.

图 5 算例RC208的最优车辆路径规划方案

算例RC208的最优车辆路径规划如表 3所示. 表 3中的N表示路线序号, RN表示路线的客户顺序(0表示物流中心, 其余数字表示客户序号), RT表示车辆抵达客户后开始配送的时间(首尾数字分别表示车辆从物流中心的出发时间与车辆回到物流中心的时间), STP表示车辆从物流中心出发的时间段.

表 3 算例RC208的最优车辆路径规划

表 3可知:

1) 从RN来看, 一共使用7辆配送车辆, 各车辆的配送任务有所差异, 车辆2的配送客户多达21个, 车辆7的配送客户只有3个, 其余车辆的配送客户均为15个左右, 这是因为车辆路径规划同时受到车辆载重、客户需求量、时间窗、服务时间与时变网络等因素约束.

2) 从RT来看:车辆2与车辆3同时进入早晚高峰时间段; 车辆1、车辆6与车辆7只进入早高峰时间段, 避开了晚高峰时间段; 车辆4与车辆5避开早高峰时间段, 进入了晚高峰时间段.这说明部分客户的时间窗属于早晚高峰时间段, 物流中心必须按照客户需求进行配送规划; 同时也说明了本文方法能有效规避早晚高峰时间段的交通拥堵, 减少车辆碳排放.

3) 本文方法还能有效规避车辆路径在普通时间段内的交通拥堵.例如车辆1从92号客户行驶到95号客户的过程中, 采用交通拥堵规避方法避开了第3时间段的交通拥堵; 从62号客户行驶到67号客户的过程中, 采用交通拥堵规避方法避开了第9时间段的交通拥堵.

4) 从STP来看, 车辆4在第14时间段出发, 车辆5在第16时间段出发, 其余车辆都在第1时间段从物流中心出发.如果所有车辆都在0时刻从物流中心出发, 则必然增加车辆等待时间, 延长车辆使用时间.说明本文方法能根据需要合理规划车辆出发时刻, 有效减少车辆等待时间与车辆使用时间, 降低人力成本.

4.2.3 不同优化目标的车辆路径规划结果分析

为检验本文方法在不同优化目标下的有效性, 将本文以所有车辆的碳排放量最小为优化目标的车辆路径规划与以车辆总行驶距离最短、以总配送成本最小为优化目标的车辆路径规划进行对比实验.

以车辆总行驶距离最短为目标的数学模型的目标函数如下:

(19)

f为车辆使用的固定成本, p为车辆停靠、等待与服务时间产生的单位时间成本, w为车辆行驶时间产生的单位时间成本. zk为0-1变量, 当车辆k被使用时值为1, 否则为0.以总配送成本最小为目标的数学模型的目标函数如下:

(20)

总配送成本包括车辆使用的固定成本和变动成本.变动成本包括车辆停靠、等待与服务时间产生的时间成本与车辆行驶时间成本.

以上2个数学模型的约束条件与以碳排放量最小为优化目标数学模型的约束条件相同.参考文献[19]的方法, 将配送成本参数设置如下: p=0.3元/ min、f =150元/辆车、w=0.7元/ min.实验采用算例C103、C104、C105、C106、R204、R205、R206、R207、RC202与RC203, 计算结果如表 4所示.其中TTC表示总配送成本(单位:元), 其余符号的含义同表 1.

表 4 不同优化目标的车辆路径规划结果

表 4可知:

1) 本文算法在不同优化目标都能取得比其他优化目标更优的目标函数值, 说明本文方法在不同优化目标下都是可行的、有效的.

2) 算例在以碳排放最小为目标求得的碳排放量分别比以行驶距离最短为目标、以总配送成本最小为目标求得的碳排放量平均要少9.36 %与17.16 %, 求得的总行驶距离比以行驶距离最短为目标求得的总行驶距离平均要高5.39 %、比以总配送成本最小为目标求得的总行驶距离平均要低0.91 %, 求得的总配送成本分别比以行驶距离最短为目标、以总配送成本最小为目标求得的总成本平均要高0.91 %与11.56 %.说明以碳排放为优化目标增加了一定的配送费用, 物流企业节能减排将会增加一定的配送成本.为促进绿色物流, 保护环境, 政府部门应制定相应的绿色物流引领政策.

5 结论

交通拥堵已经成为大中城市的一种常见现象, 导致车辆行驶时间延长、车辆能源消耗与碳排放量显著增加, 对城市环境造成严重影响.本文针对时变路网条件下的低碳车辆路径问题, 首先设计基于时间段划分的路段行驶时间计算方法, 引入碳排放计算函数; 在此基础上以所有车辆的碳排放量最小为目标构建LCTDVRP数学模型; 再引入交通拥堵指数, 设计交通拥堵规避方法, 并根据模型特点设计一种改进蚁群算法求解.通过实验发现: 1)交通拥堵规避方法能有效缩短车辆行驶时间, 减少车辆碳排放, 但在某些算例上将增加可接受范围内的车辆使用时间、稍微延长车辆行驶距离; 2)车辆碳排放受到车辆行驶时间、行驶距离、行驶速度、车辆实时载重与道路坡度等多个因素的共同影响, 单独优化其中一个因素或者少数因素, 难以取得最优值; 3)物流企业节能减排将会增加一定的配送成本.为促进绿色物流, 保护环境, 政府相关部门应制定相应的绿色物流引领政策.

交通拥堵具有一定的规律性, 同时也具有偶然性与突发性.因此, 时变路网条件下的车辆实时调度问题, 将是未来的研究方向.

参考文献
[1]
张建勇, 李军, 郭耀煌. 具有模糊预约时间的VRP混合遗传算法[J]. 管理科学学报, 2005, 8(3): 64-71.
(Zhang J Y, Li J, Guo Y H. Hybrid genetic algorithm to vehicle routing problem with fuzzy due time[J]. Journal of Management Science in China, 2005, 8(3): 64-71.)
[2]
张涛, 余绰娅, 刘岚, 等. 同时送取货的随机旅行时间车辆路径问题方法[J]. 系统工程理论与实践, 2011, 31(10): 1912-1920.
(Zhang T, Yu C Y, Liu L, et al. Method for the stochastic traveling timeVRPSPD problem[J]. Systems Engineering-Theory & Practice, 2011, 31(10): 1912-1920.)
[3]
潘震东, 唐加福, 韩毅. 带货物权重的车辆路径问题及遗传算法[J]. 管理科学学报, 2007, 10(3): 23-29.
(Pan Z D, Tang J F, Han Y. Vehicle routing problem with weight coefficients[J]. Journal of Management Science in China, 2007, 10(3): 23-29.)
[4]
陈萍, 黄厚宽, 董兴业. 求解卸装一体化的车辆路径问题的混合启发式算法[J]. 计算机学报, 2008, 31(4): 565-573.
(Chen P, Huang H K, Dong X Y. A hybrid heuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup[J]. Chinese Journal of Computers, 2008, 31(4): 565-573.)
[5]
Hickman J, Hassel D, Joumard R, et al.Methodology for calculating transport emissions and energy consumption[R].London: Deliverable for EU project MEET, 1999.
[6]
Demir E, Bektas T, Laporte G. A comparative analysis of several vehicle emission models for road freight transportation[J]. Transportation Research, Part D, 2011, 16(5): 347-357. DOI:10.1016/j.trd.2011.01.011
[7]
Kirschstein T, Meiselb F. GHG-emission models for assessing the eco-friendliness of road and rail freight transports[J]. Transportation Research, Part B:Methodological, 2015, 73(1): 13-33.
[8]
Naderipour M, Alinaghian M. Measurement, evaluation and minimization of CO2, NO, and CO emissions in the open time dependent vehicle routing problem[J]. Measurement, 2016, 90: 443-452. DOI:10.1016/j.measurement.2016.04.043
[9]
Kwon Y, Choi Y, Lee D. Heterogeneous fixed fleet vehicle routing considering carbon emission[J]. Transportation Research Part D, 2013, 16(5): 81-89.
[10]
Suzuki Y. A dual-objective metaheuristic approach to solve practical pollution routing problem[J]. International Journal of Production Economics, 2016, 176(6): 143-153.
[11]
Zhang J H, Zhao Y X, Xue W L, et al. Vehicle routing problem with fuel consumption and carbon emission[J]. International Journal of Production Economics, 2015, 170: 234-242. DOI:10.1016/j.ijpe.2015.09.031
[12]
Li J, Wang D P, Zhang J H. Heterogeneous fixed fleet vehicle routing problem based on fuel and carbon emissions[J]. Journal of Cleaner Production, 2018, 201: 896-908. DOI:10.1016/j.jclepro.2018.08.075
[13]
Jabir E, Panicker V V, Sridharan R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem[J]. Transportation Research Part D, 2017, 57: 422-457. DOI:10.1016/j.trd.2017.09.003
[14]
Niu Y Y, Yang Z H, Chen P, et al. Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost[J]. Journal of Cleaner Production, 2018, 171: 962-971. DOI:10.1016/j.jclepro.2017.10.001
[15]
吴丽荣, 胡祥培, 饶卫振. 考虑燃料消耗率的车辆路径问题模型与求解[J]. 系统工程学报, 2013, 28(6): 804-811.
(Wu L R, Hu X P, Rao W Z. New capacity-vehicle-routing-problem model and algorithm for reducing fuel consumption[J]. Journal of Systems Engineering, 2013, 28(6): 804-811.)
[16]
饶卫振, 金淳, 王新华, 等. 考虑道路坡度因素的低碳VRP问题模型与求解策略[J]. 系统工程理论与实践, 2014, 34(8): 2092-2105.
(Rao W Z, Jin C, Wang X H, et al. A model of low-carbon vehicle routing problem considering road gradient and its solving strategy[J]. Systems Engineering-Theory & Practice, 2014, 34(8): 2092-2105.)
[17]
李进, 傅培华, 李修琳, 等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学, 2015, 23(10): 98-107.
(Li J, Fu P H, Li X L, et al. Study on vehicle routing problem and tabu search algorithm under low-carbon environment[J]. Chinese Journal of Management Science, 2015, 23(10): 98-107.)
[18]
马秋卓, 王健, 宋海清. 市区小范围多车辆低碳VRP:以珠海速递公司区域收件网络为例[J]. 管理工程学报, 2016, 30(4): 153-159.
(Ma Q Z, Wang J, Song H Q. Small-scaled low carbon multi-vehicle routing problem in urban area:An example from the regional picking-up network of zhuhai express company[J]. Journal of Industrial Engineering/Engineering Management, 2016, 30(4): 153-159. DOI:10.13587/j.cnki.jieem.2016.04.019)
[19]
吴瑶, 马祖军. 时变路网下带时间窗的易腐食品生产-配送问题[J]. 系统工程理论与实践, 2017, 37(1): 172-181.
(Wu Y, Ma Z J. Time-dependent production-delivery problem with time windows for perishable foods[J]. Systems Engineering-Theory & Practice, 2017, 37(1): 172-181.)
[20]
Jabbarpour M R, Noor R M, Khokhar R H. Green vehicle traffic routing system using ant-based algorithm[J]. Journal of Network and Computer Applications, 2015, 58: 294-308. DOI:10.1016/j.jnca.2015.08.003
[21]
Xiao Y Y, Konak A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. International Journal of Production Economics, 2017, 167: 1450-1463.
[22]
Poonthalir G, Nadarajan R. A fuel efficient green vehicle routing problem with varying speed constraint (F-GVRP)[J]. Expert Systems with Applications, 2018, 100: 131-144. DOI:10.1016/j.eswa.2018.01.052
[23]
Çimen M, Soysal M. Time-dependent green vehicle routing problem with stochastic vehicle speeds:An approximate dynamic programming algorithm[J]. Transportation Research Part D:Transport and Environment, 2017, 54: 82-98. DOI:10.1016/j.trd.2017.04.016
[24]
Ehmkea J F, Campbell A M, Thomas B W. Vehicle routing to minimize time-dependent emissions in urban areas[J]. European Journal of Operational Research, 2016, 251(2): 478-494. DOI:10.1016/j.ejor.2015.11.034
[25]
李妍峰, 高自友, 李军. 动态网络车辆路径派送问题研究[J]. 管理科学学报, 2014, 17(8): 1-9.
(Li Y F, Gao Z Y, Li J. Dynamic vehicle routing and dispatching problem[J]. Journal of Management Science in China, 2014, 17(8): 1-9.)
[26]
李妍峰, 高自友, 李军. 基于实时交通信息的城市动态网络车辆路径优化问题[J]. 系统工程理论与实践, 2013, 33(7): 1813-1819.
(Li Y F, Gao Z Y, Li J. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering-Theory & Practice, 2013, 33(7): 1813-1819.)
[27]
Kok A L, Hans E W, Schutten J M J. Vehicle routing under time-dependent travel times:The impact of congestion avoidance[J]. Computers & Operations Research, 2012, 39(5): 910-918. DOI:10.1016/j.cor.2011.05.027
[28]
Ma Z J, Wu Y, Dai Y. A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery[J]. Computers & Industrial Engineering, 2017, 114: 101-113.
[29]
Ichoua S, Gendreau M, Potvin J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.
[30]
Ning J X, Zhang Q, Zhang C S, et al. A best-path-updating information-guided ant colony optimization algorithm[J]. Information Sciences, 2018, 433/434: 142-162. DOI:10.1016/j.ins.2017.12.047
[31]
Solomon M M. Algorithms for the vehicle vouting problem with time windows constrains[J]. Operation Researhc, 1987, 35(2): 254-265. DOI:10.1287/opre.35.2.254
[32]
Calvete H I, GaléC, Oliveros M J. Bilevel model for production-distribution planning solved by using ant colony optimization[J]. Computers & Operations Research, 2011, 38(1): 320-327.
[33]
Huang Y X, Zhao L, Woensel T V, et al. Time-dependent vehicle routing problem with path flexibility[J]. Transportation Research Part B, 2017, 95: 169-195. DOI:10.1016/j.trb.2016.10.013