物流运输调度问题国外一般称为车辆路径规划问题(VRP,Vehicle Routing Problem)，该问题是组合优化领域中的著名NP难题，是一种相当广泛使用价值的学术研究课题。文献[1]提出了一种协作并行元启发式算法求解车辆路径问题，该算法由多个并行禁忌搜索线程组成，并通过公共解决方案池交换异步交换各自找到的最佳解决方案;文献[2]提出了一种混合元启发式算法，将和声搜索与模拟退火算法相结合，在和声搜索算法中使用模拟退火算法来挖掘搜索空间，进一步改进和声搜索算法生成的解;文献[3]提出了一种改进蚁群算法，求解带软时间窗多车场多车型车辆路径问题;文献[4]以离散蝙蝠算法为核心，并将泰森多边形、向量比较机制、近邻策略和有限配送策略相结合，求解多车场车辆路径问题。

和声搜索算法(HS,Harmony Search)[5,6]是2001年由Geem Z W等人提出的一种新颖的元启发算法，其灵感起源于音乐创作;文献[7]将混合蛙跳算法的族群内部局部寻优模块嵌入和声搜索的算法框架中，将和声搜索算法的随机性与混合蛙跳算法的导向性相耦合;文献[8]研究了在不对称区间下，即兴创作过程的探索能力与和声搜索算法各个参数的关系，证明了算法迭代收敛的充分条件，并且提出了一种修正和声算法;文献[9]提出一种高斯全局最优和声搜索(GGHS,Gaussian Global-best Harmony Search)算法，该算法采用高斯分布函数改进和声搜索算法的音调微调规则，并根据当前迭代的次数，以及和声记忆库中每个变量的最大值与最小值，动态地调整音调微调带宽和高斯分布函数中的标准差;文献[10]利用了改进的和声搜索算法优化快递配送路径。针对多仓库问题，首先使用聚类分析将多仓库问题转换为多个单仓库问题，并将人工鱼群算法的觅食行为引入和声搜索算法，同时采用自适应策略动态调整和声搜索算法的音调微调概率和音调微调带宽。仿真结果表明:相对于基本和声搜索算法，所设计的算法具有更好的收敛速度和收敛精度。

1 模型描述

多仓库流程生产物流运输调度问题可描述为:M个仓库需要为N条生产线提供原材料配送服务，每条生产线的原材料需求量为wi(i=1,2,3，…，N)，每个仓库有Km辆车(m=1,2，…，M)，每辆车的最大载重为Wkm(k=1,2，…，Km;m=1,2，…，M)，生产线i到生产线j的距离为dmij，特别地，dm0j(或dmj0)表示仓库m到生产线j的距离。定义如下变量:

特别地，x0jmk=1表示仓库m的车辆k由仓库m出发驶向生产线j,xi0mk=1表示仓库m的车辆k由生产线i出发驶回仓库m，则多仓库的车辆同时由生产线i驶向生产线j的路线距离之和最短记为Dmin。

建立数学模型如下:

式(3)为多仓库流程生产物流运输调度问题的目标函数，式(4)、式(5)表示封闭式车辆路径规划，式(6)～式(8)表示每条生产线有且仅有一辆车完成该生产线的配送任务，式(9)、式(10)表示每辆车的容量和路程限制，式(11)表示仓库m参与运输的运输车辆总数不超过该仓库所拥有的运输车辆总数。

2 聚类分析

所研究的多仓库流程生产物流运输调度问题中，运输车辆需要从M个原材料仓库出发，为N条生产线配送原材料。对于此问题，若做归一化处理，则会导致求解时间过长。因此根据各条生产线与各原材料仓库的相对位置关系进行聚类划分，以M个原材料仓库为中心，将仓库和生产线所处区域划分为M个独立的区域，各个原材料仓库负责为不同的生产线提供原材料配送服务，这样便可以提高整个流程生产企业的原材料运输效率。仓库与生产线之间的联系因素称之为亲密度(DOI,Degree Of Intimacy)，仓库为亲密度高的生产线提供原材料配送服务。α为里程加权系数，β为载重加权系数，Mm表示已分配给仓库m的生产线数量，wn表示生产线n的原材料需求量(t)。

式(17)表示仓库与生产线之间的相对欧氏距离，式中xm、ym表示仓库m的坐标;xn、yn表示生产线n的坐标;式(18)为亲密度DOI公式，易知，仓库与生产线之间距离越短、生产线原材料需求量越小，仓库与生产线之间的亲密度越高。

聚类实现步骤如下:

Step 1:计算仓库与生产线之间的相对欧氏距离dmn,m∈M,n∈N;

Step 2:计算亲密度DOI(m,n),m∈M,n∈N;

Step 3:按照DOI(m,n)由大到小的顺序将生产线分配到各个仓库，分配时需要先验证配送车辆运输里程限制和载重限制是否满足，若满足则进行下一次分配，否则重新进行分配;

Step 4:判断是否所有的生产线均已分配到仓库，若已分配完毕则聚类到此结束，否则转Step 3。

3 基于人工鱼群算法的和声搜索算法

3.1 和声搜索算法

3.1.1 基本变量

和声记忆库大小(HMS,Harmony Memory Size):指和声记忆库中所存储和声的数量。

1)记忆库取值概率(HMCR,Harmony Memory Considering Rate):每一次迭代都有一定的概率从和声记忆库中取一组和声作为新的和声，这里的概率指的是记忆库取值概率。记忆库取值概率的值影响着算法寻优的速度和全局寻优的能力。

2)微调概率(PAR,Pitch Adjusting Rate):当在和声记忆库中选取一组和声后，会以一定概率对所选的和声进行微调，这个概率就是微调概率。微调概率的值影响着算法的全局搜索能力，若参数PAR值太小，则使得算法寻优范围减小，而PAR值太大，则使得搜索算法变成随机选择方法。

3)音调微调带宽bw:指从记忆库中取出的一组和声并且进行微调时的调整幅度。

4)创作的次数Tmax:即演奏家需要创作的次数，也就是整个调整过程需要重复的次数。

根据相关研究[10]，在和声搜索算法中，HM-CR可取0.70～0.95,PAR可取0.20～0.50,HMS值可取10～50。

3.1.2 和声搜索算法步骤

Step 1:初始化优化问题，并确定和声搜索算法基本参数:和声记忆库的大小HMS，记忆库取值概率HMCR，微调概率PAR，音调微调带宽bw以及创作的次数Tmax。

Step 2:随机初始化和声记忆库。随机生成HMS个决策变量值，并计算相应目标函数的值，从而组成如下所示的和声记忆库HM:

Step 3:构造新的和声X'=[x1',x2'，…，xN']。新的和声通过三种方式产生:(1)由和声记忆库随机产生，(2)音调微调，(3)随机选择，其产生过程可表示为:

其中，rand(0,1)是在0和1之间的均匀分布的随机变量值，xi,min、xi,max分别是决策变量xi的最小值和最大值。

若新的和声来自和声记忆库HM，则需要根据微调概率来判断每个决策变量是否需要应用微调规则，其过程表示为:

Step 4:更新和声记忆库。如果根据Step 3得到一组新和声所对应的目标函数值比HM中最差和声的目标函数值要好，则用新和声替换最差和声，得到更新后的和声记忆库。

Step 5:重复Step 3和Step 4，直到终止条件满足为止。终止条件一般设置为，给定迭代次数，或者达到一个特定的目标函数值，或者是在一定的迭代次数内目标函数值没有改变。采用给定迭代次数作为终止条件。

3.2 人工鱼群算法

在一片水域中，食物丰富的地方往往能够吸引更多的鱼类向该位置移动。鱼在水中游动，不断地寻找食物丰富的区域，这一过程与智能寻优算法的求解过程十分相似。人工鱼群算法(AF-SA,Artificial Fish Swarm Algorithm)的基本思想是通过模拟鱼群在水中的各种行为(包括觅食、随机游动等)，不断更新每条鱼的位置，从而逐步优化目标问题[11,12]。

在人工鱼群算法中，用一个n维向量Xi=(x1,x2，…，xn)表征第i条人工鱼个体所在的位置。各条人工鱼所在位置附近的食物浓度Yi可以用待优化问题的适应度值表示，即Yi=f(Xi)。人工鱼能够观察的视野半径用visual表示。第i条人工鱼和第j条人工鱼之间的相对欧式距离用表示。每条人工鱼一次游动所能前进的最大距离用range表示。人工鱼附近的拥挤度阈值设置为δ。

1)觅食行为。

设某人工鱼的当前位置为Xi，在它的视野半径内(dij<visual)存在一位置Xj，如式(19)。在求最小值问题时，若Yj<Yi，那么该人工鱼向Xj的方向，以不超过其单次前进最大距离的步长游动一次，游动后位置为Xi/next;反之需要重新生成位置Xj。如果在反复尝试try＿number次后仍然不满足前进条件，则该人工鱼随机游动一次。上述过程如式(20)。

2)随机游行为。

随机游行为是指人工鱼在其视野半径内，不确定方向地随机游动，游动后的位置如式(21)。

3)聚群行为。

鱼类在水中生活，为了抵挡天敌，基本都是以群体形式出现，这就是聚群行为。设当前人工鱼的视野半径内的人工鱼数目为nf，这些人工鱼的中心位置为Xc。如果中心位置的拥挤程度YCnf/Yi小于拥挤度阈值δ，则该人工鱼向Xc方向移动，反之人工鱼将执行觅食行为。

4)追尾行为。

设当前人工鱼的视野半径内食物浓度最大的位置为Xmax，如果Ymaxnf/Yi小于拥挤度阈值δ，则该人工鱼向Xmax方向移动，反之人工鱼将执行觅食行为。

在人工鱼群算法寻优时，通过模拟上述4种行为，并在计算执行各行为的结果后，选择结果最好的行为作为人工鱼下一步将要执行的行为。AFSA的具体步骤如下:

Step 1:初始化人工鱼群算法，设置算法的参数，并随机为各条人工鱼设定位置;

Step 2:计算每条人工鱼所处位置的食物浓度，并记录当前最优人工鱼的位置信息，将其赋值给公告板(公告板用于记录最优人工鱼的位置信息);

Step 3:模拟上述四种行为并进行比较，选择结果最好的行为作为人工鱼下一步将要执行的行为;

Step 4:执行Step 3选择的行为，计算每条人工鱼游动后的位置;

Step 5:将当前最优人工鱼的位置赋值给公告板;

Step 6:判断是否满足终止条件，若满足则输出当前公告板的信息，否则转Step 2。

3.3 自适应过程

为了提高和声搜索算法的收敛速度和全局搜索能力，将自适应思想应用到和声搜索算法，动态调整音调微调概率PAR和音调微调带宽bw。

1)音调微调概率自适应策略。

基本和声搜索算法中，音调微调概率PAR的值在算法的迭代过程中是固定的。事实上，在算法前期需要增强算法的局部搜索能力，后期需要提高和声记忆库的和声多样性，因此，音调微调概率需要由小到大变化[13]。采用式(24)对音调微调概率进行动态调整。

式中，PARmin、PARmax分别为音调微调概率的最小值和最大值，gn为算法当前迭代的次数。

2)音调微调带宽自适应策略。

音调微调带宽的自适应策略是为了使算法在前期容易跳出局部最优，同时提高后期的局部精细搜索能力，因此音调微调带宽需要由大到小变化[14,15]。采用式(25)对音调微调带宽进行动态调整。

式中，bw0表示音调微调初始带宽，bwnew表示新的音调微调带宽，gn为算法当前迭代的次数，Tmax为创作次数。

3.4 算法步骤

结合第3.2节对人工鱼群算法的介绍，在基本和声搜索算法中引入人工鱼群算法的觅食行为，改进基本和声搜索算法的随机产生规则，整个融合算法的详细步骤如下:

Step 1:初始化算法参数，包括和声记忆库大小HMS、记忆库取值概率HMCR、微调概率最小值PARmin、微调概率最大值PARmax、音调微调初始带宽bw0和创作次数Tmax，人工鱼的视野范围visual、单次游动最大距离range、尝试次数try＿number，并将算法迭代次数gn置0;

Step 2:初始化和声记忆库，并计算每个和声的适应度值，采用原材料配送车辆的行驶总路径作为适应度值的倒数，总路径越短，适应度值越大，表示和声的适应度越好;

Step 3:生成新和声;

Step 3-1:生成(0,1)之间的随机数rand(0,1)，若rand(0,1)<HMCR，则从和声记忆库HM随机挑选一组和声，记为Xnew，转Step 3-3;否则转Step 3-2;

Step 3-2:取HM中最优和声Xg作为人工鱼群算法中的一条人工鱼的位置，按照式(19)生成新的位置Xj，并比较位置Xg和位置Xj的目标函数值，如果位置Xj的目标函数值优于位置Xg，则人工鱼向位置Xj的方向，以不超过其单次前进最大距离的步长游动一次，游动后位置为Xnew;反之需要重新生成位置Xj。如果在反复尝试try＿number次后仍然不满足前进条件，则该人工鱼随机游动一次，游动后的位置赋值给Xnew，转Step 4;

Step 3-3:生成(0,1)之间的随机数rand(0,1)，若rand(0,1)<PAR(其中PAR由式(24)计算所得)，按照式(15)对Xnew进行微调，其中音调微调带宽由式(25)计算所得;否则Xnew不改变;

Step 4:更新和声记忆库。计算新和声Xnew的适应度值，若优于和声记忆库中的最差和声，则使用Xnew替换和声记忆库中的最差和声，否则，和声记忆库保持不变;

Step 5:将迭代次数gn加1，判断gn是否等于最大创作次数Tmax，若不等则返回Step 3，否则转Step 6;

Step 6:输出适应度最好(即适应度值最大)的和声并输出其对应的适应度值。

4 实验与分析

4.1 实验数据

假设有A、B、C三个仓库，每个仓库有3辆运输车辆。三个仓库共同为编号为1～20的20个生产线配送原材料。生产线和仓库坐标随机产生，仓库坐标{(x,y)|(0,0),(4,6),(7,8)}，生产线坐标{(x,y)|(5,4),(7,5),(8,10),(6,10),(4,9),(5,10),(6,6),(2,1),(1,7),(7,10),(1,5),(0,4),(4,3),(8,12),(1,3),(3,10),(8,6),(5,6),(2,2),(3,4)}。各生产线所需的原料量、卸货时间如表1所示。设定每个仓库均拥有3辆运输车辆，每辆车单次最大里程限制为15 km，每次最大载重量为10 t。

表1 各生产线原料需求量与卸货时间  

和声搜索算法参数设置为:HMS=20,HM-CR=0.8,PARmin=0.2,PARmax=0.5,Tmax=500，初始bw=0.8;人工鱼群算法参数设置为:Step=1,Visual=3,try＿number=5。

4.2 实验结果与分析

根据第2节的聚类方法，可以将A、B、C三个仓库和生产线位置进行聚类，得到的聚类分析结果如图1所示。仓库A为编号为8、9、11、12、15和19的生产线提供原材料配送服务;仓库B为编号为1、5、6、13、16、18和20的生产线提供原材料配送服务;仓库C为编号为2、3、4、7、10、14和17的生产线提供原材料配送服务。通过该聚类方法，将多仓库流程生产物流运输调度问题转化为多个单仓库流程生产物流运输调度问题。

图1 多仓库聚类分析图   

算法运行20次，仿真结果与基本和声搜索算法及其他三种常见启发式算法的对比如表2所示，最优配送线路如表3所示，最优配送轨迹图如图2所示。

表2 算法结果对比

表3 最优配送线路  

算法在经过多次迭代后，最终收敛，得到最优配送路径，配送车辆行驶路径总长度为62.04km。同时，通过与基本和声搜索算法对比可知，所提出的基于人工鱼群算法的和声搜索算法不仅提高了基本和声搜索算法的收敛速度，而且有效地提升了基本和声搜索算法的搜索精度，并且结果也优于其他3种常见启发式算法。因此可知，所提出的基于人工鱼群算法的和声搜索算法能够有效的求解多仓库流程生产物流运输调度问题。

图2 最优配送轨迹图 

5 结语

针对多仓库问题，首先使用聚类分析将多仓库问题转换为多个单仓库问题，并将人工鱼群算法的觅食行为引入和声搜索算法，同时采用自适应策略动态调整和声搜索算法的音调微调概率和音调微调带宽。仿真结果表明:相对于基本和声搜索算法，所设计的算法具有更好的收敛速度和收敛精度。