A hybrid method for the Probabilistic Maximal Covering Location–Allocation Problem

This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.     

Variable neighborhood search for the Vertex Separation Problem

The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances.     

Parallel hybrid metaheuristics for the flexible job shop problem

A parallel approach to flexible job shop scheduling problem is presented in this paper. We propose two double-level parallel metaheuristic algorithms based on the new method of the neighborhood determination. Algorithms proposed here include two major modules: the machine selection module refer to executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, therefore we call this method meta²heuristics. We carry out a computational experiment using Graphics Processing Units (GPU). It was possible to obtain the new best known solutions for the benchmark instances from the literature.     

A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times

We present a systematic comparison of hybrid evolutionary algorithms (HEAs), which independently use six combinations of three crossover operators and two population updating strategies, for solving the single machine scheduling problem with sequence-dependent setup times. Experiments show the competitive performance of the combination of the linear order crossover operator and the similarity-and-quality based population updating strategy. Applying the selected HEA to solve 120 public benchmark instances of the single machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness widely used in the literature, we achieve highly competitive results compared with the exact algorithm and other state-of-the-art metaheuristic algorithms in the literature. Meanwhile, we apply the selected HEA in its original form to deal with the unweighted 64 public benchmark instances. Our HEA is able to improve the previous best known results for one instance and match the optimal or the best known results for the remaining 63 instances in a reasonable time.     

带准备时间的单机调度问题的混合进化算法研究

提出了一种混合进化算法（HEA）用于求解具有序列相关依赖且带准备时间的单机调度问题, 其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点, 例如在局部搜索中采用了一种新提出的基于块移动的邻域结构, 这种邻域结构合理地限制了搜索空间, 提高了算法的搜索效率; 在HEA中采用了一种新的组合算子——块顺序交叉算符（BOX）来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试, HEA改进了9个算例在当前文献中的最优解, 表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较, 表明了HEA算法的优势。     

A hybrid metaheuristic approach for the capacitated p-median problem

The capacitated p-median problem (CPMP) seeks to obtain the optimal location of p medians considering distances and capacities for the services to be given by each median. This paper presents an efficient hybrid metaheuristic algorithm by combining a proposed cutting-plane neighborhood structure and a tabu search metaheuristic for the CPMP. In the proposed neighborhood structure to move from the current solution to a neighbor solution, an open median is selected and closed. Then, a linear programming (LP) model is generated by relaxing binary constraints and adding new constraints. The generated LP solution is improved using cutting-plane inequalities. The solution of this strong LP is considered as a new neighbor solution. In order to select an open median to be closed, several strategies are proposed. The neighborhood structure is combined with a tabu search algorithm in the proposed approach. The parameters of the proposed hybrid algorithm are tuned using design of experiments approach. The proposed algorithm is tested on several sets of benchmark instances. The statistical analysis shows efficiency and effectiveness of the hybrid algorithm in comparison with the best approach found in the literature.     

Effective local search algorithms for high school timetabling problems

This paper addresses the high school timetabling problem. The problem consists in building weekly timetables for meetings between classes and teachers with the goal of minimizing violations of specific requirements. In the last decades, several mixed-integer programs have been proposed and tested for this family of problems. However, medium and large size instances are still not effectively solved by these programs using state-of-the-art solvers and the scientific community has given special attention to the devising of alternative soft computing algorithms. In this paper, we propose a soft computing approach based on Iterated Local Search and Variable Neighborhood Search metaheuristic frameworks. Our algorithms incorporate new neighborhood structures and local search routines to perform an effective search. We validated the proposed algorithms on variants of the problem using seven public instances and a new dataset with 34 real-world instances including large cases. The results demonstrate that the proposed algorithms outperform the state-of-the-art approaches in both cases, finding the best solutions in 38 out of the 41 tested instances.     

一类基于FSP问题Block性质的快速TS算法

为解决现有算法在求解大规模流水线调度问题（FSP）时计算时间过长的问题,从缩小邻域的角度出发,提出一种基于FSP问题Block性质的快速禁忌搜索（TS）算法．利用Block性质．算法在保证不丢失最优解的基础上．将邻域中大部分劣解排除．将搜索重点集中在邻域中“最优希望”的区域,以缩小邻域和减少计算时闻．数值仿真实验表明,该算法能在较短时间内获得大规模FSP问题的满意解．     

A tabu search based hybrid evolutionary algorithm for the max-cut problem

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm.     

Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood search, and is then further refined by the Tabu search algorithm with back-jump tracking for a sequencing decision. The resultant solution is used to maintain the medium-term memory where the best solutions are stored. A path-relinking heuristics is designed to generate diverse solutions in the most promising areas. An improved version of the algorithm is then developed by incorporating an effective dimension-oriented intensification search to find solutions that are located near extreme solutions. The proposed algorithms are tested on benchmark instances and its experimental performance is compared with that of algorithms in the literature. Comparison results show that the proposed algorithms are competitive in terms of its computation performance and solution quality.     

An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.     

Lateness minimization with Tabu search for job shop scheduling problem with sequence dependent setup times

We tackle the job shop scheduling problem with sequence dependent setup times and maximum lateness minimization by means of a tabu search algorithm. We start by defining a disjunctive model for this problem, which allows us to study some properties of the problem. Using these properties we define a new local search neighborhood structure, which is then incorporated into the proposed tabu search algorithm. To assess the performance of this algorithm, we present the results of an extensive experimental study, including an analysis of the tabu search algorithm under different running conditions and a comparison with the state-of-the-art algorithms. The experiments are performed across two sets of conventional benchmarks with 960 and 17 instances respectively. The results demonstrate that the proposed tabu search algorithm is superior to the state-of-the-art methods both in quality and stability. In particular, our algorithm establishes new best solutions for 817 of the 960 instances of the first set and reaches the best known solutions in 16 of the 17 instances of the second set.     

Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties

This paper addresses the single machine scheduling problem with distinct time windows and sequence-dependent setup times. The objective is to minimize the total weighted earliness and tardiness. The problem involves determining the job execution sequence and the starting time for each job in the sequence. An implicit enumeration algorithm denoted IE and a general variable neighborhood search algorithm denoted GVNS are proposed to determine the job scheduling. IE is an exact algorithm, whereas GVNS is a heuristic algorithm. In order to define the starting times, an O(n²) idle time insertion algorithm (ITIA) is proposed. IE and GVNS use the ITIA algorithm to determine the starting time for each job. However, the IE algorithm is only valid for instances with sequence-independent setup times, and takes advantage of theoretical results generated for this problem. Computational experiments show that the ITIA algorithm is more efficient than the only other equivalent algorithm found in the literature. The IE algorithm allows the optimal solutions of all instances with up to 15 jobs to be determined within a feasible computational time. For larger instances, GVNS produces better-quality solutions requiring less computational time compared with the other algorithm from the literature.     

ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design

Heuristics and metaheuristics are inevitable ingredients of most of the general purpose ILP solvers today, because of their contribution to the significant boost of the performance of exact methods. In the field of bi/multi-objective optimization, to the best of our knowledge, it is still not very common to integrate ILP heuristics into exact solution frameworks. This paper aims to bring a stronger attention of both the exact and metaheuristic communities to still unexplored possibilities for performance improvements of exact and heuristic multi-objective optimization algorithms.We focus on bi-objective optimization problems whose feasible solutions can be described as 0/1 integer linear programs and propose two ILP heuristics, boundary induced neighborhood search (BINS) and directional local branching. Their main idea is to combine the features and explore the neighborhoods of solutions that are relatively close in the objective space. A two-phase ILP-based heuristic framework relying on BINS and directional local branching is introduced. Moreover, a new exact method called adaptive search in objective space (ASOS) is also proposed. ASOS combines features of the ϵ-constraint method with the binary search in the objective space and uses heuristic solutions produced by BINS for guidance. Our new methods are computationally evaluated on two problems of particular relevance for the design of FTTx-networks. Comparison with other known exact methods (relying on the exploration of the objective space) is conducted on a set of realistic benchmark instances representing telecommunication access networks from Germany.     

Applying two efficient hybrid heuristics for hub location problem with fully interconnected backbone and access networks

This paper considers the design of two-layered networks with fully interconnected backbone and access networks. The problem, a specific application of hub location to network design, is known as fully interconnected network design problem (FINDP). A novel mathematical programming formulation advantageous over an earlier formulation is presented to model the problem. Two hybrid heuristics are proposed to solve the problem, namely SA_VNS and TS_VNS which incorporate a variable neighborhood search (VNS) algorithm into the framework of simulated annealing (SA) and tabu search (TS). The proposed algorithms are able to easily obtain the optimal solutions for 24 small instances existing in the literature in addition to efficiently solve new generated medium and large instances. Results indicate that the proposed algorithms generate high quality solutions in a quite short CPU time.     

Finding low autocorrelation binary sequences with memetic algorithms

This paper deals with the construction of binary sequences with low autocorrelation, a very hard problem with many practical applications. The paper analyzes several metaheuristic approaches to tackle this kind of sequences. More specifically, the paper provides an analysis of different local search strategies, used as stand-alone techniques and embedded within memetic algorithms. One of our proposals, namely a memetic algorithm endowed with a Tabu Search local searcher, performs at the state-of-the-art, as it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature. Moreover, this algorithm is also able to provide new best-known solutions for large instances of the problem. In addition, a variant of this algorithm that explores only a promising subset of the whole search space (known as skew-symmetric sequences) is also analyzed. Experimental results show that this new algorithm provides new best-known solutions for very large instances of the problem.     

Iterated local search heuristics for the Vehicle Routing Problem with Cross-Docking

This work addresses the Vehicle Routing Problem with Cross-Docking (VRPCD). The problem consists in defining a minimum cost set of routes for a fleet of vehicles that meets the demands of products for a set of suppliers and customers. The vehicles leave a single Cross-Dock (CD) towards the suppliers, pick up products and return to the CD, where products can be exchanged before being delivered to their customers. The vehicle routes must respect the vehicle capacity constraints, as well as the time window constraints. We adapted a constructive heuristic and six local search procedures from the literature of VRP, and made them efficient in the presence of the synchronization constraints of VRPCD. Besides, we propose three Iterated Local Search (Lourenço et al., 2010) heuristics for VRPCD. The first heuristic is a standard implementation of ILS, while the second extends the classic ILS framework by keeping a set of elite solutions, instead of a single current solution. The latter set is used in a restart procedure. As far as we can tell, this is the first ILS heuristic in the literature that keeps a population of current elite solutions. The third heuristic is an extension of the second that relies on an intensification procedure based on an Integer Programming formulation for the Set Partitioning problem. The latter allows a neighborhood with an exponential number of neighbors to be efficiently evaluated. We report computational results and comparisons with the best heuristics in the literature. Besides, we also present a new set with the largest instances in the literature of VRPCD, in order to demonstrate that the improvements we propose for the ILS metaheuristic are efficient even for large size instances. Results show that the best of our heuristics is competitive with the best heuristics in the literature of VRPCD. Besides, it improved the best solution known for half of the benchmark instances in the literature.     

Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an Anarchic Society Optimization algorithm

This paper addresses a ternary-integration scheduling problem that incorporates employee timetabling into the scheduling of machines and transporters in a job-shop environment with a finite number of heterogeneous transporters where the objective is to minimize the completion time of all jobs. The problem is first formulated as a mixed-integer linear programming model. Then, an Anarchic Society Optimization (ASO) algorithm is developed to solve large-sized instances of the problem. The formulation is used to solve small-sized instances and to evaluate the quality of the solutions obtained for instances with larger sizes. A comprehensive numerical study is carried out to assess the performance of the proposed ASO algorithm. The algorithm is compared with three alternative metaheuristic algorithms. It is also compared with several algorithms developed in the literature for the integrated scheduling of machines and transporters. Moreover, the algorithms are tested on a set of adapted benchmark instances for an integrated problem of machine scheduling and employee timetabling. The numerical analysis suggests that the ASO algorithm is both effective and efficient in solving large-sized instances of the proposed integrated job-shop scheduling problem.     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

Path relinking for the vertex separator problem

This paper presents the first population-based path relinking algorithm for solving the NP-hard vertex separator problem in graphs. The proposed algorithm employs a dedicated relinking procedure to generate intermediate solutions between an initiating solution and a guiding solution taken from a reference set of elite solutions (population) and uses a fast tabu search procedure to improve some selected intermediate solutions. Special care is taken to ensure the diversity of the reference set. Dedicated data structures based on bucket sorting are employed to ensure a high computational efficiency. The proposed algorithm is assessed on four sets of 365 benchmark instances with up to 20,000 vertices, and shows highly comparative results compared to the state-of-the-art methods in the literature. Specifically, we report improved best solutions (new upper bounds) for 67 instances which can serve as reference values for assessment of other algorithms for the problem.