改进禁忌搜索算法在TSP问题中的应用

提出了一种基于改进最近邻点法的禁忌搜索算法（TSBIN）。该算法利用改进最近邻点法为禁忌搜索算法构造较优初始解,能更有效地搜索全局最优解。以旅行商问题（TSP）为倒,验证了该算法的寻优性。     

一类面向仓库车辆路径优化的改进禁忌搜索算法及其应用

在立体仓库中常需考虑车辆路径规划问题,传统的禁忌搜索算法在解决该类问题时,最终解的质量依赖于初始解。针对此问题并结合实际立体仓库,本文提出了改进的禁忌搜索算法。该算法的初始解部分由模拟退火算法生成,有效地克服了禁忌搜索算法对初值的依赖;规定禁忌搜索算法的特赦准则为模拟退火算法关联,在限定始末库位条件下,尽可能地寻找更短车辆路径,提高禁忌搜索算法的搜索能力。将改进的禁忌搜索算法与标准禁忌搜索算法进行仿真对比,改进算法在平均最短路径和稳定性上都有较大提升。将本文算法应用于立体仓库调度过程,在实际应用中效果良好,具备可行性。     

一种基于插入法的禁忌搜索算法

结合插入法和禁忌搜索算法的优点，提出了一种基于插入法的禁忌搜索算法TIS(tabu-insert search)，该算法利用禁忌搜索算法较强的局部搜索能力和插入法在构造高质量解时的优越性来进行解空间的搜索．TIS能有效地帮助搜索程序跳出局部最优解，找到全局最优或次优解．以典型的组合优化问题TSP为例，验证了该算法的有效性，计算机实验的结果表明该算法有较好的寻优能力．     

禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题

【目的】为了求解带时间窗和多配送人员的车辆路径问题,建立了该车辆路径问题的数学模型,并采用禁忌搜索算法进行求解。【方法】首先松弛车辆载重和顾客时间窗约束,在目标函数里面引入相应的惩罚成本;接着,使用贪婪算法生成初始解;最后,设计禁忌搜索算法求解该问题。在禁忌搜索中,使用了插入、删除、移动、交换等算子搜索邻域解空间,并使用扰动算子进一步加大搜索范围。为了验证禁忌搜索算法的有效性,对修改的Solomon标准测试问题进行求解,并与CPLEX的优化结果进行比较。【结果】在小规模算例求解中证实了禁忌搜索算法的准确性,在标准规模算例求解中证实了该算法的高效性。【结论】所提出的禁忌搜索算法能够有效解决带时间窗和多配送人员的车辆路径问题。     

物流管理中配送路线安排优化及其算法研究

配送路线安排是一个NP问题,因而本文将采用启发式算法,在使用节约/插入算法来构造高质量初始解的基础上,利用禁忌搜索算法和交换算法来改进初始解。通过实验数据,验证了该算法的有效性。     

基于禁忌搜索的混沌蚁群算法在SLAM数据关联中的应用

为解决SLAM的数据关联问题,提出了基于禁忌搜索的混沌蚁群算法,利用蚁群算法的正反馈和并行搜索能力构建初始解并进行优化.在全局信息素更新时加入混沌扰动,以跳出局部极值,利用禁忌搜索算法的特性,扩大解的搜索空间,得到全局最优解.在无人机SLAM仿真环境下进行试验,仿真结果表明该方法极大地提高了数据关联率,该算法是有效可行的.     

基于禁忌搜索算法的船舶舱室智能布局设计

为提高船舶舱室布置的自动化、智能化水平,建立了船舶甲板布置区域模型和包括相对位置目标、绝对位置目标及人机工程约束目标的多目标优化数学模型.在建立模型的基础上,针对船舶舱室布局优化设计的特点提出了一种基于多初始解共同进化和模拟退火算法Metropolis接受准则相结合的改进的禁忌搜索优化算法,新算法可有效减少禁忌算法对单一初始解的依赖性,加快算法的收敛.最后运用建立的优化模型和改进后的禁忌搜索算法进行了仿真实验,实验结果验证了模型的可行性和改进的禁忌搜索算法性能的优越性,可有效缩短传统的舱室布置设计周期,提高设计质量.     

有时间窗的车辆路径问题及改进禁忌搜索算法

基于改进的禁忌搜索算法求解有时间窗的车辆路径问题,建立了该问题的通用数学模型.改进算法中,在随机构造的多个可行解中挑选较好的解作为初始解,采用2-opt方法生成邻域,并构造了动态禁忌表,使禁忌表的大小和结构随搜索过程发生改变,提高了整体寻优能力.仿真实验证明了算法的可行性、有效性和优越性.     

用禁忌搜索算法求解单机总加权拖期最小问题

针对以总加权拖期最小为目标的单机调度问题,提出了一个将启发式方法与禁忌搜索算法相结合的混合禁忌搜索算法HTS（HybridTabuSearch）。利用启发式方法产生初始解,随后通过禁忌搜索算法逐步提高解的质量。大量实验结果表明,提出的混合禁忌搜索算法能够在较短的时间内得到令人满意的较优解。     

一种新的可调时间窗车辆调度问题研究

提出了一种新的时间窗可调整的车辆调度模型,设计了求解该问题的算法．设计了初始路径的构造算法、时间窗的分配以及动态调整策略和初始路径的禁忌搜索改进策略,实验计算表明,禁忌搜索算法能够显著改进初始解的质量,有效降低了运输成本,时间窗可调策略能够为顾客提供多个参考时间窗选择,增加了车辆调度的灵活性,与固定时间窗算法相比,本算法能够提高服务质量,不会产生拒绝顾客服务要求的现象．     

求解车间作业调度问题的快速禁忌搜索算法

针对车间作业调度问题的难解性，提出了一种求解该问题的快速禁忌搜索算法．该算法是按照禁忌搜索算法的一般步骤来进行设计的，在设计过程中对于算法所涉及到的初始解问题、邻域构造问题以及禁忌表长度的选取等问题给出了旨在减少算法计算时间，提高算法优度的解决方案．该算法找到了所测试的21个标准算例中18个算例的精确最优解，而且在PⅡ233的计算机上每个算例的计算时间不超过2s。     

粒子群—禁忌搜索的FMS多智能体调度

针对柔性制造系统调度问题的复杂性,提出以最小化最大完工时间为目标的多智能体调度系统,系统包含全局、工件和机器三类智能体.系统通过基于合同网协议的工件智能体和机器智能体产生初始解,然后机器智能体以初始解为基础进行局部寻优,所获得的局部最优解集由全局智能体进一步全局寻优,从而获得比一般方法更好的调度解.在进行优化模块设计时,分别引入禁忌搜索和粒子群优化作为机器智能体和全局智能体的优化算法.针对多智能体能够交互的特点,对禁忌搜索算法进行改进,提出了双禁忌表搜索算法,使得各机器智能体寻优结果更具多样化,更适合作为全局智能体优化的初始粒子群.仿真结果表明:调度系统在求解时收敛速度快、精度高,通过对10个经典柔性job-shop问题求解,所有结果均优于单独使用遗传算法和禁忌搜索算法的已知结果.     

铁路行包配送车辆路径问题模型及算法

铁路行包配送车辆路径问题属于同时具有送货和集货需求的车辆路径问题.结合该问题特点,建立数学优化模型.求解算法中采用基于最近邻居的启发式方法产生尽可能好的初始解,并通过构造合理的邻域结构,引入适合的罚函数评价解的质量,随机选取禁忌长度的禁忌搜索算法优化初始解.以5台车辆、21个配送点的实例进行仿真计算,计算结果表明,模型及算法有效可行.     

基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题

同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进; 由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.     

基于禁忌搜索的无线传感器网络多源定位研究

针对无线传感器网络多源定位容易陷入局部最优的情况,提出基于禁忌搜索的多源定位方法.通过测量多个声源发出的能量建立声音能量模型,估计出模型中的声音能量和声音位置等参数,然后使用8邻域3层格点的邻域产生方式,并合理选择禁忌表长度、初始解等禁忌算法的基本参数,有效避免了多源定位易陷入局部最优的情况.将禁忌搜索算法和多分辨率搜索算法、EM算法、AMR算法进行比较,仿真结果表明,禁忌搜索能够很好地避免局部最优,且定位精度高于其他几种算法,计算复杂度相对较低.     

一种求解带有阻塞限制的混合流水车间的禁忌搜索算法

针对带有阻塞限制的混合流水车间调度问题,提出一种禁忌搜索算法和优先级规则相结合的方法.开发了启发式调度算法求出问题初始解,应用禁忌搜索算法对工件在第一级的排序进行优化,采用优先级规则进行其他级工件的排序.实验结果表明,该方法大大缩减了搜索空间,能够较好地解决此类调度问题.     

一种融入小生境技术的遗传禁忌算法

针对遗传算法在全局优化问题中容易出现早熟和收敛速度慢,禁忌搜索强烈依赖于初始解等问题,根据遗传算法和禁忌搜索算法自身的特点,分析两者的优势和不足,提出了一种融入小生境技术的遗传禁忌算法.该算法采用融入了小生境技术的遗传算法作全局搜索,用禁忌搜索算法作局部搜索,可以加快收敛速度,同时可以抑制早熟现象,避免过早收敛到局部最优.分析和实验结果表明,该算法能很好地抑制早熟收敛,同时在计算速度和计算结果方面都有改进,是一种快速有效的优化算法.     

改进的禁忌搜索算法在梯级水库联合优化调度中的应用研究

禁忌搜索算法是模拟人的思维的一种智能搜索算法.文章在探讨梯级水库联合优化调度的禁忌搜索算法中,针对该方法对初始解依赖性强、后期迭代效率低等局限性,提出了动态规划-禁忌搜索算法在梯级水库联合优化调度中的应用.通过实际算例验证了该方法的可靠性,从而为高维梯级水库的优化调度提供了一条新的求解途径.     

最小化总完工时间的流水作业调度混合算法

针对有效求解NP难的总完工时间最小流水作业调度问题,提出了一个有效的混合启发式算法产生初始解,并使用禁忌搜索算法对初始解邻域进行搜索的算法框架.基于不同的启发式算法,获得了3个混合禁忌搜索算法HA1,HA2和HA3.使用Taillards基准程序随机产生的大量实例,进行模拟实验,结果表明,所提出的3个算法通过扩大搜索范围提高了解的质量,在性能上均优于目前最有效的启发式算法.与目前最有效的算法相比,产生最好解的平均百分比偏差均下降至少30%,最优解所占比例皆有显著提高.     

同时收发运输路径问题的禁忌搜索算法

研究同时收发的运输路径问题,要求运输工具到每个客户收取和发送一次完成,并且在运输工具容量的限制下,寻求每个运输工具的运输路径,使总运费为最少.提出两阶段的求解过程:先用启发式算法得到初始解,然后用层次禁忌搜索算法得到改进解.计算实验表明,同样规模的问题,算法所需时间比直接使用禁忌搜索算法要少.