An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p-hub median problem

This paper deals with the uncapacitated multiple allocation p-hub median problem (UMApHMP). An electromagnetism-like (EM) method is proposed for solving this NP-hard problem. Our new scaling technique, combined with the movement based on the attraction–repulsion mechanism, directs the EM towards promising search regions. Numerical results on a battery of benchmark instances known from the literature are reported. They show that the EM reaches all previously known optimal solutions, and gives excellent results on large-scale instances. The present approach is also extended to solve the capacitated version of the problem. As it was the case in the uncapacitated version, EM also reached all previously known optimal solutions.     

GRASP with path relinking for the symmetric Euclidean clustered traveling salesman problem

In this paper, we propose new heuristics using several path-relinking strategies to solve the Clustered Traveling Salesman Problem (CTSP). The CTSP is a generalization of the Traveling Salesman Problem (TSP) in which the set of vertices is partitioned into clusters and the objective is to find a minimum cost Hamiltonian cycle such that the vertices of each cluster are visited continuously. A comparison among the performance of the several different adopted path-relinking strategies is presented using instances with up to 2000 vertices and clusters varying between 4 and 150 vertices. Also computational experiments were performed to compare the performance of the proposed heuristics with an exact algorithm and a Genetic Algorithm. The obtained computational results showed that the proposed heuristics were able to obtain competitive results related to the quality of the solutions and computational execution time.     

Reactive GRASP for the strip-packing problem

This paper presents a greedy randomized adaptive search procedure (GRASP) for the strip packing problem, which is the problem of placing a set of rectangular pieces into a strip of a given width and infinite height so as to minimize the required height. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances which have been previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures. The results show that the GRASP algorithm outperforms recently reported metaheuristics.     

Efficient algorithms for the uncapacitated single allocation p-hub median problem

We present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. We develop a good heuristic algorithm for its solution based on simulated annealing (SA). We use the SA upper bound to develop an LP-based branch-and-bound solution method. We present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. We also benchmark our new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.     

A reactive GRASP for a commercial territory design problem with multiple balancing requirements

In this paper we present a reactive GRASP approach to a commercial territory design problem motivated by a real-world application in a beverage distribution firm. The mathematical framework includes, as planning criteria, minimizing a measure of territory dispersion, balancing the different node activity measures among territories and territory contiguity. The proposed GRASP approach incorporates several features such as reactivity, by allowing self-adjustment of the restricted candidate list quality parameter, and filtering, which avoids executing the local search phase in unpromising bad solutions generated by the construction phase. The algorithm has been tested in several data sets. The results show the effectiveness of the proposed approach. It was observed that the reactivity and the filtering proved very useful in terms of feasibility with respect to the balancing constraints, and find more robust solutions when tested over the basic GRASP. The local search scheme proved to be very effective as well. Moreover, the proposed approach obtained solutions of much better quality (in terms of both its dispersion measure and its feasibility with respect to the balancing constraints) than those found by the firm method in relatively fast computation times.     

Using a greedy random adaptative search procedure to solve the cover printing problem

In this paper, the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost, is discussed. As the considered problem is hard, we discuss and propose a greedy random adaptative search procedure (GRASP) to solve the problem. The quality of the proposed procedure is tested on a set of reference instances, comparing the obtained results with those found in the literature. Our procedure improves the best known solutions for some of these instances. Results are also presented for larger, randomly generated problems.     

A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems

The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considered for each phase of the algorithm and the good performance of our algorithm compared with previously reported results.     

GRASP and path relinking for the equitable dispersion problem

The equitable dispersion problem consists in selecting a subset of elements from a given set in such a way that a measure of dispersion is maximized. In particular, we target the Max-Mean dispersion model in which the average distance between the selected elements is maximized. We first review previous methods and mathematical formulations for this and related dispersion problems and then propose a GRASP with a Path Relinking in which the local search is based on the Variable Neighborhood methodology. Our method is specially suited for instances in which the distances represent affinity and are not restricted to take non-negative values. The computational experience with 120 instances shows the merit of the proposed procedures compared to previous methods.     

A GRASP approach for the extended car sequencing problem

This paper presents a solution procedure for a new variant of the Car Sequencing Problem (CSP) based on the GRASP metaheuristic. In this variant, called xCSP (extended CSP), the aim is to satisfy the hard constraints of the CSP while scheduling the maximum possible number of cars with specific options at specific times of the day in order to satisfy other production requirements. Additional constraint ratios are likewise considered that force at least a minimum specific number of consecutive options. An extension of the CSP is formalized in this paper and computational results are presented using available on-line instances that verify the good performance of a GRASP procedure defined for the xCSP.     

A GRASP approach to transporter scheduling and routing at a shipyard

We address the transporter scheduling and routing problem at a shipyard, which can be transformed into parallel machine scheduling with sequence-dependent setup times and precedence constraints. The objective is to maximize the workload balance among transporters under the time constraint that all assembly blocks should be transported in the predetermined period. We develop the GRASP algorithm for transporter scheduling and routing. Through simulation experiments we analyze some aspects of the developed GRASP algorithm and verify the performance of the developed GRASP algorithm. The comparison experiments show that the developed GRASP algorithm is a promising heuristic for transporter scheduling and routing.     

A guided reactive GRASP for the capacitated multi-source Weber problem

The capacitated multi-source Weber problem entails finding both the locations of capacitated facilities on a plane and their customer allocations. A framework that uses adaptive learning and functional representation to construct the restricted candidate list (RCL) within a greedy randomized adaptive search procedure (GRASP) is put forward. An implementation of restricted regions that forbids new facilities to be located too close to the previously found facilities is also embedded into the search to build up the RCL more efficiently. The performance of this GRASP based approach is tested on three classes of instances with constant and variable capacities. Very competitive results are obtained when compared to the best known results from the literature.     

Solving the one-dimensional bin packing problem with a weight annealing heuristic

In this paper, we develop a new procedure that uses the concept of weight annealing to solve the one-dimensional bin packing problem. Our procedure is straightforward and easy to follow. We apply it to 1587 instances taken from benchmark problem sets and compare our results to those found in the literature. We find that our procedure produces very high-quality solutions very quickly and generates several new optimal solutions.     

Local branching-based algorithms for the disjunctively constrained knapsack problem

The disjunctively constrained knapsack problem (DCKP) is a variant of the well-known single constrained knapsack problem with special disjunctive constraints. This paper investigates the use of the local branching techniques for solving large-scale DCKP. Three versions of the algorithm are considered. The first version is based on the standard local branching which uses a starting solution provided by a specialized rounding solution procedure. The second version applies a two-phase solution procedure embedded in the local branching. For each subtree, the procedure serves to construct the set of objects containing the assigned variables and a second set including the free variables. The first set provides a partial local solution to the DCKP, whereas, for the second set, a truncated exact tree-search is applied for completing the partial local feasible solution. Finally, a diversification strategy is considered constituting the third version of the algorithm. All versions of the proposed algorithm are computationally analyzed on a set of benchmark instances of the literature and the obtained solutions are compared to those provided by existing algorithms. Encouraging results have been obtained.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle

The problem of packing circles into a larger containing circle is a kind of NP-hard problem. It is of high theoretical and practical value. Lacking powerful optimization method is the key obstacle to solving this problem. The energy landscape paving (ELP) method is a class of heuristic global optimization algorithm and a generation of Monte Carlo method. By incorporating new configuration update mechanism into ELP method, an improved energy landscape paving (ELP+) algorithm is put forward. The computational results, on two sets of instances taken from the literature, show the effectiveness of the proposed algorithm.     

A multi-objective GRASP for partial classification

Metaheuristic algorithms have been used successfully in a number of data mining contexts and specifically in the production of classification rules. Classification rules describe a class of interest or a subset of this class, and as such may also be used as an aid in prediction. The production and selection of classification rules for a particular class of the database is often referred to as partial classification. Since partial classification rules are often evaluated according to a number of conflicting objectives, the generation of such rules is a task that is well suited to a multi-objective (MO) metaheuristic approach. In this paper we discuss how to adapt well known MO algorithms for the task of partial classification. Additionally, we introduce a new MO algorithm for this task based on a greedy randomized adaptive search procedure (GRASP). GRASP has been applied to a number of problems in combinatorial optimization, but it has very seldom been used in a MO setting, and generally only through repeated optimization of single objective problems, using either linear combinations of the objectives or additional constraints. The approach presented takes advantage of some specific characteristics of the data mining problem being solved, allowing for the very effective construction of a set of solutions that form the starting point for the local search phase of the GRASP. The resulting algorithm is guided solely by the concepts of dominance and Pareto-optimality. We present experimental results for our partial classification GRASP and other MO metaheuristics. These show that such algorithms are generally very well suited to this data mining task and furthermore, the GRASP brings additional efficiency to the search for partial classification rules.     

GRASP with evolutionary path-relinking for the capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) is a well-known NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours servicing a subset of required edges under vehicle capacity constraints. There are numerous applications for the CARP, such as street sweeping, garbage collection, mail delivery, school bus routing, and meter reading. A Greedy Randomized Adaptive Search Procedure (GRASP) with Path-Relinking (PR) is proposed and compared with other successful CARP metaheuristics. Some features of this GRASP with PR are (i) reactive parameter tuning, where the parameter value is stochastically selected biased in favor of those values which historically produced the best solutions in average; (ii) a statistical filter, which discard initial solutions if they are unlikely to improve the incumbent best solution; (iii) infeasible local search, where high-quality solutions, though infeasible, are used to explore the feasible/infeasible boundaries of the solution space; (iv) evolutionary PR, a recent trend where the pool of elite solutions is progressively improved by successive relinking of pairs of elite solutions. Computational tests were conducted using a set of 81 instances, and results reveal that the GRASP is very competitive, achieving the best overall deviation from lower bounds and the highest number of best solutions found.     

A parallel local search approach to solving the uncapacitated warehouse location problem

The uncapacitated warehouse location problem (UWLP) has been studied by many researchers. It has been solved using various approaches, including branch and bound linear programming, tabu search, simulated annealing, and genetic algorithms. This study presents a new local search (LS) approach to the UWLP that is quite simple and robust and is efficient in some cases. The algorithm was tested against standard OR Library benchmarks and M^* instances, which have already been used to test other approaches. The results show that the only disadvantage of the algorithm is the exponential growth of its computation time with the problem size. However, the multi-search design suggested here enables the algorithm to run under multi-processor or multi-core systems, which are currently provided as part of standard PC configurations.