基于布谷鸟算法的物流选址及路径优化研究

廖 建 国

(柳州铁道职业技术学院 广西 柳州 545616)

0 引 言

无论是传统的贸易方式还是现代电子商务模式，最终都是通过物流实现货物的送达、验收和售后服务。随着我国电子商务的蓬勃发展，物流的“第一公里”和“最后一公里”成为电商发展平台的瓶颈，物流选址成为“第一公里”的决定性因素，而车辆配送路径优化是“最后一公里”的重要因素。传统的研究是将物流选址和车辆路径优化作为两个独立的子问题进行研究，难以实现物流系统的整体最优，将物流选址和车辆路径优化集成研究对物流企业降低物流成本、提高经济效益及社会效益具有重要意义。该问题本质上属于定位-运输路线安排问题(Location-Routing Problem，LRP)，求解其方法有精确算法和智能算法，精确算法只适合小规模问题，而智能算法适合求解大规模LRP。文献[1]对不同运营模式下电商企业物流配送中心选址和路径优化进行研究；文献[2]对城市生鲜食品冷链物流配送中心选址及路径优化问题进行研究；文献[3]对电动物流车充站选址和运输路径优化问题进行研究；文献[4]对电子商务企业共享循环包装选址-路径问题进行研究；文献[5]对考虑碳排放的物流配送选址-路径问题模型及其优化方法进行研究；文献[6]对某新零售企业物流配送中心选址及配送路径规划进行研究；文献[7]对生鲜农产品多配送中心连续选址-路径规划问题进行研究；文献[8]提出电网企业的配送节点选址_路径优化问题研究，文献[9]提出基于双层规划的生鲜农产品冷链配送中心选址及路径优化研究，文献[10]提出了配送选址-多车型运输路径优化问题及求解算法，文献[11]提出两阶段启发式算法求解定位-运输路线问题，上述文献对LRP有作为整体研究和分阶段研究。由于LRP的复杂性，各种方法都有一定的局限性，因此探索新算法十分必要。

本文采用改进的布谷鸟算法分阶段求解LRP，首先利用算法1确定配送中心及服务客户群，然后利用算法2对配送中心所服务客户群的车辆路径进行优化。通过不同算例的仿真实验表明本文算法行之有效，为管理决策层提供科学的预算方案，对物流企业降低物流成本、提高经济效益提供了参考依据。

1 物流配送中心选址的数学模型

物流配送中心选址是在n个客户中建立m个配送中心，使得m个配送中心到其服务客户群运输总距离(成本)最短(最低)，同时还需要满足一些约束条件：假设每一个客户只由一个配送中心配送，每一个配送中心的货物供应量足以满足其服务客户群的需求。因此物流选址的数学模型为：

(1)

(2)

uij≤hj,i∈M,j∈N

(3)

(4)

hj∈{0,1},uij∈{0,1},i∈M,j∈N

(5)

M={j|j=1,2,…,m},N={j|j=1,2,…,n}

(6)

式(1)为目标函数，其中：m表示配送中心数目；n表示客户群数目；qj表示第j个客户需求量；distij表示配送中心i与客户j之间的距离；uij为1时表示第j个客户的货物由第i个配送中心配送。式(2)-式(6)为约束条件。

2 基本布谷鸟算法

基本布谷鸟算法(Cuckoo Search algorithm，CS)是通过模拟布谷鸟寻窝产卵的行为来求解最优解[12]，其求解过程为：

1) 设置种群数目、弃巢率、问题边界及最大迭代次数。

2) 在问题领域内随机产生一定数目的种群并计算每一个个体的目标函数值，求出当前最优值和最优解。

3) 判断迭代次数是否达到最大迭代次数，如果是则退出循环，输出最优值和最优解；否则进入步骤4)。

4) 根据式(7)更新鸟巢。

(7)

(8)

式中：β取值为1.5；ν,μ∈N(0,1)；φ按式(9)计算。

(9)

式中：Γ为Gamma函数。

5) 计算新鸟巢的目标函数值，若较之前的优越则替换函数值和相应的鸟巢，并记录最优解。

6) 随机生成[0,1]之间的数并与弃巢率比较，若小于则保留该鸟巢，否则按式(10)产生新鸟巢。

(10)

式中：a、c为第t次迭代中不重复的随机整数；r∈[0,1]的随机数。

7) 重新计算新鸟巢的目标函数值，若较之前的优越则替换函数值和相应的鸟巢，并记录最优解。

8) 判断函数值与最优值，如果小于则替换最优值与最优解；算法转入步骤3)进行下一次迭代。

3 改进布谷鸟算法求解物流配送中心选址

3.1 构造解向量

本文改进布谷鸟算法求解物流选址问题不同于文献[13]。其一：编码的方式不同，文献[13]对10个需求点选取3个配送中心，通过排序后仅仅选择前面3个序号作为一组配送中心，这样配送中心种群数目减少最终导致物流选址求解精度不高，本文的编码方式如表1所示。

表1 解向量

同样对10个需求点选取3个配送中心，则选取前面9个序号作为配送中心，如矩阵center所示，即一个鸟巢可以对应3组配送中心，大大拓展了配送中心的多样性。其二：改进策略不同。

3.2 全局搜索

在基本布谷鸟算法中全局搜索是依靠Levy飞行获取新的鸟巢，Levy飞行是短距离的移动和偶尔大步长的跳跃，该方式既有利于跳出局部最优解亦可能求解的精度较差，因此借鉴Jaya算法的搜索策略[14]，其表达式为：

(11)

3.3 局部搜索

在基本布谷鸟算法中局部搜索是按式(10)计算，未引用当前最优解，可能导致收敛速度较慢，于是增加下式：

(12)

式中：r1,r2∈[0,1]之间的随机数；a、b、c表示不重复的随机整数。

3.4 领域搜索

为了进一步提高布谷鸟算法的效果，采用轮盘赌选择、鸟巢交叉和鸟巢逆序操作，同时在这三个操作中引入精英保留策略。轮盘赌选择参见遗传算法，鸟巢交叉即随机选择两个鸟巢，对这两个鸟巢随机选择两个位置进行一定概率的交叉操作；鸟巢逆序操作即对随机选择的鸟巢进行任意两个位置的倒序操作。

3.5 改进布谷鸟算法求解物流选址的步骤(算法1)

综上分析，改进布谷鸟算法(Improved Cuckoo Search algorithm，ICS)求解物流配送中心选址的步骤如下：

1) 设置种群数目、弃巢率、问题边界及最大迭代次数。

2) 在问题领域内按表1编码方式随机产生一定数目的种群并按式(1)计算每个鸟巢的目标函数值，求出当前最优值和最优解。

3) 判断迭代次数是否达到最大迭代次数，如果是则退出循环，输出最优值和最优解；否则进入步骤4)。

4) 根据式(11)更新鸟巢，按式(1)计算新鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

5) 将r∈[0,1]与弃巢率比较，若小于则保留该鸟巢，否则再判断如果r小于弃巢率，则按式(12)计算，否则按式(10)计算。

6) 按式(1)重新计算新鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

7) 进行N次领域搜索，并重新计算新鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

8) 判断目标函数值与最优值大小，如果小于则替换最优值与最优解；算法转入步骤3)进行下一次迭代。

4 车辆路径优化

4.1 车辆路径问题的数学模型

车辆路径问题(Vehicle Routing Problem，VRP)可描述为：现有L(i=1,2,…,L)个客户，第i个客户的需求为gi(i=1,2,…,L)，每车辆的载重量为qk(k=1,2,…,K)，假设配送中心拥有K(k=1,2,…,K)辆车，车辆从配送中心出发依次配送其服务客户群，要求满足各客户需求的配送路线最短。在实际配送过程中需要对所需车辆数进行估算，通常采用下式来计算：

m=[∑gi/aqk]+1

(13)

式中：m表示车辆数；[ ]表示floor函数；a一般取值为0.98。

用0表示配送中心，dij表示客户i与客户j之间的距离，VRP的数学模型为：

(14)

(15)

(16)

(17)

(18)

xijk=0或1,∀i,j,k

(19)

yik=0或1,∀i,k

(20)

其中：式(14) 表示总距离最短，式(15)表示车辆载重约束，式(16)-式(18)表示每一客户只由一辆车服务，式(19)-式(20)表示0-1变量约束。

4.2 车辆路径问题的编码与解码

假设有8个客户3辆车，本文在表1编码的基础上采用文献[15]的编码方式，用client=[1，2，3，4，5，6，7，8，0，0]表示客户向量，其中“0”表示配送中心，其数量为车辆数减1。问题维数等于客户数加上车辆数再减1，随机产生鸟巢nest=[-3.14，-5.23，9.69，6.93，5.89，8.00，5.60，6.73，-3.57，4.85]，对其进行升序排列后得到index=[2，9，1，10，7，5，8，4，6，3]，将index视为client的配送顺序，则得到的配送方案为：3- 1- 0- 8- 6- 0- 5- 7- 2- 4，则车辆1：0- 3- 1- 0，车辆2：0- 8- 6- 0，车辆3：0- 5- 7- 2- 4- 0。利用罚函数法将上述VRP的数学模型转换为下式：

(21)

4.3 车辆路径优化(算法2)

1) 根据算法1求解的配送中心及其服务客户群作为算法2的输入，求解每个服务客户群的距离矩阵。

2) 设置参数：种群数目、弃巢率、问题边界、问题维数、最大迭代次数、车辆数目估算及罚函数系数。

3) 按4.2节编码方式产生初始种群和按式(21)计算目标函数值，并求出当前最优值和最优解。

4) 判断迭代次数是否达到最大迭代次数，如果是则退出循环，输出最优值和最优解；否则进入步骤5)。

5) 计算当前最差解，然后根据式(11)更新鸟巢，按式(21)重新计算新鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

6) 将r∈[0,1]与弃巢率比较，若小于则保留该鸟巢，否则再判断如果r小于弃巢率，则按式(12)计算，否则按式(10)计算。

7) 按式(21)重新计算鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

8) 对鸟巢进行N次领域搜索，并按式(21)重新计算新鸟巢的目标函数值，若较之前的优越则替换之前目标函数值和相应的鸟巢，并记录最优解。

9) 判断目标函数值与最优值大小，如果小于则替换最优值与最优解；算法转入步骤4)进行下一次迭代。

5 仿真实验

本文设计了算法1和算法2，算法2是在算法1确定配送中心基础之上进行路径优化，任何一个算法的求解效果将直接影响最终结果。因此将算法1和算法2结合之前，分别采用算例进行实验分析以验证算法1和算法2的有效性和优越性，然后再将算法1和算法2结合作用于同一算例C101和随机算例来验证物流选址和路径优化研究。所有的实验均运行在Intel i5- 8350U、8 GB内存、Windows 7和MATLAB 2010b环境下。首先验证算法1，选取文献[16-17]中10个配送中心和50个需求点作为测试数据，为比较公平，参数设置与其相同：种群数目为20，最大迭代次数为50，弃巢率为0.25，交叉概率为0.8，领域搜索为5。算法1独立运行30次并与其他算法比较结果如表2所示，配送方案如图1所示。从表2中8种算法比较可知，就最优值而言，ICS优于FPA、PSO、GA、DEA、BWPA，与MFPA一致，仅次于IWPA；但就最差值、平均值和方差而言，ICS均优于其他算法。这足以说明算法1的有效性和鲁棒性。再验证算法2，选取VRP标准测试算例E-n33-k4，参数设置：种群规模为60，最大迭代次数为200，弃巢率为0.25，交叉概率为0.8，领域搜索为10。算法2独立运行30次计算的最优值为835，与当前最优值一致，其车辆配送路线如图2所示。

表2 各种算法的比较结果

再结合算法1+算法2作用于同一算例C101和随机算例。由于50个需求点要建设10个配送中心，每个配送中心所服务客户群的数量较少，故采用Solomon提供的C101作为测试集，假设需要建设10个配送中心。参数设置：种群数目为50，最大迭代次数为100，弃巢率为0.25，交叉概率为0.8，领域搜索为5，每车辆的载重量为100，惩罚系数为5 000。由算法1独立运行30次求解的最优值为7 752.2，其对应的配送中心及配送范围如表3所示，由算法2独立运行30次求解的最优配送中心、车辆数、配送路线、距离(费用)如表4所示，配送中心及配送路线如图3-图4所示。由表4可知，对于C101中100个客户(包含位置和客户需求数据)如果要建设10个配送中心，算法科学地给出了配送中心建设的最佳位置、所需车辆数，每辆车行驶路线、总距离(费用)。对于该算例，所有配送中心的运输费用为400.440 28。

表4 C101配送中心、车辆、路线及距离信息

为了进一步验证算法1+算法2的有效性，增加客户数目减少配送中心，现在[1 000,4 500]之间随机生成200个客户位置，在[10,100]随机生成200个客户需求量，假设只需建设5个配送中心。参数设置为每车辆的载重量为400，其余参数与C101实验相同。由算法1独立运行20次求解的最优值为：6.025 356 2e+006，其对应的配送中心及配送范围如表5所示，由算法2独立运行30次求解的最优配送中心、车辆数、配送路线、总距离(费用)如表6所示，配送中心及配送路线如图5-图6所示。由表6可知，对于200客户5个配送中心，算法科学地给出了配送中心建设的最佳位置、所需车辆数、每辆车行驶路线、总距离(费用)。对于该算例，所有配送中心的运输费用为5.934 2e+004。

表5 200个客户的配送中心及配送范围

表6 200个客户配送中心车辆、路线及距离信息

续表6

6 结 语

本文针对NP-hard的物流选址及路径优化问题，采用两段式智能算法进行求解，由于基本布谷鸟算法在求解性能上较差，因此在布谷鸟算法基础之上融合轮盘赌选择、鸟巢交叉和鸟巢逆序操作，分别设计了算法1和算法2，通过算法1确定配送中心最佳位置及服务客户群，通过算法2对每个配送中心所服务客户群的运输路线进行优化。不同规模的仿真实验验证了本文算法的有效性，其为管理决策层提供科学的预算方案，但本文没有考虑不同车型和时间窗等约束条件，相关研究还有待于进一步深入。