Search results for "Grasp"
showing 10 items of 84 documents
GRASP and path relinking for the equitable dispersion problem
2013
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…
GRASP and path relinking for the matrix bandwidth minimization
2004
In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the nonzero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a Path Relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with Path Relinking is also found to be competitive with a recently published tabu search algorithm that is considered one of the best currently available for band…
Metaheuristics for the linear ordering problem with cumulative costs
2012
The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The compa…
GRASP and path relinking for project scheduling under partially renewable resources
2008
[EN] Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP an…
Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization
2015
We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of high-quality solutions throughout the search. After a fixed number of GRASP iterations, exterior path relinking is applied between all pairs of elite set solutions and the best solution found is returned. Exterior path relinking, or path separation, a variant of the more common interior path relinking, is first applied in this paper. In interior path relinking, paths in the neighborhood solution space connecting good solutions are explored betwe…
Multi-start methods for combinatorial optimization
2013
Abstract Multi-start methods strategically sample the solution space of an optimization problem. The most successful of these methods have two phases that are alternated for a certain number of global iterations. The first phase generates a solution and the second seeks to improve the outcome. Each global iteration produces a solution that is typically a local optimum, and the best overall solution is the output of the algorithm. The interaction between the two phases creates a balance between search diversification (structural variation) and search intensification (improvement), to yield an effective means for generating high-quality solutions. This survey briefly sketches historical devel…
GRASP and path relinking for the max–min diversity problem
2010
The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…
Heuristics for the bandwidth colouring problem
2010
The bandwidth colouring problem consists of assigning a colour to each vertex of a graph, so that the absolute value of the difference between the colours of adjacent vertices is at least the value of the weight of the associated edge. This problem generalises the classical vertex colouring problem and different heuristics have recently been proposed to obtain high quality solutions. In this paper we describe both memory-based and memory-less methods to solve the bandwidth colouring problem. In particular we propose new constructive and improvement methods based on tabu search and GRASP. Comparison of our results with previously reported instances and existing heuristics indicate that the m…
A GRASP ALGORITHM FOR THE CONTAINER LOADING PROBLEM WITH MULTI-DROP CONSTRAINTS
2015
This paper studies a variant of the container loading problem in which to the classical geometric constraints of packing problems we add other conditions appearing in practical problems, the multi-drop constraints. When adding multi-drop constraints, we demand that the relevant boxes must be available, without rearranging others, when each drop-off point is reached. We present first a review of the different types of multi-drop constraints that appear in literature. Then we propose a GRASP algorithm that solves the different types of multi-drop constraints and also includes other types of realistic constraints such as full support of the boxes and load bearing strength. The computational re…
Randomized heuristics for the Capacitated Clustering Problem
2017
In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent l…