Hybrid Nested Partitions and Mathematical Programming Approach and Its Applications

Large-scale discrete optimization problems are difficult to solve, especially when different kinds of real constraints are considered. Conventionally, standard mathematical programming is a general approach for discrete optimization, but may suffer from the unacceptable long solution time in applications. On the other hand, some heuristics/metaheuristics methods are more powerful in finding approximate solutions efficiently, but mostly are problem and constraint dependent. In this paper, we develop a new hybrid nested partitions and mathematical programming approach, which creates compliance between mathematical programming and the heuristics/metaheuristics methods. Potentially applicable to many different types of problems, the hybrid approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. The applications of the hybrid approach to the local pickup and delivery problem (LPDP) and the discrete facility location problem (DFLP) are presented in this paper.     

A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines,setup times,and dual criteria

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0–1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.     

An adaptive tabu search algorithm for the capacitated clustering problem

In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion . Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem.     

Solving the feeder bus network design problem by genetic algorithms and ant colony optimization

This paper proposes the design and analysis of two metaheuristics, genetic algorithms and ant colony optimization, for solving the feeder bus network design problem. A study of how these proposed heuristics perform is carried out on several randomly generated test problems to evaluate their computational efficiency and the quality of solutions obtained by them. The results are also compared to those published in the literature. Computational experiments have shown that both heuristics are comparable to the state-of-the-art algorithms such as simulated annealing and tabu search.     

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.     

Probabilistic stopping rules for GRASP heuristics and extensions

The main drawback of most metaheuristics is the absence of effective stopping criteria. Most implementations of such algorithms stop after performing a given maximum number of iterations or a given maximum number of consecutive iterations without improvement in the best‐known solution value, or after the stabilization of the set of elite solutions found along the search. We propose effective probabilistic stopping rules for randomized metaheuristics such as GRASP (Greedy Randomized Adaptive Search Procedures). We show how the probability density function of the solution values obtained along the iterations of such algorithms can be used to implement stopping rules based on the tradeoff between solution quality and the time needed to find a solution that might improve the best solution found. We show experimentally that, in the particular case of GRASP heuristics, the solution values obtained along its iterations fit a normal distribution that may be used to give an online estimation of the number of solutions obtained in forthcoming iterations that might be at least as good as the incumbent. This estimation is used to validate the stopping rule based on the tradeoff between solution quality and the time needed to find a solution that might improve the incumbent. The robustness of this strategy is illustrated and validated by a thorough computational study reporting results obtained with GRASP implementations to four different combinatorial optimization problems.     

An agent based approach for the implementation of cooperative proactive S-Metaheuristics

This paper introduces several cooperative proactive S-Metaheuristics, i.e. single-solution based metaheuristics, which are implemented taking advantage of two singular characteristics of the agent paradigm: proactivity and cooperation. Proactivity is applied to improve traditional versions of Threshold Accepting and Great Deluge Algorithm metaheuristics. This approach follows previous work for the definition of proactive versions of the Record-to-Record Travel and Local Search metaheuristics. Proactive metaheuristics are implemented as agents that cooperate in the environment of the optimization process with the goal of avoiding stagnation in local optima by adjusting their parameters. Based on the environmental information about previous solutions, the proactive adjustment of the parameters is focused on keeping a minimal level of acceptance for the new solutions. In addition, simple forms of cooperation by competition are used to develop cooperative metaheuristics based on the combination of the four proactive metaheuristics. The proposed metaheuristics have been validated through experimentation with 28 benchmark functions on binary strings, and several instances of knapsack problems and travelling salesman problems.     

A very fast TS/SA algorithm for the job shop scheduling problem

The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.     

Randomized local search,evolutionary algorithms,and the minimum spanning tree problem

Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.     

Sequential Monte Carlo in reachability heuristics for probabilistic planning

Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking.In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.     

Improving the Clustering Search heuristic: An application to cartographic labeling

The use of hybrid metaheuristics is a good approach to improve the quality and efficiency of metaheuristics. This paper presents a hybrid method based on Clustering Search (CS). CS seeks to combine metaheuristics and heuristics for local search, intensifying the search on regions of the search space which are considered promising. We propose a more efficient way to detect promising regions, based on the clustering techniques of Density-based spatial clustering of applications with noise (DBSCAN), Label-propagation (LP), and Natural Group Identification (NGI) algorithms. This proposal is called Density Clustering Search (DCS). To analyze this new approach, we propose to solve a combinatorial optimization problem with many practical applications, the Point Feature Cartographic Label Placement (PFCLP). The PFCLP attempts to locate identifiers (labels) of regions on a map without damaging legibility. The computational tests used instances taken from the literature. The results were satisfactory for clusters made with LP and NGI, presenting better results than the classic CS, which indicates these methods are a good alternative for the improvement of this method.     

Augmented neural networks and problem structure-based heuristics for the bin-packing problem

In this article, we report on a research project where we applied augmented-neural-networks (AugNNs) approach for solving the classical bin-packing problem (BPP). AugNN is a metaheuristic that combines a priority rule heuristic with the iterative search approach of neural networks to generate good solutions fast. This is the first time this approach has been applied to the BPP. We also propose a decomposition approach for solving harder BPP, in which subproblems are solved using a combination of AugNN approach and heuristics that exploit the problem structure. We discuss the characteristics of problems on which such problem structure-based heuristics could be applied. We empirically show the effectiveness of the AugNN and the decomposition approach on many benchmark problems in the literature. For the 1210 benchmark problems tested, 917 problems were solved to optimality and the average gap between the obtained solution and the upper bound for all the problems was reduced to under 0.66% and computation time averaged below 33?s per problem. We also discuss the computational complexity of our approach.     

Tsp-based scheduling in a batch-wise hybrid flow-shop

In the past few years, flexible production systems have allowed an extensive exploitation of new technologies, but have also led to new difficulties in production planning management science. The model presented in this paper extends the traditional HFS (hybrid flow-shop) scheduling problem to the case in which jobs are due to follow strict precedence constraints and batch assignment constraints and the parallel machines at a stage are served by a bottleneck machine. A variant of the well-known TSP problem is used to develop an efficient heuristic solution for the problem. The effectiveness of the proposed approach is validated through a comparison with different heuristics traditionally used in HFS scheduling problems. Furthermore, a simple insertion heuristic based on the TSP model of the problem is tested. Finally, a MIP-based approach is also explored to provide the optimum solutions within much larger times for comparison.     

Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics

In this work, a review and comprehensive evaluation of heuristics and metaheuristics for the m-machine flowshop scheduling problem with the objective of minimising total tardiness is presented. Published reviews about this objective usually deal with a single machine or parallel machines and no recent methods are compared. Moreover, the existing reviews do not use the same benchmark of instances and the results are difficult to reproduce and generalise. We have implemented a total of 40 different heuristics and metaheuristics and we have analysed their performance under the same benchmark of instances in order to make a global and fair comparison. In this comparison, we study from the classical priority rules to the most recent tabu search, simulated annealing and genetic algorithms. In the evaluations we use the experimental design approach and careful statistical analyses to validate the effectiveness of the different methods tested. The results allow us to clearly identify the state-of-the-art methods.     

Guest Editors' Introduction: Advanced Heuristics in Transportation and Logistics

Transportation and logistics organizations often face large-scale combinatorial problems on both operational and strategic levels. By exploiting problem-specific characteristics, classical heuristic methods--such as constructive and iterative local search methods--aim at a relatively limited exploration of the search space, thereby producing acceptable-quality solutions in modest computing times. In a major departure from a classical heuristic, a metaheuristic method exploits not only the problem characteristics but also ideas based on artificial intelligence methodologies, such as different types of memory structures and learning mechanisms, as well as analogies with optimization methods found in nature. Solutions produced by metaheuristics typically are of a much higher quality than those obtained with classical heuristic approaches.This article is part of a special issue on advanced heuristics in transportation and logistics.     

An ant colony optimization algorithm for DNA sequencing by hybridization

The reconstruction of DNA sequences from DNA fragments is one of the most challenging problems in computational biology. In recent years the specific problem of DNA sequencing by hybridization has attracted quite a lot of interest in the optimization community. Several metaheuristics such as tabu search and evolutionary algorithms have been applied to this problem. However, the performance of existing metaheuristics is often inferior to the performance of recently proposed constructive heuristics. On the basis of these new heuristics we develop an ant colony optimization algorithm for DNA sequencing by hybridization. An important feature of this algorithm is the implementation in a so-called multi-level framework. The computational results show that our algorithm is currently a state-of-the-art method for the tackled problem.     

Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem

Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path Relinking is introduced to replace the local search in the improvement phase of Meta-RaPS (Meta-Heuristic for Randomized Priority Search) which is currently classified as a memoryless metaheuristic. The new algorithm is tested using the 0–1 multidimensional knapsack problem, and it is observed that it could solve even the largest benchmark problems in significantly less time while maintaining solution quality compared to other algorithms in the literature.     

The multiobjective multidimensional knapsack problem: a survey and a new approach

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two‐phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state‐of‐the‐art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three‐objective instances.     

An investigation of fuzzy multiple heuristic orderings in the construction of university examination timetables

In this paper, we present an investigation into using fuzzy methodologies to guide the construction of high quality feasible examination timetabling solutions. The provision of automated solutions to the examination timetabling problem is achieved through a combination of construction and improvement. The enhancement of solutions through the use of techniques such as metaheuristics is, in some cases, dependent on the quality of the solution obtained during the construction process. With a few notable exceptions, recent research has concentrated on the improvement of solutions as opposed to focusing on investigating the ‘best’ approaches to the construction phase. Addressing this issue, our approach is based on combining multiple criteria in deciding on how the construction phase should proceed. Fuzzy methods were used to combine three single construction heuristics into three different pair wise combinations of heuristics in order to guide the order in which exams were selected to be inserted into the timetable solution. In order to investigate the approach, we compared the performance of the various heuristic approaches with respect to a number of important criteria (overall cost penalty, number of skipped exams, number of iterations of a rescheduling procedure required and computational time) on 12 well-known benchmark problems. We demonstrate that the fuzzy combination of heuristics allows high quality solutions to be constructed. On one of the 12 problems, we obtained lower penalty than any previously published constructive method and for all 12 we obtained lower penalty than when any of the single heuristics were used alone. Furthermore, we demonstrate that the fuzzy approach used less backtracking when constructing solutions than any of the single heuristics. We conclude that this novel fuzzy approach is a highly effective method for heuristically constructing solutions and, as such, has particular relevance to real-world situations in which the construction of feasible solutions is often a difficult task in its own right.     

Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size

The generalized vehicle routing problem with flexible fleet size (GVRP‐flex) extends the classical capacitated vehicle routing problem (CVRP) by partitioning the set of required nodes into clusters and has interesting applications such as humanitarian logistics. The problem aims at minimizing the total cost for a set of routes, such that each cluster is visited exactly once and its total demand is delivered to one of its nodes. An exact method based on column generation (CG) and two metaheuristics derived from iterated local search are proposed for the case with flexible fleet size. On five sets of benchmarks, including a new one, the CG approach often provides good upper and lower bounds, whereas the metaheuristics find, in a few seconds, solutions with small optimality gaps.