共查询到18条相似文献,搜索用时 62 毫秒
1.
2.
在分析动态车辆调度问题的基础上,建立了基于时间轴的动态模型;接着针对该问题在实际中的应用,设计了基于并行节约法和禁忌搜索的混合算法以对动态车辆调度问题进行求解;最后给出算法实现和算例模拟,验证了该算法的有效性。 相似文献
3.
针对工件不同释放时间和实际加工时间之和的学习效应情况,研究单机调度总完工时间最小化问题。根据问题的NP-hard特性,证明2个优先规则,结合禁忌搜索算法与优先规则,提出一个混合禁忌搜索算法,提高了算法跳出局部最优的能力,既保留了优异的基因又扩大了领域的搜索范围。实验结果表明,与基准算法相比,该算法在求解质量上有更好的表现,而且随着工件规模的增加优势更加明显。 相似文献
4.
本文针对最小完工时间的Job-Shop调度问题提出了一种禁忌搜索算法,该算法使用插入算法构造尽可能好的初始解,然后用禁忌搜索算法改进当前解,在算法中对未被选中的候选解信息进行记忆,合理平衡了集中搜索与分散搜索。最后用基准实例进行仿真,实验结果表明该算法是可行的和有效的。 相似文献
5.
针对流水线调度这一类NP-Hard难题,深入分析了零空闲流水线调度问题,提出了一种解决零空闲流水线调度问题的基于NEH方法的禁忌搜索算法,建立了以工件的最大完工时间为目标的算法模型.新算法利用NEH启发式算法产生问题的初始解,改善了新算法的搜索性能.利用动态方式更新禁忌表长,提高了新算法的鲁棒性.为了提高算法的运行时效,利用快速搜索算法对提出的禁忌搜索算法进行改进,即采用快速搜索算法作为禁忌搜索的邻域函数,得到另一种改进的禁忌搜索算法.仿真试验结果表明了该算法的有效性及优越性,新算法在流水线生产调度及自动化工程等领域具有较高的实用价值. 相似文献
6.
7.
考虑到实际生活中车辆受发车时间限制以及道路路况影响运输成本等因素,建立了带客户软时间窗、车场硬时间窗、多车型、道路路况等约束的关联运输调度问题模型.结合禁忌搜索与遗传算法的优势,构造了混合禁忌搜索算法,以通过构造多个初始解来增大搜索空间;设计了两种禁忌表,分别为局部禁忌表和全局禁忌表,这不仅能加快寻优速度,还可以摆脱对单个解的依赖;将禁忌搜索生成的优化解作为遗传算法的初始解,可以加快寻优速度;自适应调整禁忌表长度可以避免早熟收敛;提取核心路径便于进行后期优化,relocate算子能减少路径网络回路数目.对实例进行的仿真表明,提出的IVRP优于一般的VRP,可节约大量成本,且提出的算法在收敛速度和寻优结果两方面都优于遗传算法和禁忌搜索算法.由3种算法求解得到的总成本、总里程及收敛时间的标准差体现出该算法的稳定性比另外两种算法的好. 相似文献
8.
袁建清 《计算机应用与软件》2012,29(4):148-150,155
对带时间窗的动态车辆调度问题进行分析,引入虚拟点和时间轴概念,建立基于时间轴的动态车辆调度模型,并提出基于C-W节约法和禁忌搜索的混合禁忌搜索算法进行求解.算法中使用动态方法构造候选解和动态禁忌长度的选取策略来提高算法的收敛速度,最后通过测试实例验证了该混合算法解决动态车辆调度问题的有效性和可行性. 相似文献
9.
10.
需求可拆分车辆路径问题的禁忌搜索算法 总被引:2,自引:0,他引:2
为解决实际配送运输中的车辆路径问题(Vehicle Routing Problem,VRP),通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题(Split Delivery VRP,SDVRP)数学模型,并利用禁忌搜索算法(Taboo Search Algorithm,TSA)进行求解.在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理.算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率. 相似文献
11.
基于禁忌搜索的启发式算法求解圆形packing问题 总被引:2,自引:1,他引:1
求解具有NP难度的圆形packing问题具有很高的理论与实用价值.现提出一个有效的启发式方法,求解了货运中常遇到的矩形区域内的不等圆packing问题.此算法首先将圆按给定的优先级分组,然后逐组地用拟物拟人法放置圆,并且在整个过程中利用了禁忌搜索法的思想,通过禁止重复前面已做的工作,使搜索能有效地逃离局部极小值的陷阱,提高了搜索效率.实验结果表明,提出的算法是一个高效的实用求解算法. 相似文献
12.
13.
14.
彭茂 《计算技术与自动化》2012,31(1):78-81
禁忌搜索算法作为一种新兴的智能搜索算法,已被广泛应用于各类优化问题。本文综合解向量的分量变化和目标值变化,提出一种新的候选解和当前解选择策略,并用改进的新算法求解TSP问题。实验表明新的算法具有良好的性能。 相似文献
15.
分析了带多软时间窗VRP实际应用背景和特点,以使用的车辆数、行驶费用和偏离时间窗的惩罚费用为优化目标,结合车辆载重、最大路长等限制,建立该问题的数学模型,并设计求解该问题的自适应禁忌搜索算法。为增强算法的全局寻优能力,设计了多邻域结构并在算法中嵌入一种有限地接受不可行解的自适应机制。分别用文献中的算例和以Solomon标准算例为基础构建的新算例测试该算法,并将结果与其他方法进行对比分析。对比结果表明,所提出的算法性能较好,能在可接受的时间内求出运输成本更少、满意度更高的解。 相似文献
16.
An Advanced Tabu Search Algorithm for the Job Shop Problem 总被引:5,自引:0,他引:5
The job shop scheduling problem with the makespan criterion is a certain NP-hard case from OR theory having excellent practical applications. This problem, having been examined for years, is also regarded as an indicator of the quality of advanced scheduling algorithms. In this paper we provide a new approximate algorithm that is based on the big valley phenomenon, and uses some elements of so-called path relinking technique as well as new theoretical properties of neighbourhoods. The proposed algorithm owns, unprecedented up to now, accuracy, obtainable in a quick time on a PC, which has been confirmed after wide computer tests. 相似文献
17.
生化恐怖袭击事件是一类罕见但危害极大的突发事件。这类事件发生时,如何高效地利用有限的车辆等资源,在有限的时间内,将事发地受攻击人群尽快地送到附近的医院,并且使他们得到适当的治疗,是非常重要的。根据日本的沙林毒气事件和‘9.11’后炭疽事件等恐怖事件的经验教训,结合我国都市的特点,建立了针对生化恐怖突发事件中一特定场景的随机VRP模型,拟在"黄金救助时间"内将受害者送往各医院。基于禁忌搜索算法来求解该模型,并将该模型及算法集成到应急决策支持系统中,以算例进行仿真分析和比较,验证了模型的合理有效性,并说明了算法的应用性。 相似文献
18.
Windows环境下的禁忌搜索法解Job—shop问题 总被引:3,自引:0,他引:3
本文应用禁忌搜索算法来解决复杂的车间调度问题,介绍了禁忌搜索算法的基本概念和各项参数,讨论了基于禁忌搜索的调度方案,并给出了调度方案的编程实现。 相似文献