考虑碳排放成本的冷链物流配送车辆路径优化*

程元栋 韩佰庆

(安徽理工大学经济与管理学院 安徽淮南 232000)

我国经济发展迅速，人民越来越注重生活品质，尤其是食品质量与新鲜食品安全问题。且伴随着互联网技术的精益发展，近几年我国冷链物流发展突飞猛进，在准确定位、货品实时信息共享、精准配送、及时供给等方面拥有高效的服务技术。在各经营企业实施精细化生产服务的背景下，客户对物流的服务要求越来越高，与普通货品物流运输相比，由于生鲜农产品的特性，冷链物流对产品质量的把控更为严格，送达时效性要求更高，进而导致配送成本增高。目前我国部分物流企业存在生鲜农产品配送路径冗杂、经营效率低效果差、高成本、高碳排放等问题，众多问题限制其发展，因此冷链物流配送问题成企业关注的重中之重。

车辆路径问题(vehicle routing problem，VRP)在1959年由学者Dantzig和Ramser首先提出，描述为配送车辆由配送中心出发为已知需求量和位置点的客户进行服务，并对车辆的行驶路线做最优的规划[1]。VRP一经提出当即就成为学者关注的热门研究点。在生鲜农产品车辆路径优化问题上国内外学者进行了大量的研究。Tarantilis采用随机搜索算法为生产经营新鲜肉类食品的厂商规划配送路线，将产品送达多个客户[2]。Andrew Lim采用禁忌算法与遗传算法二者相结合的改进算法研究生鲜农产品车辆配送问题[3]。Solomon与Desrosiers较早把时间窗格限制引入到车辆路径研究中[4]。基于此，众多学者关注时间在VRP的重要性。Qiulei Ding等使用调整信息素的混合蚁群算法构建多目标函数模型求解考虑时间窗限制的农产品车辆路径优化问题[5]。我国学者也进行多方面的研究，孙溢擎分析了大数据背景下我国冷链物流终端配送的发展现状和存在的问题，并且给出大数据技术对冷链物流终端配送优化方法的意见[6]；王恒认为道路状况是影响配送路线定制的不可忽略因素之一，他综合考虑道路状况、时间窗、生鲜损耗等因素构建生鲜农产品配送路径的多目标优化模型，运用模拟退火改进的自适应遗传算法进行验证例算[7]；葛显龙运用改进遗传算法求解前置仓协作的两极配送路径优化问题[8]；何有世研究生鲜电子商务企业B2C(business to consumer)的运营模式，在冷链物流配送活动中充分考虑顾客的满意度，构建总成本最小顾客满意度最高的双重目标[9]。

以上研究不但考虑了影响车辆配送的各个因素，在计算方法上也多种多样，研究目标不仅关注经济层面。还加入满意度等心理感知层面。随着我国越来越倡导绿色发展理念，碳排放因素也逐渐成为研究VRP的一大要素。国外最早是Lin与Choy将碳排放引入到物流研究之中，认为企业在制定物流决策时不能单纯的考虑传统经济成本，还要考虑其对生态环境社会层面的影响，故引入碳排放[10]。随着考虑碳排放的研究越来越深入，Elhedhli在关注碳排放的供应链中，提出用一个凹函数来表示碳排放量与车辆载重量之间的关系，通过计算检验得到考虑碳排放可使供应链达到最佳的配置的结果[11]。我国学者中，段砚关注农产品冷链物流的碳排放量多货损率高的问题，构建了计算碳排放成本、货损成本和时间成本的路径优化模型，以北京某公司为多个客户做配送服务为实例展开研究，得到降低总成本的结果[12]；肖瑶采用碳税制度将配送过程中产生的二氧化碳成本化，对总成本进行分析，借鉴Solomon标准测试数据集构造算例并求解，发现考虑与不考虑碳排放模型这两个方案中，冷链配送企业考虑碳排放因素不但能提高社会效益还能节约企业运营成本[13]。

综上所述，考虑碳排放的冷链物流研究相对于不考虑碳排放情况的冷链物流和考虑碳排放情况的普通物流还是较少。文章的主要创新：①关注因燃油消耗产生二氧化碳而产生碳排放成本这一现象，分析碳排放成本的影响，构建的数学模型引入碳排放因素，求解优化冷链物流中的生鲜农产品配送车辆路径。充分考虑配送过程中产生的五大成本，包括发生在配送车辆上的固定费用；随配送动作发生，时间流逝生鲜农产品新鲜度下降而产生的腐败变质和货物装卸搬运过程中发生磕碰而产生的生鲜损耗成本；车辆制动与运输产生的燃油消耗费用，此部分成本与运输距离、车载重量、燃油价格等因素有关；碳排放成本，文章计算碳排放成本的方法建立在燃油消耗的基础上的，车辆运输与制冷消耗燃油的总量通过单位碳排放系数进行折算再乘碳价格则能计算出；时间惩罚成本，在给定的时间范围内早送达或晚送达都会产生一定的惩罚成本，严重超出范围导致客户拒绝接收货物会产生更大的违约成本。②文章设计了一个邻域搜索算法与蚁群算法相结合的改进蚁群算法，相对于单一算法具有优势，该算法产生更好的初始解加快收敛，更优的搜索机制提高算法随机搜索效率。③通过Matlab进行编码运算，分别采用未改进蚁群算法、改进的邻域搜索蚁群算法对模型进行求解，对比两种算法不考虑碳排放、考虑碳排放的四种求解结果，比较得出客户网络全局最优配送路线，有效降低配送成本，对企业更有利，而且符合国家低碳发展大环境。

1 问题描述与模型构建

1.1 问题描述

在当今生态环境日益严峻的背景下，物流配送路径优化问题不再单纯的只考虑经济方面的影响，对生态环境的影响也加进了物流经营的重点考虑范围之内。对此，冷链物流配送环节中配送车辆制动与行驶过程中燃油消耗产生的二氧化碳排放量及碳排放成本成为研究的焦点。为了更好地理解所要研究的问题，具体问题可以描述为：文章中已知配送中心与各个客户点的位置，具有低温冷藏功能的运输车辆为各个客户点进行生鲜农产品的配送，有多个配送路径方案可供选择，冷藏运输车辆只需按照已经规划好的路径完成配送任务，若最终生鲜农产品到达客户点的时间早于或者晚于客户最佳期望时间，会分别产生惩罚成本除此之外还关注冷藏车辆固定费用、生鲜损耗成本、燃油消耗费用、碳排放成本，计算各部分成本涉及到的参数已知。

1.2 做出假设

(1)假设只有一个配送中心为多个客户点进行配送服务，配送中心拥有多个冷藏运输车辆；

(2)货物为生鲜农产品，每个车辆起点为配送中心，完成配送任务后，最后返回配送中心；

(3)大数据时代，配送中心拥有成熟的互联网实时信息共享系统与大数据定位系统，因此文章所涉及的配送中心、各个客户点位置、产品需求量、客户期望最佳服务时间区间及客户最大限制可接受服务时间区间已知；

(4)所有配送车辆为同一品牌，规格性能统一，因此冷藏制冷效果相同，承载能力相同，且已知最大承载能力；

(5)任一个客户点的需求量都在配送车辆承重范围内，且车辆配送的货物总量不超过其最大载重量；

(6)不考虑途中车流量、路况、天气、意外等因素的影响，配送车辆以相同的速度匀速行驶；

(7)配送车辆按照合理配送路线行驶，为使成本最小，达到车辆最大使用效率，每个客户点的需求必须满足且仅由一辆配送车辆进行服务，每辆车可向多个客户点提供配送服务；

(8)配送车辆最大行驶距离大于一条配送路径的总长度，并且能返回配送中心。

1.3 模型建立

1.3.1 符号描述 为了描述方便，将所有使用的符号和决策变量定义如下：

G={N，E}：G表示为配送网络集合，E={(i，j)/i，j∈N，i≠j}为配送中心与客户点的弧集，N={0，1，2，3，4，…，n}为所有客户节点的集合；

O：配送中心；

K={1，2，3，4，…，k}：配送车辆数目集合；

fk：在配送车辆k上所发生的费用；

Lij：客户i与客户j之间的距离；

qi：客户点i对生鲜农产品的需求量；

p：每单位生鲜农产品的价格；

ti：配送车辆到达客户i的时刻；

T：生鲜农产品的保质期；

tsi：配送车辆停经客户i进行服务所需要的时间；

tij：配送车辆从客户i到达客户j所需要的时间；

[Eti，Lti]：客户i可接受货物到达的时间窗；

[Et*i，Lt*i]：客户i期望货物到达的最佳时间窗；

α：配送车辆提前于Eti时刻到达客户点产生的惩罚成本系数；

β：配送车辆晚于Lti时刻到达客户点产生的惩罚成本系数；

φ：生鲜农产品新鲜度对时间的敏感系数；

μ：生鲜农产品在装卸搬运过程中损坏比例；

Qe：配送车辆载重量；

Q0：配送车辆自身重量；

Q*：每辆运输车最大承载量；

ρ0：空载时配送车辆油耗率；

ρ*：满载时配送车辆油耗率；

Ce：单位碳价格或碳税价格，以当日碳交易市场价格为准；

ω：碳排放系数；

Pf：每单位燃油价格

Cf：单位距离油耗成本；

xkij：配送车辆k是否进行由客户点i到客户点j的配送服务，是xkij=1，否则xkij=0；

yki：客户点i是否是由配送车辆k进行服务，是yki=1，否则yki=0。

1.3.2 冷藏车辆固定费用 冷藏车辆固定费用是指直接发生在车本身的关于执行配送任务而产生的费用，包括车辆单日租赁费用，车辆保险费用，车辆维护费用，人工驾驶工资，与工作时长有关的装卸工人工资等组成，因此可以表示为：

(1)

1.3.3 生鲜损耗成本 因为生鲜农产品是物流配送面向的一种比较特殊的产品，其具有易腐败的特性而且对时间有严格的要求。生鲜农产品在运输、搬卸的过程中随时间延长导致产品水分流失新鲜度下降甚至腐败以及搬卸导致产品磕碰产生的损坏都会产生一定的货损成本。参考学者研究结果，冷链物流配送过程中生鲜农产品的品质与配送时间长短有关，所花时间越短越能保证其新鲜度，新鲜度的损耗与运输时间为指数函数关系[14]：

Xt=e-φti

(2)

因此，生鲜损耗成本可以表示为：

(3)

式(3)中，e为常数，ti为冷藏运输车到达客户点i的时刻，φ为生鲜农产品与时间相关的腐败变质的速率，μ为在装卸搬运过程中生鲜农产品磕碰损坏率，qi为客户点i对生鲜农产品的需求量，p为生鲜农产品的单位价格。

1.3.4 时间惩罚成本 因为生鲜农产品时效性比较高，在实际市场经营中客户对产品送达的时间有一定的预期，一般都希望在预期范围货物尽早送达尽早销售，因此客户大多设置了时间窗格，在客户i期望货物到达的最佳时间窗[Et*i，Lt*i]内送达货物，此时不产生任何时间成本，客户也很乐意此时收到货物，[Eti，Lti]为客户i可接受货物到达的时间窗，表明在最理想早送达时间Et*前收到货，但是不早于Et时间点，还有在最理想晚送达时间Lt*后收到货，但是不晚于Lt时间点客户可以勉强接受货物，但会分别产生一定的时间惩罚成本，在EtiLti时间送达，客户将会拒绝接受，因此将会产生常数M的惩罚，M是一个较大的常数。综上，配送车辆早到或晚到客户点所产生的时间惩罚成本为：

(4)

1.3.5燃油消耗费用 在冷链物流配送活动中运输是最为主要的工作，在冷藏车辆行驶与制冷装置工作都要消耗燃油，燃油消耗成本占冷链物流配送综合费用的大部分，其费用不容忽视。计算燃油消耗成本的总体思路是燃油消耗总量乘实时单位油价，根据文献，单位距离油耗ρ与冷藏车辆的载重量Qe近似呈线性函数关系[16]，假设为：

ρ(Qe)=a(Qo+Qe)+b

(5)

Qo表示车辆本身的重量，当车辆空载时燃油消耗量为：

ρ0=aQ0+b

(6)

Q*表示车辆最大承载量，当车辆满载时燃油消耗量为：

ρ*=a(Qo+Q*)+b

(7)

两式联立，可得

(8)

进而得出单位距离油耗ρ与冷藏车辆的载重量Qe的关系式为：

(9)

单位距离燃油消耗成本为单位距离油耗乘燃油价格：

Cf=ρ(Qe)·Pf

(10)

所以燃油消耗成本为：

(11)

1.3.6 碳排放成本 燃油消耗会产生二氧化碳气体，冷链物流配送过程碳排放成本计算公式为：

F5=Ce·ω·ρ(Qe)·Lij

(12)

ρ(Qe)·Lij表示客户点i到客户点j消耗的燃油总量；ω表示碳排放系数，ω·ρ(Qe)·Lij表示客户点i到客户点j消耗的燃油产生的二氧化碳总量，Ce是单位碳价格或碳税价格。

综上所述，文章构建的以总成本最小为目标的生鲜农产品冷链物流配送路径优模型为：

minF=F1+F2+F3+F4+F5

(13)

s.t.

(14)

(15)

(16)

(17)

(18)

(19)

Eti≤ti≤Lti，∀i∈N

(20)

(21)

式(13)表示要求总成本最小的目标函数；式(14)表示第冷藏车配送该路径货物总重量不超过其最大载重量；式(15)表示第冷藏车配送该路径总里程不超过其最大行驶距离；式(16)表示执行任务的冷藏车辆数目小于等于配送中心车辆总数；式(17)和式(18)表示每个客户点只能由一辆冷藏车服务一次；式(19)表示每辆冷藏车起点为配送中心，完成配送任务后，最后返回配送中心；式(20)表示送达货物时间要满足客户的时间窗约束；式(21)表示配送过程的连续性。

2 改进的蚁群算法

蚁群算法是一种智能启发式算法，模拟原理是蚂蚁群寻找食物的过程，过程中个体会留下一种特有的信息素分泌物，能达成信息共识，为其他蚂蚁选择觅食路径时提供一定的依据，在相应的最短路径上，随着蚂蚁经过的越来越多，分泌物也会积累越多，进而信息素浓度越高，又随着信息素浓度越来越高，会吸引更多蚂蚁走这条路径，形成正促进，最后找到最优路径。

利用蚁群算法求解车辆路径问题中，随着客户点的增多，可选求解方案众多，搜索时间较长且收敛速度较慢，对搜寻最优解带来了困难。文章对蚁群算法进行优化，邻域搜索算法改进蚁群算法，使用CW节约法构造算法初始解，在算法中加入2-OPT邻域搜索算子，随机逆转操作等进行优化，其结合邻域搜索算法的优点，具有较强的鲁棒性和搜索能力，在全局选择中有较高分类性能，是一种在巨大搜索空间中估计全局最优的元启发式算法，来逼近给定函数的全局最优值。

改进蚁群算法主要步骤如下，具体算法流程见图1：

图1 改进的蚁群算法流程图

步骤1设置初始化参数，导入各客户点信息，蚂蚁数量为m，客户点数量为n，初始迭代次数Cyclestart=0，最大迭代次数为Cyclemax，Cycle≤Cyclemax；

步骤2迭代寻找最佳路径，迭代次数加1；

步骤3初始阶段，构建解空间，轮盘赌法为蚂蚁的起点位置进行随机性选择；

步骤4对客户点操作，根据转移规则选择下一个待访客户点，直至蚂蚁完成一次循环形成一个路径，记录并更新路径表；

步骤5更新信息素；

步骤6蚂蚁数加一，重复步骤4，直至所有蚂蚁访问完所有客户点；

步骤7完成一次循环，计算该次循环中最短路径距离与成本，并同步记录；

步骤8判断是否达到最大迭代次数，若否，则返回步骤2开始再一次迭代；若是，则终止循环，进行下一步；

步骤9输出最优解。

3 算例分析

3.1 实例设置

根据收集到的数据，问题设置如下，把某地一配送中心标号为0，对26个客户进行生鲜农产品配送，已知具体信息，配送中心与客户点位置、需求量如表1所示；配送中心与各客户点间距离如表2所示；各客户点设置的最优服务时间窗、可接受服务时间窗、所需工作时间如表3所示。可供使用的配送车辆有10辆，每辆车固定使用费用500元，车型性能规格相同，车辆最大载重量Qe为5 t，行驶平均速度v为60 km/h，车辆单位距离行驶费用为2 元/公里，车辆满载时单位距离油耗ρ*为0.5 L/km，空载ρ0时0.2 L/km，碳排放系数ω为0.05，单位碳价格为10元，生鲜农产品单价为5 元/千克，运输过程中的新鲜度对时间的敏感系数φ为0.1，装卸搬运过程中磕碰导致货损比例μ为0.05。

表1 节点位置坐标与需求量

表2 配送中心与客户点间距离

表3 最优时间窗、可接受服务时间窗、工作时间

3.2 模型求解与结果分析

根据生鲜农产品配送的具体要求，文章运用Matlab进行仿真求解，分别计算未改进蚁群算法不考虑碳排放成本情况、未改进蚁群算法考虑碳排放成本情况、改进的邻域搜索蚁群算法考不虑碳排放成本情况、改进的邻域搜索蚁群算法考虑碳排放成本情况，在满足时间窗限制与车辆载重约束条件下得出最优路径。

(1)情况1：未改进蚁群算法求解不考虑碳排放的生鲜农产品配送路径。当不考虑碳排放因素时，此时配送企业忽略计算碳排放成本，结果显示配送过程中需要3辆车，第1辆车的配送路径为0→1→5→23→22→18→3→15→20→9→24→19→8→4→12→2→16→0；第2辆车的配送路径为0→17→6→13→26→25→0；第3辆车的配送路径为0→10→11→7→21→14→0；车辆行驶总里程为366.51 km，总成本为4882.19元，计算中出现最大行驶距离为418.13 km，最大总成本为4983.46元。

图2 未改进蚁群算法不考虑碳排放路径图

(2)情况2：未改进蚁群算法求解考虑碳排放的生鲜农产品配送路径。当考虑碳排放因素时，此时配送企业把因碳排放产生的成本加入到总成本计算中，结果显示第1辆车的配送路径为0→1→22→23→5→15→24→8→19→4→12→2→9→20→10→16→18→0；第2辆车的配送路径为0→3→13→6→25→17→0；第3辆车的配送路径为0→14→26→21→11→7→0；车辆行驶总里程为317.95 km，总成本为4772.63元，计算中出现最大行驶距离为371.58 km，最大总成本为4857.19元。

图3 未改进蚁群算法考虑碳排放路径图

(3)情况3：改进邻域搜索蚁群算法求解不考虑碳排放的生鲜农产品配送路径。当不考虑碳排放因素时，结果显示第1辆车的配送路径为0→1→2→19→8→24→4→12→18→3→15→20→9→23→5→16→22→0；第2辆车的配送路径为0→25→13→6→7→11→0；第3辆车的配送路径为0→10→17→14→26→21→0；车辆行驶总里程为370.40 km，总成本为4 731.31元，计算中出现最大行驶距离为386.03 km，最大总成本为4 821.44元。

(4)情况4：改进邻域搜索蚁群算法求解考虑碳排放的生鲜农产品配送路径。当考虑碳排放因素时，结果显示第1辆车的配送路径为0→1→22→23→5→3→18→15→8→19→24→4→12→2→20→9→16→0；第2辆车的配送路径为0→17→6→13→26→21→0；第3辆车的配送路径为0→14→25→10→11→7→0；车辆行驶总里程为324.91 km，总成本为4 692.49元，计算中出现最大行驶距离为363.47 km，最大总成本为4 831.88元。

图5 改进邻域搜索蚁群算法考虑碳排放路径图

对比情况1与情况2可知，用未改进蚁群算法分别求解不考虑碳排放因素、考虑碳排放因素的最优配送车辆路径，总里程为366.51 km与317.58 km，考虑碳排放因素相对于不考虑碳排放因素求解最优路径配送总里程减少48.93 km，下降13.35%，两种情况总成本为4 882.19元与4772.63元，考虑碳排放规划的路径使总成本降低109.86元；同理，对比情况3与情况4可知，采用改进邻域搜索蚁群算法分别求解不考虑碳排放因素、考虑碳排放因素的最优配送路径，总里程为370.40 km与324.91 km，考虑碳排放因素相对于不考虑碳排放因素求解最优路径配送总里程减少45.49 km，下降12.28%，两种情况总成本为4 731.31元与4 692.49元，考虑碳排放规划的路径使总成本降低38.82元。说明两种算法中考虑碳排放因素都会比不考虑碳排放因素的情况获得更低的总成本。单独比较分析算法的优劣，在不考虑碳排放因素的情况下，情况1运用未改进蚁群算法，情况3运用改进的邻域搜索蚁群算法，情况3对于情况1总里程增加约4 km，变化不明显，但总成本减少150.88元；在考虑碳排放因素的情况下，情况2运用未改进蚁群算法，情况4运用改进的邻域搜索蚁群算法，情况4对于情况2总里程增加约7 km，变化不明显，但总成本减少80.14元，说明在计算上运用改进的邻域搜索蚁群算法更有优势，搜寻的路径更优，得到的总成本最低。综合上述分析，文章运用的改进的邻域搜索蚁群算法在求解冷链物流路径优化问题时比未改进蚁群算法具有明显优势，验证了改进的邻域搜索蚁群算法的高效性和实用性，具有较强的鲁棒性，能够有效解决冷链物流路径优化问题，能快速寻找最优路径。

4 结论与展望

文章研究内容是生鲜农产品配送车辆路径问题，相较于传统物流配送，不但要满足客户制定的时间窗限制，而且还考虑碳排放这一因素并将其转化为总成本的一部分，构成考虑碳排放成本、冷藏车辆固定费用、时间惩罚成本、生鲜损耗成本、燃油消耗费用的冷链物流路径优化模型，根据客户点信息，如位置、需求量、时间窗、装卸搬运时间等分别运用未改进蚁群算法和改进的邻域搜索蚁群算法进行求解，通过对比实例结果，表明考虑碳排放之后，改进的邻域搜索蚁群算法有效降低了冷链物流总成本，增大社会效益，并积极响应了政府绿色经济发展的号召，这对生鲜农产品配送企业和政府在提高绿色配送效率、实现绿色经济收益具有现实借鉴意义，并且为今后考虑碳排放的冷链物流配送路径研究提供依据。对相关研究的展望，研究方向可以定位在考虑将碳排放这一因素加入到其他物流要素中，使降低碳排放目标在物流产业全面化；或定位在求解冷链物流路径优化问题创新性的应用更多改进算法；或求解目标不应仅局限在经济成本上，应该加入顾客满意度或者可数值化的其他社会效益等目标。