Search

Encouraged by the success of applying metaheuristics algorithms to other ranking-based problems (Kemeny ranking problem and parameter estimation for Mallows distributions), in this paper we deal with the rank aggregation problem (RAP), which can be viewed as a generalization of the Kemeny problem to arbitrary rankings. While in the Kemeny problem the input is a set of permutations, the RAP consists in obtaining the consensus permutation for a sample of arbitrary rankings. This is an NP-hard problem which can be approached by using greedy heuristic algorithms (e.g. Borda). Such algorithms are fast but the solutions so obtained are far to be optimal. In this paper, we propose the use of more complex search processes to deal with the RAP. In particular, we perform a comparative study among some local-based search metaheuristics: hill climbing (HC), iterated local search (ILS), variable neighborhood search (VNS) and greedy randomized adaptive search procedure (GRASP). We provide a complete analysis of the experimental study regarding accuracy and number of iterations required to reach the best solution. From the results we can conclude that the selection of a suitable neighborhood plays a key role, and that depending on the available resources (cpu time) a different algorithm (VNS, ILS or GRASP) could be the proper choice.

This paper is concerned with the multiple container loading problem with rectangular boxes of different sizes and one or more containers, which means that the boxes should be loaded into the containers so that the waste space in the containers are minimized or the total value of the boxes loaded into the containers is maximized. Several approaches have been taken to solve this problem (Ivancic et al., 1989; Mohanty et al., 1994; George, 1996; Bortfeldt, 2000; Eley, 2002; Eley, 2003; Takahara, 2005; Takahara, 2006). The aim of this paper is to propose an efficient greedy approach for the multiple container loading problem and to contribute to develop a load planning software and applications. The problem considered in this paper is the three-dimensional packing problem, therefore it is known to NP-hard. This implies that no simple algorithm has been found so far. In this paper this problem is solved by a relatively simple method using a two-stage strategy. Namely, all boxes are numbered and for the sequence of the numbers a greedy algorithm of loading boxes into containers is considered. This greedy algorithm is based on first-fit concept (Johnson et al., 1974) and determines the arrangement of each box. This algorith try to load the boxes all kind of containers and select the best arrangement result. It’s requires a box loading sequence and a set of orientation orders of each box type for each container type. Each box is tried to load according to these dynamic parameters. Moreover, a static parameter overhang ratio is introduced here. This is a percentage of the bottom face area of the loading box that isn’t supported with other boxes that are below. As shown by Takahara (Takahara, 2006), if this parameter is different, the arrangement given this algorithm is different in spite of using a same pair of the loading sequence and the orientation orders. Some initial pairs of solution, that is a box loading sequence and a set of orientation orders of each box type, are selected among some rules, which are given beforehand. This solution is altered by using a multi-start local search approach. The local search approach is used to find a good pair of solutions that is brought an efficient arrangement by the greedy loading algorithm. The arrangement obtained in the iterations is estimated by volume utilization or total value of the loaded boxes. The effectiveness of the proposed approach is shown by comparing the results obtained with the approaches presented by using benchmark problems from the literature. Finally, the layout examples by the application using the proposed approach for container loading are illustrated. O pe n A cc es s D at ab as e w w w .in te ch w eb .o rg

Paper waste in the mockups design with regular, irregular, and amorphous patterns is a critical problem in digital printing presses. Paper waste reduction directly impacts production costs, generating business and environmental benefits. This problem can be mapped to the two-dimensional irregular bin-packing problem. In this paper, an iterated local search algorithm using a novel neighborhood structure to detect overlaps between amorphous shapes is introduced. This algorithm is used to solve the paper waste problem, modeled as one 2D irregular bin-packing problem. The experimental results show that this approach works efficiently and effectively to detect and correct the overlaps between regular, irregular, and amorphous figures.

International audience; Relaxed correlation clustering (RCC) is a vertex partitioning problem that aims at minimizing the so-called relaxed imbalance in signed graphs. RCC is considered to be an NP-hard unsupervised learning problem with applications in biology, economy, image recognition and social network analysis. In order to solve it, we propose two linear integer programming formulations and a local search-based metaheuristic. The latter relies on auxiliary data structures to efficiently perform move evaluations during the search process. Extensive computational experiments on existing and newly proposed benchmark instances demonstrate the superior performance of the proposed approaches when compared to those available in the literature. While the exact approaches obtained optimal solutions for open problems, the proposed heuristic algorithm was capable of finding high quality solutions within a reasonable CPU time. In addition, we also report improving results for the symmetrical version of the problem. Moreover, we show the benefits of implementing the efficient move evaluation procedure that enables the proposed metaheuristic to be scalable, even for large-size instances.

The Green Vehicle Routing and Scheduling Problem (GVRSP) aims to minimize carbon Dioxide Emissions (CO2) in logistics systems through better planning of deliveries made by a fleet of vehicles. In this paper, the GVRSP considers heterogeneous vehicles, time-varying traffic congestion, capacity constraints and the delivery can be fractionated. The GVRSP also allows vehicles to stop on arcs, so vehicle is allowed to travel an arc in multiple time periods. We present a mathematical formulation to describe the problem and a hybrid algorithm that combines the metaheuristic Iterated Local Search (ILS), the Random Variable Neighborhood Descent (RVND) procedure and an exact Set Covering model. The results obtained are compared with the state of the art and we show that the proposed approach has a strong performance.

In this work, we introduce the Flowshop Scheduling Problem with Delivery Dates and Cumulative Payoffs. This problem is a variation of the flowshop scheduling problem with job release dates that maximizes the total payoff with a stepwise job objective function. This paper contributes towards proposing a mathematical formulation for this new problem and an original constructive heuristic. Additionally, we develop a new benchmark of 300 hard instances which are available in a public repository. Besides, we provide primal and dual bounds for them. Extensive computational experiments were carried out taking into account classical constructive heuristics and hybrid local searches. Results show the merit of the FF heuristic when compared to other classical heuristics for flowshop scheduling problems. Additionally, we compare an Iterated Local Search (ILS), an Iterated Greedy Search (IGS), and a Biased Random-Key Genetic Algorithm (BRKGA), both customized for the studied problem, and a commercial mixed integer programming solver. The comparison between these methods showed that the BRKGA starting with a solution from FF heuristic is able to find the best solutions in a very short period of time. Iterated local Search and the commercial solver presented significantly worse results than the aforementioned methods.

A circle packing problem involves packing given circles into a container. The objective is to minimize the size of the container without causing any overlap. This paper focuses on a representative circle packing problem where the circles are unequal and the container is a square, called Packing Unequal Circles into a Square (PUCS). It proposes a memetic algorithm to solve the problem. The memetic algorithm can be regarded as a combination of a genetic algorithm (GA) and an iterated local search (ILS). It is composed of a local search phase and a global transformation phase. The global transformation phase evolves a population; the local search phase optimizes the offsprings generated by the global transformation phase. The proposed approach exhibits several novel features in its global transformation phase, such as the z-crossover operator based on the symmetry of the container and the complementarity of the configuration, a perturbation operator inspired by gene-fragment-insertion, a reproduction selector based on the genetic relationships of the individuals, and a hybrid population updating strategy based on the diversity of the reproduction operators. Experimental results show that the memetic algorithm is effective for the problem.

The traveling repairman problem with profits is addressed.A new mixed-integer linear model is developed for the problem.A simple metaheuristic algorithm is developed for its solution.The algorithm integrates GRASP with ILS.46 best results are improved for the TRPP instances. Traveling Repairman Problem with profits (TRPP) is an extension of the Traveling Repairman Problem (TRP), where there is not an obligation to visit all vertices. A time-dependent profit is associated with each vertex and the objective is to maximize the total collected revenue. In this paper, we initially develop a new mixed-integer linear model capable of solving small size instances for the TRPP. To solve medium and large size instances, a simple and effective metaheuristic algorithm (GRASP-ILS) is introduced for the TRPP, which combines Greedy Randomized Adaptive Search Procedure (GRASP) for initial solution construction and Iterated Local Search (ILS) with an adaptive perturbation mechanism for solution improvement. The proposed GRASP-ILS is tested on the TRPP benchmark instances derived from the literature. The results indicate that the developed GRASP-ILS can produce efficient and effective solutions for the TRPP. Particularly, it has been observed that the developed GRASP-ILS has improved the best solutions for 46 instances and obtained all the best known results for the remaining instances in a reasonable computation time.

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.

The ED-LS method prioritizes defending those nodes that in the current graph state St have:1.a lower number of edges separating them from fire E(St,v).2.a higher number of edges connecting to untouched nodes D(St,v) among nodes equidistant from fireThus, in the example, the priority of nodes is: a, b, c.Display Omitted The Firefighter Problem (FFP) concerns stopping a threat spreading in a graph.The paper presents a new local search method (ED-LS) for the multiobjective FFP.The ED-LS uses heuristics to reduce the computational cost.ED-LS is tested with the MOEA/D and NSGA-II algorithms as global searches.Experiments show that the proposed approach effectively improves the results. One of the approaches to combinatorial optimization is to use global search methods, such as evolutionary algorithms combined with local search procedures. Local search can be very effective in improving the quality of solutions, however, searching large neighbourhoods can be computationally expensive. In this paper a new local search method is described that is dedicated to the Firefighter Problem (FFP). The Firefighter Problem concerns protecting nodes of a graph in order to stop a threat that is spreading in the graph. Because the resources used for protection are limited, the goal is to find the best order in which the nodes are protected and thus the FFP is a combinatorial optimization problem. One of the key elements in the design of a local search method is the definition of the neighbourhoods of solutions from which the local search starts. The method proposed in this paper (ED-LS) aims at lowering the computational cost of the local search by reducing, based on certain heuristics, the size of these neighbourhoods.In this paper the ED-LS is compared to an optimization without the local search, a local search using non-reduced neighbourhoods and a method that reduces the neighbourhood by checking only some randomly selected neighbours. The results show that the ED-LS improves the performance of the algorithm with respect to no local search at all and to the local search using non-reduced neighbourhoods, supporting the view that reducing the size of the neighbourhood is beneficial. Also, the ED-LS produces better results than when the size of the neighbourhood is reduced randomly, which means that the proposed heuristics are indeed selecting promising neighbours effectively. In the last part of the experiments the ED-LS is further improved to obtain faster improvement of solutions at the beginning of the optimization run.

© 2017 The Operational Research Society. The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances. ispartof: Journal of the Operational Research Society vol:68 issue:68 pages:861-876 status: published

We address the important step of determining an effective subset of heuristics in selection hyper-heuristics. Little attention has been devoted to this in the literature, and the decision is left at the discretion of the investigator. The performance of a hyper-heuristic depends on the quality and size of the heuristic pool. Using more than one heuristic is generally advantageous, however, an unnecessary large pool can decrease the performance of adaptive approaches. Our goal is to bring methodological rigour to this step. The proposed methodology uses non-parametric statistics and fitness landscape measurements from an available set of heuristics and benchmark instances, in order to produce a compact subset of effective heuristics for the underlying problem. We also propose a new iterated local search hyper-heuristic using multi-armed bandits coupled with a change detection mechanism. The methodology is tested on two real-world optimization problems: course timetabling and vehicle routing. The proposed hyper-heuristic with a compact heuristic pool, outperforms state-of-the-art hyper-heuristics and competes with problem-specific methods in course timetabling, even producing new best-known solutions in 5 out of the 24 studied instances.

A local optima network (LON) compresses relevant features of fitness landscapes in a complex network, where nodes are local optima and edges represent transition probabilities between different basins of attraction. Previous work has found that the PageRank centrality of local optima can be used to predict the success rate and average fitness achieved by local search based metaheuristics. Results are available for LONs where edges describe either basin transition probabilities or escape edges. This paper studies the interplay between the type of LON edges and the ability of the PageRank centrality for the resulting LON to predict the performance of local search based metaheuristics. It finds that LONs are stochastic models of the search heuristic. Thus, to achieve an accurate prediction, the definition of the LON edges must properly reflect the type of diversification steps used in the metaheuristic. LONs with edges representing basin transition probabilities capture well the diversification mechanism of simulated annealing which sometimes also accepts worse solutions that allow the search process to pass between basins. In contrast, LONs with escape edges capture well the diversification step of iterated local search, which escapes from local optima by applying a larger perturbation step.

We study a practical variant of the vehicle routing problem with compartments.We propose a heuristic solution using tabu search embedded in iterated local search.We report results of experiments which analyze the heuristic performance in detail.We find that the proposed approach dominates existing approaches in nearly all cases.We further find that allowing split demands have a limited effect. We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into a iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it to results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.

Methods for automatic algorithm configuration integrate some search mechanism for generating candidate algorithm configurations and mechanisms for handling the stochasticity of the algorithm configuration problem. One popular algorithm configurator is ParamILS, which searches the configuration space using an iterated local search algorithm. In our research, we explore variable neighborhood search mechanisms as an alternative for the one-exchange neighborhood that is searched in the local search phase of ParamILS. In this article, we explore a reduced variable neighborhood search for automatic configuration. Our experimental results are promising and indicate directions for extending our work.

[EN] In practice due dates usually behave more like intervals rather than specific points in time. This paper studies hybrid flowshops where jobs, if completed inside a due window, are considered on time. The objective is therefore the minimization of the weighted earliness and tardiness from the due window. This objective has seldom been studied and there are almost no previous works for hybrid flowshops. We present methods based on the simple concepts of iterated greedy and iterated local search. We introduce some novel operators and characteristics, like an optimal idle time insertion procedure and a two stage local search where, in the second stage, a limited local search on a exact representation is carried out. We also present a comprehensive computational campaign, including the reimplementation and comparison of 9 competing procedures. A thorough evaluation of all methods with more than 3000 instances shows that our presented approaches yield superior results which are also demonstrated to be statistically significant. Experiments also show the contribution of the new operators in the presented methods. (C) 2016 Elsevier Ltd. All rights reserved., The authors would like to thank Professors Lofti Hidri and Mohamed Haouari for sharing with us the source codes and explanations of the lower bounds. Quan-Ke Pan is supported by the National Natural Science Foundation of China (Grant No. 51575212), Program for New Century Excellent Talents in University (Grant No. NCET-13-0106), Science Foundation of Hubei Province in China (Grant No. 2015CFB560), Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20130042110035), Key Laboratory Basic Research Foundation of Education Department of Liaoning Province (LZ2014014), Open Research Fund Program of the State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, China. Ruben Ruiz and Pedro Alfaro-Fernandez are supported by the Spanish Ministry of Economy and Competitiveness, under the project "SCHEYARD Optimization of Scheduling Problems in Container Yards" (No. DPI2015-65895-R) financed by FEDER funds.

UNIRANDI is a stochastic local search algorithm that performs line searches from starting points along good random directions. In this paper, we focus on a modified version of this method. The new algorithm, addition to the random directions, considers more promising directions in order to speed up the optimization process. The performance of the new method is tested empirically on standard test functions in terms of function evaluations, success rates, error values, and CPU time. It is also compared to the previous version as well as other local search methods. Numerical results show that the new method is promising in terms of robustness and efficiency.

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.

Display Omitted The multiple objectives and the sequence-dependent setup times are considered in the permutation flowshop scheduling problem.The extension of conventional single-objective iterated local search (ILS) to solve multi-objective combinatorial optimization problem.A Pareto based variable depth search is designed to act as the multi-objective local search phase in the multi-objective ILS.The experimental results on some benchmark problems show that the proposed multi-objective ILS outperforms several powerful multi-objective evolutionary algorithms in the literature.A multi-objective iterated local search is proposed. Due to its simplicity yet powerful search ability, iterated local search (ILS) has been widely used to tackle a variety of single-objective combinatorial optimization problems. However, applying ILS to solve multi-objective combinatorial optimization problems is scanty. In this paper we design a multi-objective ILS (MOILS) to solve the multi-objective permutation flowshop scheduling problem with sequence-dependent setup times to minimize the makespan and total weighted tardiness of all jobs. In the MOILS, we design a Pareto-based variable depth search in the multi-objective local search phase. The search depth is dynamically adjusted during the search process of the MOILS to strike a balance between exploration and exploitation. We incorporate an external archive into the MOILS to store the non-dominated solutions and provide initial search points for the MOILS to escape from local optima traps. We compare the MOILS with several multi-objective evolutionary algorithms (MOEAs) shown to be effective for treating the multi-objective permutation flowshop scheduling problem in the literature. The computational results show that the proposed MOILS outperforms the MOEAs.

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA. A machine-learning based multi-objective memetic algorithm is proposed.An individual archive is adopted in the generation of new solutions.A machine-learning based two-phase local search is presented.Computational results show that the ML-MOMA is superior to other algorithms.

The article describes a solution approach for the multi-mode, resource-constrained multi-project scheduling problem. Our key ideas are based on the concepts of Variable Neighborhood Search, together with Iterated Local Search. A particular focus of this work is devoted towards the parallel implementation of such local search solution techniques. With the increasing availability of parallel (multi-core) computer hardware, we believe that such techniques are about to gain attractiveness in the future. Experiments have been conducted on benchmark instances of the MISTA 2013 Challenge, as well as on the well-known MMLIB -datasets. The approach described in this article ranked second in the Challenge, and found new best results to 1371 of the 4320 MMLIB -instances. Note that the source-code of our implementation has been made available under http://dx.doi.org/10.17632/cw95t56hjv.1 . The software may be freely used for non-profit (research/education) purposes.

Modulation diversity (MoDiv) is a simple and practical transmission enhancement technique that utilizes different modulation mappings to reduce packet loss rate and achieve higher link throughput. MoDiv is particularly meaningful and effective in Hybrid-Automatic Repeat reQuest (HARQ) systems. We study the deployment and optimization of MoDiv for HARQ in a MIMO-coordinated multi-point scenario under Rician fading channel to mitigate packet loss. We formulate the design optimization of MoDiv into a quadratic 3-D assignment problem, then solve it using a modified iterated local search method. Numerical results demonstrate clear performance gain over simple retransmissions and over a heuristic design under fading channels.

A 1-block in a binary matrix is any maximal sequence of 1s occurring consecutively in the same row. Consecutive block minimization (CBM) requires a permutation of the matrix columns that minimizes the number of 1-blocks. CBM is NP-hard for matrices with a maximum of two 1s per row and an arbitrary number of 1s per column. First, we prove that it is NP-hard even when it is restricted to binary matrices having a maximum of two 1s per row and a maximum of three 1s per column. In these circumstances, a reasonable and traditional approach to solve the problem is to design a heuristic capable of finding good configurations within acceptable computation times. This paper proposes an Iterated Local Search (ILS) metaheuristic. A binary matrix satisfies the strong consecutive ones property (is strongly C1P) if its non-zero entries occur consecutively in each row. It is C1P if there is a permutation of its columns such that the resulting matrix is strongly C1P. In this study, two necessary conditions for a binary matrix to be C1P are provided, each allowing to define a neighborhood for local search (LS). In addition, a third large-scale neighborhood is proposed where the local optimal solution can be directly obtained by solving a Traveling Salesman Problem (TSP). It is noteworthy that the three neighborhoods are being proposed for the first time. The ILS algorithm is tested on a dataset from the OR-library, composed of thirty large-scale set covering instances of varying sizes and densities. Comparison with two TSP solvers as well as with a recently published metaheuristic, from both accuracy and computing time points of view, allows to conclude that the proposed method competes favorably with the methods available in the literature.

The emergence of Gaussian model-based partitioning as a viable alternative to K-means clustering fosters a need for discrete optimization methods that can be efficiently implemented using model-based criteria. A variety of alternative partitioning criteria have been proposed for more general data conditions that permit elliptical clusters, different spatial orientations for the clusters, and unequal cluster sizes. Unfortunately, many of these partitioning criteria are computationally demanding, which makes the multiple-restart (multistart) approach commonly used for K-means partitioning less effective as a heuristic solution strategy. As an alternative, we propose an approach based on iterated local search (ILS), which has proved effective in previous combinatorial data analysis contexts. We compared multistart, ILS and hybrid multistart-ILS procedures for minimizing a very general model-based criterion that assumes no restrictions on cluster size or within-group covariance structure. This comparison, which used 23 data sets from the classification literature, revealed that the ILS and hybrid heuristics generally provided better criterion function values than the multistart approach when all three methods were constrained to the same 10-min time limit. In many instances, these differences in criterion function values reflected profound differences in the partitions obtained.

We propose a method that combines Column Generation (CG) and Iterated Local Search (ILS) to solve the Capacitated Arc-Routing Problem (CARP). One of the goals is to integrate into the ILS (some of) the duality information that underpins the CG paradigm. The CARP is expressed in a space of permutations and sub-permutations (sequences, routes) of the set of required edges. For this, the ILS uses an exact decoder that maps any permutation s to a list of sequences (routes) of minimum cost servicing all edges in the order s(1), s(2), s(3), etc. This permutation space is explored both by an ILS process and a CG process that run in parallel and that communicate by exchanging sequences. The first use of the CG paradigm in ILS is the following: all sequences discovered by CG are sent to the ILS process that can inject them into the current ILS solution. The second application of CG in ILS is a “CG improver” operator that acts on the current ILS solution, so as to (try to) improve it by running several CG iterations. The first half of the paper describes the method in a general framework based on sequences, permutations and set covering. The second part is devoted to more specialized Arc-Routing techniques. For instance, the CG convergence could be accelerated by factors of tens or even hundreds by exploiting two ideas in the Dynamic Programming (DP) pricing: (i) avoid as much as possible to traverse edges without service, and (ii) record only non-dominated DP states using a fast-access data structure mixing an array and a red-black tree. Regarding the ILS, we show that the permutation-level search can be substantially improved if the exact decoder is reinforced by a deterministic post-decoder acting on explicit routes. The general results are competitive (reducing the best-known gap of five instances) and certain ideas could be potentially useful for other set-covering or permutation problems.

A partial Latin square (PLS) is a partial assignment of n symbols to an $$n\times n$$n×n grid such that, in each row and in each column, each symbol appears at most once. The PLS extension problem is an NP-hard problem that asks for a largest extension of a given PLS. We consider the local search such that the neighborhood is defined by (p, q)-swap , i.e., the operation of dropping exactly p symbols and then assigning symbols to at most q empty cells. As a fundamental result, we provide an efficient $$(p,\infty )$$(p,ź)-neighborhood search algorithm that finds an improved solution or concludes that no such solution exists for $$p\in \{1,2,3\}$$pź{1,2,3}. The running time of the algorithm is $$O(n^{p+1})$$O(np+1). We then propose a novel swap operation, Trellis-swap, which is a generalization of (p, q)-swap with $$p\le 2$$p≤2. The proposed Trellis-neighborhood search algorithm runs in $$O(n^{3.5})$$O(n3.5) time. The iterated local search (ILS) algorithm with Trellis-neighborhood is more likely to deliver a high-quality solution than not only ILSs with $$(p,\infty )$$(p,ź)-neighborhood but also state-of-the-art optimization solvers such as IBM ILOG CPLEX and LocalSolver.

This paper addresses to the flowshop scheduling problem with blocking constraints. The objective is to minimize the makespan criterion. We propose a hybrid combinatorial particle swarm optimization algorithm (HCPSO) as a resolution technique for solving this problem. At the initialization, different priority rules are exploited. Experimental study and statistical analysis were performed to select the most adapted one for this problem. Then, the swarm behavior is tested for solving a combinatorial optimization problem such as a sequencing problem under constraints. Finally, an iterated local search algorithm based on probabilistic perturbation is sequentially introduced to the particle swarm optimization algorithm for improving the quality of solution. The computational results show that our approach is able to improve several best known solutions of the literature. In fact, 76 solutions among 120 were improved. Moreover, HCPSO outperforms the compared methods in terms of quality of solutions in short time requirements. Also, the performance of the proposed approach is evaluated according to a real-world industrial problem. Highlights The blocking flowshop scheduling problem is very attractive problem in engineering. A particle swarm optimization approach is proposed. Extensive experiments are conducted to choose the initialization way. Improvement procedure is introduced based on iterated local search algorithm. A real-world case is solved by the proposed algorithm.

This paper presents an evolutionary algorithm for the fixed-charge multicommodity network design problem (MCNDP), which concerns routing multiple commodities from origins to destinations by designing a network through selecting arcs, with an objective of minimizing the fixed costs of the selected arcs plus the variable costs of the flows on each arc. The proposed algorithm evolves a pool of solutions using principles of scatter search, interlinked with an iterated local search as an improvement method. New cycle-based neighborhood operators are presented which enable complete or partial re-routing of multiple commodities. An efficient perturbation strategy, inspired by ejection chains, is introduced to perform local compound cycle-based moves to explore different parts of the solution space. The algorithm also allows infeasible solutions violating arc capacities while performing the "ejection cycles", and subsequently restores feasibility by systematically applying correction moves. Computational experiments on benchmark MCNDP instances show that the proposed solution method consistently produces high-quality solutions in reasonable computational times.

We study a multivehicle inventory routing problem (MIRP) in which supplier delivers one type of product along a finite planning horizon, using a homogeneous fleet of vehicles. The main objective is to minimize the total cost of storage and transportation. In order to solve MIRP, we propose an algorithm based on iterated local search (ILS) metaheuristic, using a variable neighborhood descent with random neighborhood ordering (RVND) in the local search phase. Moreover, we combined this algorithm with an exact procedure based on mathematical programming to solve specifically the inventory management as a subproblem. To validate our approach, computational tests were performed on 560 benchmark instances, achieving very competitive results in comparison to the best known algorithms.

This paper presents an Iterated Tabu Search and Variable Neighborhood Descent (ITS-VND) algorithm for packing unequal circles into a circular container (PUCC). The algorithm adapts the Tabu Search procedure of Iterated Tabu Search algorithms and proposes a Tabu Search and Variable Neighborhood Descent (TS-VND) procedure. We observe there are strong complementarities between the small circles and the large vacant places, and propose the insert neighborhood to match up the small circles with the large vacant places. Although the insert neighborhood is inefficient and time-consuming, it is an important supplement to the classic swap neighborhood as it could arrange the small circles properly. Predicated on these features, we employ the insert neighborhood only at chosen local minima of the swap neighborhood that shows promise for an improvement. The traditional Tabu Search procedure is then transformed into a hybrid procedure composed of two alternative parts, namely Variable Neighborhood Descent and Tabu Search respectively. Besides this reformed procedure, ITS-VND also incorporates other new features, such as an adaptive evaluation function, a novel method for accelerating the neighborhood exploration, and the “collision accidents” criterion for evaluating how intensively the area near the current solution has been explored. The computational results on three well established benchmark sets show that the proposed algorithm not only has a good discovery capability but also can provide good results within a reasonable time. For a total of 84 benchmark instances, the proposed algorithm improves the best-known results on 23 instances, matches 60, and only misses one.

This paper proposes a hybrid heuristic algorithm, based on the metaheuristics Greedy Randomized Adaptive Search Procedure, Iterated Local Search and Variable Neighborhood Descent, to solve the Clustered Traveling Salesman Problem (CTSP). Hybrid Heuristic algorithm uses several variable neighborhood structures combining the intensification (using local search operators) and diversification (constructive heuristic and perturbation routine). In the CTSP, the vertices are partitioned into clusters and all vertices of each cluster have to be visited contiguously. The CTSP is 𝒩𝒫-hard since it includes the well-known Traveling Salesman Problem (TSP) as a special case. Our hybrid heuristic is compared with three heuristics from the literature and an exact method. Computational experiments are reported for different classes of instances. Experimental results show that the proposed hybrid heuristic obtains competitive results within reasonable computational time.

Graphical abstractDisplay Omitted HighlightsAdd and delete operations are encoded as a list/string of integers (ADL).An effective hyper-heuristic approach operating with ADLs is proposed.Low level heuristics perform search over the space of feasible solutions.Proposed approach produces new best solutions to some instances.Proposed approach achieves generality across two variants of the timetabling problem. Hyper-heuristics are (meta-)heuristics that operate at a higher level to choose or generate a set of low-level (meta-)heuristics in an attempt of solve difficult optimization problems. Iterated local search (ILS) is a well-known approach for discrete optimization, combining perturbation and hill-climbing within an iterative framework. In this study, we introduce an ILS approach, strengthened by a hyper-heuristic which generates heuristics based on a fixed number of add and delete operations. The performance of the proposed hyper-heuristic is tested across two different problem domains using real world benchmark of course timetabling instances from the second International Timetabling Competition Tracks 2 and 3. The results show that mixing add and delete operations within an ILS framework yields an effective hyper-heuristic approach.

The optimal design of water distribution networks is a complex non-linear combinatorial optimization problem. It consists in finding the least-cost pipe configuration that satisfies hydraulic laws and customer requirements, using a limited set of available pipe types. In a previous paper De Corte and Sorensen, Eur J Oper Res 228 2013, 1-10, we have argued that state-of-the-art optimization algorithms proposed in this domain are unduly complicated and poorly tested. The main contribution of this article is a straightforward, fast, transparent, and effective iterated local search ILS algorithm that has at least equivalent performance when compared to the best approaches in the literature, but has a much simpler algorithmic structure. A full-factorial experiment is conducted to obtain the heuristic's best parameter settings. Contrary to existing algorithms, the ILS algorithm is additionally shown to perform well on a broad set of much more challenging HydroGen De Corte and Sorensen, Water Resour Manage 28 2014, 333-350 test instances. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 673, 187-198 2016

We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules. HighlightsWe propose a constructive heuristic for non-permutation flow shop scheduling.The constructive heuristic finds good makespans in a short time.We further propose a local search heuristic for the problem.The local search is significantly better than current non-permutation heuristics.The local search is competitive with and often improves best permutation schedules.We also find that non-permutation schedules reduce buffer requirements.

Batch processes are typically used to manufacture, among other, specialty and fine chemicals. As the construction of grassroot batch plants requires major investments, models for determining the optimal design of such plants have been developed over the past decades. These models are often formulated as Mixed Integer Linear Programming (MILP) models which are solved exactly. In a previous study, we introduced the concept of parallel production lines as a design option into existing mathematical plant design models. The design problem now also aims at optimising the number of production lines, their design and the allocation of products (and production quantities) to the installed lines. However, with this extension, the complexity increases significantly. To tackle this combinatorial divergence, we formulated a matheuristic solution approach which combines an iterated local search metaheuristic with exact MILP calculations. In this paper, the hybrid solution method is described and its performance, in comparison to an exact algorithm, is illustrated for several example problems. It was found that our matheuristic obtained very good solutions in significant lower computation time. As a consequence, this technique is suitable to solve more realistic instances and enables us to expand these design models with e.g. different objectives in the future.

The key idea underlying iterated local search is to focus the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm, typically a local search heuristic. The resulting search behavior can be characterized as iteratively building a chain of solutions of this embedded algorithm. The result is also a conceptually simple metaheuristic that nevertheless has led to state-of-the-art algorithms for many computationally hard problems. In fact, very good performance is often already obtained by rather straightforward implementations of the metaheuristic. In addition, the modular architecture of iterated local search makes it very suitable for an algorithm engineering approach where, progressively, the algorithms’ performance can be further optimized. Our purpose here is to give an accessible description of the underlying principles of iterated local search and a discussion of the main aspects that need to be taken into account for a successful application of it. In addition, we review the most important applications of this method and discuss its relationship to other metaheuristics.

The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of travelling salesperson fitness landscapes of different classes, including random and structured real-world instances of realistic size. Our study brings rigour to the characterisation of so-called funnels, and proposes an intensive and effective sampling procedure for extracting the networks. We propose enhanced visualisation techniques, including 3D plots and the incorporation of colour, sizes and widths, to reflect relevant aspects of the search process. This brings an almost tangible new perspective to the landscape and funnel metaphors. Our results reveal a much richer global structure than the suggestion of a ‘big-valley’ structure. Most landscapes of the tested instances have multiple valleys or funnels; and the number, disposition and interaction of these funnels seem to relate to search difficulty on the studied landscapes. We also find that the structured TSP instances feature high levels of neutrality, an observation not previously reported in the literature. We then propose ways of analysing and visualising these neutral landscapes.

International audience; In this study, we provide two approximate methods for solving both Unidirectional and Multidirectional Road Network problems with Disruptions and connecting requirements. These problems aim at defining alternative paths to deviate traffic flows, allowing the arc orientation to be reversed, such that the network remains strongly connected. The objectives are set to minimize the total travel cost and the number of reversed arcs. Two methods, a Biased Random Key Genetic Algorithm and an Iterated Local Search, are proposed. Numerical experiments with single objective and bi-objective versions are performed and results are hence compared to the exact method studied in previous works.

This paper studies a version of the fixed-charge multicommodity network design problem where in addition to the traditional costs of flow and design, congestion at nodes is explicitly considered. The problem is initially modeled as a nonlinear integer programming formulation and two solution approaches are proposed: (i) a reformulation of the problem as a mixed integer second order cone program to optimally solve the problem for small to medium scale problem instances, and (ii) an evolutionary algorithm using elements of iterated local search and scatter search to provide upper bounds. Extensive computational results on new benchmark problem instances and on real case data, are presented.

HighlightsWe deal with the problem of parameter estimation in Generalized Mallows model (GMM).We deal with 22 real datasets, all of them but one created by the authors.We have designed two experiments varying the maximum evaluations allowed.Obtained results significantly improve the previous competing approaches. This paper deals with the problem of parameter estimation in the generalized Mallows model (GMM) by using both local and global search metaheuristic (MH) algorithms. The task we undertake is to learn parameters for defining the GMM from a dataset of complete rankings/permutations. Several approaches can be found in the literature, some of which are based on greedy search and branch and bound search. The greedy approach has the disadvantage of usually becoming trapped in local optima, while the branch and bound approach, basically A* search, usually comes down to approximate search because of memory requirements, losing in this way its guaranteed optimality. Here, we carry out a comparative study of several MH algorithms (iterated local search (ILS) methods, variable neighborhood search (VNS) methods, genetic algorithms (GAs) and estimation of distribution algorithms (EDAs)) and a tailored algorithm A* to address parameter estimation in GMMs. We use 22 real datasets of different complexity, all but one of which were created by the authors by preprocessing real raw data. We provide a complete analysis of the experiments in terms of accuracy, number of iterations and CPU time requirements.