Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms

The well-known one-dimensional Bin Packing Problem (BPP) of whose variants arise in many real life situations is a challenging NP-Hard combinatorial optimization problem. Metaheuristics are widely used optimization tools to find (near-) optimal solutions for solving large problem instances of BPP in reasonable running times. With this study, we propose a set of robust and scalable hybrid parallel algorithms that take advantage of parallel computation techniques, evolutionary grouping genetic metaheuristics, and bin-oriented heuristics to obtain solutions for large scale one-dimensional BPP instances. A total number of 1318 benchmark problems are examined with the proposed algorithms and it is shown that optimal solutions for 88.5% of these instances can be obtained with practical optimization times while solving the rest of the problems with no more than one extra bin. When the results are compared with the existing state-of-the-art heuristics, the developed parallel hybrid grouping genetic algorithms can be considered as one of the best one-dimensional BPP algorithms in terms of computation time and solution quality.     

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.     

A hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem

This paper investigates the Heterogeneous Dial-A-Ride Problem (H-DARP) that consists of determining a vehicle route planning for heterogeneous users’ transportation with a heterogeneous fleet of vehicles. A hybrid Genetic Algorithm (GA) is proposed to solve the problem. Efficient construction heuristics, crossover operators and local search techniques, specifically tailored to the characteristics of the H-DARP, are provided. The proposed algorithm is tested on 92 benchmarks instances and 40 newly introduced larger instances. Computational experiments show the effectiveness of our approach compared to the current state-of-the-art algorithms for the DARP and H-DARP. When tested on the existing instances, we achieved average gaps of only 0.47% to the best-known solutions for the DARP, and 0.05% to the optimal solutions for the H-DARP, compared to 0.85% and 0.10%, respectively, obtained by the current state-of-the-art algorithms. For the 40 newly generated instances, average gaps of the hybrid GA are 0.35% smaller compared to the current state-of-the-art method. Besides, our method provides best results for 31 of these instances and ties with the existing method on 8 other instances.     

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.     

Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem

This paper addresses a novel distributed assembly permutation flowshop scheduling problem that has important applications in modern supply chains and manufacturing systems. The problem considers a number of identical factories, each one consisting of a flowshop for part-processing plus an assembly line for product-processing. The objective is to minimize the makespan. To suit the needs of different CPU time and solution quality, we present a mixed integer linear model, three constructive heuristics, two variable neighborhood search methods, and an iterated greedy algorithm. Important problem-specific knowledge is obtained to enhance the effectiveness of the algorithms. Accelerations for evaluating solutions are proposed to save computational efforts. The parameters and operators of the algorithms are calibrated and analyzed using a design of experiments. To prove the algorithms, we present a total of 16 adaptations of other well-known and recent heuristics, variable neighborhood search algorithms, and meta-heuristics for the problem and carry out a comprehensive set of computational and statistical experiments with a total of 810 instances. The results show that the proposed algorithms are very effective and efficient to solve the problem under consideration as they outperform the existing methods by a significant margin.     

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.     

Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics

We propose a general-purpose heuristic approach combining metaheuristics and mixed integer programming to find high quality solutions to the challenging single- and parallel-machine capacitated lotsizing and scheduling problem with sequence-dependent setup times and costs. Commercial solvers fail to solve even medium-sized instances of this NP-hard problem; therefore, heuristics are required to find competitive solutions. We develop construction, improvement and search heuristics all based on MIP formulations. We then compare the performance of these heuristics with those of two metaheuristics and other MIP-based heuristics that have been proposed in the literature, and to a state-of-the-art commercial solver. A comprehensive set of computational experiments shows the effectiveness and efficiency of the main approach, a stochastic MIP-based local search heuristic, in solving medium to large size problems. Our solution procedures are quite flexible and may easily be adapted to cope with model extensions or to address different optimization problems that arise in practice.     

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.     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

Heuristics for the variable sized bin-packing problem

We investigate the one-dimensional variable-sized bin-packing problem. This problem requires packing a set of items into a minimum-cost set of bins of unequal sizes and costs. Six optimization-based heuristics for this problem are presented and compared. We analyze their empirical performance on a large set of randomly generated test instances with up to 2000 items and seven bin types. The first contribution of this paper is to provide evidence that a set covering heuristic proves to be highly effective and capable of delivering very-high quality solutions within short CPU times. In addition, we found that a simple subset-sum problem-based heuristic consistently outperforms heuristics from the literature while requiring extremely short CPU times.     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

Multi-dimensional visual tracking using scatter search particle filter

Multi-dimensional visual tracking (MVT) problems include visual tracking tasks where the system state is defined by a high number of variables corresponding to multiple model components and/or multiple targets. A MVT problem can be modeled as a dynamic optimization problem. In this context, we propose an algorithm which hybridizes particle filters (PF) and the scatter search (SS) metaheuristic, called scatter search particle filter (SSPF), where the optimization strategies from SS are embedded into the PF framework. Scatter search is a population-based metaheuristic successfully applied to several complex combinatorial optimization problems. The most representative optimization strategies from SS are both solution combination and solution improvement. Combination stage enables the solutions to share information about the problem to produce better solutions. Improvement stage makes also possible to obtain better solutions by exploring the neighborhood of a given solution. In this paper, we have described and evaluated the performance of the scatter search particle filter (SSPF) in MVT problems. Specifically, we have compared the performance of several state-of-the-art PF-based algorithms with SSPF algorithm in different instances of 2D articulated object tracking problem and 2D multiple object tracking. Some of these instances are from the CVBase’06 standard database. Experimental results show an important performance gain and better tracking accuracy in favour of our approach.     

A VNS heuristic for escaping local extrema entrapment in normalized cut clustering

Normalized cut is one of the most popular graph clustering criteria. The main approaches proposed for its resolution are spectral clustering methods and a multilevel approach of Dhillon et al. (TPAMI 29:1944–1957, 2007), called graclus. Their aim is to obtain good solutions in a small amount of time for large instances. Metaheuristics are general frameworks for stochastic searches often employed in global optimization to improve the solutions obtained by other heuristics. Variable neighborhood search (VNS) is a metaheuristic which exploits systematically the idea of neighborhood change during the search. In this paper, we propose a VNS heuristic for normalized cut segmentation. Computational experiments show that in most cases this VNS heuristic improves significantly, and in moderate time, the solutions obtained by the current state-of-the-art algorithms, i.e., graclus and a spectral method proposed by Yu and Shi (ICCV, 2003).     

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.     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

Inference of regular languages using state merging algorithms with search

State merging algorithms have emerged as the solution of choice for the problem of inferring regular grammars from labeled samples, a known NP-complete problem of great importance in the grammatical inference area. These methods derive a small deterministic finite automaton from a set of labeled strings (the training set), by merging parts of the acceptor that corresponds to this training set. Experimental and theoretical evidence have shown that the generalization ability exhibited by the resulting automata is highly correlated with the number of states in the final solution.As originally proposed, state merging algorithms do not perform search. This means that they are fast, but also means that they are limited by the quality of the heuristics they use to select the states to be merged. Sub-optimal choices lead to automata that have many more states than needed and exhibit poor generalization ability.In this work, we survey the existing approaches that generalize state merging algorithms by using search to explore the tree that represents the space of possible sequences of state mergings. By using heuristic guided search in this space, many possible state merging sequences can be considered, leading to smaller automata and improved generalization ability, at the expense of increased computation time.We present comparisons of existing algorithms that show that, in widely accepted benchmarks, the quality of the derived solutions is improved by applying this type of search. However, we also point out that existing algorithms are not powerful enough to solve the more complex instances of the problem, leaving open the possibility that better and more powerful approaches need to be designed.     

The min-conflict packing problem

In the classical bin-packing problem with conflicts (BPC), the goal is to minimize the number of bins used to pack a set of items subject to disjunction constraints. In this paper, we study a new version of BPC: the min-conflict packing problem (MCBP), in which we minimize the number of violated conflicts when the number of bins is fixed. In order to find a tradeoff between the number of bins used and the violation of the conflict constraints, we also consider a bi-objective version of this problem. We show that the special structure of its Pareto front allows to reformulate the problem as a small set of MCBP. We solved these two problems through heuristics, column-generation methods, and a tabu search. Computational experiments are reported to assess the quality of our methods.     

Fast,effective heuristics for the 0–1 multi-dimensional knapsack problem

The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.     

A Global Repair Operator for Capacitated Arc Routing Problem

Capacitated arc routing problem (CARP) has attracted much attention during the last few years due to its wide applications in real life. Since CARP is NP-hard and exact methods are only applicable for small instances, heuristics and metaheuristic methods are widely adopted when solving CARP. This paper demonstrates one major disadvantage encountered by traditional search algorithms and proposes a novel operator named global repair operator (GRO) to address it. We further embed GRO in a recently proposed tabu search algorithm (TSA) and apply the resultant repair-based tabu search (RTS) algorithm to five well-known benchmark test sets. Empirical results suggest that RTS not only outperforms TSA in terms of quality of solutions but also converges to the solutions faster. Moreover, RTS is also competitive with a number of state-of-the-art approaches for CARP. The efficacy of GRO is thereby justified. More importantly, since GRO is not specifically designed for the referred TSA, it might be a potential tool for improving any existing method that adopts the same solution representation.     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.