碳排放规制下生鲜农产品配送车辆路径优化问题

邱玉琢，张 磊

(南京财经大学 营销与物流管理学院，江苏 南京 210023)

一、 引言与文献综述

近年来，我国生鲜农产品供应链已经得到较大的改善，但是与欧美发达国家相比，我国每年因果蔬损耗造成的损失超出世界平均水平5～6倍。随着生活质量的提高，人们开始追求高品质的服务，对新鲜、健康的农产品的需求大大提高。各大生鲜配送企业相继寻找快速配送农产品的方法，然而，随之快速增加的配送成本限制了配送的发展。当前配送过程环境复杂，如何将更多因素纳入规划中使决策更贴合实际成为企业主关心的问题。此外，随着国家越发强调“低碳物流”，降低运输过程的碳排放也成为配送企业不得不关注的重中之重。

生鲜农产品配送优化的核心是车辆路径优化问题。自Dantzig and Ramser[1]于1959提出车辆路径问题开始，主要目的是降低运输成本和距离。近年来越来越多学者从不同的角度丰富了车辆路径问题的研究内容。在综合车队方面，Krajewska and Kopfer[2]首次考虑自有车队和外包方式的综合运输规划问题(ITTP)，他们认为自有车队与外部承运人结合的运输规划方式在应对波动的需求时更有优势。Gahmetal.[3]在此基础上，从货主角度出发，解决交货计划问题，完善前人各类型车队的成本计算过程，使成本更加合理。在碳排放因素方面，Bektaand Laporte[4]首次引入影响碳排放量多少的各种因素，提出污染路径问题，揭示了车辆负载、速度和总成本各参数之间的关系，进一步贴合实际。Koçetal.[5]考虑车队规模、多车场位置和碳排放因素的影响，其目标是实现仓库、车辆和配送路径的成本最小化。Eshtehadietal.[6]保留了需求不确定性因素，补充需求不确定下的污染路径问题，在需求端更加贴合市场变化，从时点研究变为时段研究。Wang and Li[7]引入时空距离的概念，考虑时间窗惩罚成本和仓库成本因素，在多目标多因素条件下解决具有异构车队、同时取货和时间窗的路径问题。Micheli and Mantella[8]对现有的碳排放政策做细致分析，考虑非均质车队，将不同的碳控制政策的经济和环境影响纳入模型，考虑成本最小化和碳排放量最低，对比分析了不同政策对路径优化的影响。在各因素被考虑到模型中前提下，Lietal.[9]进一步完善因素分析，指出燃料燃烧是碳排放产生的主要来源，降低燃料消耗对降低成本和碳排放起主要作用。可以看出，前人的研究对多种因素的考虑逐渐完善，但是对碳排放政策影响下的综合运输车队问题研究较少，本文在此基础上，考虑异构车队、时间窗、碳排放等因素，目的是降低配送总成本，不同于单独的异构车队污染路径问题，进一步研究租赁车队增加的碳排放权是否对新的最优配送路径有影响，租赁碳排放权不增加配送公司成本，在控制碳排放权变化范围的前提下，寻求成本和碳排放的平衡。

解决异构车队和污染路径问题的模型和算法已经被很多学者提出和改进，其中禁忌搜索算法和遗传算法受到众多学者关注，也有部分学者采用混合元启发式算法解决该问题，越来越多的研究表明混合算法在计算效率和结果上均优于单一算法。禁忌搜索算法的变种有很多，Krajewska and Kopfer[2]首次提出该问题，设计了一种用四种移动类型促进解空间的搜索，不严格的禁忌表得到更多可能的解，使获得的解更丰富更好。Gahmetal.[3]提出那种基于变量邻域搜索的元启发式算法，结果表明该算法能获得更好的解。此外遗传算法的发展也备受学者关注。Baietal.[10]结合虚拟编码策略、多子代方法、异族交叉策略和禁忌搜索机制相结合，设计一种多种群遗传算法，具有协同进化的性能。从算法自身改进出发，Costaetal.[11]结合局部和种群搜索启发式的元素，实现了减排的结果。从混合算法出发，Tohidifardetal.[12]结合粒子群和遗传算法，优化染色体的排列顺序，对寻找更好的解做出贡献。Wang and Li[7]利用遗传算法对客户点聚类，并用模拟退火的思想提高变邻域搜索算法的全局优化能力，凸显了混合算法的优势。近期有文献表明混合算法结果优于单一算法结果，较优的初始解能快算法收敛，交叉方式的多样化保证解的多样化。本文基于上述分析，设计一个结合最近邻启发式算法和改进遗传算法的混合遗传算法，该算法采用最近邻法产生更好的初始解，从遗传算法本身，参考禁忌搜索的邻域搜索机制，设计三种交叉规则提高算法搜索效率，同时，为了测试算法的有效性，本文做了数据分析，探索算法本身的有效性和模型的敏感性。

本文的主要贡献在于：(1)针对生鲜农产品配送过程成本优化问题，结合运输过程中亟待控制的重要因子—碳排放，考虑了多种成本影响因素，着重引入了租赁增加的碳排放权因素，构建了相应的数学模型，分析成本、时间窗、碳排放因素对配送决策的影响，确定最优配送车辆组合和路径。(2)设计了混合遗传算法对模型进行求解，优于单一算法的计算结果，而且较优的初始解能加快算法收敛，交叉方式的多样化也保证了解的多样化。(3)通过案例分析验证了模型和算法的有效性和实用性。

二、 混合整数规划模型

(一) 问题描述

给定完全图G=(V,E)，其中V表示图上的节点集，其中0表示生鲜配送中心，1,2，…,n表示n个客户点，每一个顾客需求量为qi，E={(i,j)|i,j∈V，i≠j}表示节点之间的边构成的集合,dij表示车辆从节点i到节点j经过的距离。具有碳排放约束和时间窗的异构车队车辆问题，即自有车辆和租赁车辆均从生鲜配送中心出发，满足所有顾客后回到配送中心，在碳排放和时间窗约束的条件下，使包括自有车队固定成本、运输成本、租赁成本、惩罚成本、制冷成本和碳排放成本的总成本最小化。

假设配送中心自身拥有一定的车辆数固定为m，每一辆车的载重限制为Q。在自身拥有车辆数不足以满足配送需求时，需租赁专业运输车队用于配送，假设租赁方式有两种，一种是根据车辆行驶距离收费，单位距离的租赁费用为c2；另一种是按日收费，单天的租赁费用为c3，假设租赁的车辆与自有车队完全一致，具有相同的载重限制Q。需要强调当选择按日租赁方式时，必须支付整数天的费用，即不足一天仍以一天计费，租赁车辆在每天开始配送之前统一调配到配送中心，由配送中心统一安排，即每一辆车都是从配送中心出发最终又回到配送中心。

生鲜农产品配送时间过长会腐烂变质，为了提高客服满意度，必须在规定的时间范围内将货物送到顾客手中，假设配送中心与客户约定最早送货时间为ei，最迟送货时间为li，本文假设节点i服务时间窗为[ei，li]，如果车辆早于时间ei到达，则需要等待交货，因此需要支付惩罚成本μ1，如果晚于时间li到达，则可能会引起客户不满，因此需要支付惩罚成本μ2。假设车辆到达客户点i的时间为ti,在规定时间内可以即时交货，不考虑交货时间，则客户点i的软时间窗惩罚函如下：

G(i)=μ1max(ei-ti,0)+μ2max(ti-li,0)，∀i∈V

(1)

冷藏车的制冷成本和碳排放成本是配送成本的重要组成部分，制冷的能量来源是燃油，因此采用燃油消耗成本来衡量制冷成本。另外在配送货物过程中，配送车辆会排放大量的尾气，尾气中包括甲烷、一氧化碳和二氧化碳等温室气体，但是其中二氧化碳还是占大部分，因本文主要是为了得出最优的生鲜农产品配送路径，故仅估算二氧化碳的排放量及成本。Zhangetal.[13]优化了油量消耗模型，考虑车辆增加一定负载的时候增加多少油耗的油量消耗计算模型。Wangetal.[14]进一步结合满载计算车辆行驶过程中的油耗。据此，车辆k从客户点i到客户点j的油耗函数如下：

Fijk= (f1+θijk(f2-f1) )dij，∀i,j∈V,∀k∈K

(2)

参数：

G=(V,E)，表示物流配送网络；

V={1,2,…,n}，表示节点集，V′={0,1,2,…,n}，0表示生鲜农产品配送中心；

E={(i,j)|i,j∈V，i≠j}是节点之间的连接弧；

δ={1,2，…，m}表示自有车队的车辆集合；

δ′={m+1，…，m′}表示按日租赁的车辆集合；

δ″={m′+1，…，m″}表示按距离租赁的车辆集合；

K=δ+δ′+δ″表示所有可用车辆集合；

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

c1表示自有车辆的成本均摊到每一天得到其固定成本；

c0表示自有车辆的单位运输成本；

Q表示车辆载重限制；

dij表示车辆从节点i到节点j经过的距离；

c2表示按距离租赁的车辆单位距离的租赁费用；

c3表示按日租赁的车辆每日的租赁费用；

dmax表示按日租赁的车辆最大配送距离；

ei表示节点i可以接受的最早配送时间；

li表示节点i可以接受的最晚配送时间；

f1表示车辆空载每千米的油耗，当车辆已知时，它的值是常数；

f2表示车辆满载每千米的油耗，当车辆已知时，它的值是常数；

θijk表示车辆k从i到j的装载率；

μ1表示配送车辆早于约定时间到达的惩罚成本系数；

μ2表示配送车辆晚于约定时间到达的惩罚成本系数；

ti表示车辆到达节点i的时间；

ψ表示生鲜农产品随时间变质因子；

φ表示允许的最大变质率；

OWNco2表示自有的碳排放权；

RENTco2表示因租赁车辆所增加的碳排放权；

σ表示配送车辆的制冷成本系数；

ω表示政府征收的碳排放税；

决策变量：

(3)

(4)

(5)

(二) 模型建立

给定上述参数和决策变量，具有碳排放约束和时间窗的异构车队车辆问题模型如下

Minm·c0

(6)

(7)

(8)

(9)

(10)

s. t.

(11)

(12)

(13)

(14)

(15)

(16)

(17)

Qijk≥Q(i-1)ik+pj-M(1-xijk)，∀i∈V′,∀j∈V,∀k∈K

(18)

Qijk≤Q(i-1)ik+pj-M(1-xijk)，∀i∈V′,∀j∈V,∀k∈K

(19)

(20)

ti+tij-M(1-xijk)

(21)

(22)

xijk∈{0,1},∀i,j∈V′，∀k∈K

(23)

zik∈{0,1},∀i∈V′，∀k∈K

(24)

yk∈{0,1},∀k∈δ″

(25)

Qijk≥0,∀i,j∈V′，∀k∈K

(26)

目标函数中(6)是自有车队固定成本，(7)是运输成本，(8)是租赁成本，(9)是惩罚成本，(10)是制冷成本和碳排放成本。载重限制(11)对自有车队和租赁车辆都适用。限制(12)是按日租赁车辆是否被使用。限制(13)～(16)使得配送车辆从配送中心出发最后回到配送中心，且每一个节点仅被访问一次。限制(17)表示按日租赁车辆最大配送距离。限制(18)～(19)表示供需平衡。限制(20)表明配送中心0到客户点i的第k辆车的装载量不超过总负载限制。限制(21)是满足客户约定的软时间窗限制。限制(22)是为了使碳排放量低于限定值，限制(23)～(26)表示xijk、yk和zik是0,1变量，车辆负载Qijk必须大于等于0。

三、 混合遗传算法描述

图1 混合GA流程

遗传算法(GA)是模拟达尔文的生物进化论遗传学机理设计的一种算法模型，模拟大自然中自然选择和进化的过程。本文结合最近邻法构建初始解和以此跳出局部最优的方式设计了混合遗传算法，算法流程见图1。

(一) 初始种群

混合遗传算法利用最近邻法得到初始解，随机一个客户点作为初始点，然后在剩余的点中寻找与初始点最近的点，直到被选择的点需求总和大于车辆最大负载时，再重新随机一个初始点，直到所有客户点全部被选择为止，该算法所得到的解比较接近最优解，产生的初始种群本身即是最优种群，不管选择哪些个体作为父代，均可能快速产生较优的解，加快算法的收敛速度。

(二) 适应度函数

本文采用的适应度函数是传统遗传算法的适应度函数设置，以f=1/F为个体的适应度，F为目标函数的值，它的倒数为个体的适应度值，记为f。

(三) 轮盘对赌选择

本文采用轮盘对赌选择法选择保留的个体，根据适应度大小选择个体，个体的适应度越大，则被选中的概率越高，轮盘对赌选择法使得每一个个体都有一定的概率可以被选择，提高解的丰富性，轮盘对赌选择法的步骤如下：

第一步：计算个体被遗传到下一代群体的概率；

第二步：计算累积概率；

第三步：在[0,1]之间产生一个均匀分布的伪随机数r，若r小于个体1被遗传概率，则选择个体1，否则选择个体k，使r在第k-1个个体被遗传概率和第k个个体被遗传概率之间。

(四) 染色体交叉

染色体交叉规则是遗传算法能否快速找到最优解的关键，本文采用强强交叉的原则，综合多篇文献，本文设计了三种交叉规则，如下：

片段交叉：随机两个点(i,j)，将染色体1与染色体2中位于两点之间的部分置换，如(1→2→3→4→5→6)与(6→5→4→3→2→1)在第2到第4的位置进行置换得到(1→5→4→3→5→6)和(6→2→3→4→2→1)，然后消除重复点，即得到新的染色体。

连续点交叉：在染色体中随机一个点i，i不是最后一个点，将两个染色体连续的两个点i和i+1位置相互置换，如(1→2→3→4→5→6)与(6→5→4→3→2→1)在第2到第3的位置进行置换得到(1→5→4→4→5→6)和(6→2→3→3→2→1)，然后消除重复点，即得到新的染色体。

两点交叉：随机两个点i和j,将染色体1的i位置与染色体2的j位置置换，然后消除重复点，即得到新的染色体。

(五) 变异

本文采用简单的三次2变换变异，使算法不会陷入局部最优。当随机数小于变异概率时，则开始变异，随机三组变异位，交换三组变异位上的顾客点形成新解，并与父代做比较，如果变异后产生的子代优于父代，则用子代替代父代，否则放弃，循环直到被选择的个体全部进行变异步骤为止。

(六) 重组新种群

在进行交叉和变异操作之后，新种群由部分父代和全部子代共同组成，为了保证快速寻找到最优解，选择父代适应度排名前十的个体与子代形成新种群，新种群既保留了父代优秀个体，也产生了新的优秀子代，通过调整保留父代优秀个体的个数和产生子代的个数可以提高种群收敛速度。此外，设置一个跳出最优解的机制，即当某一最优解连续次数超过10次时，利用最近邻法产生一个解替代原种群中的最差的解，使得算法进一步搜索全局。

(七) 终止条件

终止条件设置为算法循环达到一定的迭代次数之后，将此时所得的最优的解作为模型的最优解，输出最优配送和最优总成本，终止算法。

四、 计算分析

为了研究混合GA的有效性和数学公式的有效性，本文设置了一个数据集，并采用混合GA和传统TS算法计算结果比较，在一台具有Intel 2.40GHz，安装内存4GB的电脑上，运用MATLAB R2018b软件计算的结果。

(一) 数据描述

本文选取10客户点、25客户点、50客户点、75客户点和100客户点做案例验证，0代表配送中心，其他点坐标、需求数据如表1，所有自有车队和租赁车队的最大载重量限制相同为60，参考Krajewska and Kopfer[2]文中设置自有车辆持有成本为c1=100，按距离租赁车辆单位距离收费c2=2.25，按日租赁的车辆每日收费c3=200且有最大配送距离限制为dmax=120公里，所有车辆空载时单位距离运费为0.58元，车辆满载时单位距离运费为1.68元，本文使用的一般车辆的运行平均速度设置为60公里/小时。

表1 0～100节点需求、位置和时间窗数据

表1(续)

生鲜产品配送有时间窗限制，表1中给出了每个客户点的时间需求限制，配送车辆均从早晨5点开始配送，如果提前到达顾客点，需要承担惩罚成本u1=10元/小时，如果迟到顾客点，需要承担惩罚成本u2=20元/小时。生鲜配送车辆在行驶过程中不仅需要支付运输成本和固定成本等，还需要为产品保鲜付出制冷成本，假设自有车辆的制冷系数为0.068，Wang and Li[7]文中给出碳排放系数为0.0025，假设碳排放成本为1元/千克，配送中心可用于运输消耗的碳排放权为30千克。每一辆承担配送任务的车辆均从配送中心出发，完成配送任务后回到配送中心。

经过多次试验测试，混合GA的参数设置见表2。

表2 混合GA参数设置

表3 混合GA和传统TS对比

(二) 混合GA与传统TS比较

为了研究混合遗传算法的性能，本文进行了一个实验来验证混合GA的有效性和稳定性，该实验中配送任务均由自有车队承担。计算结果如表3所示，从表3中可知，与传统禁忌搜索算法相比，本文设计的混合遗传算法在客户点逐渐增加的过程中提高了最优解的质量，在客户点为10时，与传统禁忌搜索算法相似为566.8。当客户点为25和50时，混合遗传算法获得更好的解，对最优解的优化率分别为12.8%和2.5%，客户点为75和100时，混合遗传算法的优化率也达到了达到3.6%。客户点为10时，混合遗传算法能够很快得到最优值，偶尔会陷入局部最优，客户点增多时，混合遗传算法获得的解更好，且所使用的车辆数更少。表4是混合遗传算法运行10次的计算结果，从表4中可知，混合遗传算法的计算结果较为平稳，最优值为2579.9，最差值为2613.1，平均函数值为2597.7，最佳运输车辆数为13,可知该算法的鲁棒性较好，能够获得较好的解。

表4 混合GA计算结果

图2 迭代过程对比

为了更直观地看到混合遗传算法的优化效果，本文在这一部分进行了迭代过程对比实验，结果如图2，很明显可以看出，采用了最近邻元启发式算法产生的初始种群获得较优的初始解，混合遗传算法和紧急搜索算法均在较短时间得到最优解并趋于稳定，而不管是从所得最优解还是迭代过程相比混合遗传算法均优于传统禁忌搜索算法。

(三) 自有车队数量变化分析

为了观察自有车队和租赁车队对成本的影响，本文变换自有车队数量进行了试验，计算结果如表5所示。从表5中可知，持有少量的自有车队，在总需求不变前提下，租赁车辆可以降低配送中心总成本，客户点为50时，完全使用自有车队最低成本为2579.7，自有车队持有数量降低过程中，总成本和碳排放成本逐渐降低，当自有车队数量为9时，目标函数值反而高于自有车队数量为10时，当自有车辆极少时，总成本函数值并非一直持下降趋势，而是逐渐趋于平缓，在持有车辆数为3时，成本升高，这与Krajewska and Kopfer[2]的结论是一致的。从碳排放成本变化知，如果单从配送企业来看，租赁车辆对减少自身的碳排放权消耗是有效的，但是还得进一步观察对总体碳排放量是否产生影响。可以发现，在需求不稳定时，选择自有车队的持有规模是必要的，合理的自有车队规模这给生鲜配送中心管理者提供了一定的借鉴。另一方面，从计算数据来看，租赁车辆用于补充自身运力的不足，此种方式对惩罚成本没有显著性影响，从表5中可知，完全由自有车队完成配送任务时总的惩罚成本为238.5144，随着自有车队规模的减少，惩罚成本呈现不规则变动，在持有3辆车时，惩罚成本低于自有车队配送，其他时候均高于自有车队配送。本文介绍了两种不同的租赁方式，在自有车队规模变化时，合理选择不同的租赁方式对成本有一定的影响。

表5 自有车队不同规模下成本计算数据

(四) 碳排放量变化趋势分析

图3 碳排放量变化趋势对比

本文不仅考虑了经济因素，同时考虑了环境因素，计算结果如图3所示，现有文献中考虑碳排放成本基本从社会出发，将碳排放成本计算在生鲜配送厂商自身总成本之内，因租赁车辆少消耗的碳排放权未考虑在限制之内。从图3可以看出随着降低自有车队规模，生鲜配送企业自身的碳排放量会逐渐递减，如图3中线条1，租赁所带来的碳排放权逐渐增加，如线条2，总体碳排放量基本处于稳定，如线条3。考虑各种碳排放量的变化可知，租赁车辆对碳排放量的整体影响较小，但是由此所带来的成本影响较大，这进一步表明在需求非常不稳定时，使用外部车队是配送企业优化自身成本的重要手段，且对降低碳排放有适当的作用。

综合上述分析，验证了混合遗传算法的有效性和实用性，该算法在实际应用中优于传统算法，具有一定的实际意义。其次，通过上述案例分析，也为生鲜配送企业提供了几点管理启示：一是不可提前预测需求时，自身持有一定车队，在必要时向周边租赁公司租赁类似车辆配送可以降低配送企业的总成本，因此配送企业在选址时应充分考虑与周边汽车租赁企业合作的因素，以备不时之需；二是在配送企业自身碳排放权不足时，除了在碳交易市场购买碳排放权，也可以采用租赁车辆的方式，将运输过程的碳排放转移到汽车租赁企业，以此弥补自身碳排放权；三是租赁车队虽然可以在一定程度上降低配送企业成本，但是对顾客满意度影响并不明显，因此需要和租赁企业协商，在降低成本的同时保证顾客满意度。

五、 结论与展望

本文研究了具有碳排放约束和时间窗的异构车队车辆问题，为生鲜农产品配送企业降低成本，响应国家低碳号召提供借鉴。本文提出了一个混合遗传算法来解决具有碳排放约束和时间窗的异构车队车辆问题，计算实验证明该算法有较强的鲁棒性。本文还对自有车队与租赁车队的成本和碳排放进行了敏感性分析，可为生鲜配送企业提供管理启示。计算分析表明，考虑外部车队对降低碳排放和成本是有效的，异构车队能够降低本企业的碳排放，通过不同的租赁方式和选择能够使总碳排放量变化较小，在对环境友好的前提下，降低企业配送成本。

未来可能的研究方向之一包括考虑需求的随机性等因素，使问题更贴合实际。另一个研究方向是根据问题特点，开发基于分支—割平面或分支—定价等确切算法的数学启发式算法，使问题的求解更加高效。