考虑交通状况的冷链物流路径优化

赵邦磊，桂海霞，李慧宗，王向前

（安徽理工大学 经济与管理学院，淮南 232001）

0 引言

供给侧改革下，我国冷链物流业发展机遇与挑战并行。随着产业结构调整和居民消费水平的提升，人们对生鲜食品的安全和品质提出了更高的要求，优质快捷的冷链服务就显得十分必要。对于一般产品配送而言，只需考虑配送车辆的固定成本和运输成本即可，但是生鲜产品以其易腐的特点，在配送过程中与普通产品存在着本质区别。

冷链配送车辆路径问题（Vehicle Routing Problem，VRP）一直是学界研究的热点，缪小红[1]等建立了冷链物流配送的基本模型，但是研究当中并未涉及碳约束问题。James[2]指出冷链会产生显著的碳排放量，并且认为世界上1%的排放量是由冷链业务产生的，因此奠定了从低碳视角研究冷链物流的必要性。除碳约束外，载重量[3]、能耗[4]、碳税和碳限[5]、食品新鲜度[6]等冷链配送过程中的相关影响因素也被学者们考虑其中。在模型求解上，遗传算法[7]、模拟退火算法[8]、人工蜂群算法[9]等启发式算法也得到广泛地应用，但是求解的精度还有进一步提升的空间。

上述学者们的研究考虑了配送过程中车辆行驶速度的时变性，但并未建立不同道路状况与配送路径优化模型之间的联系[10]。鉴于不同天气状况、不同时间段道路拥堵情况等因素对行驶速度产生的影响，建立车速特征影响模型，在基于各种成本条件的前提下，综合考虑客户满意度、货损比、载重量和碳约束等建立冷链物流配送路径优化模型，利用改进的蚁群算法进行求解，通过实验验证该模型的有效性与实用性。在此基础上通过比较碳约束情况下的配送成本，对碳税价格进行了灵敏度分析。

1 问题描述及模型构建

冷链物流配送问题可描述为冷藏配送中心用一定数量的车辆为客户服务的过程。配送中心和所有客户的地理位置是已知的，在一定的条件约束下，配送方案的不同会对配送成本、顾客满意度和碳排放产生不同的影响。因此找到一种配送成本最小化、客户满意度最高和货损比最低的解决方案至关重要。其中相关问题假设为：1）顾客货物需求量和时间窗要求已知；2）所有的冷藏车分配任务完成后必须返回仓库，每个客户都能得到服务且只被访问一次；3）冷藏车的载重量有限；4）车辆在运送途中会因为时间原因导致产品变质，产生货损成本；5）配送过程中不存在缺货和中途收货等其它特殊状况。

1.1 交通状况模型

恶劣天气状况、早晚高峰和节假日等都会对车辆行驶速度造成一定的影响，为了更加贴近实际，本文在天气状况基础上，构造不同时间段车速特征模型，车速影响率μi如图1所示。

图1 车速影响率

其中μi∈[0，1]，对应晴天、雨天、雪天和雾天等不同天气状况车速影响率，一天中不同时间段车速影响率也不尽相同，具体车速模型可表示为：

Sv代表不同天气状况的车速，v是正常行驶车速，[1-（±At±B）]是不同时间段车速影响率，其中A、B是常数，t是时间段。

1.2 成本模型

本文综合考虑冷链物流环节中各项成本，以冷链配送中综合总成本最小化为优化目标，综合成本包括冷链配送过程中车辆固定成本、运输成本、货损成本、制冷成本和碳排放成本等。

1.2.1 参数定义

λk：0～1变量，第k辆车被使用；fk：第k辆车的固定成本；Ckij：第k辆车从客户i到客户j每公里所花费的费用；dij：客户i到客户j之间的距离；pu：单位重量货物的价格；qi：客户i的货物需求量；ä1：车辆行驶过程中货物的腐败率；pu：单位重量货物的价格；QI：车辆送完客户i后车上所剩的货物量；δ2：车辆在卸货时间内的货物腐败率；Si：车辆在客户i所停时间；ps：单位时间运输过程中的制冷成本；pX：单位时间卸货过程中的制冷成本；Skij：车辆k在客户处所停留的时间；u1：车辆在行驶过程中单位距离油耗；u2：车辆制冷设备单位货物、单位时间油耗；pr：单位碳税价格；E：碳排放系数。

1）固定成本C1：

2）运输成本C2：

3）货损成本：

C31：运输途中产生的货损成本；

C32：车辆卸货过程中产生的货损成本；

因此，货损成本总额为：

4）制冷成本：

C41：车辆行驶过程中的制冷成本；

C42：车辆卸货过程中的制冷成本；

运输车辆制冷成本可表示为：

5）碳排放成本C5：

1.3 建立模型

考虑交通状况和碳排放的成本模型为：

式(14)表示配送车辆不能超过配送中心原有车辆，式(15)表示配送车辆在送货完成后返回配送中心；式(16)表示客户只能被访问一次，即客户只能由一辆车送货；式(17)表示客户货物的总需求量不能超过车辆的原始载重。

2 改进蚁群算法求解冷链配送问题

2.1 基本思想

上节所建立的冷链物流优化模型属于非线性模型，用一般的方法很难求解。蚁群算法是一种仿生式迭代搜索算法，对于求解非线性问题具有良好的效果，而且在全局搜索上有很强的性能，能够有效处理具有大规模节点的问题。

蚁群算法中可以将蚂蚁比作送货车辆，食物分布点比作所有的客户点，蚁穴为物流配送中心，蚂蚁们对所有食物点遍历后返回蚁穴。通过多次循环往复，蚂蚁们爬行路径都将逐渐接近于最优化爬行方案。蚂蚁选择下一食物点的规则如式(16)所示：

随着时间的推移，路径上的信息素将逐渐减弱，每次全部蚂蚁访问完所有的客户之后，路径上的信息素都会随之更新，借鉴MMAS算法（MAX-MIN Ant System）思想，信息素的变化调整可用如式(7)表示：

1）Ant Cycle System（ACS）模型：

在ACS模型中，释放的信息素量与路径距离有关，当所有蚂蚁完成一次遍历时，它们将更新所有路径上的信息素，这是一种全局更新方法。

2.3 改进蚁群算法

ACO算法在搜索过程中主要利用正反馈机理，旨在强化寻找到的性能较好的解。基本ACO算法在迭代过程中，易受早期较好解的影响，这些早期较好解以极大概率引导蚁群走向局部最优解，这是蚁群算法在搜索过程中容易出现停滞现象的主要原因。为了避免ACO算法陷入局部最优，动态改进信息素衰减系数和信息素增量，扩大最优解搜索空间。

2.3.1 衰减系数更新规则：

基本蚁群算法衰减系数是固定的，在此把信息素衰减系数更新规则改为式(19)，迭代初期给p一个较小的值，以此来扩大算法的搜索空间，寻找那些可能存在最优解的解空间，增加更优路径的可能性，避免在算法初期搜索集中在较优的几条路径，陷入局部最优；在迭代过程N中动态增加p的值，使算法在搜索过程中逐步集中在搜索到的较优路径上，加快算法收敛。

2.3.2 信息素增量更新规则

表1 客户资料表

此时式(17)可写成：

2.3 禁忌蚁群算法具体求解步骤

Step1：设定信息素重要程度系数（α），启发式重要程度系数（β），信息素增强系数（Q），最大迭代次数（N_max），蚂蚁总量（m）等初始值。

Step2：建立禁忌表，在禁忌表中把物流配送中心设置为蚂蚁们的初始位置。

Step3：设定迭代次数N=N+1，执行各步骤。

Step4：根据式(18)计算m只蚂蚁的转移概率，车辆在送货过程中应满足约束条件。车辆在当前路径上选择当前客户外的另一客户点，然后将其置于当前路径中，另一客户点不能再被别的路径车辆所选择。若找不到满足运输车辆约束条件的下一个节点时，车辆则返回物流配送中心。

Step5：如果m只蚂蚁遍历了所有客户点，得出数条以配送中心为起点并且满足约束条件的闭合路径，计算配送成本并对路径进行保存。

Step6：动态更新信息素与禁忌表。

Step7：对迭代次数进行判断，如果达到预先设置最大值，则停止迭代，输出最优结果，否则禁忌表清零，转到Step3。

3 实验验证

3.1 数据采集

本文选取某市20家生鲜超市为研究对象进行分析，通过对相关数据的分析整理，依托MATLAB 2017a版进行程序语言汇编，得出优化结果。其中配送中心和20个客户的地理位置坐标、货物需求量以及时间窗要求如表1所示。

3.2 参数设置

通过多次实验并参考相关文献，改进蚁群算法参数设置如下，信息素重要程度因子α=0.1，启发式因子β=0.5，信息素释放总量Q=10，最大迭代次数N_max=500。其它参数设置如表2所示。

表2 模型及其他参数设置

3.3 结果分析

图2是改进ACO算法配送路径图，由运行结果可知配送中心需要三辆冷藏车为其服务，车辆1路径：1-12-16-15-11-6-13-1；车辆2路径：1-17-10-7-8-4-2-1；车辆3路径：1-3-5-14-18-19-21-20-9-1，三辆车在给客户送货过程中均符合时间窗要求，配送成本为2064.01元，比ACO算法平均配送成本2268.73元减少了9%，ACO算法配送路径如图3所示，具体车辆路径为：1-17-5-7-10-4-18-1，1-8-15-6-11-16-12-1；1-13-3-2-9-14-19-21-20-1。改进算法中第一辆车载重率为88.9%，第二、三辆车载重率为100%，这样在最大程度上减少了车辆空载率，并且保证了客户满意度。具体配送路径如表3所示。

图2 改进ACO配送路径示意图

图3 ACO配送路径示意图

表3 改进ACO车辆送货表

图4是四种不同天气状况下配送成本，按照每种天气状况运行算法10次，迭代263次左右搜索到最优解，运行时间约95.76秒，晴天平均配送成本是2064.01元，在雨雪和雾天等恶劣天气状况下，平均配送成本分别是2080.87、2098.47和2120.62元，可见交通状况对配送成本有一定影响，恶劣天气下由于交通状况原因企业配送成本会有所增加。

图4 不同天气状况配送成本

3.4 碳税价格的灵敏度分析

合理开征碳税对于我国具有重要的现实意义，是我国继续坚定履行《巴黎气候变化协定》承诺的重要体现，同时可以促进我国经济结构优化和发展方式转变。不同国家和地区在不同的经济社会发展阶段，碳税的实施效果有较大差异。不同燃料所征收的碳税也有所不同，从财政部和环保部规划院课题组的建议中可以看出未来所征收碳税还将逐步提高。为了探究碳税价格的改变对配送成本的影响，在其他条件不改变的前提下，探究无碳约束、20元碳税价格和50元碳税的配送成本，对碳税价格进行灵敏度分析。

图5 具体配送成本

图6 碳税灵敏度

从图5中可以看出在不同碳约束情况下配送成本差别显著，不考虑碳约束的平均配送成本为1566.09元，而在20元碳约束的情况下，物流配送成本达到了2064.01元，比在无碳约束的情况下成本增加了497.92元，50元碳约束情况下平均配送成本为2822.32元，比在无碳约束的情况下成本增加了1256.23元。图6为在碳税不同的情况下算法运行10次的总成本增长比，当碳税价格由20元提高到50元时，成本增长由原来的31.8%提高到了36.7%，可以看出碳税价格和配送总成本呈现出正比例的关系，随着碳税价格的提高，配送成本也随之增加。通过碳税灵敏度分析说明碳税价格对成本有着至关重要的影响，考虑碳约束意味着配送过程中可以节约更多的成本。

4 结语

本文针对（VRPTW）问题进行了研究，按照不同道路状况建立了车速影响率模型，并考虑碳约束建立了多目标成本最小化函数模型，设计改进蚁群算法进行求解，提高了求解的精度。对碳约束情况下企业配送成本进行比较，得出碳税价格对企业配送成本有一定影响。在日常生活中，企业可能会忽视碳约束对成本的影响，为了更好地减少企业运行成本并兼顾社会效益，冷链物流走低碳之路是十分必要的。企业应树立低碳理念，在物流配送过程中将碳约束也进行考量，在提高企业经济效益的同时兼顾社会效益。碳税是一个有效的环境经济政策工具，能有效地减少CO2排放。尤其从中长期来看，可以降低能源消耗，并在一定程度上改变能源消费结构，促进我国的可持续发展。