人工鱼群算法在模糊VRP问题中的应用

朱颢

（湖州职业技术学院，浙江 湖州 313000）

人工鱼群算法在模糊VRP问题中的应用

朱颢

（湖州职业技术学院，浙江 湖州 313000）

针对一类同时带模糊旅行时间、卸货时间和模糊需求的VRP问题，建立了以可信性测度为基础的模糊机会约束规划模型；然后设计了基于模糊模拟、神经网络和人工鱼群算法的混合智能算法，在人工鱼群算法寻优过程中，针对问题设计了专门的人工鱼修复策略、行为策略和寻优策略；最后通过仿真实验证明，该算法对解决此类模糊VRP问题是行之有效的。

模糊车辆路径问题；人工鱼群算法；模糊模拟；神经网络

1 引言

车辆路径问题作为一类经典的组合优化问题，也是NP难问题，长期以来都是科学界的研究热点。模糊车辆路径问题作为其中的一个分支，其含义为：在外部环境（如交通状况、客户需求量、车辆旅行时间等）无法精确预测的情况下，如何合理地为每个客户分配车辆，安排车辆的行驶路线和出发时间，以使得某些指标（如总费用、总行驶距离等）最优。鉴于此类问题，Yanfang Ma等[1]讨论了时间窗为模糊随机变量的车辆路径问题，提出了基于粒子群优化的云理论。Lian Xue等[2]针对带模糊需求的车辆路径问题，提出了基于模糊模拟和差分进化算法的混合智能算法。Mehdi Adelzadeh[3]等考虑了一类带模糊时间窗的多车型、多车场车辆路径问题，并提出了一种启发式算法。Ghannadpour等[4]针对一类带模糊旅行时间和客户满意度的多目标动态车辆路径问题，提出了基于遗传算法的动态解决策略。Kuo,R.J等[5]以带模糊需求的车辆路径问题为对象，提出了一种基于粒子群算法和遗传算法的混合算法，在粒子群算法中加入交叉和变异操作。Cao Erbao等[6]探讨了一类带模糊需求的开放式车辆路径问题，运用随机模拟和改进的差分进化算法进行了求解。Chang Shi Liu等[7]针对带模糊需求的车辆路径问题，提出了一种混合元启发式算法。Lian Xue等[8]针对同样的问题，利用模糊模拟和差分进化算法进行了求解。Peng Yang等[9]则运用粒子群算法进行了求解。

国内文献中，祝崇隽等[10]针对带模糊需求的VRP问题，提出了基于可能性分布和基于需求上界的2-OPT算法。张建勇等则先后提出了一种Sweeping启发式算法[11]和基于模糊模拟的混合遗传算法[12]，针对具有模糊旅行时间的VRP问题，用模糊逻辑和遗传算法相结合进行了求解[13]，并针对带模糊预约时间的VRP问题，提出了基于“推一碰一掷”的改进遗传算法[14]。曹二保等[15]针对带模糊需求的车辆路径问题，用基于随机模拟的差分进化算法进行优化。陈宝文等[16]针对带模糊需求的车辆路径问题，提出了基于多蚁群协作的改进蚁群算法。崔雪立等[17]针对具有模糊预约时间的车辆路径问题，利用蚂蚁算法进行求解。王君等[18]针对具有模糊需求的带时间窗的车辆路径问题，设计了嵌入模糊模拟的改进非支配排序混合遗传算法。王连锋等[19]考虑带硬时间窗车辆路径问题的多重模糊性质，建立了多目标模糊期望值模型，提出了一种自适应粒子群算法。

从有关模糊车辆路径问题的文献看，问题主要集中于带模糊需求量和模糊时间窗、模糊预约时间等几种类型上，对于带模糊旅行时间的文献较少，只有文献[4]和文献[13]涉及，同时具有模糊需求量、模糊旅行时间、模糊卸货时间的研究文献更少。优化算法主要集中于各种启发式算法[3,7，10,11]、蚁群算法[16，17]、粒子群算法[1，5，9，19]、遗传算法[4,12,13,14，18]、差分进化算法[2,6,8,15]等几类算法上。

人工鱼群算法作为一种新型的智能优化算法，由我国学者李晓磊[20]提出，该算法通过模拟鱼群的觅食、聚群、追尾、随机游动等行为，能有效地在问题的解空间进行搜索，寻找问题的最优解。目前，人工鱼群算法在车辆路径问题中已有一定的应用，如覃磊等[21]利用一种基于三维粒子编码的改进人工鱼群算法，对确定性VRP问题进行了研究。王培崇等[22]针对确定性的VRP问题，提出了将鱼群算法和遗传算法相混合的策略。柳毅等[23]对带模糊需求的可回程车辆路径问题，提出了改进的人工鱼群算法。郭海湘等[24]针对煤矿物资行业中的配送车辆路径问题，用人工鱼群算法进行了求解。虽然人工鱼群算法在车辆路径问题中得到了一定的应用，但是从相关文献来看，主要基于确定性的车辆路径问题，该算法在同时带模糊需求和模糊时间的车辆路径问题的应用还不多见。

本文针对同时带模糊需求量、模糊旅行时间、模糊卸货时间的车辆路径问题，建立相应的模糊机会约束规划模型；设计了基于模糊模拟、神经网络和人工鱼群算法的混合智能算法：首先通过模糊模拟产生样本数据，然后将样本数据作为一个BP神经网络的输入和期望输出，对神经网络进行训练，使得该神经网络能逼近模型中的两个可信性函数；最后利用训练好的神经网络计算任意一个问题解所对应的两个可信性函数的值，以此判断该解是否满足约束条件，并利用人工鱼群算法进行寻优，在此阶段，设计了适合该问题的人工鱼修复策略、移动策略和寻优策略。

2 带模糊时间和模糊需求量的VRP模型

带模糊时间和模糊需求量的VRP问题可以被描述为：一个配送中心（用0表示，以下简称为“车场”）为n个客户（i=1,2,...,n）提供送货服务；车场共拥有m辆车（k=1,2,...,m），每辆车的额定载重量为Qk，从车场出发，完成一系列客户的送货后回到车场；每个客户i只能由一辆车提供服务，其需求量qi为三角模糊数(qi1,qi2,qi3)；每个客户i均有一个服务时间窗口[ai,bi]，送货尽可能在此时间范围内进行；客户i和 j的距离为Dij（i,j=0,1,2,...,n）；车辆从客户i到客户 j的旅行时间Tij不确定，用三角模糊数(Tij1,Tij2,Tij3)表示；车辆在客户i处的卸货时间Si不确定，用三角模糊数(Si1,Si2,Si3)表示；fi为车辆抵达客户i的时间，若车辆在客户i的时间窗口[ai,bi]之前抵达，则须等待至时间ai处才能开始卸货，若在[ai,bi]之间到达，则立即卸货。该问题的实质是在满足一系列约束（如车辆装载能力约束、客户需求时间窗口约束等）的条件下，为各辆车分配相应的客户及安排送货顺序，并确定各车辆从车场出发的时间，以使得某些指标最优（如距离最短、成本最低等）。

问题的决策变量为x,y,t，其含义如下[25]：

x=(x1,x2,...,xn)，表示n个不同的客户编号的一个排列，对于所有的 i≠j，有 1≤xi≤n，xi≠xj, i,j=1,2,...,n。

y=(y1,y2,...,ym-1)，表示m-1个位于区间[0,n]内的整数，且 y0=0≤y1≤y2≤…≤ym-1≤n=ym，其含义如下：

对于每个k=1,2,...,m，yk-yk-1表示车辆k服务的客户数量。若yk=yk-1，车辆k不运行；若yk>yk-1，则表明车辆k服务的客户数为yk-yk-1，服务的客户按顺序从 xy(k-1)+1开始，到 xyk为止，其行驶路线为：车场0→客户xy(k-1)+1→客户 xy(k-1)+2→…→客户 xyk-1→客户 xyk→车场0 t=(t1,t2,...,tm)，tk代表车辆 k从车场出发的时间，k=1,2...,m。

对于每个x,y,t表示的送货安排（问题解），可知：若车辆k已经投入运行，则其到达第1个客户的时间为：

车辆k运行的路程为：

综上所述，可以建立如下的模糊机会约束模型：

模型中目标（4）表示最小化所有车辆的总行驶路程；约束（5）为车辆载重能力约束，表示每一辆车k所装载货运量不超过其额定载重量的可信性应该不小于主观给定值α；约束（6）为服务时间约束，表示车辆抵达每个客户i的时间 fi处于时间窗口[ai,bi]内的可信性应该不小于主观给定值 β；约束（7）、（8）和（9）分别能确保每个客户只由一辆车提供服务，每辆车最多只被使用一次。

3 算法介绍

3.1 问题的编码及解码

针对本模型，以(x,y,t)的形式进行整数和实数的混合编码，该向量长度为n+2m-1，其中：x部分和y部分的含义如前所述，t部分为m个实数，代表m辆车的出发时间，可以限定在区间内。采用此编码方式肯定能满足约束条件（7）-（9），按照如下方式进行解码：先根据y部分的元素判断每辆车是否执行任务，对执行任务的车辆，记录每辆车服务的客户数量number_custom和对应的客户编号code。

为更好地解释解码规则，给出一个由10个客户，4辆车构成的问题，其编码长度为17：某一个解如下，[1,2, 4,3,6,5,7,8,9,10,1,4,8,8.004 9,8.069 4,8.101 4,8.099 4]。对此编码，前10个整数元素代表10个客户的重排；第11-13位的元素为1,4,8：表示第一辆车服务的客户数量为1，对应客户编号为1，第二辆车服务的客户数量为3，对应客户编号依次为2,4,3，第三辆车服务的客户数量为4，对应客户编号依次为6,5,7,8；第四辆车服务的客户数量为2，对应客户编号依次为9,10；第14-17位的元素分别表示四辆车从车场出发的时间。四辆车均执行任务，每 辆 车 的客户服务数量为 number_custom= [1 3 4 2]，对应的客户编号code由一个m×n的矩阵表示，如图1所示。

图1 客户编号code矩阵

矩阵code具有如下特点：第一行表示第一辆车服务的客户，第二行表示第二辆车服务的客户，以此类推；所有非0的元素均表示客户的编号，必须出现且只出现一次，且均排在0元素（称为“伪元素”）之前；所有为0的元素无任何意义，表示此位置无任务安排，不同于前面所述的车场编号0；若某一行元素均为0，则表示该车辆没有行驶。反过来，根据任意给定的符合上述条件的矩阵code，均可以通过倒推获取(x,y,t)中x部分和y部分的值，在此称为“逆映射”。

3.2 模糊变量的处理

由于本文中客户的货物需求量、车辆旅行时间、车辆卸货时间均为三角模糊数，传统的方法已经无法解决约束条件（5）和（6），需要采用模糊模拟的方法。首先考虑随机生成 sample_num个输入样本 solution[p]，p=1,2,...,sample_num，然后对样本进行解码，记录每辆车服务的客户数量number_custom和对应的客户编号code，得到该车辆的行驶路线。

对于每个输入样本solution[p]，采用如下方法进行模糊模拟：

Step1：对于每辆执行任务的车辆k（1≤k≤m），首先判断该车是否执行任务，若未执行任务，则跳过至下一辆车，否则，得到其行驶路线为：

g,其中Pos为模糊可能性测度。

Step2：重复 Step1共 mod_ti mes次，可获得mod_ti mes个的值和的值，g=1,2,...mod_ti mes。

Step3：计算d1和d2。

d1即为的估计值,d2即为Cr{ai≤fi(x,y,t)≤bi,i=1,2,…,n}的估计值。

3.3 用遗传算法训练神经网络

针对前述车辆能力约束和需求时间窗口约束，将sample_num个输入样本solution[p]（p=1,2,..., sample_num）的编码经归一化处理后，作为具有三层感知结构的BP神经网络的输入数据，3.2节模糊模拟得到的数据作为BP神经网络的期望输出，利用遗传算法训练BP神经网络，使得该BP神经网络能逼近公式（5）和（6）中的两个可信性函数。

3.3.1 神经网络的结构和参数的确定。假设该BP网络的输入层节点数为M，隐层节点数为N，输出层节点数为L，则对于每个solution[p]，将其每个基因作为输入层节点，节点数M为solution[p]的编码长度；输出层节点数L=2，分别对应公式（5）和（6）中的两个可信性函数；隐层节点数N经过多次实验后确定，节点数太少会使BP神经网络的逼近能力不够，而太多会增加网络训练的时间。

由于神经网络的输入层节点为solution[p]中的基因(x,y,t)，隐层节点阈值可考虑为x、y、t三部分基因之和的一半，由于x部分各基因之和始终不变，y、t部分的基因始终在变化，根据随机生成的输入样本中y、t部分的情况，考虑取平均值。因此可将隐层节点阈值初步设为：

输出层节点阈值设为：

3.3.2 遗传算法的编码及解码。设染色体种群集合为title_pop，种群规模为popsize。本节中染色体为神经网络的权值，如图2所示：染色体总长度为M×N+2×N，前M×N个基因为输入层节点i和隐层节点j之间的权值，表示为wij∈[0,1]；后2×N个基因为隐层节点 j和输出层2个节点之间的权值，表示为。对于每个权值染色体，采用文献[26]的方法计算所有输入样本训练后的总误差Error。

图2 BP网络权值结构

3.3.3 遗传算法的适应度。神经网络的训练目标为极小化所有训练样本的总误差Error，本文采用基于序的评价函数，见式（14）：

其中a'为一较小的参数。

3.4 人工鱼群算法优化

随机产生以 (x,y,t)表示的人工鱼种群fi sh[p]，p=1,2,...,popsize_fi sh，种群规模为popsize_fi sh，然后利用训练好的神经网络计算出Qk,k=1,2,...,m}和Cr{ai≤fi(x,y,t)≤bi,i=1,2,…,n}的值，判断该人工鱼是否可行，若不满足约束条件（5）和（6），则采用如下3.4.1的方式进行修复。

3.4.1 人工鱼的修复策略。首先需要对不可行的人工鱼 fi sh[p]进行解码，得到其对应的矩阵codep，然后针对两个能力约束进行修正：

（1）若不满足车辆载重能力约束，表明有车辆服务的客户过多，先从矩阵codep中选择服务客户数最多的那辆车（如图3为第3辆车）开始调整，选择最末尾的客户（图中客户编号为8），将其分配给已执行任务且服务客户数最少的那辆车（图中为第1辆车），该客户编号插入已有客户最后面（客户1后面），此方法表示在几条子路径之间进行客户数量的增减，然后逆映射操作，判断是否满足该约束，否则重复该步骤直到满足约束条件为止。

图3 客户编号codep子线路间调整

（2）若满足车辆载重能力约束但不满足服务时间窗口约束，则表明每辆车装载能力满足要求，各条子路径客户分配没有问题，但是子路径内的客户顺序以及车辆的出发时间需要调整。由此，可以依照客户数量多少依次在每条子路径中随机交换两个子路径内的客户位置（如图4中将第3辆车所构成的子线路内客户7和8交换位置），然后逆映射操作，判断是否满足该约束，若所有的子路径均交换完毕，还不能满足约束条件，则对车辆出发时间t进行变异，随机生成一个t'替换t直至满足约束条件。

图4 客户编号codep子线路内调整

3.4.2 人工鱼的距离。人工鱼对外界的感知靠视觉来实现，只有视觉范围内的环境信息才能被人工鱼所接收，因此如何设计两条人工鱼的距离对算法来说就显得尤为重要，本文拟借鉴文献[24]所述的方法来定义两条人工鱼之间的距离及中心鱼。

不失一般性，任意两条由(x1,y1,t1)和(x2,y2,t2)表示的人工鱼 fi sh[1]和 fi sh[2]，均可以经过解码得到矩阵code1和code2，用符号eki表示两个矩阵第k行和第i列位置客户编号的相似度，如果相同，则eki=0，否则eki=1，则两条人工鱼的距离表示为公式（15）。

3.4.3 人工鱼的适应度函数。由于该模型需要将目标函数极小化，对人工鱼进行解码后，根据式（4）求得目标函数值Z，令人工鱼的适应度函数为：

3.4.4 人工鱼的步长step。根据人工鱼群算法的原理，当前人工鱼 fi sh在执行聚群行为和追尾行为时，若发现中心鱼或最优伙伴鱼较自身状态更优（食物更浓），且周围不太拥挤时，fi sh朝中心鱼或最优伙伴鱼的方向前进一步达到状态 fi shnext。以聚群行为为例，应同时满足式（17）和（18）。

且应该保证 fi shnext较 fi sh更优，否则聚群行为没有意义，这一思想在连续空间中容易实现。在VRP这一类的组合优化问题中，解的空间是离散的，不一定存在一个合适的状态 fi shnext满足以上特征，即使搜寻到了符合这样特征的一个状态 fi shnext，该人工鱼不一定是可行的，还需要按照3.4.1的方式再次进行修复，而修复的过程还会再次改变它们的距离，导致新状态 fi shnext有可能处于当前人工鱼 fi sh的视野之外。因此，对于本文的人工鱼群算法，若符合聚群行为和追尾行为的条件，则让当前人工鱼直接跳跃到中心鱼或最优伙伴鱼上，一方面节省了算法寻优的时间，另一方面避免了过多的修复，此时，其步长step其实是根据自身情况决定的，在执行觅食行为时同样如此。

3.4.5 人工鱼的聚群行为

（1）确定人工鱼视野内伙伴群的中心鱼位置。对于中心鱼的确立，本部分采用逆向的方式，先确定可能的中心鱼 fi shcenter所对应的矩阵codecenter，然后“逆映射”可得到中心鱼 fi shcenter编码方式(xcenter,ycenter,tcenter)中 xcenter部分和ycenter部分的值。

Step1：对伙伴群 partner内的每条人工鱼 fi sh[j]，先通过解码分别获得矩阵codej；

Step2：令k=1,2,...,m和i=1,2,...,n，统计客户编号1,2,…,n及伪元素0在每个矩阵code的第k行和第i列位置上出现的次数，取出出现次数最多的那个客户编号（包括伪元素0）填入 codecenter[k][i]，并用另一个矩阵max_numcenter[k][i]记录该客户编号（包括伪元素0）在该位置出现的次数。

通过Step1和Step2可以初步得到一个矩阵codecenter，但该矩阵可能不符合3.1节中所描述的特征：①某个客户编号出现2次及以上；②某个客户编号未曾出现；③某个客户编号前面存在伪元素0。对于以上可能出现的情况，采用如下方式进行修正：

首先设置存储器storage={1,2,…,n}，并将已经安排在codecenter中的客户编号清除。对于codecenter中出现的情况①，先比较相应位置上该编号分别出现的次数，保留max_numcenter[k][i]取值大的位置（最大限度地保留了伙伴鱼群的共性），若出现的次数一样，则优先保留最左边的位置（这样减少了矩阵codecenter中伪元素0在客户编号1,2,…,n前出现的可能性），其余位置的编号暂时用伪元素0代替,并记录其横坐标k和纵坐标i，此方法解决了问题①；然后重新扫描codecenter，查找排在客户编号前面的伪元素0，从存储器中随机安排一个尚未插入的客户编号，重复操作直到问题③解决，若所有客户均安排完毕，仍然存在问题③的现象，则将本行后面的非0客户编号依次前移。若上述问题①和③解决，但是还有剩余客户编号未安排，则随机安排在某一行最后非0的客户编号后，此方法解决了问题②。

Step3：在得到矩阵codecenter后进行逆映射操作，可得到中心鱼 fi shcenter编码方式(xcenter,ycenter,tcenter)中 xcenter部分和 ycenter部分的值。至于 tcenter的值，可以取伙伴群partner内的每条人工鱼 fi sh[j]中t部分的平均值。

Step4：检验该中心鱼 fi shcenter是否可行，将训练好的神经网络嵌入，计算该VRP模型中两个可信性函数的值，若不满足约束条件（5）和（6），则采用3.4.1策略进行修复，否则说明可行。

（2）执行聚群行为准则。当中心鱼 fi shcenter优于当前人工鱼 fi sh[p]，且 fi shcenter的周围不太拥挤时（判断准则见式（23）），则让 fi sh[p]直接跳向 fi shcenter（当然，此处不是直接改变 fi sh[p]的值，而是将 fi shcenter先作为fi sh[p]的下一代候选状态之一储存起来，以备和其他行为执行结果进行比较，再来决定下一代迭代时fi sh[p]的状态），否则不执行聚群行为。

式（19）中Fcenter为 fi shcenter的适应度，n_f为伙伴群内人工鱼数量，δ为拥挤度因子，Fp为 fi sh[p]的适应度。

3.4.6 人工鱼的追尾行为。在 fi sh[p]视野范围visual内，搜寻适应度最大的其他伙伴鱼，令其为 fi shbest_parter，若其位置较 fi sh[p]更优，且周围不太拥挤（判断准则见式（20）），则让 fi sh[p]直接跳向 fi shbest_parter（同样将fi shbest_parter作为 fi sh[p]的下一代候选状态之一储存），否则不执行追尾行为。

式（20）中Fbest_parter为伙伴群内最优人工鱼的适应度，其他符号同上。

3.4.7 人工鱼的觅食行为。在 fi sh[p]视野范围visual内，随机产生一条新的人工鱼 fi shnew（假设其对应的矩阵为codenew），方法如下：

（1）以 fi sh[p]对应的矩阵codep为基础，从该矩阵编号1,2,…,n中随机选择至少n-visual个编号（其余编号组成集合identifier_no），将其插入另一个矩阵codenew相同的位置，这样可以保证 fi shnew与 fi sh[p]距离在visual内，其他位置暂时用伪元素0代替。

（2）对codenew进行扫描，若某客户的前面有伪元素0，从identifier_no中随机选择客户编号，替代该伪元素0，直至无此现象；若codenew中已有的客户前面已经无伪元素0，而identifier_no中仍然有客户未安排，则将identifier_no中客户随机安排在一辆车的末尾。

（3）逆映射操作，得到 fi shnew编码结构中的xnew部分和ynew部分，tnew部分的取值可以随机生成。

（4）检验人工鱼 fi shnew是否可行，若该人工鱼不可行，需要进行修复，修复时优先考虑在集合identifier_no中的元素间进行位置的交换以及对tnew部分的取值重新随机生成，以保证 fi shnew依然在 fi sh[p]视野范围visual内。

（5）若 fi shnew优于 fi sh[p]，则让 fi sh[p]直接跳向fi shnew（将 fi shnew作为 fi sh[p]的下一代候选状态之一储存）；若 fi shnew的状态较 fi sh[p]差，则重新尝试，反复尝试tr y_number后，仍不能获得一个更好的状态，则放弃觅食行为。

3.4.8 人工鱼的随机移动行为。随机移动行为是觅食行为的缺省行为。在人工鱼 fi sh[p]视野范围visual内，随机产生一条新的人工鱼 fi shrandom（同3.4.7所述的方法），并检验对该人工鱼是否可行，若可行则直接让fi sh[p]跳向 fi shrandom。

3.4.9 人工鱼的行为策略。人工鱼的行为包括聚群、追尾、觅食、随机移动四种，每条人工鱼究竟采取何种策略，关系到算法的搜索空间和收敛速度。本文拟采用并行的搜索策略，先判断聚群、追尾、觅食能否执行，若能执行，选择最优的行为，若三种均不能执行，则执行随机移动行为。具体如下：

对每条人工鱼 fi sh[p]，首先判断是否满足执行聚群、追尾、觅食的判断准则，若满足则先分别尝试执行聚群行为、追尾行为、觅食行为，并比较三种行为执行后得到的新的人工鱼fi shcenter、fi shbest_parter、fi shnew的适应度，取适应度最高的状态作为 fi sh[p]的下一代。若三种行为均不满足判断准则，则执行随机移动行为，将 fi shrandom作为 fi sh[p]的下一代。

在该算法寻优的过程中，为了避免算法陷入局部最优，令变量no_update=0，用来对公告板的更新情况进行记录，若某一次迭代完后公告板进行了更新，则令no_update=0，否则令no_update自动加1，若公告板连续若干代（用no_update_ti mes表示）无法更新，即 no_update=no_update_ ti mes，则将人工鱼种群中适应度最差的10%个体进行替换，用随机产生的人工鱼替代，以扩大问题的搜索空间，希望有所发现，具体的寻优策略如图5所示。

图5 人工鱼群算法寻优策略

4 仿真实例

本文拟以包含20个客户、4辆车的VRP问题为例进行仿真，部分数据如车场与客户及客户之间的行驶距离、行驶时间、各客户的需求时间窗口、各车辆的运载能力均来源于文献[25]，由于篇幅所限，在此不一一列出，其他数据如客户对货物的模糊需求量、车辆在客户处的模糊卸货时间基于假设，具体数据见表1。实例中的置信水平α和β均为0.6。

（1）实验结果。针对本文提出的VRP问题，利用Matlab进行仿真实验，仿真参数如下：模糊模拟输入样本 个 数 sample_num=400，模 糊 模 拟 次 数mod_ti mes=5 000；神经网络权值染色体种群数量popsize=100，迭代次数 AG_iter=2 000，交叉概率pos_cross=0.8，变异概率 pos_mu=0.5；人工鱼群规模popsize_fi sh=50，人工鱼视野范围visual=16，拥挤度因子δ=0.1，觅食行为反复尝试次数tr y_number=10，最优解无更新允许次数no_update_ti mes=10，人工鱼群最大迭代次数max_iter=500。

表1 各客户的模糊需求、模糊卸货时间

经过Matlab 7.0编程，得到问题的最优解为：

该最优解满足车辆能力约束和需求时间窗口约束条件，经过解码分析，共有三辆车执行任务（分别为第1、2、4辆车），其出发时间为8.332 6时、8.222 4时和8.248 3时。

对应的客户编号如下：

每辆车的客户服务数量为 number_custom= [7 7 0 6]，总行驶里程为740。

图6为经过模糊模拟5 000次，训练神经网络2 000次，人工鱼群算法500次迭代后总行驶里程的迭代示意图。

图6 总行驶里程迭代结果

（2）人工鱼群算法与其他算法的比较。针对同样的仿真数据，基于同样的种群编码格式，以同样的神经网络最优权值，在种群规模均为50，总迭代次数均为500的情况下，以本文所提算法为基础随机运行10次，与传统的遗传算法和模拟退火算法运行的结果进行比较，结果见表2。

表2 本文算法和遗传算法、模拟退火算法的比较

实验结果表明，在种群规模相同且总迭代次数一样的情况下，本文算法的最优值、平均值和均方差均要优于遗传算法和模拟退火算法，算法较遗传算法和模拟退火算法更稳定，且获得最优值所需的迭代次数较少。

5 结束语

本文考虑了一类车辆行驶时间、卸货时间和客户的需求量均为模糊变量的VRP问题，针对该问题建立了基于可信性测度的模糊机会约束规划模型，然后针对该问题提出了基于人工鱼群算法的智能优化算法，通过仿真实验证明，该算法对于解决带模糊车辆行驶时间、模糊卸货时间和模糊需求量的VRP问题是行之有效的。

[1]Yan fang Ma,Jiu ping Xu.A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows[J].Engineering optimization,2015,47(6):825-842.

[2]Lian Xue.Fuzzy simulation on the vehicle routing problem[J]. Information technology journal,2013,12(21):6 098-6 102.

[3]Mehdi Adelzadeh,Vahid Mahdavi Asl,Mehdi Koosha.A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle[J].The international journal of advanced manufacturing technology,2014,5(8):793-802.

[4]Ghannadpour S F,Noori S,Tavakkoli-Moghaddam R.Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’satisfaction in supply chain management[J]. IEEE transactions on engineering management,2013,60(4): 777-790.

[5]Kuo R J,Zulvia F E,Suryadi K.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand-A case study on garbage collection system[J].Applied mathematics and computation,2012,219(5):2 574-2 588.

[6]Cao Erbao.The open vehicle routing problem with fuzzy demands[J].Expert systems with application,2010,37(3):2 405-2 411.

[7]Chang Shi Liu,Shu Jin Zhu.Hybrid meta-heuristic approaches for vehicle routing Problem with fuzzy demands[J].Key engineering materials,2010,(439):241-246. [8]Lian Xue,Xiaoxia Dai.Research on the vehicle routing problem with fuzzy demands[A].International conference on computer-aided material and engineering[C].2011.

[9]Peng Yang,Qian Ye-mei.Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[A].International conference on management and service science[C].2010.

[10]祝崇隽,刘民,吴澄,等.针对模糊需求的VRP的两种2—OPT算法[J].电子学报,2001,(8):1-3.

[11]张建勇,李军.模糊需求VRP的一种Sweeping启发式算法[J].中国管理科学,2007,15(10):71-75.

[12]张建勇,李军.模糊车辆路径问题的一种混合遗传算法[J].管理工程学报,2005,19(2):23-26.

[13]张建勇,李军.具有模糊旅行时间的VRP的一种混合遗传算法[J].管理工程学报,2006,20(4):13-16.

[14]张建勇，李军，郭耀煌.具有模糊预约时间的VRP混合遗传算法[J].管理科学学报,2005,8(6):64-70.

[15]曹二保,赖明勇,李董辉.基于混合差分进化算法的模糊需求车辆路径问题[J].系统工程理论与实践,2009,29(2):106-113.

[16]陈宝文,宋申民,陈兴林.模糊需求车辆路径问题及其启发式蚁群算法[J].计算机应用,2006,26(11):2 639-2 642.

[17]崔雪立,朱道利,马良.模糊约定时间车辆路径问题及其蚂蚁算法求解[J].系统工程学报,2009,24(8):489-493.

[18]王君,李波.基于多目标优化的模糊需求VRPTW动态管理[J].管理学报,2013,(2):238-243.

[19]王连锋,宋建社,曹继平等.带硬时间窗模糊车辆路径问题的多目标优化[J].计算机工程,2013,(4)9-13.

[20]李晓磊.一种新型的智能优化方法—人工鱼群算法[D].杭州:浙江大学,2003.

[21]覃磊,周康.基于改进的人工鱼群算法的车辆优化调度[J].微电子学与计算机,2015,32(6):50-53.

[22]王培崇,钱旭,周玉.求解VRP问题的混合鱼群遗传优化算法[J].计算机工程与应用,2009,45(24):201-203.

[23]柳毅.求解模糊需求可回程取货车辆路径问题的改进人工鱼群算法[J].模式识别与人工智能,2010,23(8):560-564.

[24]郭海湘,刘嫣然,等.煤矿物资配送车辆路径问题的人工鱼群算法[J].系统管理学报，2012,21(5):341-351.

[25]刘宝碇,赵瑞清,王纲.不确定规划及应用[M].北京:清华大学出版社,2003.

[26]朱颢,唐万生.加工时间为连续随机变量的JobShop调度问题[J].系统工程与电子技术,2007,29(5):759-763.

App lication of Artificial Fish Swarm A lgorithm in Fuzzy VRP

Zhu Hao
(Huzhou Vocational&TechnicalCollege,Huzhou 313000,China)

In this paper,in view of a type of VRP simultaneously with fuzzy traveling time,fuzzy discharging time and fuzzy demand,we built a fuzzy chance-constrained programming model based on credibility measurement and designed the hybrid intelligent algorithm based on fuzzy simulation,neural network and artificial fish swarm algorithm for its solution.Then we developed specifically the artificial fish recovery strategy,behavior strategy and optimization strategy for the optimization process using the artificial fish swarming algorithm.At the end,throughasimulationexperiment,wedemonstrated thevalidityof thealgorithm in solving this typeof fuzzy VRPs.

fuzzy VRP;artificial fish swarm algorithm;fuzzysimulation;neuralnetwork

F224.0;F252.14

A

1005-152X(2017)05-0064-08

10.3969/j.issn.1005-152X.2017.05.017

2017-03-31

湖州市自然科学基金（2015YZ07）

朱颢（1980-），男，讲师，硕士，研究方向：车辆路径问题。