文档介绍：该【禁忌搜索算法 】是由【小s】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【禁忌搜索算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。无时限单向配送车辆优化调度问题的禁忌搜索算法
无时限单向配送车辆优化调度问题,是指在制定配送路线时不考虑客户对货物送到(或
取走)时间要求的纯送货(或纯取货)车辆调度问题。
无时限单向配送车辆优化调度问题可以描述为:从某配送中心用多台配送车辆向多个客
户送货,每个客户的位置和需求量一定,每台配送车辆的载重量一定,其一次配送的最大行
驶距离一定,要求合理安排车辆配送路线,使目标函数得到优化,并满足一下条件:
(1)每条配送路径上各客户的需求量之和不超过配送车辆的载重量;
(2)每条配送路径的长度不超过配送车辆一次配送的最大行驶距离;
(3)每个客户的需求必须满足,且只能由一台配送车辆送货。
一、禁忌搜索算法的原理
禁忌搜索算法是解决组合优化问题的一种优化方法。该算法是局部搜索算法的推广,其
特点是采用禁忌技术,即用一个禁忌表记录下已经到达过的局部最优点,在下一次搜索中,
利用禁忌中的表信息不再或有选择地搜索这些点,以此来挑出局部最优点。
在禁忌搜索算法中,首先按照随机方法产生一个初始解作为当前解,然后在当前解的领
域中搜索若干个解,取其中的最优解作为新的当前解。为了避免陷入局部最优解,这种优化
方法允许一定的下山操作(使解的质量变差)。另外,为了避免对已搜索过的局部最优解的
重复,禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息,这可在一定程度上使
搜索过程避开局部极值点,从而开辟新的搜索区域。
二、算法要素的设计
禁忌对象是指禁忌中表被禁的那些变化元素。由于解状态的变化可以分为解的简单变化、
解向量分量的变化和目标值变化三种情况,则在确定禁忌对象时也有相对应的三种禁忌情况。
一般来说,对解的简单变化进行禁忌比另两种的受禁范围要小,因此可能早能造成计算
时间的增加,但其优点是提供了较大的搜索范围。
根据配送车辆优化调度问题的特点,可采用对解的简单变化进行禁忌的方法。举例进行
说明:当解从x变化到y时,y可能是局部最优解,为了避开局部最优解,禁忌y这一解再
度出现,可采用如下禁忌规则:当y的领域中有比它更优的解时,选择更优的解;当y为其
领域的局部最优解时,不再选y,而选比y稍差的解。
禁忌长度是指被禁对象不允许被选取的迭代步数,一般是给被禁忌对象x一个数l(称
为禁忌长度),要求x在l步迭代内被禁,在禁忌中采用表Tabu(x)=l记忆,每迭代一步,该
指标做运算Tabu(x)=l-1,直到Tabu(x)=0时解禁。关于禁忌长度l的选取,可归纳为以下几种
情况。
(1)l为常数,可取l=10、l=n(n为领域中邻居的总个数)。这种规则容易在算法中
实现。
(),l。此时,l是可以变化的数,其变化的依据是被禁对象的目标函数值
2l∈lminmax
和领域的结构。、是确定的数,确定的常用方法是根据问题的规模,限定变化区
lminlmaxN
间aN,bN(0<ᵄ<ᵄ);也可以用领域中邻居的个数n确定变化区间an,bn(0<ᵄ<
ᵄ)。
禁忌长度的选取同实际问题和算法设计者的经验有紧密联系,同时它也会影响计算的复
杂性,过短会造成循环的出现,过长又会造成计算时间的增加。
候选集合由领域中的邻居组成,常规的方法是从领域中选择若干个目标函数值或评价值
最佳的邻居。
由于上述常规方法的计算量太大,一般不在领域的所有邻居中选择,而是在领域中的一
部分邻居中选择若干个目标值或评价值最佳的解;也可以采用随机选取的方法实现部分邻居
的选取。
利用禁忌搜索算法求解无时限单向配送车辆优化调度问题时,算法的终止准则可采用迭
代一定步数终止的准则、频率控制准则、目标值变化控制等准则。除以上准则外,还可以采
用下述的目标值偏离程度终止准则:记一个问题目标函数值的下界为,目标值为,
ZLBf(x)
对给定的充分小的正数,当≤e时,终止计算,这表示目前计算得到的解与最
efx−ZLB
优解已经非常接。近
实例1某配送中心有2台配送车辆,其载重量均为8t,车辆每次配送的最大行驶距离均为
,配送中心(编号为)与个客户之间及个客户相互之间的距离、个客户的货
50km088dij8
物需求量(、,,…,8)均如表所示。要求根据以上条件合理安排车辆配送路线,
qjij=121
是配送总里程最短。
表1实例1的已知条件表
i
d
012345678
j
q(t)—12121422
j
实例2设配送中心和20个客户分布在一个边长为20km的正方形地域内,每个客户的货物
需求量都在2t及其以下,配送中心有5台配送车辆,车辆的最大载重量均为8t,车辆一次
配送的最大行驶距离均为50km。现利用计算机随机产生了配送中心和20个客户的位置坐标
以及各客户的货物需求量,其中配送中心的坐标为(,),20个客户的坐标及
,使配送总里程最短。
表2实例2的已知条件表
客户编号**********
横坐标x(km)
纵坐标y(km)
货物需求量
q(t)
客户编号11121314151617181920
横坐标x(km)
纵坐标y(km)
货物需求量
q(t)
实例3设配送中心和100个客户分布在一个边长为20km的正方形地域内,每个客户的货
物需求量都在2t及其以下,配送中心有20台配送车辆,其中10台车辆的最大载重量均为
8t,车辆一次配送的最大行驶距离均为50km;另10台车辆的最大载重量均为10t,车辆一
次配送的最大行驶距离均为60km。现用计算机随机产生了配送中心和100个客户的位置坐
标及各客户的货物需求量,设配送中心的坐标为(,),100个客户的坐标及
其货物需求量已知(没列出来)。要求合理安排配送车辆的行车路线,使配送车辆的总吨位
公里数最少。
三、实验计算和结果分析
对实例1、实例2和实例3各项参数的设置如表3-1所示。
每次迭代共
不可行路径
迭代步数搜索当前解禁忌长度
的惩罚权重
的邻居个数
实例1100km50205
实例2300km4004010
实例312000t·km40020020
四、算法策略和运行参数对禁忌搜索算法性能的影响
在禁忌搜索算法中,禁忌长度是一个非常重要的运行参数。为了分析禁忌长度对算法性
能的影响,在其他策略与运行参数不变的前提下,分别取禁忌长度为:2、5、10、15、20
和30,并分别对实例2随机求解10次,.
配送总里程的平首次搜索到最终解
禁忌长度平均使用的车辆数平均计算时间
均值(km)的平均迭代步数
由表可见,用禁忌搜索算法求解无时限单项配送车辆优化调度问题时,禁忌长度对算法
性能的影响总体上不太明显,但过短的不利于取得较好的计算结果,而过长的禁忌长度尽
管会带来计算时间的增加,却不一定能提高算法的寻优结果。
用禁忌搜索算法求解无时限单向配送车辆优化调度问题时,其搜索次数为迭代步数T
与每次迭代搜索当前解的邻居的个数N的乘积,则在搜索次数一定的前提下,可以采用T
较大N较小的迭代搜索方案,也可以采用N较大T较小的方案。为了分析迭代搜索方案对
禁忌搜索算法性能的影响,在其他算法策略与运行参数保持不变的前提下,分别采用以下迭
代方案对实例2进行计算:(1)T=1600,N=10;(2)T=800,N=20;(3)T=400,N=40(4)
T=200,N=80,(5)T=100,N=160,用上述迭代搜索方案分别对实例2随机求解10次,得
.
次搜索到首最终解的平均搜
迭代搜索策略配送总里程平均值(km)平均使用车辆数
索次数
T=1600,N=
T=800,N=
T=200,N=
T=200,N=
T=100,N=
由表可见,用禁忌搜索算法求解无时限单项配送车辆优化调度问题时,不同的迭代搜索
策略对算法的寻优性能有一定的影响,在总搜索次数一定的前提下,每次迭代搜索当前解的
邻居的个数N过小货过大都不利于取得好的计算结果,对于实例2来说,当总的搜索次数
为16000且N取20—40时,即可取得很好的计算结果。
为了分析邻域选点策略对禁忌搜索算法性能的影响,设计无时限单项配送车辆优化调度
问题的基于逆转邻域选点策略的禁忌搜索算法。设在该算法其他算策略和运行参数不变的前
提下,利用该算法对实例2随机求解10次,。为了便于比较,将
。
次搜索到首最终
邻域选点策配送总里程平均值
平均使用车辆数解的平均迭代步平均计算时间
略(km)
数
由表可见,用禁忌搜索算法求解无时限单项配送车辆优化调度问题时,邻域选点策略对
对算法性能的影响总体上不太明显。在各种邻域选点策略中,由于两交换法的操作最简单,
计算效率也较高,因而,在禁忌搜索算法中一般采用两交换法实施邻域操作。