考虑时空拥堵和时间窗的多配送中心路径优化

陈沿伊，侯华保

(武汉理工大学 交通学院，武汉 430070)

0 引 言

由于生鲜产品的易腐性特征，生鲜配送过程中，客户满意度不仅受客户预约时间的影响，还受生鲜产品保鲜期长短及配送时间等因素的影响。当前关于生鲜配送的研究主要考虑商品保鲜期，综合考虑多种不确定因素的研究较少。

梁承姬等[1]为提高生鲜配送的时效性，考虑待配送客户时间窗，以实现配送过程中成本最小且客户满意度最大；王恒等[2]研究生鲜配送时间不确定情况下配送时效性的问题，考虑客户时间窗及道路实际特征，建立了生鲜配送路径优化模型；李畅等[3]研究生鲜配送的时效性问题时，考虑生鲜产品易腐性，建立以商品新鲜度最大和配送成本最低的多目标生鲜配送路径优化模型；吴欣[4]、张济风等[5]在研究配送时间不确定背景下的生鲜配送问题时，考虑配送过程中配送速度的时变性；康凯等[6]以碳排放最低为目标，研究了考虑客户时间窗的冷链配送问题，建立了考虑碳排放的生鲜配送模型。但是，上述研究主要研究配送时效性或配送时间的不确定性，综合考虑二者的研究较少，且生鲜配送的时效性影响因素较多。当前关于生鲜配送时效性的研究，影响因素考虑得不全面，且当前研究多配送中心下的生鲜配送问题较少，不符合当下生鲜配送多配送中心化的趋势。

关于路径优化的求解方法，张建勇等[7]结合聚类思想与遗传算法，提出混合遗传算法，解决带模糊时间窗的多对多车辆路径问题；S.HUBER等[8]采用变邻域搜索的方式解决路径优化问题；胡蓉等[9]设置多种邻域操作及局部优化模型，嵌入蚁群算法，解决考虑速度空间特征的车辆路径问题；邵倩[10]将遗传算法引入非支配算子，求解考虑速度空间特征带模糊时间窗的物流配送问题；S.IQBAL等[11]利用人工蜂群算法，结合局部邻域搜索优化，解决带软时间窗的车辆路径问题；B.D.SONG等[12]提出基于优先级的启发式(PBH)算法进行求解单目标车辆路径问题；范厚明等[13]基于擂台赛法构造非支配解，将局部优化算子引入遗传算法，解决多目标车辆路径问题；周鲜成等[14]在蚁群算法中设计确定性和随机性结合的转移策略；赵志学等[15]结合模型特点，在蚁群算法中引入约束算子，缓解了复杂问题易陷入局部最优的问题；张得志等[16]采用遗传算法解决考虑速度时变特征的路径优化问题；M.ALZAQEBAH等[17]采用改进人工蜂群算法解决带时间窗的车辆路径问题。

综上所述，当前关于生鲜配送的研究主要以单配送中心为主，考虑多配送中心的研究较少，不能适应当前生鲜电商配送多配送中心化的发展趋势。另外，当前研究综合考虑时间窗、保鲜期、路网拥堵特征的研究较少，研究结果不能完全反映配送的实际情况。鉴于此，笔者建立综合考虑客户时间窗、商品保鲜期和路网拥堵特征的多配送中心生鲜路径优化模型。因模型的复杂性较高，笔者在传统蚁群-遗传算法的基础上，采用两边逐次修正算法对初始种群进行局部优化，对种群适应度值降序排列后，选择前30%作为精英个体，利用蚁群-遗传算法进行迭代优化，并对算法参数进行正交试验设计，优化算法参数。基于上述操作，可以有效改善算法搜索空间及求解质量。最后以多种分布特征的Solomon算例和笔者提出的算法为基础，将该模型与不考虑商品保鲜期和不考虑客户时间窗的模型计算结果进行对比，以验证该模型可以在配送时间不确定情况下有效提升配送的时效性，并将笔者提出的算法与传统算法进行对比，验证算法有效性。

1 模型描述

1.1 模型描述

某生鲜企业在该区域有多个配送中心，每个配送中心存在多种车型。现需要对该区域的客户订单进行配送，需尽量满足客户预约时间要求且维持商品新鲜度，以保证客户满意度。考虑到车辆行驶速度受高峰小时及所处位置的影响和客户满意度受客户时间窗及商品保鲜期的影响，笔者提出速度时空拥堵函数和综合模糊时间窗，建立时空拥堵下考虑客户时间窗和商品保鲜期的多车场多车型生鲜配送路径优化模型。

1.2 模型参数与假设

1.2.1 模型参数

1.2.2 模型假设

模型假设如下：①该区域有多个配送中心，每个配送中心有多种车型，车辆数足够；②每个客户仅被一辆车一次服务；③车辆行驶速度受时间和空间的影响；④每辆车服务结束后返回原车场；⑤车辆晚于商品保鲜期到达，客户满意度为0；⑥配送速度不能超过最大允许速度。

1.3 模型建立

1.3.1 客户满意度函数

1)客户模糊时间窗

基于客户模糊时间窗，货物在时间区间[Li,Ui]内送达，客户满意度为1；在[li,ui]区间外到达客户满意度为0，其他区间客户满意度处于递增或递减状态，具体见图1。

图1 客户满意度函数

2)商品保鲜期

假设在商品保鲜期前送达客户满意度为1，超过商品保鲜期，客户满意度为0，详见图2。

图2 商品保鲜期

3)综合模糊时间窗下客户满意度函数

综合考虑客户时间窗和商品保鲜期，取客户时间窗和商品保鲜期交集，以反映客户时间窗和商品保鲜期共同作用下的客户满意度随时间的变化情况。假设当商品超过保鲜期送达时，客户满意度为0，当在客户时间窗和商品保鲜期之间送达，满意度变化服从客户时间窗下的满意度对应法则。综上所述，建立综合模糊时间窗下的客户满意度函数，见图3。图3(a)～图3(d)满意度关系式分别对应式(1)～式(4)。

图3 综合模糊时间窗下客户满意度函数

(1)

(2)

(3)

(4)

1.3.2 速度时空函数

1)速度时间拥堵系数

速度时间拥堵系数反映了不同时刻的路网拥堵特征。高峰小时附近，路网较为拥堵；其他时间，路网交通流较少，拥堵程度降低，见式(5)：

(5)

2)速度空间拥堵系数

配送速度受空间因素制约。郊区配送速度高于市区配送速度；距离区域中心越远配送速度越大。空间拥堵系数计算方法见式(6)：

(6)

3)速度时空函数

综合考虑速度的时间和空间因素及道路最大限度vmax、道路最低时速vmin等因素，建立速度时空演变函数，见式(7)：

(7)

1.3.3 目标函数去量纲处理

1)车辆使用数、配送距离、客户平均满意度处理分别如式(8)～式(10)：

(8)

(9)

(10)

2)多目标加权处理

笔者采用加权法将多目标转化为单目标，权重由专家打分确定，各个目标通过去量纲化，消除单位对加权后目标值的影响。去量纲化方法见式(11)～式(14)：

(11)

式中：maxf1、minf1分别表示当次迭代中种群最多和最少车辆使用数。

(12)

将客户平均满意度与1做差，使得各目标协同，max(1-f3)、min(1-f3)分别表示做差后的当次迭代种群内的极值。

(13)

经过专家打分，确定车辆使用数、配送里程、客户平均满意度的权重分别为0.22、0.47，0.31，对各个子目标加权处理得到总体目标值：

(14)

1.3.4 模型与约束

模型与约束见式(15)～式(25)：

(15)

(16)

(17)

(18)

(19)

(20)

∀k∈HP,∀S∈J)

(21)

∀j∈V)

(22)

(23)

(24)

(25)

其中，式(15)表示加权后的目标值；式(16)表示每个客户由且仅由一辆车务；式(17)表示车辆服务完一个客户后会返回车场或前往下一个客户；式(18)表示车辆行驶距离不应超过其规定最大行程；式(19)表示任何从车场出发的车辆最终返原车场；式(20)表示任意一辆车的载重不可超过其额定载重；式(21)表示任意一辆车的服务客户集合不出现闭环；式(22)表示两个决策变量之间的关系；式(23)表示车场之间不允许通车；式(24)和式(25)为决策变量取值约束。

2 模型求解

2.1 求解思路

首先，利用扩展启发式算法产生初始可行解，在传统蚁群遗传算法的基础上，引入两边逐次修正算法对精英群体进行局部优化。然后，利用定点交叉算法对精英种群进行交叉变异，使之达到初始种群规模。最后，利用正交试验设计思想，对算法参数进行优化，以最大迭代次数作为算法终止条件。对模型进行求解算法流程见图4。

图4 算法流程

2.2 算法初始化

2.2.1 编码与解码

1)编码

笔者采用十进制编码，根据车辆和车辆服务的顾客顺序进行多段编码。车辆采用三位数编码，百位数用于防止与客户编号重复，十位数表示车场编号。个位数表示车型编号，如112表示第一个车场第二个车型。客户编码采用十进制编码，编号表示客户编号，见图5。

图5 路径编码

2)解码

根据编码顺序，结合车辆、客户数据信息，计算该路径长度、客户满意度、使用车辆数，进而计算该路径的加权目标值。

2.2.2 初始可行解

Step 1随机选择服务客户的车辆，转Step 2。

Step 2当客户集不为空集的时候，计算各个未访问客户的状态转移概率。采用轮盘赌法选择待服务客户，转Step 3；否则，转Step 4。

Step 3判断该车辆里程是否能够返回车场及容量是否有剩余，如果可以，转Step 2；否则，转Step 1。

Step 4输出路径，计算顾客平均满意度、车辆数、路径长度，计算整体目标值。

2.3 改进蚁群-遗传算法

Step 1设置算法初始参数，导入客户、车场数据，基于启发式算法产生初始可行解，详见2.2.2节，转Step 2。

Step 2求解本代可行解目标值，若NC>2，则R(1)=R_best(NC-1)，其中，R_best(NC-1)为NC-1代最优解；否则，转Step 3。

Step 3记录本次迭代最优解，更新信息素，清空禁忌表，转Step 4。

Step 4对该代个体目标值进行降序排列，选择前10%作为精英个体，转Step 5。

Step 5基于轮盘赌法随机选择精英个体，利用两边逐次修正算法进行改良，见2.4.1节，转Step 6。

Step 6把改良个体加入精英种群，判断种群是否达到初始种群规模，是则转Step 7；否则转Step 5。

Step 7基于轮盘赌法判断个体是否需要交叉变异，是则基于定点交叉算法对个体进行交叉变异，详见2.4.2节，转Step 8。

Step 8基于轮盘赌法，选择正交试验参数，详见2.4.3节，对交叉变异后的精英种群目标值进行计算，求其平均值，转Step 9。

Step 9判断种群平均水平是否得到改善，是则转Step 10；否则转Step 8。

Step 10记录当代种群最优解，判断是否满足迭代终止条件，是则转Step 11；否则转Step 2。

Step 11输出最优解。

2.4 局部优化算法

2.4.1 两边逐次修正算法

Step 1输入需要改良的路径R。

Step 2按服务顺序选择潜在改良点，翻转改良点之间路径，即R(i+1:j)=R(j:-1:I,i+1)。记新路径为R1，判断改良点是否均被遍历，是则转Step 7；否则转Step 3。

Step 3判断改良点i与j或改良点i+1和j+1是否皆为车辆，是则令i=i+1，转Step 2；否则转Step 4。

Step 4计算R1各车辆行程和荷载，转Step 5。

Step 5判断路径R1中行程或荷载是否存在超出额定值的车辆，若存在，令i=i+1，转Step 2；否则转Step 6。

Step 6计算R、R1路径长度、客户平均满意度，分别记为len、len1、S、S1；若len>len1且S

Step 7输出改良的个体R1。

2.4.2 定点交叉算法

路径R1经过多点、不定点交叉或不定点变异后，易产生未服务客户或里程、容量超过额定值的车辆。笔者提出定点交叉算法，使得路径交叉、变异后仍为可行解，步骤如下：

Step 1从种群中随机选择两个个体，记为R1、R2，转Step 2。

Step 2从R1、R2中随机选择两个基因，分别记为a、b，转Step 3。

Step 3利用find(a=R2(1,:))、find(b=R1(1,:))函数，分别找到a在R2中的位置、b在R1中的位置，分别用p1、p2记录基因在路径中的位置，转Step 4。

Step 4算法随机把p1、p2位置的基因对应调换在R1、R2其他位置(非首位)，产生的新路径分别记为R_new1、R_new2，转Step 5。

Step 5计算R_new1、R_new2各个车辆的里程及荷载，转Step 6。

Step 6判断R_new1或R_new2中是否存在超出额定荷载和最大行程的车辆，若存在，转Step 4；否则，转Step 7。

Step 7输出R_new1、R_new2。

2.4.3 正交参数设计

对改良蚁群-遗传混合算法的5个关键参数设计L25(56)正交表，每组参数的初始绩效值Ni=1，各组参数的选择概率由式(21)确定：

(21)

Step 1利用轮盘赌法选择一组参数应用于当次迭代，转Step 2。

Step 2判断种群平均水平是否得到改善，且该组参数的绩效值增加1，是则转Step 3；否则转Step 1。

Step 3记录当前最优参数组合及种群最优解。

3 算例分析

3.1 算例描述

某生鲜企业在该区域有5个配送中心，每个中心有多种车型，对该区域25个客户进行配送。每个客户存在一个模糊预约时间，客户所定商品具有一定的保鲜期。配送速度受时间和空间的影响，但不能超过最大限速。求得合适的客户服务顺序，使得总目标值最低。

3.2 算例说明

3.2.1车场车型数据

调整Solomon标准算例R101、R201、C101、C201、RC101、RC201，删除算例中车场，额外增加5个车场。每个车场存在多种车型，车场车型数据见表1、表2。

表1 车场信息

表2 车型信息

3.2.2 客户位置、时间窗数据

在Solomon算例中客户时间窗基础上，向两侧随机扩展成模糊时间窗，并随机生成商品最后交货期。取交集形成综合模糊时间窗，用x、y表示坐标，C表示客户需求，l、L、U、u分别表示客户模糊时间窗上下限，ts表示客户服务时间，G表示商品保鲜期。部分客户数据见表3。

表3 客户数据信息

3.2.3 速度时空参数

设ρ=2,α=0.5,β=0.5，tm取各算例车场运营时间中点，dr0为距离车场中心距离最远的客户到车场中心的距离。

3.2.4 正交试验参数

选择6个参数，参数水平见表4。设计L25(56)正交表，部分见表5。其中，M、δ、μ、ε、Pc、Pm分别表示蚂蚁数、信息素启发式因子、期望启发因子、信息素蒸发因子、交叉率、变异率。

表4 正交试验参数水平

表5 正交试验表

3.2.5 算法运行环境

算法运行环境为CPU2.20 GHz,内存为4.00 GB,操作系统为64位Windows10,编程语言采用MATLAB R2016a。

3.3 不同模型相同算法比较结果

表6 不同模型计算结果对比

设其他条件不变，对不同类型的时间窗展开讨论，可见对不同分布特征下的客户，不同类型时间窗车辆配送距离和车辆使用数量差别不大，IFTW模型相比FTW和GTW模型的客户平均满意度较高。

因此，综合考虑路网拥堵特征、客户时间窗、商品保鲜期的生鲜配送模型可以有效平衡配送时效性和配送时间窗不确定性的矛盾。

3.4 相同模型不同算法比较结果

为测试结合蚁群算法、遗传算法、两边逐次修正算法提出的改进蚁群-遗传算法的有效性。将改进算法的各部分分别对不同分布特征的客户群进行求解，并与改进算法求解结果进行对比。即用改进蚁群-遗传算法(IACGHA)中的蚁群算法(ACO)模块、嵌入两边逐次修正算法的改进遗传算法(IGA)模块、去除两边逐次修正算法的遗传算法(GA)模块分别对不同分布特征的客户群进行求解，将求解结果分别与改进蚁群-遗传算法(ACO-GA)的求解结果进行对比，以检验ACO-GA算法的求解能力，对比结果见表7。ACO算法的蚂蚁数M=50，信息素启发因子β=2.5，期望启发因子μ=4.5，信息素会发因子ε=0.4，信息素强度Q=100。GA和IGA除嵌入两边逐次修正算法的差异外，其他参数相同。其中，种群规模NP=100,交叉率Pc=0.7，变异率Pm=0.006，算法迭代次数G=500。

表7 不同算法改进百分比对比

由表7可知，虽然针对部分数据，改进蚁群-遗传算法计算结果不如传统算法，但整体上ACO-GA算法计算能力优于传统算法，平均优化5%以上。由此可见，改进蚁群-遗传算法相比于传统算法，计算能力更强，优化效果更好。然而因算法中嵌套正交试验设计等局部优化模块，使得算法以最大迭代次数作为迭代终止条件时，计算时间较长。

4 结 语

为解决生鲜配送时效性和配送时间不确定的矛盾及应对生鲜配送多配送中心化的趋势，笔者综合考虑客户时间窗、商品保鲜期、配送速度的时空特点，建立起综合模糊时间窗和速度的时空函数，以反映生鲜配送过程中的时间不确定性；建立多车场多车型生鲜配送路径优化模型，以反映生鲜配送多配送中心化的特点。采用不同类型的Solomon算例反映不同分布情况的客户特点。考虑到在时变路网下考虑时间窗的多车场多车型车辆路径优化模型较为复杂，提出在传统蚁群-遗传算法的基础上，嵌入两边逐次修正算法、正交实验设计等局部优化模块的改进蚁群-遗传算法，对该问题进行求解。

结果表明，考虑多配送中心的综合模糊时间窗和速度时空演变函数的生鲜配送模型更符合实际，可有效缓解配送时效性和配送时间不确定性之间的矛盾，且改进蚁群-遗传算法相对传统算法求解效率更高。文中模型和算法可为生鲜配送企业制定调度计划提供参考。