1. 引言
近年来,地球的温室效应已经受到了世界各国的重视,每个国家都根据自身的实际情况制定了相应的节能减排策略。交通运输过程中所产生的碳排放在所有碳排放的过程中占据了很大的比例,而物流行业作为道路交通运输中高耗能、高碳排放的行业,如何能够减少碳排放、寻找可持续发展方法的同时保证相关企业的成本不会增加成为学者们研究的一个热门问题。
VRP问题指车辆路径问题,是被普遍公认的NP问题,最早由Dantzig和Ramsen [1] 于1959年首次提出,Solomon [2] 在前者的基础上首次将时间窗的理念引入到VRP问题的求解中,Ombuki [3] 分别将配送路线总耗时和占用车辆数目定为优化目标,使用两种启发式算法进行求解,并发现该混合式算法的求解结果优于单一算法的求解结果。石建力和张锦 [4] 在建立VRP模型时,使用了将部分条件假设成不确定因素。范立南 [5] 则根据货物的特性,在建立VRP模型时,将生鲜农产品的腐蚀函数加入到其中并进行求解。邱雅君和宋国防 [6] 在VRP模型当中,研究了考虑碳排放因素的车辆路径问题,但在碳排放的计算中将距离视为主要影响因素,却忽视了车辆载重对于油耗的影响,朱长征和李艳玲 [7] 将碳排量作为目标建立VRP模型,对前者进行了补充并用遗传算法进行求解。
以上文献对于VRP模型的建立进行了深入研究,同时学者们对于该问题的求解算法也进行了深入的研究。张丽萍 [8] 等人通过对遗传算法中的交叉过程进行改进,加快了遗传算法的迭代速度。张海刚 [9] 在求解带有硬时间窗的车辆路径问题时,将免疫算法的理念引入到遗传算法的交叉和编译过程当中,并于其他遗传算法进行对比,发现该算法的计算结果优于其他遗传算法且迭代次数较少,显著提高了收敛速度。杨宇栋 [10] 使用模拟退火算法求解该问题时发现,模拟退火算法计算效率较高,且结果相对稳定。康凯 [11] 在建立生鲜农产品配送模型时,考虑了碳排放和时间窗的因素,在求解过程中使用了带有局部搜索机制的改进蚁群算法,得到了较为理想的结果。
通过对以上文献进行分析后可以发现,在模型的构建方面,从最短距离的单目标规划问题中加入多个影响因素成为多目标规划问题,如客户满意度、时间窗约束、碳排放、配送路径的拥堵程度等多个方面,能够使模型更加逼真地模拟出不同配送环境,且在当前的研究趋势当中如何根据配送货物的不同特性建立模型成为研究者们的热点,使其结果能够更加贴近实际。在模型的求解方面,智能算法针对非线性规划问题能够表现出较好的空间求解能力和鲁棒性等优点,学者们在总结出不同算法的优点后进行算法融合,如何有效地避免陷入局部最优解的同时提升模型的收敛速度成为研究者们的热点问题。本文以某市配送中心为例,将各个需求地抽象为需求点,在建立车辆路径配送模型时加入碳排放以及时间窗惩罚机制的因素,降低碳排放同时考虑车辆的行驶里程和载重影响。将这两种因素加入到配送成本当中,以总配送费用最小作为优化目标,使用遗传算法求解该问题的方法。
2. 问题描述与基本假设
2.1. 问题描述
该地共有2个配送中心,每个配送中心拥有的配送车辆型号相同,共有18个需求点需要配送,每台配送车辆固定费用为200元,每个需求点的服务时间为10 min,加入碳排放以及时间窗惩罚机制、车辆负重空余以及配送车辆的体积限制。该地配送中心及需求点如图1所示:
![](//html.hanspub.org/file/15-2760492x9_hanspub.png)
Figure 1. Location of demand and distribution points
图1. 需求点与配送点位置示意图
2.2. 基本假设
(1) 该配送中心所配送的区域内各个需求点的需求量和时间窗已知;
(2) 单个需求点的需求量不会超过配送车辆的最大承载量,且配送车辆的吨公里耗油量已知;
(3) 配送网络中的道路相互连通,且路况信息可知(配送距离、配送费用、配送时间)。
3. 模型建立
本文在构建配送车辆路径模型时分为车辆固定成本、车辆运输成本、碳排放成本这4个方面分别建立函数。
3.1. 参数说明
f为配送成本;
z表示所有配送路线集合;
r表示第r条配送路线;
表示当前第r条配送路线车辆载重;
volume表示车辆负重最大值;
表示第r条配送路线的总长度;
LD表示配送路线最大长度;
x表示当前配送路线长度是否超过车辆路程最大约束,超过为1,否则为0;
表示第j个需求点配送货物所需要的存储体积;
表示配送车辆到达第r条配送路线最后一个点的所需时间;
speed表示配送车辆速度;
表示第r条配送路线共有多少个需求点;
表示第r条配送路线所需配送货物的装载体积;
V表示车辆额定装载体积;
表示车辆从配送中心到达第一个需求点的距离;
表示需求点j到需求点p的距离;
表示车辆从完成配送后返回配送中心的距离。
3.2. 模型建立
(1) 固定成本
固定成本指车辆的固定损耗、驾驶员工工资等,一般取常数
,相关函数为线性函数,且与配送车辆的行驶里程与配送路线当中所服务的客户数量无关,用
表示,具体公式如下:
(1)
(2) 车辆运输成本
车辆运输成本一般指车辆的油耗成本,与车辆在配送过程中的总行驶里程相关,用
表示,公式如下
(2)
(3)
(3) 时间窗惩罚函数
时间窗惩罚指当配送车辆到达该配送路线上的客户时没有在客户需要的时间段内送达,无法满足客户的需求所带来的相应的惩罚成本用
表示,如能够在客户要求的时间段内送达则五该项成本,公式如下:
(4)
(5)
(4) 碳排放成本 [11]
碳排放成本指在配送车辆送货过程中消耗燃料所产生的二氧化碳成本用
表示,该成本受到车辆的行驶里程和载重量等因素的影响,假定单位距离燃料消耗量为
,
为车辆自重,X为车辆所承载的货物重量,
为配送车辆从j点到p点过程中的车辆载重,
为二氧化碳排放系数,成本公式如下:
(6)
(7)
综上所述,考虑碳排放的配送路径优化模型如下所示
目标函数:
(8)
约束条件如下:
(9)
(10)
(11)
4. 实例分析
配送中心的坐标分别为(35, 48)、(70, 50),各地的需求量、时间窗如表1、图2、图3所示:
![](Images/Table_Tmp.jpg)
Table 1. Time window statistics of demand points
表1. 需求点时间窗统计
![](//html.hanspub.org/file/15-2760492x39_hanspub.png)
Figure 2. Schematic diagram of demand and time window
图2. 需求及时间窗示意图
![](//html.hanspub.org/file/15-2760492x40_hanspub.png)
Figure 3. Distribution of distance between distribution point and demand point
图3. 配送点距需求点距离分布
将各地区应急物资需求量转换为重量和体积需求随后使用遗传算法进行配送路线优化,设定参数种群为100,交叉概率0.8,变异概率0.2,迭代次数为200,带入到遗传算法中进行计算,迭代过程如图4,优化前后配送路线如表2、表3所示,示意图如图5、图6所示:
![](Images/Table_Tmp.jpg)
Table 2. Optimized distribution route planning
表2. 优化后配送路线规划
![](Images/Table_Tmp.jpg)
Table 3. Distribution route planning before optimization
表3. 优化前配送路线规划
![](//html.hanspub.org/file/15-2760492x43_hanspub.png)
Figure 6. Distribution road map before planning
图6. 规划前配送路线图
此时共有5条配送路线,根据目标函数计算得到此时的成本为13,248元,优化前成本为36,815元,二者相比成本降低了百分之64,且客户的满意度从百分之20提高到了百分之80以上,提高了客户满意度的同时显著降低了配送成本和配送车辆的碳排放量,达到了预期的效果。
5. 结论
本文将碳排放的相关模型引入到配送路线规划问题当中,以石家庄市某物流公司所提供的相关数据作为基础数据,在成本方面降低了百分之64,在客户满意度方面提高了百分之60,达到了客户满意度的同时降低配送车辆的碳排放量的目标,并且在物流配送过程中体现了可持续发展的理念。
在下一步的研究中,将考虑根据不同种货物在配送时所拥有的特性建立相关成本函数,达到进一步降低成本的目的。