An Iterative Construction Heuristic for the Ore Selection Problem

The ore selection problem involves choosing a processing option for a number of mining blocks that maximises the expected payoff for a given level of financial risk. An innovative neighbourhood search heuristic is proposed for the ore selection problem. This iterative construction heuristic employs a stochastic demolition and reconstruction strategy. Computational experiments with this heuristic for two ore selection problem instances, one involving 2,500 blocks and the other involving 78,000 blocks, are given. These problem instances are made publicly available for use by future workers. Our computational experiments indicate that the proposed heuristic produces better quality solutions faster than a relay hybrid (constructive-simulated annealing) heuristic.     

A mathematical formulation and complexity considerations for the blocks relocation problem

The blocks relocation problem (BRP) may be defined as follows: given a set of homogeneous blocks stored in a two-dimensional stock, which relocations are necessary to retrieve the blocks from the stock in a predefined order while minimizing the number of those relocations? In this paper, we first prove NP-hardness of the BRP as well as a special case, closing open research questions. Moreover, we propose different solution approaches. First, a mathematical model is presented that provides optimal solutions to the general BRP in cases where instances are small. To overcome such limitation, some realistic assumption taken from the literature is introduced, leading to the definition of a binary linear programming model. In terms of computational time, this approach is reasonably fast to be used to solve medium-sized instances. In addition, we propose a simple heuristic based upon a set of relocation rules. This heuristic is used to generate “good” quality solutions for larger instances in very short computational time, and, consequently, is proposed for tackling problem instances where solutions are required (almost) immediately. Solution quality of the heuristic is measured against optimal solutions obtained using a state-of-the-art commercial solver and both of them are compared with reference results from literature.     

The balanced academic curriculum problem revisited

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.     

TSPACK: A two-level tabu search for the three-dimensional bin packing problem

Three-dimensional orthogonal bin packing is a problem NP-hard in the strong sense where a set of boxes must be orthogonally packed into the minimum number of three-dimensional bins. We present a two-level tabu search for this problem. The first-level aims to reduce the number of bins. The second optimizes the packing of the bins. This latter procedure is based on the Interval Graph representation of the packing, proposed by Fekete and Schepers, which reduces the size of the search space. We also introduce a general method to increase the size of the associated neighborhoods, and thus the quality of the search, without increasing the overall complexity of the algorithm. Extensive computational results on benchmark problem instances show the effectiveness of the proposed approach, obtaining better results compared to the existing ones.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

An artificial bee colony algorithm for the capacitated vehicle routing problem

This paper introduces an artificial bee colony heuristic for solving the capacitated vehicle routing problem. The artificial bee colony heuristic is a swarm-based heuristic, which mimics the foraging behavior of a honey bee swarm. An enhanced version of the artificial bee colony heuristic is also proposed to improve the solution quality of the original version. The performance of the enhanced heuristic is evaluated on two sets of standard benchmark instances, and compared with the original artificial bee colony heuristic. The computational results show that the enhanced heuristic outperforms the original one, and can produce good solutions when compared with the existing heuristics. These results seem to indicate that the enhanced heuristic is an alternative to solve the capacitated vehicle routing problem.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.     

A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

A heuristic algorithm for the strip packing problem

The two-dimensional strip packing problem is to pack a given set of rectangles into a strip with a given width and infinite height so as to minimize the required height of the packing. From the computational point of view, the strip packing problem is an NP-hard problem. With the B*-tree representation, this paper first presents a heuristic packing strategy which evaluates the positions used by the rectangles. Then an effective local search method is introduced to improve the results and a heuristic algorithm (HA) is further developed to find a desirable solution. Computational results on randomly generated instances and popular test instances show that the proposed method is efficient for the strip packing problem.     

A Slope Scaling/Lagrangean Perturbation Heuristic with Long-Term Memory for Multicommodity Capacitated Fixed-Charge Network Design

This paper describes a slope scaling heuristic for solving the multicomodity capacitated fixed-charge network design problem. The heuristic integrates a Lagrangean perturbation scheme and intensification/diversification mechanisms based on a long-term memory. Although the impact of the Lagrangean perturbation mechanism on the performance of the method is minor, the intensification/diversification components of the algorithm are essential for the approach to achieve good performance. The computational results on a large set of randomly generated instances from the literature show that the proposed method is competitive with the best known heuristic approaches for the problem. Moreover, it generally provides better solutions on larger, more difficult, instances.     

An improved decomposition-based heuristic to design a water distribution network for an irrigation system

In this paper the authors address a pressurized water distribution network design problem for irrigation purposes. Two mixed binary nonlinear programming models are proposed for this NP-hard problem. Furthermore, a heuristic algorithm is presented for the problem, which considers a decomposition sequential scheme, based on linearization of the second model, coupled with constructive and local search procedures designed to achieve improved feasible solutions. To evaluate the robustness of the method we tested it on several instances generated from a real application. The best solutions obtained are finally compared with solutions provided by standard software. These computational experiments enable the authors to conclude that the decomposition sequential heuristic is a good approach to this difficult real problem.     

A fast heuristic attribute reduction approach to ordered decision systems

Rough set theory has shown success in being a filter-based feature selection approach for analyzing information systems. One of its main aims is to search for a feature subset called a reduct, which preserves the classification ability of the original system. In this paper, we consider ordered decision systems, where the preference order, a fundamental concept in dominance-based rough set approach, plays a critical role. In recent literature, based on the greedy hill climbing method, many heuristic attribute reduction algorithms are proposed by utilizing significance measures of attributes, and they are extended to deal with ordered decision systems. Unfortunately, they are often time-consuming, especially when applied to deal with large scale data sets with high dimensions. To reduce the complexity, a novel accelerator is introduced in heuristic algorithms from the perspectives of objects and criteria. Based on the new accelerator, the number of objects and the dimension of criteria are lessened thus making the accelerated algorithms faster than their original counterparts while maintaining the same reducts. Experimental analysis shows the validity and efficiency of the proposed methods.     

A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem

The aim of the Single Container Loading Problem (SCLP) is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. We propose a new block building approach that constructs packings by placing one block (of boxes) at a time until no more boxes can be loaded. The key to obtaining high quality solutions is to select the right block to place into the right free space cuboid (or residual space) in the container. We propose a new heuristic for evaluating the fitness of residual spaces, and use a tree search to decide the best residual space-block pair at each step. The resultant algorithm outperforms the best known algorithms based on the 1600 commonly used benchmark instances even when given fewer computational resources. We also adapted our approach to address the full support constraint. The computational results for the full support support variant on the 1600 instances similarly show a significant improvement over existing techniques even when given substantially fewer computational resources.     

Fix and Relax Heuristic for a Stochastic Lot-Sizing Problem

This paper addresses a particular stochastic lot-sizing and scheduling problem. The evolution of the uncertain parameters is modelled by means of a scenario tree and the resulting model is a multistage stochastic mixed-integer program. We develop a heuristic approach that exploits the specific structure of the problem. The computational experiments carried out on a large set of instances have shown that the approach provides good quality solutions in a reasonable amount of time.     

A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems.     

Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls

A heuristic approach based on a hybrid operation of reactive tabu search (RTS) and adaptive memory programming (AMP) is proposed to solve the vehicle routing problem with backhauls (VRPB). The RTS is used with an escape mechanism which manipulates different neighbourhood schemes in a sophisticated way in order to get a continuously balanced intensification and diversification during the search process. The adaptive memory strategy takes the search back to the unexplored regions of the search space by maintaining a set of elite solutions and using them strategically with the RTS. The AMP feature brings an extra robustness to the search process that resulted in early convergence when tested on most of the VRPB instances. We compare our algorithm against the best methods in the literature and report new best solutions for several benchmark problems.     

Heuristics for flight and maintenance planning of mission aircraft

Flight and Maintenance Planning (FMP) of mission aircraft addresses the question of which available aircraft to fly and for how long, and which grounded aircraft to perform maintenance operations on, in a group of aircraft that comprise a unit. The objective is to achieve maximum fleet availability of the unit over a given planning horizon, while also satisfying certain flight and maintenance requirements. The application of exact methodologies for the solution of the problem is quite limited, as a result of their excessive computational requirements. In this work, we prove several important properties of the FMP problem, and we use them to develop two heuristic procedures for solving large-scale FMP instances. The first heuristic is based on a graphical procedure which is currently used for generating flight and maintenance plans of mission aircraft by many Air Force organizations worldwide. The second heuristic is based on the idea of splitting the original problem into smaller sub-problems and solving each sub-problem separately. Both heuristics have been roughly sketched in earlier works that have appeared in the related literature. The present paper develops the theoretical background on which these heuristics are based, provides in detail the algorithmic steps required for their implementation, analyzes their worst-case computational complexity, presents computational results illustrating their computational performance on random problem instances, and evaluates the quality of the solutions that they produce. The size and parameter values of some of the randomly tested problem instances are quite realistic, making it possible to infer the performance of the heuristics on real world problem instances. Our computational results demonstrate that, under careful consideration, even large FMP instances can be handled quite effectively. The theoretical results and insights that we develop establish a fundamental background that can be very useful for future theoretical and practical developments related to the FMP problem.     

A stochastic local search algorithm with adaptive acceptance for high-school timetabling

Automating high school timetabling is a challenging task. This problem is a well known hard computational problem which has been of interest to practitioners as well as researchers. High schools need to timetable their regular activities once per year, or even more frequently. The exact solvers might fail to find a solution for a given instance of the problem. A selection hyper-heuristic can be defined as an easy-to-implement, easy-to-maintain and effective ‘heuristic to choose heuristics’ to solve such computationally hard problems. This paper describes the approach of the team hyper-heuristic search strategies and timetabling (HySST) to high school timetabling which competed in all three rounds of the third international timetabling competition. HySST generated the best new solutions for three given instances in Round 1 and gained the second place in Rounds 2 and 3. It achieved this by using a fairly standard stochastic search method but significantly enhanced by a selection hyper-heuristic with an adaptive acceptance mechanism.