考虑碳排放的农产品冷链物流配送路径优化研究

段 砚，蒋洪伟

(北京信息科技大学 信息管理学院，北京 100192)

0 引言

自Dantzig 提出车辆路径问题(vehicle routing problem，VRP)后，该问题引起国内外学者的广泛关注。Miroslav[1]通过冷链产品的腐败时间变化构建了冷链路径的优化模型；Ahbrid[2]采用遗传算法禁忌算法相结合的方法研究冷链物流车辆路径规划问题；Montanari[3]从物流管理的角度提出了结构化框架来确定最合适的物流配送路径以最大限度地降低物流成本。王红玲等[4]提出使用改进的粒子群算法求解生鲜农产品路径优化模型；张云川[5]在现有的第三方冷链物流配送路径优化研究的基础上建立新的成本和约束模型，并给出采用模拟退火算法的优化方法；王智忆[6]建立以碳排放量最低为目标的配送路径优化模型，运用蚁群算法进行路径优化；詹长书[7]基于标准遗传算法的基本思想和原理研究了城市冷链物流配送决策问题，并利用周期进化遗传算法对构建的城市冷链物流路径数学模型进行求解。本文研究了农产品冷链背景下的车辆配送路径规划，考虑在多种条件限制下，车辆如何选择最优路径，以保证配送中车辆运输距离最短、运输成本最小，并结合低碳物流的要求，减少碳排放量。

1 数学建模

1.1 模型描述

已知农产品配送中心的位置坐标及每个配送点的位置坐标，农产品配送中心使用的运输工具是能够进行低温冷藏农产品的运输车辆，冷藏运输车辆在运送过程中只需按照规划好的路径进行配送。配送车辆需要在配送点规定的农产品到达的时间窗范围内完成配送，若最终农产品到达配送点的时间不在配送点的规定时间窗范围内，农产品配送中心需向配送点进行一定的赔偿作为时间惩罚成本。

综合上述约束条件，在农产品配送过程中需要考虑的总成本包括固定成本、运输成本、碳排放成本、货损成本和时间窗惩罚成本，本文综合以上各项成本构建了以总成本最小为目的的农产品冷链物流配送路径优化模型。

1.2 模型假设

本文在建立考虑碳排放的农产品冷链物流配送路径优化模型时做出如下假设。

1)农产品配送中心是唯一的，配送车辆完成自身的配送任务后直接返回配送中心，不存在车辆运输途中收货的情况。

2)农产品配送中心的所有配送车辆都是同一型号的，且配送车辆的最大车载重量等信息都是相等且已知的。

3)每个配送点的农产品需求量是已知的，且其需求量都是在冷藏车辆的最大载重范围内。

4)每个配送点的位置坐标和配送点的需求时间都是已知和固定不变的。

5)每辆配送车辆的速度都是固定的，都为匀速行驶。

6)农产品货损只与配送车辆的配送时间有关，外界的温度变化对车内农产品质无影响。

7)规定每个配送点的农产品需求都是静态的，不存在车辆配送途中配送点的需求发生变化，不会对已规划好的车辆配送路径进行改变。

1.3 模型参数

模型中用到的参数和变量如下。

F:目标函数；

V:配送点集合，V={v1,v2,v3…vn}；

K:配送车辆集合，K={k1,k2,k3…km}；

dij:需求点i和需求点j之间的距离；

mi:需求点i对农产品的需求量；

Q:配送车辆的最大载重量；

λ1:农产品配送车辆早于配送点时间窗的惩罚系数；

λ2:农产品配送车辆晚于配送点时间窗的惩罚系数；

Eti:配送点i可接受配送服务的最早时间；

Lti:配送点i可接受配送服务的最晚时间；

c0:单位碳排放费用；

e0:CO2排放系数；

ρ:配送车辆的单位距离燃料消耗量；

ρ0:配送车辆空载时的单位距离燃料消耗量；

ρ*:配送车辆满载时的单位距离燃料消耗量；

N:农产品的单位价值；

α:农产品对时间的敏感系数；

β:农产品的变质速度；

Ck:使用一辆运输车辆的固定费用；

1.4 模型建立

冷链物流配送过程中农产品品质和配送时间时间呈指数变化关系，建立农产品损耗与配送时间的损耗函数：

Q(t)=e-αtQ0

(1)

式中：Q0为农产品在的初始状态的品质；α为在特定温度下农产品的腐败变质速率；t为配送时间；e为常数。

配送车辆到达配送点时，所产生的农产品货损成本为

(2)

冷藏车在农产品配送途中所产生的二氧化碳一部分是来自于车辆自身燃油消耗，还有一部分是车厢内部制冷剂消耗所产生的。结合两部分的碳排放，本文的研究中碳排放成本利用碳税成本进行计算。设碳税为一个固定值c0，那么在农产品运输途中所产生的碳排放成本为

(3)

运输途中所产生的冷藏车辆的固定成本为

(4)

冷藏车辆的运输成本为

(5)

农产品配送时还需考虑客户的时间窗需求，如果农产品配送车辆早于客户规定的时间窗，那么农产品配送车辆就会在配送点进行等待，因为农产品品质和时间是紧密相关的，因此运输车的等待也会产生相关费用，该费用作为早于客户时间窗的惩罚成本。如果晚于客户规定的最晚送达时间窗，根据客户的意愿产生晚于时间窗惩罚成本。综上，单位农产品运输车早到或者晚到配送点所增加的时间惩罚成本为

(6)

基于以上成本的分析，建立考虑碳排放的农产品冷链物流配送路径优化的数学模型为

minF=F1+F2+F3+F4+F5

(7)

s.t.

式(7)目标函数为总成本最小，总成本包括车辆固定成本、车辆运输成本、运输途中农产品货损成本、碳排放成本和时间窗惩罚成本；式(8)为农产品在配送过程中，车辆的实际载重在配送车辆的最大载重范围内；式(9)为配送中心提供的配送车辆的数量不能超过配送中心的全部配送车的数量；式(10)～(12)为每个配送点都只能接受一次配送服务；式(13)为配送车辆的配送时间要在客户规定的时间窗范围内；式(14)、(15)为配送车辆完成各配送点的配送需求后返回配送中心。

2 改进的人工蜂群算法

人工蜂群算法是运用群智能思想，通过观察模仿蜜蜂采蜜行为所提出的一种优化方法。该算法最早是在2005年由Karaboga为了解决多变量函数优化的问题所提出的，主要特点是不需要了解求解问题的特殊信息，只对比问题的优劣度，将人工蜂群中的个体寻优行为凸显在在全局最优解中，有着较快的收敛速度。

2.1 求解路径规划的人工蜂群算法

2.1.1 构造食物源编码

本文采用自然数编码方式，具体可表示为

(0,r11,r12,…,r1n;0,r21,r22,…,r2n;0,rm1,rm2,…,rmn)

含义为第1辆车的配送点为r11,r12,…,r1n；第2辆车的配送点为r21,r22,…,r2n；…；第m辆车的配送点为rm1,rm2,…,rmn。假设现有3辆车7个配送点，食物源编码则为01350270460，其表示第1辆车的配送路线为0-1-3-5-0，第2辆车的配送路线为0-2-7-0，第3辆车的配送路线为0-4-6-0。

2.1.2 生成候选食物源

本文采用交换邻域点的方法，随机交换食物源中的两个邻域点得到候选食物源。以上文食物源编码0135027046为例，图1表示交换前和交换后的食物源，可见通过交换第3位和第7位的点，得到候选食物源。

图1 生成候选食物源编码

2.1.3 适应度函数

适应度函数是根据所建立的考虑碳排放的农产品冷链物流配送路径优化模型的目标函数转化得到的，因为模型中的目标函数追求成本最小化，所以目标函数的倒数作为人工蜂群算法的适应度函数[10]：

(15)

2.1.4 算法步骤

本文采用人工蜂群算法求解考虑碳排放的农产品冷链物流配送路径优化问题的具体步骤为：

1)设置车辆、配送点信息，采用自然数编码方式对其进行编码；

2)设置参数，设置车辆数为K，种群大小为NP，最大迭代次数为maxCycle，限制次数为Limit；

3)初始化种群，生成初始可行解，并计算其适应度值；

4)进行局部搜索，计算适应度值并与当前解进行比较；

5)计算每个解被选择的概率；

6)跟随蜂根据概率大小选择一个解，并在该解附近进行邻域搜索，保留适应度值大的解；

7)判断搜索次数是否大于Limit，如果是则放弃该解，如果否则记录当前最优解，选择最优路径；

8)判断迭代次数是否达到最大值MaxCycle，若达到，输出最优配送路径，若未达到，则转至步骤4)继续进行迭代。

利用人工蜂群算法求解考虑碳排放的农产品冷链物流配送路径优化模型的流程如图2所示。

图2 农产品冷链物流配送路径问题的人工蜂群算法流程

3 实验仿真

本文采用改进的人工蜂群算法，以北京华康绿源食品有限公司的26个顾客作为配送点进行分析求解，获取每个配送点的经纬度，并在此基础建立平面直角坐标系，配送点与农产品配送中心的直角坐标系的位置如图3所示。

图3 农产品配送中心及配送点坐标图

北京华康绿源食品有限公司的冷藏车每天从农产品配送中出发的时间为早上5点钟，出发后一次将农产品送到每个配送点，农产品配送中心共有10辆待选的冷藏车，其中冷藏运输车辆全部为同种型号，发动机均为柴油发动机，车自身重量为2500 kg，车辆最大载重量3000 kg，车辆的最低油耗速度为60 km/h，单位车辆固定成本为565.74元，单位油耗成本为6.521元，单位碳排放成本为0.643元。根据每个配送点的地理位置坐标、需求量、服务时间和时间窗等数据分别采用基本的人工蜂群算法和改进的人工蜂群算法进行求解，程序运行10次，选择成本最少的一组数据作为对比对象，得到基本人工蜂群算法与改进人工蜂群算法算法仿真结果如表1所示。

表1 基本ABC算法与改进ABC算法仿真结果的对比

利用改进的人工群峰算法求得农产品配送中心需要7辆冷藏运输车进行配送，总成本为5909.066 5元，其中货损成本为325.589 6元，占比5.51%；碳排放成本为213.908 2元，占比3.62%；时间窗惩罚成本为251.726 2元，占比4.26%；运输成本为2747.125元，占比46.49%；固定成本为2371.308元，占比40.13%。最终得到考虑碳排放的农产品冷链物流优化配送路径如表2所示。

表2 考虑碳排放的冷链物流车辆配送路线

4 结束语

本文的研究内容是农产品冷链物流的车辆路径问题，在配送过程中考虑了碳排放成本、农产品货损成本和客户时间窗成本。根据配送的各项成本构建了农产品冷链配送路径的数学优化模型，结合邻域搜索对人工蜂群算法改进用于模型求解。本文以北京华康绿源食品有限公司的26个配送点为算法案例，根据每个客户的地理位置坐标、需求量、服务时间和时间窗等数据分别采用基本的人工蜂群算法和改进的人工蜂群算法进行求解，最终结果证明改进后的人工蜂群算法有效降低了农产品冷链物流成本。