基于改进遗传算法的末端共同配送车辆路径优化

彭会萍,李士伟,孙宏进,曹晓军

(兰州财经大学 丝绸之路经济研究院,兰州 730020)

城市快递配送网络的运行模式较为单一,物流配送企业普遍通过划分包括城市转运中心、区域配送中心、末端配送网点等不同的物流节点等级进行包裹的运输、配送以及揽收服务.在末端配送网点进行配送服务时由于配送地址较分散等问题,使得末端配送成本占物流企业总成本比例较高.随着电子商务的发展,末端配送包裹数量激增为末端配送网点带来了较大压力,城市末端物流共同配送策略研究具有较高应用价值.商务部、交通运输部等部门多次发文,要求大中城市积极推进城市共同配送[1],近年来共享经济的思想深入各行各业,共同配送是物流配送行业的发展趋势,在资源共享的基础上对车辆行驶路线进行合理规划,是企业降低物流成本、提高企业效益的关键.

在城市末端共同配送方面,提出合理的共同配送策略,科学调配车辆进行包裹配送,合理的利润分配和责任承担是需要深入考虑并解决的问题,国内外学者对共同配送的研究重点各有侧重.王勇等[2]提出充电站和电动车共享策略并设计3D-K-means时空聚类算法和多目标粒子群算法进行求解,其研究方法与结论对为多中心共同配送问题提供新思路.孔继利等[3]在末端共同配送背景下,以快递共配联盟为研究对象建立相关定价博弈模型为共同配送企业进行最佳决策提供理论依据.孙荣庭[4]分析了生鲜农产品在实施共同配送时面对的问题,提出了对应的解决策略.李珍萍等[5]通过对比奶制品企业进行共同配送前后花费的成本,验证所其提出的共同配送策略的可行性及设计的算法对共同配送网络优化的有效性.任腾等[6]设计改进遗传算法求解共同配送路径问题,发现共同配送能有效提升客户的满意度及降低配送车辆的空载率.WANG等[7]设计了一种改进遗传算法求解客户需求拆分以及时间窗约束下的多仓库共同接送车辆路径问题.许茂增等[8]构建了Shapley值综合修正模型用于解决快递企业在低配送密度区域中转站共同配送问题.陆华等[9]从城市视角出发,对比实施共同配送前后的城市交通、货运系统的效益变化,验证了共同配送是治理城市的有效途径.付朝晖等[10]证明了共享物流模式能更合理规划车辆路径,有效避免交叉配送与迂回运输等不合理现象.

综上所述,目前国内外学者已经分别对多配送中心共同配送车辆路径问题进行了分析与研究,并提出了较多求解算法,但在城市区域配送下的电商订单涉及到多家物流配送企业的共同配送的研究较少.此外,共同配送的路径优化问题所处的环境较为复杂,考虑的约束比普通的车辆路径问题更多.本文通过构建以车辆固定使用成本、车辆行驶成本和碳排放成本最小为目标的数学模型,设计引入节约里程算法的遗传算法进行该模型求解,通过仿真实验证明改进的算法的有效性及共同配送策略的优越性.

1 共同配送车辆路径问题建模

1.1 问题描述与假设

若干物流配送企业决定在城市某区域实行末端共同配送,将参与共同配送的各个企业末端配送网点相互共享.在进行“最后一公里”的配送时,参与共同配送企业的末端配送网点作为公共末端配送网点,各企业的配送中心可将包裹送往任意公共末端配送网点,再由公共末端配送网点对经过K-means聚类后的新服务区域安排车辆路线执行配送任务.各个客户需求点末端配送网点位置与每一个客户需求点都只能由一辆车服务一次,各客户需求点的需求量己知,各末端配送网点的坐标已知且能够满足服务对象的需求.为便于分析和研究,做出以下假设:

1) 快递均为经过折算后的标准快递.

2) 未成功配送的快递不考虑重新配送.

3) 某城市区域内有多个末端配送网点且拥有充足的配送车辆.

4) 末端配送服务车辆具有容量限制.

5) 考虑为服务对象的收货需求,暂不考虑寄件需求.

6) 每个客户的收货需求量小于车辆容量.

7) 每个客户只能由一辆车提供配送服务.

8) 独立配送情形下给客户的货物由该客户归属的末端配送网点进行货物配送服务,共同配送情形下由公共末端配送网点进行货物配送服务.

9) 车辆自末端配送网点出发,完成配送任务后回到原末端配送网点.

1.2 模型构建

所建模型的变量、集合以及决策变量的定义见表1.

表1 变量符号及其含义

车辆固定使用成本主要与车辆使用数目有关,车辆固定使用成本C1定义如下:

C1=kf

(1)

配送车辆在向客户运送包裹的过程中,会产生油耗成本和保养费、折旧费等,将车辆运送过程中的成本称作行驶成本.利用负载估计法测算油耗量[11],油耗主要与车辆载重和行驶距离有关[12],保养费、折旧费等费用主要和行驶距离有关.

单位距离油耗函数为:

(2)

其中:p0为车辆空载时单位距离油耗,p*为满载时单位距离油耗,Z为车辆自重,X为当前车辆载重量.

车辆行驶成本C2定义如下:

(3)

车辆运输过程中燃烧燃料产生二氧化碳,根据我国碳税制度对碳排放成本估算,碳税成本公式如下:

Cost=碳税*碳排放量

(4)

碳排放成本C3定义如下:

(5)

基于总配送成本最小化为目标建立的共同配送模型如下:

式(1)为目标函数式,计算最小化的总配送费用,包括车辆固定成本C1和车辆行驶成本C2以及碳排放成本C3.

(6)

(7)

(8)

i,j不同时为0

(9)

(10)

(11)

xij∈{0,1},i,j∈A

(12)

K∈{1,2…,n,…}

(13)

(14)

2 改进遗传算法设计

2.1 车辆路径的编码与解码

针对于车辆路径问题采取顺序实数编码方式,无需进行解码,可以直接得到染色体对应的车辆路线.染色体序列取决于末端配送网点与客户的服务先后顺序,基因值是末端配送网点编号和客户编号,基因数是末端配送网点数与客户数之和.假设有8个客户,2个末端配送网点,对其进行编码,1-2编码设为车场, 3-10编码为客户,一条完整的染色体长度应为10,如下所示:

1 4 7 10 3 9 2 6 5 8

该染色体对应的车辆路径问题即为1号末端网点按照4-7-10-3-9的顺序为客户服务,2号车场按照6-5-8的顺序为客户服务.

2.2 种群初始化

初始种群的生成方式以及生成质量对于最终的结果有重要影响,良好的初始种群可加快算法收敛速度,更高效地获得最优解.若初始种群的大小为M,将节约里程算法得到的解复制为M份作为遗传算法初始解.

2.3 适应度函数

在生物学中使用适应度这个概念来衡量生物对于所处环境的适应程度,与此相同在遗传算法中也通过适应度来衡量种群中个体的优劣,个体的适应度值就代表了个体的适应能力,适应度函数通常由目标函数来决定,较大的适应度说明该个体较优,可以进入下一代子种群[13].本文模型中目标函数为配送总成本最小,如式(6)所示,因此适应度函数为应取配送总成本的倒数,具体表达式为:

(15)

2.4 遗传算子策略选取

1)选择算子.利用轮盘赌法在当前种群中选出部分个体作为产生子代的父代,对各个染色体的个体适应度值进行计算,适应度高的个体被优先进行选择并保存进下一代.

2)交叉算子.对种群进行选择操作后随机设置交叉点的位置,交换配对染色体之间的部分基因.例如染色体上某两个基因片段为:

父代个体1: 1-8-19-6-2-1

父代个体2: 2-5-10-11-2

交叉后:

父代个体1: 1-8-10-11-2-1

父代个体2: 2-5-19-6-2

3)变异算子.变异是指种群中的染色体在进行复制时有概率使得这一过程中发生变化,例如染色体上某基因片段为:

个体i: 2-4-9-8-2

变异后

个体i*: 2-17-9-8-2

改进后算法的流程见图1.

图1 CW-GA流程图

3 算例与结果分析

3.1 算法验证

为验证设计的CW-GA算法的有效性,使用Python对Solomon数据集中的R101算例进行仿真实验,算法参数如下:初始种群M=500,迭代次数500,变异概率设为0.1,交叉概率设为0.8.GA算法与CW-GA的迭代曲线见图2.对比图中算法的迭代结果可以看出,设计的CW-GA算法的收敛速度和最终结果明显优于传统GA算法.从迭代曲线的变化趋势对比分析,CW-GA算法在迭代初期迅速找到最优解,在迭代100次左右趋于收敛;而传统GA算法在算法终止后未找到优秀解,在迭代过程一直处于波动状态.收敛速度较慢且收敛结果较差.CW-GA迭代500次找到的解为1 514.79,传统GA的解为2054.46.两者差距较大.说明所设计的算法在求解性能上较优.

图2 目标值迭代图

3.2 仿真实验

为验证提出的共同配送方案有效性进行实例仿真.某区域有两家物流公司四个末端配送网点,分别向20个客户需求点进行电商产品订单配送.两个物流公司的客户高度重叠.末端配送网点坐标与各客户节点的坐标、需求量见表2、3.

表2 配送网点坐标

表3 客户信息表

利用上文设计的遗传算法进行模型求解,算法参数设置:种群规模为500,设置终止条件为迭代500次后停止,染色体变异、交叉概率设为0.1和0.8,仿真实验参数设置见表4.

表4 仿真实验参数设置

3.3 结果分析

利用所设计的CWGA算法求解独立配送策略,仿真得到的A、B企业独立配送最优配送车辆路径结果见图3.

图3 A、B独立配送车辆路径

利用K-means聚类算法根据客户到末端配送网点的距离进行客户归属划分,划分结果见图4(A).选择距离聚类中心较近的末端配送网点作为该聚类客户的末端配送网点,在考虑聚类的基础上利用改进后遗传算法求得共同配送车辆路径结果见图4.仿真结果中独立配送和共同配送方案所用配送车辆路径信息见表5.共同配送前后成本变化见表6.

图4 基于客户聚类的A、B共同配送车辆路径

表5 配送车辆路径

表6 共同配送前后成本变化

通过表5可知,共同配送之后使用的车辆数量并未减少,因共同配送需要满足A、B客户的需求,每辆车的服务客户数量降低,可以更快地完成配送任务减少后续客户等待时间,且客户能够同时取得A、B企业需配送的货物,方便用户取件,对配送企业而言更容易协调满足不同客户的时间窗要求.

从表6可以看出, 共同配送总成本相比独立配送时总成本节约了854.08元,其优化比率为26.13%,车辆行驶成本优化比率高达37.00%.碳排放成本优化比率为36.98%.此外,从图5可知,共同配送后的车辆的油耗以及配送行驶距离也有大幅度降低.只有车辆使用成本在共同配送前后未发生变化.说明共同配送可以有效优化车辆行驶成本和碳排放成本,降低物流配送企业的运营成本.

图5 独立配送与共同配送差别

4 结 语

本文对城市末端共同配送进行分析,在基于物流企业末端网点共享的基础上,构建以包括车辆使用成本、运输成本和碳排放成本最小化为目标的共同配送车辆路径问题模型.设计一种基于节约里程算法的遗传算法进行模型的求解,采用节约里程算法的解作为遗传算法的初始解,有效提高了初始解的质量,并通过公开的数据集算例验证了算法的有效性;在成本对比分析中,根据现实生活中包裹配送情况建立的共同配送模型求解得到的物流总成本花费有大幅下降,将该策略大规模应用到现实生活可帮助企业实现降本增效.