改进的和声搜索算法求解带时间窗的物流运输调度问题

广东工业大学自动化学院 李旭阳 蔡延光

针对带时间窗的物流运输调度问题，设计一种改进的和声搜索算法。该算法利用类电磁机制算法改进和声搜索的随机产生规则，并且使用了和声记忆库扰动策略和2-Opt局部搜索策略提高算法性能。结果表明：相比基本和声搜索算法及其他启发式算法，所设计的算法具有更好的收敛速度和收敛精度。

物流运输调度问题国外一般称为车辆路径规划问题（Vehicle Routing Problem，VRP），该问题自提出以来就一直是研究的热点。戚远航等提出了一种双层变邻域蝙蝠算法求解带容量约束的物流问题，该算法采用变邻域局部搜索策略加强算法的寻优能力，很好的解决了带容量约束的物流运输调度问题；邓丽娟等提出了一种混合蚁群算法求解带时间窗的VRP，该算法探索两个目标函数，获得了很好的实验效果；蔡延光等提出了一种带遗传算子的自适应蚁群算法，求解带软时间窗的车辆路径问题。

2001年Geem ZW等人源于音乐的创作，提出了和声搜索（Harmony Search，HS）算法，一种新的元启发算法；高立群等把粒子群算法与和声搜索算法相结合，提出自适应和声粒子群搜索算法；欧阳海滨等研究了在非对称区间内，证明了和声搜索算法的参数与即兴创作过程的探索之间的关系，从而证明了算法的迭代收敛性，提出了一种改进的和声搜索算法；王艳等采用改进的和声搜索算法，用一种离散编码方式，解决了车间调度问题。本文针对带时间窗的物流运输调度问题，设计了改进的和声搜索算法。该算法利用类电磁机制算法改进和声搜索算法的随机生成的规则，并且使用了和声记忆库扰动策略和2-Opt局部搜索策略提高算法性能。实验结果表明：该算法比基本和声搜索算法有更好的收敛速度和精度。

1 问题描述

带时间窗物流运输调度(Vehicle Routing Problem with Time Windows，VRPTW)问题可描述为：某车场需要为N个客户提供货物配送服务，并要求在[Ei,Li]所表示的时间窗内将货物送达，其中Ei表示客户i要求的最早货物到达时间，Li表示客户i要求的最晚货物到达时间。若未按时送达则增加相应的时间惩罚成本，用C1（单位：元/min）表示早到的惩罚系数，C2（单位：元/ min）表示晚到的惩罚系数；tik表示车辆k到达客户i的实际时间；UTik表示运输车辆k在客户i卸货所需的时间；RTijk表示运输车辆k从客户i行驶到客户j所需的时间；每条客户的货物需求量为qi(i=1,2,3,...N)，该仓库有K辆车且车型相同，车的最大载重为W，客户i到客户j的距离为dij，其中i=0表示仓库，定义决策变量：，当k经过客户i驶向客户j时为1，否则为0，；，当客户i由车辆满足时为1，否则为0。并建立数学模型如下：

目标函数：

约束条件：

式(1)为VRPTW的目标函数，式(2)(3)表示封闭式的车辆路径规划，式(4)(5)(6)表示每条客户仅要一辆车完成任务，式(7)(8)表示车的最大容量和行驶限制，式(9)表示参与任务的车辆数不能超过车场所拥有的车辆总数，式(10)(11)表示保证运输车辆在配送货物在时时间上的连续性，避免时间冲突。

2 算法设计

2.1 和声搜索算法

2.1.1 基本变量

（1）和声记忆库大小HMS：指和声记忆库中和声的数量。

（2）记忆库取值概率HMCR：在每次迭代中，有一组和声将从库中被选择为一个新和声的特定概率。

（3）微调概率PAR：选择一组和声需要用微调概率判断是否要微调。如果PAR值过小，算法的优化范围减小，而PAR值过大，搜索算法会变成随机选择。

（4）音调微调带宽 bw：指微调时的调整幅度。

（5）创作的次数 Tmax：即算法的迭代次数。

根据相关研究，算法参数为HMS值可取10～50，HMCR可取0.70～0.95，PAR可取0.20～0.50。

2.1.2 和声搜索算法步骤

Step 1：初始化算法，指定和声搜索算法各项基本参数：HMS、HMCR、PAR、bw、Tmax。

Step 2：根据HMS生成和声记忆库，并计算目标函数的值，组成如下所示的和声记忆库HM：Step 3：产生新的和声X'=[x'1,x'

2,...,x'N]。新的和声通过三种方式生成：①由HM随机产生。②音调微调。③随机选择，其生成过程可表示为：

IF rand(0,1)

ELSE

END IF

其中，rand(0,1)是在0和1之间的随机变量值，xi,min,xi,max分别是决策变量xi的最小、最大值。若新的和声来自和声记忆库HM，则用微调概率来判断是否要微调规则：

Step 4：更新记忆库。若Step3得到的一组新的和声比HM中最差和声要好，则用新和声替换最差和声。

Step 5：重复Step3和Step4，直到满足最大迭代次数Tmax。

2.2 类电磁机制算法

在物理学中，带电粒子之间存在着相互吸引或相互排斥的库仑力。Birbil和Fang受到这一现象的启发，于2003年提出了类电磁机制（Electromagnetism-like Mechanism，EM）算法，并且用该算法成功解决了无约束优化问题。

EM算法将待优化问题的每个解模拟为电磁场中的带电粒子，并根据解的适合度来确定每个粒子的电荷。每个带电粒子会被其他粒子吸引或排斥，这取决于它们所携带的电荷和它们之间的距离。根据粒子受到的合力的大小，粒子会沿着合力的方向移动一定的距离。由于算法是对电磁原理的一种类比，两者之间并不完全相同，因此称为类电磁机制。

EM算法主要由以下四个步骤组成：

（1）初始化。将一定数量的粒子随机、均匀地分布在待优化问题的可行解域里，然后计算出每个粒子所在位置的适应度值，并将适应度最好的粒子的位置记为Xbest。

（2）局部搜索。EM算法中的局部搜索是指以粒子当前的位置为中心，按照一定的步长搜索解空间的每个维度。如果找到了更好的解决方案，搜索将被终止，并执行下一步。

（3）计算合力。计算合力是为了将EM算法的局部搜索能力和全局搜索能力相结合，提高算法的求解能力，并为下一步更新粒子位置提供相应的信息。

粒子i所带电荷量的多少qi决定了粒子i所受的库伦力的大小，电荷量qi的计算公式为：

式中，n为待优化问题的维度，m为解空间中带电粒子的个数。由式(16)可知，适应度越好的粒子所带的电荷数越大，对其他带电粒子的吸引或排斥能力也就越强。一个粒子受另一个粒子的库仑力的方向由两个粒子的适应度好坏决定。在计算粒子i受到解空间中其他每个粒子的力的大小和方向后，即可通过累加方法得到作用在粒子i上的合力Fi：

（4）移动粒子

计算完合力Fi之后，粒子i将沿着Fi的方向移动，移动后粒子i的位置为：

式中，步长λ在[0,1]上服从矩形分布；Range为一个向量，向量中的每一个分量表示粒子在解空间的对应维度上能够移动的距离。同时，为了保证每个粒子移动后的位置不会超出解空间的范围，EM算法对粒子所受的合力做了无量纲化处理。

这样，粒子的位置得到更新，也就完成了EM算法的一次迭代。

2.3 和声记忆库扰动策略

当和声搜索算法运算一定的次数后，和声记忆库中的和声多样性水平降低，甚至出现大部分和声的适应度都相等的情形。此时，算法将会限入局部最优解。这个时候如果能够对和声记忆库中的一部分和声进行扰动，以提高和声记忆库的和声多样性水平，将会有利于算法跳出局部最优解继续寻优，从而增加得到全局最优解的概率。

2.3.1 扰动时机

和声记忆库的扰动需要在算法迭代至一定次数，且和声记忆库中的和声相似程度达到一定阈值时进行。设和声记忆库大小为HMS，算法最大迭代次数为Tmax，当前迭代次数为gn，则进行和声记忆库扰动的时机需要同时满足如下两个条件：

②和声记忆库连续t次迭代未更新：

2.3.2 扰动步骤

当满足扰动时机时，扰动步骤如下：

Step1：对HM中的和声按照适应度值排序，随机选取(HMS/2)组非最优和声；

Step2：对Step1中选择的(HMS/2)组非最优和声进行混沌扰动；

Step3：计算生成的新和声的适应度值，若优于和声记忆库中的最差和声，则用新和声替换最差和声，更新和声记忆库；否则需要重新扰动。

2.4 局部搜索策略

在求解物流运输调度问题时，常用的局部搜索算法主要有2-Opt搜索，0-1搜索和1-1搜索等算法。本文采用2-Opt方法进行局部搜索。一次2-Opt操作可描述为：在一条路径中随机选择两个点i和j，将i-1与j连接，i与j+1连接，并将i和j之间的路径反向，若2-Opt操作后的路径长度比操作之前的长度小，则更新路径。2-Opt操作示意如图1所示。

图1 2-Opt操作示意图

2.5 编码策略

为实现VRPTW路线的解空间和和声搜索算法的搜索空间的解空间之间的转换，本文采用序列号编码方案。对于n个客户，k辆车的车辆路径规划问题，采用个n+k-1个的整数来编码，编码中的n位表示客户，k-1位为车辆号，0表示配送中心。例如对于10个客户，3辆车的车辆路径规划问题，有如下编码：3，10，9，11，5，8，7，2，12，6，4，1，其中11和12为车辆标识编码，该编码对应和声库里面的一个和声。该组编码表示第一辆车行车路径为0－3－10－9－0，第二辆车行车路径为0－5－8－7－2－0，第三辆车行车路径为0－6－4－1－0。这些编码就组成了和声记忆库，接下来就是对库中编码寻找最优解的过程。

2.6 算法步骤

将改进策略整合到基本的和声搜索算法，改进的算法的具体步骤如下：

Step1：初始化算法各项参数；生成和声记忆库，并计算每个和声的适应度值，采用车辆的行驶总路程与时间窗惩罚之和的倒数作为适应度值，适应度越大，表示和声越优。

Step2：生成新和声；

Step2-1：若生成的随机数rand(0,1)

Step2-2：以当前和声记忆库中的所有和声作为类电磁机制算法中的粒子，以HM中的最优和声作为最优粒子Xbest，根据式(16)与式(17)计算所有粒子的电荷量以及每个粒子受到的合力，并结合式(18)计算每个粒子移动后的位置，选择最优的粒子赋值给Xnew，转Step3；

Step2-3：若生成的随机数rand(0,1)

Step3：2-Opt操作，将迭代次数gn加1。对Xnew进行一次2-Opt操作，若操作后路径长度变短则更新Xnew；

Step4：更新和声记忆库。计算Xnew的适应度值，如果优于库中的最差和声，则使用Xnew替换最差和声，否则，库不变；

Step5：判断是否满足扰动条件，若满足则根据扰动策略对HM进行扰动，否则转Step6；

Step6：判断gn是否达到最大迭代次数Tmax，若没有则返回Step2，否则转Step7；

Step7：输出适应度最好的和声并输出其对应的适应度值，该和声即为最优解。

3 实验与分析

3.1 实验数据

为验证算法的有效性，假设一个配送中心需要为14个客户配送货物，客户坐标随机产生，各客户所需的货物量、时间需求如表1所示。设定车场坐标(0,0)，编号为0拥有4辆运输车辆，每次最大载重量为15t，配送中心于上午8:00开始为各客户运输，运输车辆匀速行驶，车速为2020km/h，运输车辆早到的惩罚系数为2元/min，晚到的惩罚系数为5元/min。

表1 客户坐标、需求量与时间窗

本章和声搜索算法参数设置为：HMS=20，HMCR=0.75，PAR=0.3，Tmax=200。

3.2 实验结果与分析

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

表2 结果对比

表3 最优配送线路

图2 最优配送轨迹图

由表2中的数据可知，基于类电磁机制的和声搜索算法因为引入了类电磁机制算法加快了收敛速度，并使用了和声记忆库扰动策略和2-Opt局部搜索策略能够有效的跳出局部最优解，提高了算法的局部搜索能力，所以在50次运算后，所得到的平均里程、平均搜索时间以及平均时间窗惩罚都要优于基本和声搜索算法所得到的平均结果，并且优于其他几种算法。

算法在迭代完成后，得到最优配送路径图，配送车辆行驶路径总长度为91.65km，总时间窗惩罚为143元。其中，编号为1、2和4的配送车辆所执行的配送任务中，分别出现59元、32元和52元的时间窗惩罚，而编号为3的运输车辆所执行的配送任务没有时间窗惩罚，即不存在早到和迟到的情况。由此可见，本文提出的改进的和声搜索算法能够有效地解决带时间窗的物流运输调度问题。

总结：本文设计了改进的和声搜索算法来解决带时间窗的路径规划问题，该算法通过类电磁机制算法改进和声搜索算法的随机产生规则，并且使用了和声记忆库扰动策略和2-Opt局部搜索策略提高算法的搜索能力，性能得到了提高，具有更快的收敛速度和更高的精度。本文所提的模型在很大程度上贴合了实际情况，但是车辆过少，下一步准备研究多车场下的模型，提出一种适合求解多车场下物流运输调度问题的算法。

基金项目：国家自然科学基金（61074147）；广东省自然科学基金（S2011010005059）；广东省教育部产学研结合项目（2012B091000171，2011B090400460）；广东省科技计划项目（2012B050600028，2014B010118004，2016A050502060）；广州市花都区科技计划项目（HD14ZD001）；广州市科技计划项目（201604016055）；广州市天河区科技计划项目（2018CX005）。