考虑交通拥堵的冷链物流城市配送的GVRP研究

赵志学，李夏苗，周鲜成，刘长石

1.中南大学 交通运输工程学院，长沙410083

2.湖南商学院 移动商务智能湖南省重点实验室，长沙410205

1 引言

随着经济发展和人民生活水平的日益提高，人们对生鲜产品的需求量和品质要求也越来越高，冷链物流配送越来越受到重视。目前物流行业向绿色物流转型已是大势所趋，随着城市规模的扩大，交通拥堵情况频繁发生，合理规划冷链物流配送路径，不仅可以降低冷链物流中的配送成本，保证生鲜产品的新鲜度，增加客户的满意度，还可以降低能耗成本和碳排放，促进物流企业的节能减排，实现绿色环保。

车辆路径问题（Vehicle Routing Problem）自1945年提出以来[1]，产生了大量的研究成果。Desrocherst等[2]提出了一种混合动力车辆路径模型；Solomon 等把时间窗的概念融入到车辆路径问题中[3]，而在此基础上Jabali等通过惩罚成本解决时间窗约束[4]，引出软时间窗和硬时间窗的概念，并建立了软时间窗的车辆路径问题；Moghaddam等[5]探讨了不确定性的VRP问题。近年来，倡导绿色发展，以降低能耗、减少碳排放为目标的绿色车辆路径问题（Greed Vehicle Routing Problem）已经引 起了学术界的关注。Kara 等[6]、Tarantilis 等[7]、李进等[8]、陈玉光等[9]、吴丽荣等[10]分别以最小化油耗、最短行驶距离、最小化租车费用以及准时送货为优化目标建立GVRP 模型，并分别采用改进的粒子群算法、基于模拟退火和禁忌搜索的两阶段求解方法以及基于路径划分的禁忌搜索算法进行求解。为突出车辆能耗和碳排放对环境的影响，文献[11]提出了污染路径问题（Pullution Routing Problem，PRP），文献[12-15]分析了车辆出发时间对车辆速度的影响，构建了基于时间依赖的单目标污染路径模型，并分别采用禁忌搜索算法、出发时间和速度优化算法、启发式算法、基于迭代邻域搜索和局部MIP的混合算法和改进的粒子群算法进行求解。

本文研究的绿色车辆路径问题主要应用于我国冷链物流运输领域。目前该领域国内外已经有一系列的研究成果。Tarantilis 等[17]以希腊肉类和牛奶的配送为例，研究了多车型、多配送中心的开放冷链物流配送车辆路径问题，并采用门槛值法进行求解；Amorim等[18]针对葡萄牙一个食品配送问题构建了多时间窗多车型车辆路径问题；Yang 等[19]研究了冷链物流中易腐货物的VRP 模型，并利用遗传算法对配送路径进行优化；张亚明等[20]设计了一种多车场多车型的冷链物流车辆路径数学模型，并通过遗传算法和精英选择方法进行求解；Ma等[21]研究了基于随机需求的冷链物流车辆路径优化模型；石兆等[22]针对时变网络导致服务时间延误的问题，设计客户满意度最大化的冷链物流车辆路径优化模型，并通过聚类算法和遗传算法相结合进行求解。兰辉等[23]分析了城市道路拥堵状况对冷链物流车辆配送成本的影响，构建了相应的车辆路径优化模型，并设计了混合遗传算法进行求解。李娜等[24]在不确定需求情况下，建立了顾客需求随机的带时间窗易腐产品配送路径优化问题；康凯等[25]、李杉[26]、Wang等[27]在构建冷链物流运输时，不仅考虑了车辆使用成本、运输成本、货损成本、制冷成本和惩罚成本，还考虑了碳排放成本作为总成本优化目标进行冷链物流配送路径优化，并分别采用了改进的蚁群算法、遗传算法等算法进行求解。郑海娟[28]、李明泽[29]在求解冷链物流配送车辆路径时将交通拥堵因素加入模型，并分别采用改进的遗传算法和阶段优化法进行求解。

综上所述，关于冷链物流配送车辆问题的研究已经产生一定的研究成果，为冷链物流绿色车辆路径问题的研究奠定了良好基础，但也存在一定的局限性，主要体现在以下三个方面：（1）已有冷链物流配送研究成果大都假设车辆行驶速度恒定，基于时变网络的研究文献较少；（2）已有冷链物流配送研究成果大都没有考虑拥堵状况的发生，车速和载重的变化如何影响路径规划；（3）目前冷链物流车路径优化相关文献主要是讨论经济性，对车辆节能减排实现的绿色效益鲜有涉及。

本文在此基础上首先分析拥堵状况对车辆路径规划的影响，考虑冷藏车辆行驶速度和载重对油耗和碳排放的影响，引入相应的碳排放率度量函数；在此基础上构建以车辆管理成本、运输油耗成本、货损成本、制冷成本、惩罚成本以及碳排放成本作为目标函数构建模型，并设计基于路径划分策略的改进蚁群算法进行求解，实现冷链物流的低碳配送，降低能耗和环境污染，将物流可持续发展与节能减排的全新理念有效衔接。

2 问题描述与模型构建

2.1 问题描述与基本假设

本文研究考虑城市交通拥堵的冷链物流配送绿色车辆路径问题，可描述为：一个配送中心为多个客户点提供冷链物流配送，综合考虑物流配送成本，找出最优车辆调度和路径规划方案。其中客户点的位置、时间窗、需求量均已知，城市交通拥堵时段和交通拥堵的状况可从交通部门获得，配送成本主要包括车辆管理成本、运输成本、货损成本、制冷成本、客户需求时间窗的惩罚成本以及在冷链物流运输和制冷过程中的碳排放成本。为便于分析和研究，做出如下假设：（1）考虑单一配送中心，且货源充足，并且多辆同质冷藏车；（2）配送车辆从冷链物流配送中心出发，完成任务后即刻返回配送中心；（3）客户点的需求量均小于车辆容量，且有服务时间窗要求；（4）在交通拥堵时段，车辆以拥堵速度行驶，在非交通拥堵时段，车辆以正常速度行驶；（5）假设在配送过程中所用的冷藏车厢内部的温度恒定、适宜；（6）车辆管理费用包括发车费、人力成本、车辆使用成本；（7）每辆车最大载重量固定，而且每个客户点有且仅有一辆车为其服务。

2.2 符号和变量

dij：车辆从节点行驶到节点j 的距离；

Q：车辆最大载重量；

qi：表示客户点i 的需求量；

sti：客户点i 的卸货服务时间；

[ETi,LTi]：为客户点i 服务时间窗；

σik：车辆k 提前到达客户点i 等待时间；

ϕh：车辆行驶路段h 开始时间；

vijkh：车辆k 在道路(i,j)中的路段h 内行驶速度；

tijkh：车辆k 行驶在道路(i,j)中路段h 消耗的时间；

dijkh：车辆k 行驶在道路(i,j) 中路段h 的距离，dijkh=vijkh×tijkh；

Rnik：车辆k 到达客户点i 的时间；

Lnik：车辆k 离开客户点i 的时间；

fijkh：车辆k 行驶在道路(i,j)中的路段h 内的油耗率（单位：L/km）；

cyijkh：车辆k 行驶在道路(i,j)中的路段h 内的碳排放率（单位：kg/km）；

p：运输生鲜产品的单价；

θ1：配送产品时单位时间内的货损比例；

θ2：装卸时单位时间内产生的货损比例；

θ3：配送过程中单位时间内的制冷成本；

θ4：装卸时单位时间内产生的制冷成本；

gk：车辆k 的固定发车费用；

μ：车辆使用单位时间成本；

ψ：车辆使用人力单位成本；

gf ：单位油耗费用（单位：元/L）；

cf ：单位碳排放费用（单位：元/kg）。

xijk：0-1变量，当车辆k 在道路(i,j)行驶时为1，否则为0；

yjk：0-1 变量，当车辆k 为客户点j 服务时为1，否则为0；

zijkh：0-1 变量，当车辆k 行驶在道路(i,j)中路段h时为1，否则为0；

ηk：0-1变量，当车辆k 使用时为1否则为0。

2.3 考虑交通拥堵的路径划分设计

随着城市汽车拥有量的急剧增加，城市交通拥堵已成为一种普遍现象。这种交通拥堵状况使得冷链物流配送的路径规划必须考虑“时空效应”，两个客户点之间的“最短路径”需要考虑的并非是“空间距离”最短，而应该是“时间最短”。在时变网络下，不同时段内由于道路拥堵情况不同，车速不同，行驶时间很难计算，需要进行处理。为此，本文拟对考虑交通拥堵状况的冷链物流配送路径规划问题进行研究。为量化道路拥堵程度，引入交通拥堵系数，则vc=vf/ρij，其中vc是拥堵情况下车速，vf是道路畅通时车速。

在时变网络下，城市道路拥堵的时间段已知，车辆在同一路段行驶过程中，很可能一部分在自由行驶时段，一部分在拥堵时段。本文采用路段划分方法进行求解。根据实际情况和驾驶规律，车辆在足够短的距离的子路段行驶时，该路段车速可认为是恒定。因此设计出解决拥堵时段的路径划分方法，步骤如下：

步骤1 路段划分。令ϑ=0.5 km作为最短路段基本单元，对于车辆k 行驶在路径(i,j)中，按照一定的距离ϑ 将(i,j)划分为个子路段（表示向上取整）。前H-1 个子路段距离都为ϑ ，最后一个子路段为dij-ϑ*(H-1)。

步骤2 前H-1 个i 路段行驶时间计算。将车辆k离开客户点i 的时间Lnik作为驶入路段(i,j)的第一个子路段开始时间ϕ1=Lnik。如果Lnik属于拥堵时段，则该路段的行驶速度为vc，该子路段的行驶时间为，驶出该子路段时刻作为即将进入下一子路段的出发时刻；否则车辆以正常速度行驶，行驶时间为，第二子路段出发时刻为ϕ2=Lnik+ϑ/vf。中间的子路段行驶时间可以此类推。

步骤3 最后一个子路段行驶时间计算。判断最后一个子路段出发时刻ϕh是否为拥堵路段，如果是则行驶 时 间 为ϕH=[dij-ϑ(H-1)]/vc；否 则 为ϕH=[dijϑ(H-1)]/vf。

2.4 冷链物流配送成本分析

在低碳经济环境背景下，为了更好地反映城市冷链物流配送实际情况，本文参考文献[22，27-29]模型，不仅考虑冷链配送冷藏车管理使用成本、运输成本、制冷成本、货损成本、未能满足时间窗的惩罚成本等常规成本，又要考虑运输过程和制冷设备的碳排放成本，同时还考虑到城市道路交通情况对总成本的影响。综合上述各项成本为目标，构建冷链物流配送绿色车辆路径优化模型。

（1）车辆管理使用成本

车辆管理使用成本主要包括车辆发车费用、车辆租用费用和人力成本费用。其中车辆租用费用和人力成本费用为总行驶时间与单位费用的乘积，而总行驶时间包括道路行驶时间、客户服务卸货时间和早到客户点等待时间之和，因此车辆管理使用成本C1公式为：

（2）运输成本

主要指车辆运输过程中的油耗成本，本文油耗模型主要采用Hickman 等提出的MEET 模型[31]，油耗率fijkh获得参照本节（6），因此运输成本C2公式为：

（3）货损成本

主要指冷链产品在配送和装卸时受温度、湿度以及运输时间等影响而发生腐烂变质的现象而产生损失。参考文献[32]，总货损成本C3就包括配送路途上和等待时间内的货损成本C31和装卸过程中货损成本C32。

（4）制冷成本

主要指冷藏运输车的制冷设备在配送和装卸时消耗制冷剂的成本，因此总制冷成本C4就包括配送制冷成本C41和装卸制冷成本C42[22]。

（5）时间惩罚成本

由于冷链运输物品都是易腐的，客户对收货时间有着严格的限制，要求配送车辆必须在规定好的时间窗内到达，但是由于道路拥堵、调度失误等原因，配送车辆往往不能在规定的时间段内送达，这就予以一定的惩罚，因此冷藏车辆配送过程中时间窗惩罚成本为：

其中，ch 为时间窗惩罚因子，σik=ETik-Rnik为车辆k提前到达客户点i 等待时间，Mp 为非常大的正常数。

（6）碳排放成本

碳排放成本主要包括车辆运输过程中油料消耗产生的碳排放成本和冷藏设备制冷产生的碳排放成本。本模型运输过程中油耗产生碳排放主要采用MEET 模型计算碳排放率（坡度假设为零）[33]，MEET包括碳排放估计函数、载重修正因子和道路坡度修正因子等因素，其中碳排放率估计函数为：

其中，ω(v)为汽车空载时在坡度为0的道路上以车速v行驶的碳排放率（单位：g/km），ω0,ω1,ω2,ω3,ω4,ω5,ω6为修正因子参数，根据不同载重车型取值不同；MEET模型载重修正因子为：

其中，γ 为实际载重与其容量的比值，χ0,χ1,χ2,χ3,χ4,χ5,χ6,χ7为载重修正因子，根据不同载重车型取值不同。配送车辆运输时的碳排放率（单位：kg/km），即为cyijk=ω(v)×LC/1 000。本文设定1 L汽油产生2.32 kg碳排放量[32]，则产生1 kg碳的油耗为∂=1/2.32=0.431 L，本文油耗率为fijkh=∂×cyijkh，行驶中碳排放成本为：

配送过程中冷藏设备消耗制冷剂产生的碳排放成本，参考文献[29]，设定ez 为制冷设备配送单位重量货物行驶单位距离产生的碳排放，则冷藏设备制冷产生的碳排放成本为：

总的碳排放成本为C6=C61+C62。

2.5 模型的构建

以上述所有成本作为目标函数，构建冷链物流配送绿色车辆路径模型如下：

目标函数（10）表示冷链物流运输包含碳排放在内总的综合成本；式（11）表示每个客户点只能由一辆车服务且所有的客户点都得到服务；式（12）表示选择的道路只允许一辆车行驶；式（13）和（14）表示变量xijk和zijkh间限制关系；式（15）表示每辆车辆只用使用一次；式（16）表示dijkh和dij限制关系；式（17）表示只要道路被选择，就要行驶完整条道路；式（18）和（19）表示时间窗约束；式（20）表示汽车容量约束；式（21）表示变量取值约束。

3 改进蚁群算法设计

VRP 属于NP-hard 问题，而考虑交通拥堵的带有时间窗的VRP 更为复杂，如何精准高效地求解算法方面存在较大难度。蚁群算法具有自我组织能力、正反馈机制和并行搜索能力等特点，这些也是相对于其他启发式算法自身的优势，能够更好地解决复杂的组合优化问题，同时也被广泛应用到各个领域[34-35]。故本文通过对标准的蚁群算法进行改进，设计一种求解本文模型的改进蚁群算法。具体步骤如下：

步骤1 变量与参数的初始化。初始化各变量与参数，令全局最优解为Gbest ，置迭代次数NC=0，最大迭代次数为NCmax，将M只蚂蚁放在配送中心，令初始时刻信息素矩阵τij(0)=c,c为常数，计算节点之间的距离矩阵，令车辆增开标志Gh=1。

步骤2 状态转移规则的改进。参照文献[34-36]，对状态转移概率规则进行改进，其计算公式如下：

其中，tabum为禁忌表，记录蚂蚁已经访问过的节点，τij表示信息素浓度；ηij表示能见度（ηij=1/dij）；考虑搜索过程中加强先验信息对搜索的引导，引入节约矩阵引导蚂蚁选择下一个城市（Uij=d(i,1)+d(j,1)-d(i,j)）；为了解决客户点服务的紧迫性，引入客户点时间窗跨度因素（widthj=LTj-ETj）；为了避免概率为零，导致蚂蚁不能选择下一节点，所以进行了相应处理。α、β、φ、γ 分别为信息素浓度、能见度、节约矩阵因素和时间跨度因素的相对重要性。r 为在[0，1]内随机数rt为随着进化过程动态调整的选择概率，初始值r0=1。具体rt调整规则[37]如下：。时刻τ 蚂蚁m 位于当前节点i，在候选节点列表中找出所有未访问过的节点，并按照式（22）选择蚂蚁下一个访问的节点j。

步骤3 路段(i,j)行驶时间的计算。

步骤3.1 根据步骤2 获得的节点j，采用路径划分策略计算车辆k 在路段(i,j)行驶时间。

步骤3.2 判断车辆k 是否满足车辆容量和时间窗限制，如果满足，j ∈tabum，Gh=0 ；否则返回节点，Gh=1，转步骤2。

步骤3.3 判断已搜索的蚂蚁数是否为M ，若是转步骤4；否则转步骤2。

步骤4 本轮路径目标函数值的计算。

步骤4.1 根据式（10）分别计算每只蚂蚁的搜索路径Rm的目标函数值f(Rm)NC即适应度值，并记录此次遍历中蚂蚁走过的最优的适应度值和相应的最优路径。

步骤4.2 对得到的最优路径采用文献[34]方法结合2-opt方法对最优解进行进一步优化，得到全局最优解，并记录相应的路径Lbest。

步骤5 全局信息素的更新。对最优蚂蚁经过的路径组成的路段进行信息素更新。为了防止每条道路上积聚的信息素发生过大或过小的情况，本文采用最大最小蚁群算法避免算法过早收敛[32]。将所有线路上信息素浓度τij设置在[τmin,τmax]内。

步骤6 算法结束的判断。看NC 是否达到NCmax，未达到转步骤2，否则算法结束。

4 算例仿真

4.1 实验设置

考虑到冷链物流车辆配送各种因素，测试算例采用Solomon’s VRPTW 数据库中的C 类（集中分布）、R 类（随机分布）、RC 类（混合分布）的数据作为本文测试数据[31]，各算例均有100 个客户点和1 个配送中心。为更贴合实际，对上述案例进行如下修改：本文设定模型初始时间为早上6：00，为该配送中心最早服务时间，设置该时刻为0时刻，根据城市交通规律，将7：00至9：00和下午17：00 至19：00 设为交通拥堵时间段，其余时间段为正常行驶时间。时变网络下，正常行驶速度vf为60 km/h，拥堵时段速度vc为30 km/h，所选用车辆空载车重为5 000 kg，容量为1 000 重量单位，令一个重量单位为2 kg，则车载容量为2 t，对应的碳排放率系数为：ω0=110,ω1=0,ω2=0,ω3=3.75×10-4,ω4=8 702,ω5=0,ω6=0;对应载重修正因子的系数为[31]：χ0=1.27,χ1=0.061 4,χ2=0,χ3=-0.001 1,χ4= -0.002 35, χ5=0,χ6=0,χ7=-1.33，其中模型涉及到的其他参数取值如表1，算法参数取值如表2[15，34-35]。算法采用Matlab R2016 编程，在CPU2.0 GHz内存为8 GB微机上计算。

4.2 大型数据算例规划

算例采用数据集RC204进行计算，程序运行时间为290.3 s，得到配送总成本为10 052.8元，共使用9辆车进行配送，人力和车辆使用成本（车辆启动和租用费）为2 943.9元，货损成本为102.4元，制冷成本为2 656.6元，油耗成本为3 904.1元，碳排放成本为50.1元，早到客户点等待惩罚成本为395.7 元，具体路径优化方案如表3所示。表3中SN表示车辆号，VR表示车辆行驶路径（0表示配送中心，1～100 表示客户点），VAT 表示车辆到达各个客户点的时间。

表1 模型参数值

表2 蚁群算法参数值

通过计算可知：（1）本文算法能在较短时间内得到最优规划路径。（2）综合VR和VAT可以看出，由于受到城市拥堵状况、客户服务时间窗、车辆载荷等条件限制，各冷链物流车配送路线存在明显差异性。车辆2 服务客户点数目最多，达到21 个；车辆8 和9 服务客户点数目最少，只有4 个，其原因是每个需求点时间窗都不一样，车辆路径规划在确保适应度最小化同时，必须满足客户点时间窗要求。（3）从VAT 可知，车辆1 和2 都是在0时刻开始从配送中心出发进行配送，其余车辆出发时间都各不相同。如果0 时刻出发则需要承担较大的时间窗惩罚费用。说明物流企业路径规划时考虑时间依赖很有必要，应根据路网状况、客户点时间窗等实际情况并综合考虑运输过程中制冷成本和油耗等成本科学规划路线。（4）从VAT 可知，车辆4 完全避开拥堵时段，车辆1、3、6、7 和8 只进入早高峰拥堵时段，没有进入晚高峰拥堵时段，而车辆2、5和9仅进入晚高峰拥堵时段，没有进入早高峰拥堵时段。这说明本文提出的方法能够合理地规避交通拥堵时段，提高车辆配送效率。

4.3 不同分布算例路径规划

采用不同类型算例进行求解，每个算例求解10次，取平均值作为最终结果。实验结果如表4，其中EX 表示算例类型，TC 表示配送总成本，TMC 表示人力和车辆启动、租用成本，DC货损成本，CC为制冷成本，FC表示油耗费，CF为碳排放费用，PC为时间窗惩罚成本，VN表示车辆数目。

由图1 和表4 可以看出：（1）不同算例在求解过程中，算法在迭代400 次内能够达到最优解并达到稳定，说明该算法能够很好求解本文模型，而且收敛性较为优良。（2）C 类算例的总配送费用、车辆使用和人力成本、货损成本、制冷成本、车辆使用数量在所有类型中最高，但是油耗成本相比其他类型最低。主要由于C 类分布客户点主要集中分布在几个区域，行驶距离较短，因此油耗成本相对较低；但是客户时间窗相对较窄，由于Solomon 数据库中C 类模型客户点服务时间为90 min，不同于R 和RC 类客户10 min 服务时间，使得对车辆到达客户点满足其时间窗要求较高，因此车辆只能服务较少客户，而且总的配送行驶时间较长。（3）R 类和RC 类总配送费用、车辆租用和人力成本、车辆数均小于C类，主要由于这两种类型服务时间只有10 min，客户均随机分布，客户时间窗要求相对宽松，使得车辆可以配送多个客户，而且总行驶时间较短。（4）配送总成本构成中，所有类型的TMC与CC占比相对较高，达到总成本一半以上，而C 类占比高达70%以上，说明物流配送成本主要来自车辆使用费用、人力费用和制冷费用，而这些主要影响因素就是行驶时间，因此要降低物流成本，最主要就是降低总的运输时间。（5）油耗成本占物流比例较低，最高也只有RC类占总成本38%左右，最低C类只占22%左右；而碳排放比例就非常低，只占总成本0.2%～0.4%。说明物流企业从经济角度看，目前的碳税产生的碳排放成本很难真正有效促进企业的节能减排。

表3 RC204数据案例车辆路径规划

表4 不同分布算例实验数据结果

图1 不同分布类型算例车辆路径规划

4.4 不同拥堵状况下算例仿真

在算法其他条件不变的前提下，根据2.3 节vc=，vf为60 km/h 不变，分别以拥堵系数ρij取值1.5、2.0、3.0（即拥堵速度为40 km/h、30 km/h、20 km/h）对RC204算例进行求解，每种情况求解10次，取平均值作为最终结果，得到的优化结果如表5，其中CP 表示碳排放量，TT表示行驶时间。

通过表5可知：（1）随着拥堵系数的增加，配送总成本、车辆使用成本与人力成本、货损成本和制冷成本都会不同程度随之增加，说明这些成本与拥堵情况正相关。（2）随着拥堵系数的增加，油耗和碳排放量随之增加，说明拥堵状况会影响冷链物流配送路径绿色度；行驶时间也随之增加，说明交通拥堵会影响车速，从而影响车辆路径规划。（3）虽然拥堵系数显著变化，但是TC、TMC、CC、FC、CP、VN 变化不大，因为本文构建的模型能使大多数车辆有效地避开交通拥堵时段，说明了本文模型和求解算法的有效性。

5 结论

随着物流节能减排活动推进，冷链物流由于自身的特点：（1）在配送的整个过程中都不同程度存在影响环境的非绿色因素，尤其是在运输过程中产生的油耗和碳排放以及在制冷过程中产生的碳排放，对城市环境污染有着非常大的影响。（2）日益严重的城市道路拥堵状况延迟了配送车辆在途时间，降低了货物品质和服务效率，增加了货损成本和能耗成本，凸显冷链物流配送过程中考虑道路拥堵状况的必要性。本文研究拥堵状况的冷链配送绿色车辆路径问题，综合考虑了车辆管理成本、油耗碳排放成本、货损成本、制冷成本和时间窗惩罚成本，构建该问题优化模型，并设计了基于路径划分策略的改进蚁群算法模型，对基本蚁群算法的启发式因子、移动概率选择规则以及信息素的更新进行改进。仿真实验结果表明，本文构建的模型能得到成本最低且最优的配送路径，并有效地规避了交通拥堵，提出的算法在不同分布数据案例下都能取得较好的优化成果。本文模型和算法可为冷链物流企业科学规划配送路径方案提供方法支持和参考。

表5 不同拥堵系数下仿真结果