基于人工鱼群算法的模糊运输路径问题研究

徐博文，程 然

（兰州交通大学 交通运输学院，甘肃 兰州 730070）

1 引言

运输路径问题作为库存路径问题（IRP）下的子问题，是研究如何降低物流总成本要攻克的主要问题之一。由于该问题是典型的NP-HARD问题，使用传统优化方法很难得到问题最优解或满意解。Montoya-Torres J R[1]回顾了1988—2014年以来运输路径问题的主要论文，并提出构造启发式算法是该问题的主要研究方向；Amr Farahat[2]等针对IRP问题中库存和运输两方面开发了两种不同处理方法，其中产品运输问题被分解为一组独立的报童问题。并通过计算实验，发现分类优化性能优于整体优化；Lalla-Ruiz E[3]在库存分配完毕基础上提出了一种多车库开放路径模型(MDOVRP)，车辆将货物交付给他们路线上的顾客后，不需要返回仓库可以继续工作；李昌兵[5]等建立了选址—路径—库存问题一体优化的混合整数规划模型，并分别设计了库存和路径的两阶段启发式算法，并通过算例仿真证明了该策略的合理有效性。张丽萍[6]等采用一种改进的遗传算法对其路径模型进行优化，通过数值分析表明，其改进的方法具有更优性。本文在已知IRP问题的相应库存分布方案的基础上，从运输路径角度出发，建立了相应模型，然后尝试使用启发式算法-人工鱼群算法解决该问题，得到相应的库存分布方案。

2 模型建立

IRP问题的模型是多阶段模型，优化目标是确定每个销售渠道所占的比例，并制定相应的运输计划，以最大限度地降低总预期成本。由于本文是在已知IRP问题的相应库存分布方案的基础上，制定相应开放路径运输方案以优化运输成本，故作一些粗糙模型假设[4]如下：

（1）需求分配：各个零售商的需求已对应分配给各配送点。

（2）无限供应：无论时间或规模如何，货物都可立即运输。

（3）货物兼容：不同零售商的货物可混在同一辆车中运输。

（4）延期交货：不考虑库存阶段延误成本。

部分指数如下：

车辆：k=1,2,…,M；配送点：i=1,2,…,Nk；零售商：j=1,2,…,L。

部分参数如下：

W：总成本；

γ：影响因子；

nk：车辆承载零售商的数量；

bk：车辆载重；

：车辆从零售商j1到零售商j2产生的物料成本；

ej：每个零售商所占的份额；

μ(nk-1)：任何时期零售商期望总量；

rkj：运送路径；

Vislk：车辆视野。

相应成本函数[6]如下：

式（1）表示运输距离成本部分，式（2）表示时间成本部分。

2.1 精确模型建立

式（3）是数学模型的目标函数,目的是最小化总成本；式（4）保证每条路径上的各商店的总需求量不超过此条路径配送车容量；式（5）表示每条路径服务的商店数不超过总商店数；式（6）要求每个商店都得到车辆的配送服务；式（7）表示每条路径的商店个数；式（8）表示每个商店有唯一的车辆为之服务；式（9）表示检测车辆是否需要进行二次运输。

2.2 模糊模型建立

由于供应链网络的复杂性和现实运输市场的不确定性，整个分配网络中的很多参数很有可能是随着时间、空间等因素在不断变化的，各层级的能力也都是模糊变量，且上述模型的约束多为非线性或非凸形，求解最优解比较困难，因此，我们基于供应链网络模型，利用模糊数学[10]和不确定规划[11]的知识，将精确模型转化为模糊期望值模型（EVM）来降低求解难度，并在此基础上进行分析。

步骤1：令E=0;

步骤2：在ξij的ε-水平集随机产生，k=1,2,…,m。记uk为组成的向量，i=1,2,…,N，其中ε为一个充分小的数;

步骤3：

令a=f(x,u1)∧f(x,u2)...∧f(x,um),b=f(x,u1)∨f(x,u2)∨...∨f(x,um)

步骤4：在区间[a,b]随机产生r;

步骤5：如果r≥0，则E←E+Cr{f(x,ξ)≥r};

步骤6：如果r＜0，则E←E-Cr{f(x,ξ)≤r};

步骤7：重复第4步到第6步N次;

步骤8：U(x)=E[f(x,ξ)]=a∨0+b∧0+E(b-a)/N。

EVM模型如下：

式（11）是数学模型的目标函数,目的是使期望值总和最小；式（12）保证每条路径上的各商店的总期望不超过此条路径配送车容量；式（13）表示每条路径服务的商店期望不超过总商店数；式（14）要求每个商店都得到车辆的配送服务；式（15）表示每条路径的商店个数；式（16）表示每个商店有唯一的车辆为之服务；式（17）表示检测车辆是否需要进行二次运输。

3 人工鱼群算法（AFSA）

由于该分配网络问题的NP-HARD特性，本文探讨启发式算法作为求解方法，选择了一种适应该分配网络的人工鱼群算法[7]并进行相应改进来求解上述模型。

人工鱼群算法是2002年李晓磊等观察鱼类流动特点后提出的一种与动物本能活动反应相似的寻优模式，其相关概念简介如下：

3.1 AFSA几种典型行为

（1）随机行为。鱼在水中漫无目的进行本能移动，它是觅食行为的一个缺省行为。

（2）觅食行为。在发现食物时，鱼类会迅速的朝着有食物的方位游去，是鱼类所具有的最基本的行为。

（3）聚群行为。鱼类会通过聚群在一起的方式来提高其本身的生存率。该行为具有跳出局部约束去寻找其他局部最优的能力。

（4）追尾行为。在鱼群游动过程中，当其中一条或几条鱼感觉到食物并逐渐向它转移时，相邻的鱼在发掘其行动后有跟随动作。该行为可以在某个局域内明确目标快速做出选择与行动，进而快速寻优，并防止AF在局部范围内滞留过久。

3.2 AFSA中一些特殊的用法

（1）拥挤度[8]。鱼群算法中引入拥挤度δ(0＜δ＜1)限制人工鱼群的大小。此方法可以避免在较优的领域内聚集过多的鱼而增加竞争、增大成本，在次优或其他领域聚集鱼类较少或没有鱼而产生资源浪费现象。

（2）公告板。算法中设置公告板来记录当前人工鱼状态，每一条鱼在行动之后就与公告板上所记录的状态相比较，如若状态更加优秀，就取而代之。这样，公告板就记录了整个寻优过程中的大部分数据。通过使用人工鱼群算法不断改变各点自身状态，并将相应数据与公告栏比较，在经过一系列反复搜索寻优后，所得最优结果最终被留在公告板上。

3.3 鱼群算法中的主要函数

鱼群算法主要函数见表1。

4 运输路径问题人工鱼群算法（AFSA）

人工鱼群算法解决运输路径问题的基本过程如下：

步骤1:初始化解空间；

步骤2:零售商通过觅食行为、聚群行为、追尾行为选择分销中心；

步骤3:更新公告栏数据；

步骤4:检查终止条件；

步骤5:优化数据，循环步骤2-步骤4；

步骤6:输出结果。

4.1 算法设计

算法中用一个二维数组来表示车辆的配送路径，一个二维数组作为公告板记录当前零售商与运载车辆的状态。Xj为当前零售商状态，Step为移动步长，di，dj分别表示运载车辆、零售商的位置。选择一个零售商，尝试各种行为并依次判断当前状态是否能够执行聚群行为、追尾行为。

4.1.1 觅食行为。在当前车辆视野Visual内随机移动到新的位置作为下一步移动的方向公告栏更新数据并进行下一个零售商的行为选择。

4.1.2 聚群行为。移动至当前视野Visual内交接能力最强的分销中心所处的位置判断是否满足聚群行为的条件，如果满足，则得到下一步移动的方向公告栏更新数据并进行下一个零售商的行为选择；不满足条件则继续进行觅食行为，如重复Tru_number次，仍找不到更合适的位置，则执行随机行为。

4.1.3 追尾行为。搜索至当前步长Step 内最大零售商所选择分销中心位置以计算运输成本；判断是否满足追尾行为的条件，如果满足，则得到下一步移动的方向公告栏更新数据并进行下一个零售商的行为选择；不满足条件则继续进行追尾行为，如重复Tru_number次，仍找不到更合适的位置，则执行随机行为。

4.2 改进及优化

可以发现，人工鱼群算法在运算初期具有很强的收敛性；随着算法的运算过程，收敛速度有所下降，此时可以采用改进视野、分段优化、混合优化等方法提升其后期收敛性。

4.2.1 视野的改进及优化。在鱼群模式所讨论的视野概念中，视野的选择、移动的步长都是随机的，而视野对算法中各种行为和收敛性能有较大影响。若视野范围较大，则人工鱼的全局搜索能力强，但精度低，运算量大；若视野范围较小，则人工鱼的局部搜索能力强，精度高。所以我们在算法运行前期，采用了较大的视野，意在增强全局搜索能力和收敛速度，并随着算法的进行，视野和步长逐渐缩小，提高其局部搜索能力和结果精度。视野和步长的调整公式如下:

其中，Visualz为供货商的视野；Visualt，Stept为当前视野，步长，初始值为Visualz/4 、Stepz/4 ；Visualm，Stepm为最小可移动视野，步长。 s ∈[0,1]用来控制α的变化速率，这里分别取S=1,S=3/4,S=2/3,S=1/2，所得的α值及视野Visual变化如图1、图2所示。

图1 函数α 变化图

图2 视野变化图

4.2.2 觅食行为的优化。觅食行为执行的是一种随机试探行为,其目的是寻找较优的解,该行为受视野、步长等条件约束。在试探Try_number次的过程中,如果不满足前进条件,但有合适的矢量方向，则记录下这个矢量步长，这样可以化简运算量,加快向全局最优解转化。

5 算例分析

本文以五个配送点（97，120；-100，40；-133，-104；-10，-79；137，-30）和十五个零售商（251，200；-156，-91；-93，79；-210，282；126，143；-18，-157；-238，-239；78，-92；246，-217；-201，-224；-80，-127；-169，-138；262，-64；40，262；204，-72）组成的配送系统进行研究，各零售商的期望分别为（327.5；236.5；207.5；329；439.5；492；315.5；148；516；557；417；328.5；218.5；111.5；356），相应的库存分布方案见表2。

表2 库存分布方案

仿真1 给出了改进AFSA 算法求解与遗传算法（GA）求解结果分析，算法进化代数为30 次，成本比γ=1/3；车辆载重bk=1 000 ；Visualz=500 ，Visualm=0.001，Step=Visual/3，选取s=3/4、s=1 进行迭代，其中，GA 的交叉率为0.6，变异概率为0.1。最终的最优路径数据见表3。

表3 最优路径数据对比

通过实验结果可知，AFSA不仅所需确定的参数少，加入S值优化后其收敛速度和精确度间的调整更加简单、直观。在迭代次数相同的情况下，改进视野及步长后取S=3/4 的人工鱼群算法取得了比遗传算法更好的优化结果。

6 结语

本文通过对IRP问题下的子问题-运输路径问题的相关分析及建立相应模型并实践计算，得到了如下结论：

（1）库存分布问题和运输路径问题，既可以分开考虑，也可以一并研究。

（2）对相应的运输路径问题模型进行模糊处理既可以降低模型的难度，也可以使模型更加直观明了。

（3）对以人工鱼群算法为基础的启发式算法进行相应的改进和优化，使之应用于运输路径问题，是可行有效的。

（4）改进优化视野和步长可以提高人工鱼群算法局部搜索能力及运算结果的精度。

本文通过模糊模拟简化了相应的库存路径模型，实际问题中的一些不稳定因素的影响，还需进一步的研究以改进和完善。