基于禁忌搜索的启发式算法求解圆形packing问题 被引量：12

1

作者 康雁 黄文奇 《计算机研究与发展》 EI CSCD 北大核心 2004年第9期1554-1558,共5页

求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程... 求解具有NP难度的圆形 packing问题具有很高的理论与实用价值 现提出一个有效的启发式方法 ,求解了货运中常遇到的矩形区域内的不等圆 packing问题 此算法首先将圆按给定的优先级分组 ,然后逐组地用拟物拟人法放置圆 ,并且在整个过程中利用了禁忌搜索法的思想 ,通过禁止重复前面已做的工作 ,使搜索能有效地逃离局部极小值的陷阱 ,提高了搜索效率 实验结果表明 。 展开更多

关键词 圆形PACKING问题 禁忌搜索法 启发式算法 NP难问题

下载PDF 职称材料

一种基于时空距离的带时间窗车辆路径问题算法 被引量：9

2

作者 戚铭尧 丁国祥 +1 位作者 周游 缪立新 《交通运输系统工程与信息》 EI CSCD 2011年第1期85-89,共5页

带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法.传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求.本文同时考虑顾客的时间和空间特性... 带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法.传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求.本文同时考虑顾客的时间和空间特性,提出了一种基于时空度量的顾客分组方法.在路径优化阶段,本文提出了一种禁忌搜索算法来进行求解,该算法中禁忌的对象不是解,而是这些解的目标函数值的区间,以便于提高收敛效率.作为验证,本文以Solomon标杆问题集为算例进行演算,结果表明,在窄时间窗约束下,基于时空距离的两阶段启发式算法明显优于基于空间距离的算法,且部分算例的解达到了国内外已发表的最好解. 展开更多

关键词 物流工程 时空距离 禁忌搜索算法 车辆路径问题 两阶段启发式算法 广义指派问题

下载PDF 职称材料

双目标突发事件应急救援前摄性调度优化 被引量：9

3

作者 何正文 贾涛 徐渝 《运筹与管理》 CSSCI CSCD 北大核心 2012年第1期124-130,共7页

本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式... 本文以救援时间最短化与计划鲁棒性最大化为目标,研究突发事件应急救援前摄性调度优化问题。作者首先对所研究问题进行界定,其中计划鲁棒性定义为各活动开始时间可调整时差的总和,任务是在应急预算和救援期限的约束下,确定活动执行模式与开始时间以实现上述两个目标。随后,构建问题的0-1规划优化模型,鉴于其强NP-hard属性,设计禁忌搜索启发式算法。最后用一个算例对研究进行说明,得到如下结论:救援时间随应急预算的增加而缩短,随救援期限的放宽而延长;计划鲁棒性随应急预算的增加或救援期限的放宽而提高;当权重分配系数增大时,应急救援时间先保持不变而后缩短,计划鲁棒性则呈减小趋势。本文研究可为突发事件应急救援的组织与协调提供决策支持。 展开更多

关键词 应急管理 前摄性调度优化 优化模型 禁忌搜索启发式算法 突发事件应急救援

下载PDF 职称材料

基于资源约束的突发事件应急救援鲁棒性调度优化 被引量：9

4

作者 胡信布 何正文 徐渝 《运筹与管理》 CSSCI CSCD 北大核心 2013年第2期72-79,共8页

突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用... 突发事件应急救援的调度优化,对于救援活动的顺利实施及应急资源的有效使用具有至关重要的作用。本文研究资源约束下的突发事件应急救援鲁棒性调度优化问题,其中,鲁棒性定义为各活动的时间缓冲与其权重系数乘积的总和,目标是在资源可用量及救援期限的约束下,安排活动开始时间和执行模式以最大化应急救援计划的鲁棒性。作者构建了问题的0-1规划优化模型,针对其NP-hard属性,基于问题特征设计双环路禁忌搜索启发式算法。通过对一个算例的计算分析,得到如下结论:给定网络结构及时间参数,利用权重系数的定义可以将时间缓冲分配到重要活动上,由此提高应急救援计划的鲁棒性;随着资源可用量的增加,计划的鲁棒性呈上升趋势,而当救援期限延长时,计划的鲁棒性单调增加。本文研究可为突发事件应急救援基准计划的制定提供决策支持。 展开更多

关键词 鲁棒性调度 突发事件应急救援 优化模型 禁忌搜索启发式算法 资源约束

下载PDF 职称材料

一种适用于求解TSP问题的改进的禁忌算法 被引量：3

5

作者 武妍 周欣 《计算机工程与应用》 CSCD 北大核心 2008年第1期57-59,共3页

利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法(MTS)。该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区,然后对区域连接... 利用传统的禁忌算法的基本思想,针对TSP问题,提出了一种改进的禁忌算法(MTS)。该算法在初始解的生成,邻域结构及禁忌策略方面进行了大的改进,充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区,然后对区域连接,生成初始解;同时生成每个城市的k邻居列表,利用k邻居列表和改进的禁忌策略来突破局部最优。通过对CHN144问题及若干TSPLIB中问题的求解,结果表明所提算法能够以较快速度求得较好的满意解。 展开更多

关键词 禁忌算法 启发式算法 旅行商问题

下载PDF 职称材料

求解带动不平衡约束的卫星舱布局问题的启发式算法 被引量：5

6

作者 刘景发 高泽旭 +3 位作者 龙羽正 姚永雷 刘文杰 刘朝霞 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2014年第8期1232-1239,共8页

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布... 以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性. 展开更多

关键词 动不平衡约束 装填问题 禁忌搜索 启发式算法

下载PDF 职称材料

基于资金约束的项目支付进度问题研究 被引量：5

7

作者 何正文 任世科 徐渝 《系统工程学报》 CSCD 北大核心 2012年第3期399-406,共8页

研究资金约束下的项目支付进度安排问题,其中活动具有多种执行模式,目标是最大化项目净现值.首先界定研究假设条件并定义文中用到的符号;随后构建问题的非线性整数规划优化模型;针对其强NP-hard属性,设计三层迭代循环嵌套的禁忌搜索启... 研究资金约束下的项目支付进度安排问题,其中活动具有多种执行模式,目标是最大化项目净现值.首先界定研究假设条件并定义文中用到的符号;随后构建问题的非线性整数规划优化模型;针对其强NP-hard属性,设计三层迭代循环嵌套的禁忌搜索启发式算法;以多重迭代改进算法为对比基准,在随机生成的3240个标准算例上对算法进行测试,结果表明:禁忌搜索获得的满意解质量远高于多重迭代改进,但其计算时间要长于后者.该研究可为承包商安排项目进度及平衡现金流提供决策支持. 展开更多

关键词 项目支付进度 资金约束 优化模型 禁忌搜索启发式算法

下载PDF 职称材料

混合超启发式法求解大规模VRP的优化研究 被引量：4

8

作者 杜玲玲 《华东交通大学学报》 2011年第1期62-67,共6页

车辆路径是一类NP(non-deterministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义。提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题... 车辆路径是一类NP(non-deterministic polynomial)完全问题,研究解决车辆路径问题的高质量启发式算法有着重要理论价值和现实意义。提出一种将最近邻搜索法和禁忌搜索法优势相结合的混合超启发式算法,用来解决带容量约束的车辆路径问题。先利用最近邻搜索法构建初步路线,再利用禁忌搜索法对内部线路和互跨线路进行优化。通过对基于标准数据集和6 772个烟草客户真实数据集进行应用验证,新算法在减少线路的总路程上具有显著效果,为大规模车辆路径问题的求解提供了新的求解思路。 展开更多

关键词 大规模车辆路径问题 容量约束 最近邻搜索 禁忌搜索 混合启发式算法

下载PDF 职称材料

基于随机交箱序列的集装箱堆场出口箱箱位优选 被引量：3

9

作者 周鹏飞 方波 《沈阳工业大学学报》 EI CAS 2011年第6期678-685,共8页

为了优选客户提交箱时间不确定条件下的集装箱堆场出口箱箱位,降低作业成本,提出了基于随机交箱序列的堆场箱位优选方法,即两阶段随机规划模型和基于禁忌搜索的启发式算法.模型通过优选贝位和堆栈最小化堆场龙门吊行车成本和翻箱量,探... 为了优选客户提交箱时间不确定条件下的集装箱堆场出口箱箱位,降低作业成本,提出了基于随机交箱序列的堆场箱位优选方法,即两阶段随机规划模型和基于禁忌搜索的启发式算法.模型通过优选贝位和堆栈最小化堆场龙门吊行车成本和翻箱量,探讨了随机交箱序列条件下的翻箱量和龙门吊行车成本求解方法,并针对模型最优解特点开发了基于禁忌搜索的启发式算法.模拟实验表明,该方法能够有效利用不确定集装箱交箱序列信息改善调度效果,算法能够在合理时间内获得满意解. 展开更多

关键词 集装箱运输 堆场箱位优化 两阶段随机规划模型 禁忌搜索算法 随机交箱序列 翻箱率 启发式算法 模拟

下载PDF 职称材料

基于两阶段遗传算法的传感器网络布点 被引量：1

10

作者 胡坚明 何颖佳 张毅 《交通信息与安全》 2009年第3期68-73,共6页

随着传感器网络在世界范围内得到越来越广泛的应用,具有感知、计算和通信能力的传感器节点以及由大量此类节点互联构成的传感器网络需要不断地优化并进行自动设计。文中致力于设计1种新型交通信息监测传感器网络,并采用两阶段启发式算... 随着传感器网络在世界范围内得到越来越广泛的应用,具有感知、计算和通信能力的传感器节点以及由大量此类节点互联构成的传感器网络需要不断地优化并进行自动设计。文中致力于设计1种新型交通信息监测传感器网络,并采用两阶段启发式算法完成网络的自动布点,分析不同启发式算法运行结果性能指标的差异,从而证明了两阶段启发式算法在交通监测网络中的优越性。 展开更多

关键词 遗传算法 模拟退火算法 禁忌搜索算法 传感器网络布点 两阶段启发式算法

下载PDF 职称材料

定位路线问题的两阶段禁忌搜索算法研究 被引量：1

11

作者 徐丽蕊 《陕西工业职业技术学院学报》 2008年第3期34-40,共7页

定位路线问题是定位配给和车辆路线问题的集成决策，本文在对该问题进行描述的基础上，建立了多站点定位路线问题的数学模型，并用Lingo10．0验证了模型的正确性。针对此模型的NP—hard属性，设计了两阶段禁忌搜索启发式算法；即第一阶... 定位路线问题是定位配给和车辆路线问题的集成决策，本文在对该问题进行描述的基础上，建立了多站点定位路线问题的数学模型，并用Lingo10．0验证了模型的正确性。针对此模型的NP—hard属性，设计了两阶段禁忌搜索启发式算法；即第一阶段用禁忌搜索算法求解定位配给问题，确定设施定位及客户分配；第二阶段用禁忌搜索算法求解车辆路线问题，经过两个阶段的多次迭代求得定位路线问题的优化解，通过物流决策过程的实例计算，结果表明该算法具有可行性和有效性。 展开更多

关键词 定位路线 车辆路线 禁忌搜索 启发式算法

下载PDF 职称材料

定位路线问题的两阶段禁忌搜索算法研究 被引量：1

12

作者 徐丽蕊 李静 《陕西理工学院学报（自然科学版）》 2011年第4期81-89,共9页

定位路线问题是定位配给和车辆路线问题的集成。分析了定位路线问题的含义,建立了此问题的数学模型,并用Lingo 10.0验证了模型的正确性。由于该模型属于NP-hard问题,设计了两阶段禁忌搜索算法:第一阶段用禁忌搜索算法求解定位配给问题,... 定位路线问题是定位配给和车辆路线问题的集成。分析了定位路线问题的含义,建立了此问题的数学模型,并用Lingo 10.0验证了模型的正确性。由于该模型属于NP-hard问题,设计了两阶段禁忌搜索算法:第一阶段用禁忌搜索算法求解定位配给问题,确定设施定位及客户分配;第二阶段用禁忌搜索算法求解车辆路线问题,经过两个阶段的多次迭代求得定位路线问题的优化解,通过实例计算验证该算法的可行性和有效性。 展开更多

关键词 定位路线 车辆路线 禁忌搜索 启发式算法

下载PDF 职称材料

配电网检修计划优化模型 被引量：47

13

作者 黄弦超 张粒子 +1 位作者 舒隽 莫小燕 《电力系统自动化》 EI CSCD 北大核心 2007年第1期33-37,共5页

从配电网设备检修计划编制的实际情况出发,建立了考虑多种约束条件的负荷转移路径和设备检修时间联合优化模型。该模型以设备检修时间优化为主问题,以负荷转移路径优化为子问题。通过主问题和子问题的反复优化迭代,最终获得供电企业售... 从配电网设备检修计划编制的实际情况出发,建立了考虑多种约束条件的负荷转移路径和设备检修时间联合优化模型。该模型以设备检修时间优化为主问题,以负荷转移路径优化为子问题。通过主问题和子问题的反复优化迭代,最终获得供电企业售电损失最小的检修计划以及停电负荷、开关操作次数和系统网损最小的负荷转移方案。针对该模型的特点,采用免疫禁忌混合算法对主问题进行求解,采用改进的待恢复树切割算法对子问题进行求解。针对基本待恢复切割算法需要对联络开关进行全排列,以穷举的方式获取最优解的不足,通过应用“优先选择备用容量较大的联络开关”启发规则以及在恢复树切割过程中引入网损比较环节,在保证解的质量的同时有效地降低了恢复树的切割次数,提高了计算速度。通过算例计算和分析,验证了所提出的模型和算法的正确性和实用性,适合求解配电网检修优化问题。 展开更多

关键词 配电网 检修计划 负荷转移 免疫禁忌混合算法 启发式算法

下载PDF 职称材料

基于改进的禁忌搜索算法的机场场面优化研究

14

作者 冯思旭 《数学的实践与认识》 北大核心 2024年第4期119-127,共9页

对跑道和滑行道进行联合优化有助于提高机场现有的硬件与软件资源的使用率,缓解航班延误.首先综合考虑滑行的相关规定以及跑道放行间隔的约束,以所有航空器滑行时间最小为目标函数,构建基于机场基本元素布局的场面滑行道与跑道联合优化... 对跑道和滑行道进行联合优化有助于提高机场现有的硬件与软件资源的使用率,缓解航班延误.首先综合考虑滑行的相关规定以及跑道放行间隔的约束,以所有航空器滑行时间最小为目标函数,构建基于机场基本元素布局的场面滑行道与跑道联合优化模型;其次针对遗传禁忌搜索算法的特点和场面运行实际情况改进了遗传禁忌搜索算法,并以此求解该优化模型;最后以南京禄口国际机场为例,将改进的遗传禁忌搜索算法所得最优解与实际运行数据进行比较验证模型的优化性. 展开更多

关键词 改进的遗传禁忌搜索算法 滑行道与跑道联合优化 机场场面优化 启发式算法

原文传递