求解护士排班问题的变邻域搜索算法

变邻域搜索算法是求解护士排班问题的一个有效算法,其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度,提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构,而且当使用任意的邻域都不能进一步改进当前解时,设计了一个对当前最优解进行扰动的方法,即在排班期间内随机地选择两天,在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较,在Sprint-early、Medium-early和Long-early组算例上的结果表明,IVNS算法的最优值至少不劣于HVNS,而平均值均优于HVNS;IVNS算法的最大方差为0.72,波动范围小,求解性能稳定。IVNS的扰动方案对现有方案的扰动较小,能有效跳出当前局部最优,增强变邻域搜索算法的优化能力,与HVNS算法相比,其求解性能更优。     

求解柔性作业车间调度问题的新型改进Jaya算法

为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。     

求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法

针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题,提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题（TDVRP）。首先,根据连续型行驶时间依赖函数来刻画时变车速,采用综合油耗模型来评估实时燃油消耗量,并建立了以总成本最小化为目标的路径优化模型;然后,根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子,并将破坏-修复大邻域搜索算子融入到人工蜂群（ABC）算法之中,以提高算法的全局搜索能力。仿真实验结果表明,与自适应可变邻域搜索精英蚁群（AVNS_EAC）算法、自适应大邻域搜索精英蚁群（ALNS_EAC）算法、自适应大邻域搜索精英遗传（ALNS_EG）算法和自适应大邻域搜索模拟退火（ALNS_SA）算法相比,所提出的自适应大邻域搜索人工蜂群（ALNS_ABC）算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强,能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。     

面向柔性作业车间调度问题的改进变邻域搜索算法

针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计3种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解的搜索过程中解的可行性以提高求解效率。针对一系列典型的柔性作业车间调度问题的实例,运用所设计的改进变邻域搜索算法进行测试求解,并将计算结果与文献中其他算法的测试结果进行比较,验证了所提出方法求解柔性作业车间调度问题的可行性和有效性。     

基于混合差分进化算法的无等待流水车间总流水时间优化*

以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。     

变邻域遗传算法在车间物流调度中的应用

针对含有自动引导小车(Automated Guided Vehicle,AGV)的离散化车间物流调度问题,以最小化物流任务时间惩罚成本和最小化运载小车的总行驶距离为优化目标,构建离散化车间多目标物流调度优化模型,设计一种基于Pareto寻优的多目标混合变邻域搜索遗传算法(VNSGA-II).以遗传算法为基础,通过使用NSGA-II的Pareto分层和拥挤度计算方法评估种群优劣实现多目标优化,为了提高算法的寻优能力,避免算法陷入局部最优,通过添加保优记忆库对精英个体进行保护,并利用变邻域搜索算法在搜索过程中的局部寻优能力,针对本文模型特点,设计6个随机邻域结构,来达到算法求解最优值的目标.并提出了基于关键AGV小车的插入邻域和基于关键物流任务的交换邻域调整策略以进一步降低成本.最后,以某离散车间物流调度为实例,分别使用VNSGA-II、带精英策略的快速非支配排序遗传算法Ⅱ(Nondominated Sorting Genetic AlgorithmⅡ,NSGA-II)和强Pareto进化算法(Strong Pareto Evolutionary Algorithm 2,SPEA2)对问题进行求解,计算结果表明,VNSGA-II能得到更好的Pareto解集,验证了算法的有效性和可行性.     

大规模无等待流水调度问题的邻域迭代搜索算法

在分析大规模无等待流水调度问题特点的基础上,提出了利用相邻工件间完工时间距离求最小化完工时间的方法;通过研究工件插入和工件对的交换对最小化完工时间的影响,提出一种邻域迭代搜索算法,该算法降低了求解完工时间的时间复杂度,大大提高了算法效率;为避免算法在邻域搜索过程中陷入局部最优,将变邻域结构算法的思想应用于其中.仿真结果表明,所提出的算法能高效率解决大规模无等待流水调度问题,所得结果令人满意.     

有禁飞区的时间依赖型车辆与无人机协同配送路径优化

本文针对有禁飞区的时间依赖型车辆与无人机协同配送路径问题,综合考虑分时段禁飞的无人机禁飞区域、车辆行驶速度连续变化、车辆及无人机能耗等因素,以车辆派遣成本、车辆能耗成本、无人机能耗成本之和最小为目标建立优化模型.根据问题特征,设计遗传变邻域搜索算法对其进行求解.针对遗传算法易早熟、局部搜索能力较差等缺陷,将变邻域搜索算法与其结合以增强算法的局部搜索能力,引入自适应邻域搜索次数以增强对种群的搜索深度,采用精英保留策略不断改进最优解.通过多组算例验证了算法的有效性,并分析了配送模式、禁飞区数量、车辆行驶速度变化对配送方案的影响,结果表明禁飞区及车辆速度等因素在很大程度上影响物流配送成本.研究成果不仅丰富了车辆与无人机协同配送的场景,拓展了VRP问题的研究,也为物流企业制定配送方案提供了依据.     

一种SAT邻域的快速搜索算法

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。     

模糊Job Shop调度中的混合搜索策略的研究

采用并行遗传算法作为全局搜索算法，提出一种混合搜索策略，用于求解模糊Job Shop调度问题．根据模糊Job Shop调度问题解的特征，提出基于关键工序的邻域选择方法，并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法，加强了遗传算法局部搜索能力．针对13个困难benchmark问题的实验结果表明，在较短的时间内，混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%，比TSAB算法提高5.76%．采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．     

Multiobjective pseudo‐variable neighborhood descent for a bicriteria parallel machine scheduling problem with setup time

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria parallel machine scheduling problem. The problem considers two objectives, one related to the makespan and the other to the flow time, where the setup time depends on the sequence, and the machines are identical. The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose changing the local search inside the VND to a sequential search through the neighborhoods to obtain nondominated points for the Pareto‐front quickly. In the numerical tests, we consider a single‐objective version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective. Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the well‐known nondominated sorting genetic algorithm II.     

A filter-and-fan approach with adaptive neighborhood switching for resource-constrained project scheduling

This paper presents an effective heuristic algorithm based on the framework of the filter-and-fan (F&F) procedure for solving the resource-constrained project scheduling problem (RCPSP). The proposed solution methodology, called the filter-and-fan approach with adaptive neighborhood switching (FFANS), operates on four different neighborhood structures and incorporates improved local search, F&F search with multiple neighborhoods and an adaptive neighborhood switching procedure. The improved local search, in which a new insert-based move strategy and new time compression measurement of schedules having the same makespan are embedded, is utilized to identify a local optimum and a basic move list. The F&F search, aimed to further improve the local optimum, applies multi-neighborhood filter and fan strategies to generate compound moves and a neighborhood-switch list in a tree search fashion. When the current neighborhood cannot further improve the local optimum, the adaptive neighborhood switching procedure picks the most potential neighborhood for the next run of the local search procedure. The entire solution procedure is autonomous and adaptive due to its variable search range depending on the project sizes and characteristics. Computational results and comparisons with some state-of-the-art algorithms indicate the effectiveness and competence of the proposed FFANS.     

The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation

The multi-depot fleet size and mix vehicle routing problem, also known as the multi-depot routing with heterogeneous vehicles, is investigated. A mathematical formulation is given and lower as well as upper bounds are produced using a three hour execution time of CPLEX. An efficient implementation of variable neighborhood search that incorporates new features in addition to the adaptation of several existing neighborhoods and local search operators is proposed. These features include a preprocessing scheme for identifying borderline customers, a mechanism that aggregates and disaggregates routes between depots, and a neighborhood reduction test that saves nearly 80% of the CPU time, especially on the large instances. The proposed algorithm is highly competitive as it produces 23 new best results when tested on the 26 data instances published in the literature.     

一类自适应免疫进化算法

基于免疫系统中的进化机理，提出一种自适应免疫进化算法，通过定义扩展半径和突交半径两个新算法参数构造了较小和较大两个邻域，分别利用这两个邻域进行局部和全局搜索，从而形成两层领域搜索机制，以保证算法的全局和局部搜索能力，定义了群体的多样度，并以此自适应调节算法参数以提高算法性能，给出了算法的全局收敛性证明，仿真结果表明，该算法收敛速度快，具有良好的全局寻优和局部求精能力。     

Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem

In a single local search algorithm, several neighborhood structures are usually explored. The simplest way is to define a single neighborhood as the union of all predefined neighborhood structures; the other possibility is to make an order (or sequence) of the predefined neighborhoods, and to use them in the first improvement or the best improvement fashion, following that order. In this work, first we classify possible variants of sequential use of neighborhoods and then, empirically analyze them in solving the classical traveling salesman problem (TSP). We explore the most commonly used TSP neighborhood structures, such as 2‐opt and insertion neighborhoods. In our empirical study, we tested 76 different such heuristics on 15,200 random test instances. Several interesting observations are derived. In addition, the two best of 76 heuristics (used as local searches within a variable neighborhood search) are tested on 23 test instances taken from the TSP library (TSPLIB). It appears that the union of neighborhoods does not perform well.     

混合粒子群算法求解带软时间窗的VRPSPD问题

针对带软时间窗的同时集配货车辆路径问题（VRPSPD）,建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型;设计混合粒子群算法进行求解,该算法结合以变邻域下降搜索为主体的适应性扰动机制,采用适应性选择邻域策略,并在每个邻域搜索中应用可变的循环次数,以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。     

基于增强型kick策略的ILS算法求解一类聚类问题

提出一种新型的基于环交换邻域的迭代局部搜索算（ILS）．用于求解一类聚类问题,算法的主要特点是：1）基于环交换的邻域结构;环交换邻域与传统的Swap和Insert邻域相比,算法在一次迭代中允许多个点同时移动;2）针对聚类问题提出了增强型的kick移动策略：根据每组内点的密度分布摄动聚类中心,对给定的解重新聚类,实验结果表明,基于环交换的迭代局部搜索算法对求解该类聚类问题是有效的．     

面向大学课程时间表的并行多视图搜索算法

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

A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date

Although the concept of just-in-time (JIT) production systems has been proposed for over two decades, it is still important in real-world production systems. In this paper, we consider minimizing the total weighted earliness and tardiness with a restrictive common due date in a single machine environment, which has been proved as an NP-hard problem. Due to the complexity of the problem, metaheuristics, including simulated annealing, genetic algorithm, tabu search, among others, have been proposed for searching good solutions in reasonable computation times. In this paper, we propose a hybrid metaheuristic that uses tabu search within variable neighborhood search (VNS/TS). There are several distinctive features in the VNS/TS algorithm, including different ratio of the two neighborhoods, generating five points simultaneously in a neighborhood, implementation of the B/F local search, and combination of TS with VNS. By examining the 280 benchmark problem instances, the algorithm shows an excellent performance in not only the solution quality but also the computation time. The results obtained are better than those reported previously in the literature.