摘要：区划问题是将特定地理区域划分为若干空间连续的分区,满足分区内差异最小和分区间差异最大这一基本原则,广泛应用于地理、环境、生态、经济、农业、城市等领域。1960s以来,学者尝试建立各种区划问题数学模型,设计了一系列的求解算法,代表性的算法主要有:AZP、ARISEL、SKATER和REDCAP。本文提出了一个基于迭代局部搜索(ILS)的区划问题算法,进一步提升算法性能。该算法主要机制包括:邻域单元移动搜索改进分区质量;参照中心单元快速计算分区方差,提升算法速度;使用扰动机制跳出当前解局部最优状态;更新分区中心点提升分区方案目标值;使用群搜索探索更大的解空间;以及算法各步骤中通过分区空间连续判断和破碎修复保持分区空间连续。55个基准案例测试表明:ILS算法求解质量优于ARISEL和SKATER算法。一个多指标气候分区实验也表明:ILS算法求解质量优于SKATER、REDCAP和ARISEL算法。

摘要：基于第Ⅰ类混流双边装配线平衡具有生产品种多样性和生产过程复杂性的特点,研制了一种改进迭代局部搜索算法进行求解。在工位数量相同时引入新的二级目标,使前面工位承担更多负载,推进解的细微改进;提出基于工位的启发式解码方式,使成对工位内的负载更为均衡。在解码设计中,优先选择空闲时间较多的边作为分配操作的边,对每种产品优先选择不产生空闲时间的操作分配,然后通过最后成对工位调整策略进一步减少工位的数量。同时设计了新的改进启发式初始化和局部搜索方式,并通过参数校验验证改进的合理性。将所提解码方式与3种不同的解码方式进行对比,并将所提算法与7种不同算法进行对比,结果表明,基于工位的启发式解码优于对比解码,所提迭代局部搜索算法优于其他对比算法。

摘要：随着现代空间科技的迅猛发展,光学遥感图像数据的应用需求越来越广泛,大力推动了光学对地观测卫星的发展.然而,由于高昂的发射成本的约束,对地观测卫星的资源是有限的,远远无法满足各类数据需求.因此,提高对地观测卫星的使用效率,提高其任务执行率,具有非常重要的应用价值.本文聚焦于敏捷对地观测卫星的任务调度问题,即在给定的调度周期内,对有限的卫星资源制定合理的任务调度方案,在满足一定星上资源约束下,最大化观测任务收益.该问题难点在于星上的资源是非常有限的,例如存储图像数据的固存资源、用于采集数据和卫星姿态切换的能量资源及执行任务活动耗费的时间资源.需要注意的是,能量消耗量和时间消耗量依赖于任务的执行时间,这是敏捷卫星相对传统的非敏捷卫星独有的特性.不同任务场景对不同类型资源的需求不同,多种资源约束互相耦合,资源约束具有时间依赖特性,这些难点无疑极大地增加了卫星调度的求解难度.为高效地求解该问题,本文构建了多类型时间依赖资源约束的敏捷卫星调度整数规划模型,并针对问题特性提出了一种基于自适应选择因子的迭代局部搜索启发式算法.自适应选择因子综合考虑了目标收益、资源消耗量、资源约束的松弛量,采用动态变化的资源重要度,能快速自适应地根据当前场景下各种类型的资源数据使用量来确定最佳局部搜索方向,从而在有限时间内找到高质量的解.实验结果证明,本文所提出的算法在多种情况下相比当前最好算法求解效果显著更优.此外,算法独有的自适应选择因子相比传统的选择因子的求解质量更高,这是因为所设计的自适应选择因子兼顾了目标收益和资源消耗量之间权衡关系的同时,采用动态变化的资源重要度准确捕捉了资源需求的迫切程度.

摘要：对于容量约束的车辆路径问题（ capacitated vehicle routing problem, CVRP）以及容量和最大行驶距离约束的车辆问题（ capacitated and distance constrained vehicle routing problem, CDVRP）,邻域解的评估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示,提出用于CVRP/CDVRP问题的邻域解合法性快速评估策略.该策略针对交换、插入、2-opt和2-opt？四种常用的局部搜索算子,通过引入前载重、后载重、前向距离和后向距离的概念,实现了邻域解合法性的快速评估.将改进后的局部搜索算子与迭代局部搜索（ iterated local search, ILS）算法相结合,提出用于车辆路径问题的快速多邻域迭代局部搜索（ fast multi-neighborhood ILS, FMNILS）算法.该快速评估策略将评估一个邻域解的时间复杂度由O（ N）降至O（1）,算法仿真结果表明, FMNILS算法运算能力的提高大致与配送路线所服务的客户数成正比；对客户数介于200~500的容量/最大距离约束VRP问题,该算法能在短时间内获得较满意解,平均求解精度1．2%以内,平均耗时约96 s,仅为对比算法的6%或更少.

摘要：为了改进原始和声搜索算法的全局搜索性能,提出了基于迭代局部搜索的和声搜索算法。该算法在充分利用和声记忆库中信息和提高搜索效率的同时,对于不满足停止准则的新和声采用基于改进kick策略移动的迭代局部搜索算法进行寻优,从而使新算法具有较强的"爬山"能力。针对4个benchmark函数对新算法做了测试,并与粒子群优化算法以及已有的几个算法进行了比较,结果表明该算法跳出局部极值点的能力较强、收敛速度更快、寻优精度较高;最后将新算法应用到焊接梁的优化设计问题中,仿真结果验证了该算法在求解焊接梁最小造价问题时优于原始的和声搜索算法、遗传算法等方法。

摘要：针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题(SBRP),提出一种改进迭代局部搜索(ILS)算法以提升求解质量。该算法使用大规模邻域搜索(LNS)算法作为扰动算子;在解的破坏过程中,设计一组解的破坏因子并赋予一定的选择概率,每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率,进而调整解的破坏程度。为提升ILS解的多样性,算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试,测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升;与蚁群算法的比较结果进一步验证了改进算法的有效性。

摘要：随着物流行业竞争的日益激烈,客户对第四方物流(fourth party logistics,4PL)网络的服务水平提出了新的要求,故如何在保证服务水平的情况下设计总成本最小的4PL网络具有重要的现实意义。客户需求满足情况一直是影响物流网络服务水平的重要因素。近些年来,随着人们生活节奏的不断加快,客户对物流的时效性越来越重视,时效性也成为影响物流网络服务水平的另一因素。本文的4PL网络服务水平为考虑时效性和客户需求满足情况的双重服务水平。为保证满足双重服务水平,本文以成本最小为目标,以时效性和客户需求满足情况为约束,建立了第四方物流网络设计模型。由于该问题具有NP难特性,本文提出了一种嵌入迭代局部搜索的自适应粒子群算法进行求解。不同规模算例的仿真实验结果验证了所提出算法的有效性。将本文模型与不加入时效性约束的第四方物流网络设计模型进行对比,实验结果验证了本文模型既能够有效满足客户要求的服务时间,又能够一定概率下满足客户的需求,从而保证网络的双重服务水平。

摘要：在恶劣天气和机械故障等原因造成航班不能按照原计划执行时,航空公司需要采取相应的措施对航班进行恢复。本文基于经典的资源指派模型,综合考虑了调整时间、换机、联程拉直、取消航班和调机5种恢复策略,提出一种以最小化加权成本为优化目标的航班恢复模型,并设计一种迭代局部搜索算法。首先用构造-修复启发式方法构造可行解,然后从该初始解出发,在飞机路线对的邻域中进行局部搜索。当陷入局部最优后,对解进行扰动,然后从扰动后的解重新出发进行局部搜索。为了提高搜索效率,同时降低陷入局部最优解的概率,局部搜索过程采用模拟退火算法。实例结果表明,本文提出的模型及算法能够在短时间内对受到影响的大规模航班计划进行恢复。

摘要：针对大学课程时间表问题,提出一种基于改进迭代局部搜索的并行多视图搜索算法进行求解。依据课程时间表问题特性设计包含八种基础邻域的多邻域集,并根据提升速度比制定基邻域选择概率设置规则。在迭代局部搜索过程中,运用多视图学习策略对多个局部搜索步骤进行视图共享,及时调整搜索方向以提升搜索效率。通过并行计算思想对算法优化,提升多视图搜索的收敛速度。实验结果表明,提出的算法求解精度更佳,且具有优异的扩展性和并行效率。

摘要：容量约束p-中位问题(Capacitated P-Median Problem,CPMP)已被证明是一类计算机难以求解的具有NP-hard特性的组合优化问题.本文提出一种多阶段粒子群优化算法(Multi-Phase Particle Swarm Optimization,MPPSO)及在算法设计中应用模式有关理论和方法.所提MPPSO在标准PSO基础上,考虑CPMP结构特征信息,采用一种以字符编码为基础的结构体编码结构,重新定义粒子速度与位置更新方式.它将CPMP优化求解分为种群粒子初始化阶段及两个优化阶段.在优化求解第一阶段,分析了惯性因子对所求问题编码结构粒子搜索的局限性,设计一种保留粒子最优特征中位点信息的变异算子.以粒子全局搜索算子操作为重点,期望从整个搜索空间搜索到好的模式结构分布特性的粒子.在优化求解第二阶段,对高适应性粒子执行一种改进的迭代局部搜索操作,达成对粒子精度的进一步提升.迭代局部搜索分为基本局部搜索和深层次局部搜索.基本局部搜索侧重对粒子需求点和中位点提炼用于发现候选粒子相邻的局部最优解.在深层次局部搜索中,采用对粒子执行扰动算子操作,使得算子操作在更大邻域范围内搜索粒子新的模式结构,从而发现蕴含高适应性模式结构的潜在更好解.文中提出模式范数及模式结构距离等概念,并将它们用于扰动算子设计.实验测试表明:MPPSO对4大类CPMP用例问题进行求解得到的实验数据,与4种文献对比算法提供的数据相比有一定优势,且能发现3个大数据集用例新的最好解.