细菌觅食优化算法求解物流配送问题

王 垚，李 珺，屈艺晖

(兰州交通大学 电子信息与工程学院，甘肃 兰州 730070)

0 引 言

随着生活质量的提高和物流技术的发展，以及电商平台的普及，生鲜食品与消费者的联系愈加紧密，使得人们对于生鲜的需求越来越大[1]。但是，生鲜需求增大的同时，生鲜物流配送也存在着问题，例如：配送中心选择、配送路径安排的不合理，造成的配送成本高、配送时间不及时、消耗时间长，生鲜损耗高等都制约着生鲜贸易的发展[2]。

文献[3]对产品配送过程中的易腐性进行研究，并通过建立一个多目标规划模型，实现对配送过程中成本最小化目标及新鲜度最大化目标的双目标模型求解。文献[4]在改进的层次分析法基础上，提出了针对农产品物流中心的多准则选址决策模型，并通过综合评价值的最优和最劣值，获取方案的综合评价值。文献[5]通过设计一种双目标混合整数数学规划方法，用于评估和预测配送中心中的易变质产品，对预测生鲜货物量提供了一种思路。文献[6]针对生鲜产品时效性特点，应用模糊隶属度函数表示的时间窗反映客户满意度，综合考虑系统成本和客户满意度的多目标模型，同时加入生鲜度损耗系数，对带时间窗的生鲜物流配送问题进行了求解。文献[7]建立了基于时间约束的生鲜配送优化模型，通过Dijkstra算法和节约里程法对问题进行求解。文献[8]分析了B2C环境下生鲜物流配送系统中造成的损耗及客户满意度影响，采用多配送中心分区配送模式，构建以物流成本最小及客户满意度最大的多目标模型，并通过遗传算法对该问题进行求解。

由于生鲜食品的特殊性，在配送上对于时间方面要求较高。此外，从供应商角度出发，整个系统的成本也不容忽视。实际生活中，同时考量多种因素影响下的优化问题，称之为多目标问题(multi-objective optimization problems，MOPs)。对于多目标问题，传统的求解方法有加权法、约束法、混合法等，这些方法求解思路都是通过将多个目标赋予一定的权值从而转化为单目标问题，再通过传统单目标求解方法对相关问题进行求解，但是这种方法只能求解给定权值下得到的最优问题。近年来，随着多目标问题和智能算法的发展，越来越多的学者设计了相应的多目标算法对多目标问题进行求解。例如，文献[9]将原有PESA算法进行改进，设计出了PESA-II并提出了区域选择的概念；文献[10]提出了基于非支配解排序的多目标遗传算法NSGA-II。

细菌觅食优化算法(bacterial foraging optimization algorithm，BFO)，是由Passino[11]于2002年根据大肠杆菌觅食行为提出的一种启发式算法。大肠杆菌会根据周围环境做出如翻转、游动等趋利避害的一系列行为。算法通过趋向性操作模拟大肠杆菌群体随机性向富营养区游动的行为来实现随机搜索的目的；复制操作则模拟了菌群优势劣汰后进行增殖的行为，使得优良个体得以保留；在经过趋向性操作和复制操作以后，菌群个体进行迁徙操作并以一定概率消亡，随机在其他位置产生新的个体，增加种群的多样性，降低算法陷入局部最优的可能。该算法具有收敛速度快、搜索精度高、跳出局部最优能力强等特点。在综合考虑时间、成本的多目标前提下，构建相应的双目标选址-路径问题(location routing problem，LRP)[12]模型。根据Pareto支配关系[13]对标准BFO进行改进，设计相应MOBFO算法(multi-objective bacterial foraging optimization algorithm)，并通过相应算例验证该算法的有效性和优越性。

1 问题描述

生鲜物流配送问题，实质是选址-路径问题。LRP问题指的是在一系列潜在设施点中选择合适的设施点，使得各个设施点到各个客户之间的运输成本最低。该问题可以进一步描述为：设G=(V,E)是一个连通网络，其中V为顶点集合(配送中心和配送点)，E为有向边集合(表示配送路径)。每个配送点的需求量已知，要求进行配送作业的车辆到该配送点的时间一定，即在该点规定的时间窗内到达该配送点；在满足一定约束条件下，从配送中心出发，有序到达所有配送点处作业，最后返回配送中心。

1.1 模型建立及假设

生鲜物流配送问题可以分为两个子问题进行求解，即配送中心选址和配送路径安排。首先对配送点进行路径安排，解决配送路径安排问题。再通过分配各个配送中心到每条已规划好的路径，选择成本最小的配送中心作为一种子方案，从而解决选址的问题。配送路径安排问题是其核心，实质是带软时间窗的车辆路径问题(vehicle routing problem with soft time window，VRPSTW)[14]。软时间窗问题是指从配送中心出发的车辆必须在规定的时间窗[ETi,LTi]内到达第i个配送点处进行作业，其中ETi为车辆到达第i个配送点处允许的最早时间，LTi为车辆到达第i个配送点处允许的最晚时间，早于或者晚于到达时间窗内规定时间，都将为配送成本造成一定损失，需要进行一定的惩罚。

生鲜物流配送问题主要目标是解决：(1)在潜在的配送中心处选择合适的配送中心；(2)对配送点和配送中心规划合理路径。使得系统总成本最小，花费时间最短。基于以上分析，对该问题模型的假设有：(1)潜在配送中心的平面坐标已知，且容量足够大；(2)每个配送点的平面坐标和需求量已知；(3)每个配送点有且仅有一辆车进行作业，每辆车固定成本和每公里行驶成本、速度已知，且不受路面、交通、天气等影响；(4)每辆车必须由配送中心出发依次在路径上的各个配送点进行作业后返回该配送中心；(5)车辆的载货量已知；(6)每辆车到达各个配送点的到达时间需要在时间窗[ETi,LTi]内，否则进行一定惩罚。

根据以上分析可知，需要求解的目标函数有2个：基于选址-路径问题的成本最小目标函数S1，如式1，以及带软时间窗车辆路径问题的花费时间最短目标函数S2，如式2。

(1)

(2)

1.2 符号说明

M-备选的配送中心集合；Zi-第i个配送中心是否被选中；N-配送点集合；V-选中配送中心和配送点集合；K-参与作业的车辆集合；Q-车辆的最大载货量；qi-配送点i处需求量；rk-第k辆车负责的配送点的总需求；tsi-车辆在配送点i处作业时间；[ETi,LTi]-配送点i处软时间窗；dij-车辆从配送点i到配送点j间平面坐标的欧氏距离；v-车辆的行驶速度；C0-车辆的固定成本；C1-车辆单位距离运输成本；C2-配送中心启用成本；h1-车辆早于时间窗到达所受惩罚因子；h2-车辆晚于时间窗到达所受惩罚因子；E-惩罚成本常量；g1(x)-该路线总需求超过车辆限重时对目标进行的惩罚；g2(x)-该路线总需求超过车辆限重时对目标进行的惩罚；factor-车辆k的载重不能满足该路线上配送点总需求时的惩罚因子；H-车辆早于或者晚于时间窗到达所造成成本损失的惩罚函数，具体为式3和式4。

当0

Hijk=Eh1(ETi-ti)

(3)

当ti>LTi时

Hijk=Eh2(ti-LTi)

(4)

其中约束条件为

(5)

(6)

(7)

(8)

rk=∑qiYik,i∈V,k∈K

(9)

0≤rk≤Q,k∈K

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

式5～8为0-1约束；式9和式10表示车辆k实际载重，且不能超重；式11和式12表示车辆k超重时对目标函数的惩罚；式13表示车辆k从配送中心出发，作业完成后再返回该配送中心；式14和式15表示配送点有且只有一辆车进行服务；式16表示每辆车只能被使用一次；式17和式18表示所有配送点都有对应的配送中心。

2 算法设计

BFO算法主要通过趋向性操作、复制操作、迁徙操作来模拟大肠杆菌在觅食过程中寻找富营养区，从而找出问题最优解的过程。通过改进标准BFO算法已取得了一系列优化成果，如文献[15]中针对趋向性操作，提出自适应步长更新公式，根据算法的迭代次数动态地调整菌群步长，提高算法的求解效率和精度，并通过解决高维问题验证了算法的有效性和优越性。但是标准BFO算法适用于求解单目标连续问题，而生鲜物流配送问题即LRP问题是一个离散问题，加之引入了成本、时间成为了一个多目标离散问题，因此在使用细菌觅食优化算法对该问题进行求解时需要对算法的编码方式、趋向性操作、复制操作、迁徙操作做出相应的改进。

2.1 编码及解码

对于有N个配送点、K辆车进行作业的网络，对每个细菌个体生成一个2行N列的数组，列号作为配送点编号，范围是[0,N-1]，每个细菌个体代表一种配送方案。

每个细菌个体数组第一行X1，采用整数编码，共N个数字，代表该配送点进行作业的车辆编号。初始化时，随机得开放配送中心，根据就近原则对配送点进行分配；数组第二行X2采用实数编码，表示配送顺序权值，根据随机生成的权值大小来决定由同路径上配送点的配送顺序，其取值为(0，N)。对于M个备选配送中心，将其加入到各条路径中，选择使得子方案成本最小的配送中心，并将其编号记录在车辆组的结构体中。

具体某个细菌个体编码方式如表1所示。

表1 细菌个体编码示意

假设carc[K]为struct car类型的车辆组，由表1解码可知，参与配送任务的车辆编号为：0，1，2；若0号车辆由2号配送中心负责，则c[0].flag=2，0号车辆的配送路线为：2-1-4-2；同理，1号车辆的配送路线为：4-5-3-4；2号车辆的配送路线为：1-0-2-1。

2.2 多目标趋向性操作

若设Ox(i,j,k)表示第x个细菌在第i次趋向性操作，第j次复制操作以及第k次迁徙操作后的位置。其在第i+1次趋向性操作，第j次复制操作以及第k次迁徙操作后的位置调整为Ox(i+1,j,k)=Ox(i,j,k)+C(i)α(i)。其中C(i)为细菌个体移动的步长，α(i)为细菌个体移动的方向。在趋向性操作中，针对车辆编号为整数，配送点权值为实数的问题，采用不同的步长数组进行位置更新。车辆组步长固定为1和-1；配送点权值组采用步长计算公式进行位置更新，步长计算公式如下:

C(i)=cos(2*π*(angle/360))*step

(19)

其中，angle为[0，360]上的随机数；step为固定步长。

菌群个体所代表的每个方案中每次尝试对车辆编号及配送点权值进行更新后，都需要比较该个体更新前后新、旧方案的好坏，如果新方案更好，个体继续向前寻优，直到新方案不再优于旧方案或者达到最大尝试次数Ns为止。由于多目标问题不能通过单目标求解方法来考量菌群个体每次前进后新、旧位置的好坏，因此引入Pareto支配关系进行择优。当新方案和旧方案存在支配关系时，可以根据Pareto支配关系判断新旧方案的好坏；但是当新旧方案互不支配时，需要对其进行归一化统一量纲来比较新旧方案的好坏。

定义1:Pareto占优。

假设有M个以最小化为目标进行优化的函数(f1,f2,…,fm)。x,y为其两组解，对于所有m=1,2,…,M，有fm(x)≤fm(y)，且至少存在一个n满足fn(x)

∀m=1,2,…,Mfm(x)≤fm(y)∧

∃n=1,2,…,M

fn(x)≤fn(y)

(20)

定义2:Pareto最优解。

若Xf为所有可行解的集合，解x*不被其他可行解支配，则称之为Pareto最优解，即：

(21)

定义3:Pareto最优解集。

由所有非支配解构成的集合称之为Pareto最优解集p*，即：

p*≜{x*|∃x∈Xf:x≻x*}

(22)

归一化方法如下：

(23)

其中

gi(xnew)=fi(new)/fi(total)

(24)

gi(xold)=fi(old)/fi(total)

(25)

fi(total)=fi(new)+fi(old)

(26)

2.3 多目标复制操作

MOBFO中通过每种方案之间的Pareto支配关系，统计每种方案的被支配次数，根据被支配次数来对菌群个体进行排序。引入外部集用于存放找到的非支配解，以保留寻优过程中找到的较优方案。具体寻优过程如下：

Step1:统计每种方案的被支配次数并排序；

Step2:判断该方案是否为非支配解；

Step3:判断该方案是否已经存在于外部集中，如果是转Step2；否则转Step4；

Step4:判断外部集中方案个数sunny是否等于菌群个体数S，如果是转Step5；否则该方案存储于外部集中，sunny++；

Step5:判断当前找到的非支配解与外部集中的解是否存在支配关系；如果当前方案更好，取代外部集中该解，Step2；如果该方案不优于外部集中任一，Step2；如果该方案和外部集中的解存在互不支配关系，根据2.2中归一化方法进行择优，Step2。

2.4 多目标迁徙操作

迁徙操作中，个体在满足了一定的迁徙概率Ped时，该个体消亡，但同时在搜索空间的随机位置重新生成新的个体，相当于将原来的细菌个体重新进行初始化。这一行为大大降低了算法陷入局部最优的概率，增加了种群的多样性，扩大了个体的搜索空间。迁徙次数的大小影响着算法的时间复杂度。随着迁徙次数的增加，种群中消亡个体增加，种群多样性也随之增大；反之种群多样性则降低。

2.5 算法步骤

具体步骤如下：

Step1:初始化，设定趋向性操作、复制操作、迁徙操作的次数Nc、Nr、Ne，趋向性操作最大尝试次数Ns，迁徙概率Ped，种群规模N，外部集个数sunny，并将N个配送点随机分配给随机开放的配送中心；

Step2:迁徙操作循环：l=l+1；

Step3:复制操作循环：k=k+1；

Step4:趋向性操作循环：j=j+1；计算适应度S1，S2；对每个细菌个体的X1和X2行进行步长更新，计算新分组后的适应度值S1，S2，并按照2.2节进行择优；

Step5:如果j

Step6:根据2.3节所述进行复制操作过程，并更新外部集；

Step7:如果k

Step8：根据2.3节所述进行迁徙操作；

Step9:如果l

3 实验结果与分析

为了验证算法的有效性，数据采用Augeral等共享的有约束的车辆路径问题(capacitated vehicle routing problem，CVRP)数据库中A-n36-k5.vrp文件的实例。其中共有30个配送点，6个备选配送中心，具体参数见表2和表3。其他参数如下：Q=80，v=50，E=100，h1=0.1，h2=0.2，C0=30，C1=5。

表2 配送中心参数

表3 配送点参数

续表3 配送点参数

3.1 参数设置

算法相关参数设置如下：S=20，Nc=30，Nr=50，Ne=5，Ped=0.2，Ns=10，F1=F2=0.5。实验基于Win10操作系统，通过C语言编程，在VC++6.0平台进行仿真。重复运行程序50次，取每次运行结果中的最优解，最终确定方案如表4所示。

表4 实验结果

本算例最终选择开放三个配送中心，由计算结果可知，系统总成本为5 895.268。该次方案的拓扑如图1所示。

图1 方案拓扑

3.2 实验分析

为了验证MOBFO的有效性和优劣性，通过与文献[16]和Liu&Lin[16]提出的启发式算法进行对比，具体结果如表5所示。

表5 算法结果对比

由表5可知，MOBFO所求得方案在总成本上优于另两种算法所得结果。但由于文中涉及多目标问题，因此还需比较MOBFO所得最佳方案与文献[16]中最佳方案在配送时间与路程长短上的优劣。由于配送车辆进行配送任务的同时性，配送时间的判断可根据最长路径所花费的时间来衡量。

表6 配送时间、总路程长度比较

由表6可知，MOBFO所得最佳方案在配送总路程长度上要优于文献[16]中的最佳方案，配送时间与文献[16]中相当。但在实际生活中，配送时间和距离长度也会受到一些如路况、气候等因素的影响，从而直接或者间接地影响到方案总成本。决策者的决策情况也会对方案成本等产生一定约束。例如：在配送过程中，决策者为了尽可能地保证生鲜的新鲜度，而忽略在成本上的耗费。由表5和表6表明，MOBFO在求解这一类问题上具有一定的优越性，同时在对于多个目标的优化问题上也具有一定的优势。

4 结束语

以成本最低和配送时间最短为目标，针对生鲜物流配送问题构建了相应的LRP问题模型，根据Pareto支配关系设计相应的多目标细菌觅食优化算法，在个体互不支配时采用归一化方法进行择优处理，通过引入惩罚函数限制车辆所服务客户点的需求，使得每一条路线上的配送点需求都可以被满足。对该问题进行求解，通过算例对比验证了算法的有效性和优劣性，对于LRP问题提供了一定的参考。但还有一些约束没有考虑充分，如配送中心库存问题，交通路况对于车辆行驶速度的影响。而且生鲜物流系统也具有很多不确定性，主要体现在生鲜产品对时间的要求。同时也缺少相应的实际案例，对具体问题进行模拟规划。因此，下一步研究工作可以考虑引入库存问题，解决选址-路径-库存这一集成问题，同时添加随机变量，使得模型更加符合实际情况。