改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。     

求解多车型校车路径问题的混合集合划分的GRASP算法

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法。根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解。为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息。使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性。     

基于GRASP算法的多成像卫星协同观测调度

针对摘要多成像卫星协同观测调度问题,具有观测任务的时间窗口、卫星存储及能量等约束,是一个NP难的组合优化问题。建立了多成像卫星协同观测调度模型,采用贪婪随机自适应搜索算法(GRASP)对问题模型进行求解,并且对基本的GRASP算法做出了一定的改进,在其初始解的构造阶段设计了定长受限候选列表和变长受限候选列表两种策略,在邻域搜索阶段结合模拟退火算法来搜索更好的解。仿真实例表明,该算法在解决成像卫星任务调度问题时是有效的。     

一种混合局部搜索算法的嵌套分区算法

提出了一种混合多种局部搜索算法的嵌套分区算法用于求解中小规模旅行商问题.该算法使用加权抽样法产生初始最可能域,用带约束的3-opt局部搜索算法搜索每个子域的最优解,然后对Lin-Kemighan算法进行了改进,并且用改进的Lin-Kemighan算法搜索每个裙域的最优解,最后通过实验分析法确定了子域和裙域最优的抽样个数及初始最可能域的长度.对TSPLIB中15个问题实例的仿真结果表明,所提出的混合局部搜索算法的改进嵌套分区算法在求解旅行商问题时可以获得高质量的解.     

求解多车型校车路径问题的带参数选择机制的GRASP算法

考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。     

基于禁忌搜索的生产—库存—配送协同计划问题研究

针对具有一定生产期和存储期的快速消费品,从供应链集成的角度研究了确定性需求情形下多工厂、多产品、多客户供应网络的生产—库存—配送协同计划问题,并建立了多周期环境下生产—库存—配送协同计划问题的混合整数规划模型,以协同优化各工厂的生产计划、库存计划与配送计划.提出了求解该模型的禁忌搜索算法方案,且通过设计启发式顺序分配方法生成初始解,采用了从改进的2-opt和λ-interchange的邻域解中产生候选解的策略,给出了提出算法的具体实现过程.最后,通过测试算例的仿真结果,证明了禁忌搜索算法在求解该类问题时具有比混合遗传算法更强的鲁棒性,并且能够得到更好的解.     

混和进化算法求解具有分段恶化效应的并行机调度问题

本文提出了一种新的混合进化算法求解具有线性恶化的并行机调度问题,目标是使总完工时间最小.该算法采用对立策略以及最小比率优先规则生成初始种群,并且引入种群多样度指标加快算法的收敛;同时加入含有3-opt扰动算子的变邻域搜索算法对遗传算法得到的结果进行局部搜索.通过对不同规模算例的实验进行仿真,其结果与传统GA和VNS算法相比,效果均有所提升.     

一种改进的禁忌搜索法在函数优化问题中的应用

禁忌搜索法对初始解、邻域个数及禁忌列表的大小等参数有比较严格的要求,这些参数直接影响着算法的优化能力。文章提出了一种改进的禁忌搜索法,它用有效空间来压缩搜索范围,这样可以提高搜索效率和全局搜索能力。用短期和长期禁忌列表存储器来保证算法能搜索到全局空间的每一点,并且不重复搜索。经过验算和分析,证明它是一种较好的全局启发式搜索法。     

独立任务分配的贪婪随机自适应搜索过程

提出了一种贪婪随机自适应搜索过程求解异构环境下的独立任务分配问题。使用随机化的最小最小完成时间算法来产生问题的初始解，再通过变邻域下降算法来改进这个解，在变邻域下降算法中，为增强算法的空间勘探能力，外层局部搜索采用允许接收劣质解的策略，使用禁忌表来防止迂回搜索，使算法在多样性和集中性间取得了较好的平衡。与领域中的典型算法进行了仿真比较，结果表明提出的算法具有良好的性能。     

基于改进ACS-3-opt蚁群算法的TSP

在ACS-3-opt算法求解中,大规模TSP问题易于停滞。该文提出一种改进的算法,在ACS-3-opt算法停滞后,自适应地调整具有局部搜索能力蚂蚁的数量,并通过提高最小信息素的阈值扩大搜索空间,当算法再次停滞时,增强算法两次停滞时最优路径的公共路径上的信息素,为算法的运行提供较好的初始信息,并引导算法朝最优解的方向进行求解。大中型规模TSP问题的求解结果表明,该算法能够有效地跳出局部最优,解的质量优于ACS-3-opt算法。     

GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem

In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the “exterior form” of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR.     

The fixed set search applied to the power dominating set problem

In this article, we focus on solving the power dominating set problem and its connected version. These problems are frequently used for finding optimal placements of phasor measurement units in power systems. We present an improved integer linear program (ILP) for both problems. In addition, a greedy constructive algorithm and a local search are developed. A greedy randomised adaptive search procedure (GRASP) algorithm is created to find near optimal solutions for large scale problem instances. The performance of the GRASP is further enhanced by extending it to the novel fixed set search (FSS) metaheuristic. Our computational results show that the proposed ILP has a significantly lower computational cost than existing ILPs for both versions of the problem. The proposed FSS algorithm manages to find all the optimal solutions that have been acquired using the ILP. In the last group of tests, it is shown that the FSS can significantly outperform the GRASP in both solution quality and computational cost.     

带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法.该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计.为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率.实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002％,优于对比算法.     

Embedded local search approaches for routing optimization

This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.     

Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem

Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate “good” solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC’00, 2000, pp. 126–133). We show that it is possible to get in linear time, a -approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1,2) problem where every edge is associated to a couple of distances which are either 1 or 2 (Math. Oper. Res. 18 (1) (1993) 1).     

Efficient local search on the GPU—Investigations on the vehicle routing problem

We study how to implement local search efficiently on data parallel accelerators such as Graphics Processing Units. The Distance-constrained Capacitated Vehicle Routing Problem, a computationally very hard discrete optimization problem with high industrial relevance, is the selected vehicle for our investigations. More precisely, we investigate local search with the Best Improving strategy for the 2-opt and 3-opt operators on a giant tour representation. Resource extension functions are used for constant time move evaluation. Using CUDA, a basic implementation called The Benchmark Version has been developed and deployed on a Fermi architecture Graphics Processing Unit. Both neighborhood setup and evaluation are performed entirely on the device. The Benchmark Version is the initial step of an incremental improvement process where a number of important implementation aspects have been systematically studied. Ten well-known test instances from the literature are used in computational experiments, and profiling tools are used to identify bottlenecks. In the final version, the device is fully saturated, given a large enough problem instance. A speedup of almost an order of magnitude relative to The Benchmark Version is observed. We conclude that, with some effort, local search may be implemented very efficiently on Graphics Processing Units. Our experiments show that a maximum efficiency, however, requires a neighborhood cardinality of at least one million. Full exploration of a billion neighbors takes a few seconds and may be deemed too expensive with the current technology. Reduced neighborhoods through filtering is an obvious remedy. Experiments on simple models of neighborhood filtering indicate, however, that the speedup effect is limited on data parallel accelerators. We believe these insights are valuable in the design of new metaheuristics that fully utilize modern, heterogeneous processors.     

基于蚁群优化算法的网格任务映射策略

针对网格环境下实现任务最优映射的问题,提出一种基于蚁群优化算法的网格任务映射策略(ACO-GTM)。该算法通过人工蚂蚁在构建图上行走构建初始解,利用最优改进2-选择局部搜索方法对初始解进行局部优化,并采用全局信息素更新与局部信息素更新相结合的信息素更新策略。最后通过实验与其他算法进行比较,表明所提出的映射算法在最优跨度和负载平衡方面具有明显的优越性。     

Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics

In this paper, we discuss a scheduling problem for parallel batch machines where the jobs have ready times. Problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). In addition, we consider precedence constraints among the jobs. Such constraints arise, for example, in scheduling subproblems of the shifting bottleneck heuristic when complex job shop scheduling problems are tackled. We use the total weighted tardiness as the performance measure to be optimized. Hence, the problem is NP-hard and we have to rely on heuristic solution approaches. We consider a variable neighborhood search (VNS) scheme and a greedy randomized adaptive search procedure (GRASP) to compute efficient solutions. We assess the performance of the two metaheuristics based on a large set of randomly generated problem instances and based on instances from the literature. The obtained computational results demonstrate that VNS is a very fast heuristic that quickly leads to high-quality solutions, whereas the GRASP is slightly outperformed by the VNS approach. However, the GRASP approach has the advantage that it can be parallelized in a more natural manner compared to VNS.     

应用LK算法求解旅行商问题的混合蚂蚁算法

目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法,文章通过对几种局部搜索的灵活运用,并结合改进的接受准则接受局部优化解,提出了一种高效的混合蚂蚁算法。算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵,加快收敛速度,后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受,有效地避免陷入局部最优,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。