Search results for " search"
showing 10 items of 654 documents
Reactive GRASP for the strip-packing problem
2008
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.
On Randomness and Structure in Euclidean TSP Instances: A Study With Heuristic Methods
2021
Prediction of the quality of the result provided by a specific solving method is an important factor when choosing how to solve a given problem. The more accurate the prediction, the more appropriate the decision on what to choose when several solving applications are available. In this article, we study the impact of the structure of a Traveling Salesman Problem instance on the quality of the solution when using two representative heuristics: the population-based Ant Colony Optimization (ACO) and the local search Lin-Kernighan (LK) algorithm. The quality of the result for a solving method is measured by the computation accuracy, which is expressed using the percent error between its soluti…
Heuristics for the Mixed Rural Postman Problem
2000
Abstract The Rural Postman Problem on a mixed graph (MRPP) consists of finding a minimum cost tour which traverses, at least once, the arcs and edges of a given subset of the arcs and edges of the graph. This problem is known to be NP-hard. This paper presents two heuristic approaches to solve it. An approximate algorithm based on the resolution of some flow and matching problems and a tabu search implementation is presented. The tabu search algorithm seeks high-quality tours by means of a switching mechanism in an intensification phase and two levels of diversification. Computational results are presented to assess the merits of the method. Scope and purpose Routing Problems arise in sever…
A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems
2002
Abstract In this paper we develop several heuristic algorithms for the two-dimensional cutting problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximising the value of the pieces cut. They can be considered to be general purpose algorithms because they solve the four versions of the TDC: weighted and unweighted, constrained and unconstrained. We begin by proposing two constructive procedures based on simple bounds obtained by solving one-dimensional knapsack problems. We then use these constructive algorithms as building blocks for more complex procedures. We have developed a greedy randomised adaptive search procedure (GRASP) which is very fast an…
An efficient variable neighborhood search heuristic for very large scale vehicle routing problems
2007
In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are use…
GRASP for the uncapacitated r-allocation p-hub median problem
2014
In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on t…
Active-guided evolution strategies for large-scale capacitated vehicle routing problems
2007
We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, …
Scheduling in a continuous galvanizing line
2009
In this paper we address a sequencing problem in a Continuous Galvanizing Line of a Spanish Steel Company. Production scheduling in this context is an extremely complex task which needs to take into account many constraints. We present a conceptually simple model and a Tabu Search (TS) algorithm that efficiently solves it. The TS moves are defined in order to repair non-satisfied constraints, leading to smaller and more efficient neighbourhoods. The TS co-ordinates several intensification and diversification procedures guided by an evaluation function based on a shifting penalty strategy. This function reinforces the anticycling mechanism and makes the algorithm avoid already visited soluti…
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…
Variable neighborhood search for the linear ordering problem
2006
Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is cou…