@Article{HelHad00a, author = "S. Abdinnour-Helm and S.W. Hadley", title = "Tabu search based heuristics for multi-floor facility layout", journal = "International Journal of Production Research", volume = "38", pages = "365--383", year = "2000", annote = "Two two-stage heuristics are proposed for solving the multi-floor facility layout problem. {GRASP}/TS applies a {GRASP} to find the initial layout and tabu search to refine the initial layout, based on total inter/intra-floor costs. Computational tests indicate that {GRASP}/TS compares favorably with heuristics that do not rely on exact algorithms.", } @inproceedings{AlvParTam01a, author = "R. Alvarez-Valdes and A. Parajon and J.M. Tamarit", title = "A computational study of heuristic algorithms for two-dimensional cutting stock problems", booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", year = "2001", pages = "7--11", annote = "To solve the column generation subproblem arising while solving two-dimensional cutting stock problem, the authors propose the Gilmore-Gomory approach and several heuristics, including a {GRASP}. The greedy criterion is the potential benefit of an item, while at each iteration of the local search, waste rectangles produced in the construction phase are merged if possible with adjacent pieces thus creating new rectangles that could be cut with greater value." } @Article{AlvParTam02a, author = "R. Alvarez-Vald\'es and A. Paraj\'on and J.M. Tamarit", title = "A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems", journal = "Computers \& Operations Research", volume = "29", pages = "925--947", year = "2002", annote = "This paper proposes several heuristics for the two-dimensional cutting problem, in which a single stock sheet has to be cut into a set of small pieces, while maximizing the value of the pieces cut. One algorithm is a tabu search procedure, while two further heuristics are simple constructive procedures based on bounds obtained by solving one-dimensional knapsack problems. Those two constructive procedures have been then embedded in a {GRASP}, whose local search looks for an improving solution by merging two adjacent rectangles (i.e. two rectangles that have a common side) into a single rectangle and trying to cut it with a greater value. The authors have also implemented a path-relinking procedure as post-optimization phase for improving the final results of all above cited algorithms.", } @inproceedings{AmaCapMalSig03a, author = {E. Amaldi and A. Capone and F. Malucelli and F. Signori}, title = {{Optimization models and algorithms for downlink {UMTS} radio planning}}, booktitle = {{Wireless Communications and Networking, 2003 (WCNC 2003)}}, volume = {2}, month = {March}, annote = "In this paper, the authors deal with the UMTS base station location problem. Two mathematical programming formulations are provided for locating directive base stations considering downlink (base station to mobile) direction and assuming a power-based as well or a SIR-based (Signal-to-Interface Ratio) power control mechanism. Already in Amaldi et al. (2003), the authors proposed two randomized heuristics, which are adapted in this paper for solving the simailar problem.", year = {2003}, pages = {827--831} } @article{AmaCapMal03a, author = {E. Amaldi and A. Capone and F. Malucelli}, title = {{Planning {UMTS} base station location: {O}ptimization models with power control and algorithms}}, journal = {IEEE Transactions on Wireless Communications}, volume = {2}, number = {5}, year = {2003}, pages = {939--952}, annote = "The UMTS base station location problem is NP-hard and to solve it, the authors propose two greedy randomized algorithms and a tabu search. The greedy function used takes into account the fraction of traffic covered and the installation costs. A swap procedure is used until no improvement can be done." } @incollection{AreVan97a, author = "S. Areibi and A. Vannelli", title = "A {GRASP} clustering technique for circuit partitioning", booktitle = "Satisfiability problems", editor = "J. Gu and P.M. Pardalos", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "35", pages = "711--724", year = "1997", annote = "This paper adapts a basic node interchange scheme for solving the circuit partitioning problem and develops a clustering technique that uses {GRASP} to generate clusters of moderate sizes. The number of clusters is predetermined as a function of the number of partitions required. Initially, the heuristic reads the circuit description and resizes the blocks to be used by {GRASP}, which utilizes only the construction phase to generate the number of required clusters. The {GRASP} construction phase is followed by a post-processing stage, in which a simple dynamic hill climbing algorithm is used as local search to improve the initial solution generated." } @inproceedings{AreVan00a, author = {S. Areibi and A. Vannelli}, title = {Efficient Hybrid Search Techniques For Circuit Partitioning}, booktitle = {{IEEE 4th World Multiconference on Circuits, Systems, Communications \& Computers}}, city = {Athens, Greece}, month = {July}, year = {2000}, annote = "In this paper, for solving the problem the authors apply a simulated annealing, a tabu search, a {GRASP}, and a genetic algorithm. Two further search techniques are also proposed as hybrids, where a {GRASP} and a genetic algorithm are used for generating good initial partitions." } @inproceedings{Are99a, author = "S.M. Areibi", title = "{GRASP}: {A}n effective constructive technique for {VLSI} circuit partitioning", booktitle = "Proc. IEEE Canadian Conference on Electrical \& Computer Engineering (CCECE'99)", city="Edmonton, Alberta, Canada", month = "May", year = "1999", volume = {1}, pages = {462--467}, annote = "This article proposes a {GRASP} for obtaining good initial solutions for an iterative improvement technique. At each iteration of the randomized approach, the gains associated with moving modules to the current block being filled are examined, and a restricted candidate list is built using the modules with the highest gains." } @inproceedings{CanCorHerSan02a, author = "J.R. Cano and O. Cord\'on and F. Herrera and L. S\'anchez", title = "A {GRASP} Algorithm for clustering", editor = {F. J. Garijo and J.C.R. Santos and M. Toro}, booktitle = {Advances in Artificial Intelligence - IBERAMIA 2002, 8th Ibero-American Conference on AI, Seville, Spain, November 12-15, 2002, Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {2527}, pages = {214--223}, year = {2002}, isbn = {3-540-00131-X}, annote = "A {GRASP} for cluster analysis is described. Construction is done using a randomized greedy Kaufman procedure and local search uses the $K$-means algorithm. High quality solutions are found for benchmark problems. The best solutions are found with a hybid {GRASP}/$K$-means with Kaufman initialization." } @article{ChiKouUrb02a, author = {W.C. Chiang and P. Kouvelis and T.L. Urban}, title = {{Incorporating workflow interference in facility layout design: {T}he quartic assignment problem}}, journal = {Management Science}, volume = {48}, number = {4}, pages = {584--590}, annote = {In this paper, a Branch \& Bound and a Tabu Search algorithms are proposed for the Quartic Assignment Problem. Computational effeciency and performance of the proposed methods have been investigated on a set of randomly generated instances by comparing them with the {GRASP} proposed in Mavridou et al. (1998) for the Biquadratic Assignment Problem.}, year = {2002} } @techreport{DelDiaFerOrt97a, author = "H. Delmaire and J.A. D\'{\i}az and E. Fern\'andez and M. Ortega", title = "Comparing new heuristics for the pure integer capacitated plant location problem", number = "DR97/10", institution = "Department of Statistics and Operations Research, Universitat Politecnica de Catalunya", address = "Barcelona, Spain", year = "1997", annote = "To solve the pure integer capacitated plant location problem, several heuristics are proposed: evolutionary algorithms, {GRASP}, simulated annealing, and tabu search. All the algorithms share the same neighborhood definition, which can be one of the following: client plant, client reassignment, client interchange, open plans interchange, and open-closed plants interchange." } @Article{DelDiaFerOrt99a, author = "H. Delmaire and J.A. D\'{\i}az and E. Fern\'andez and M. Ortega", title = "Reactive {GRASP} and tabu search based heuristics for the single source capacitated plant location problem", journal = "INFOR", volume = "37", pages = "194--225", year = "1999", annote = "The single source capacitated plant location problem is a discrete location problem that takes into account capacities in the plants to be opened and imposes that clients be served from a single open plant. The authors propose a hybrid heuristic that embeds reactive {GRASP} in a tabu search algorithm as a diversification method that provides elite i candidate sets. Intensification is also done.", } @phdthesis{Gar01a, author = "J.A. D\'{\i}az Garc\'{\i}a", title = "Algorithmic approaches for the single source capacitated plant location problem", school = "Departamento d'Estad\'{\i}stica i Investigaci\'o Operativa, Univarsitat Polit\'ecnica de Catalunya", address = "Barcelona, Spain", annote = {Scope of this thesis has been to propose several algorithmic alternatives based on both exact and approximate methods for efficiently solving the single source capacitated plant location problem. One of the proposals is a reactive {GRASP} that uses a greedy function based on a percentage of the sum of the cost associated with opening a plant and the cost of allocating clients. The local search procedure uses two neighborhood structures: a client shift neighborhood and a client swap neighborhood.}, year = "2001" } @techreport{GomSil99a, author = "M.J.N. Gomes and J.B.C. {da Silva}", title = "An experimental evaluation of the {GRASP} metaheuristic applied to the uncapacitated location problem", number = "004/99", institution = "Department of Statistics and Computation, State University of Cear\'a", address = "Fortaleza, Cear\'a, Brazil", year = "1999", annote = "Two {GRASPs}, one using the ADD heuristic and the other using the DROP heuristic, are proposed for the uncapacitated location problem. Computational experiments with instances from Beasley's OR-Library show that {GRASP}-DROP dominates {GRASP}-ADD, while both {GRASPs} dominate ADD and DROP." } @incollection{HolMigPar97a, author = "K. Holmqvist and A. Migdalas and P.M. Pardalos", title = "Greedy randomized adaptive search for a location problem with economies of scale", booktitle = "Developments in Global Optimization", editor = "I.M. Bomze et al.", publisher = "Kluwer Academic Publishers", pages = "301--313", year = "1997", annote = "This paper proposes a {GRASP} for finding approximate solutions to a facility location problem with concave costs. The greedy function of the construction phase favors the facilities that give lower cost for a costumer, regarding the effect that already connected costumers have on the solution. The neighborhood function is defined as changing facility connection for one costumer. Instead of a time consuming computation of the objective function value for each neighborhood solution, the difference in cost for changing supplier is examined." } @Article{Kli92a, author = "J.G. Klincewicz", title = "Avoiding local optima in the $p$-hub location problem using tabu search and {GRASP}", journal = "Annals of Operations Research", volume = "40", pages = "283--302", year = "1992", annote = "This paper proposes two heuristics based on tabu search and {GRASP} for the $p$-hub location problem. The objective is to overcome the difficulty that local search algorithms encounter. The local search procedure of proposed {GRASP} is based on the $2$-exchange.", } @Article{Kli02a, author = "J.G. Klincewicz", title = "Enumeration and search procedures for a hub location problem with economies of scale", journal = "Annals of Operations Research", volume = "110", pages = "107--122", year = "2002", annote = "An optimal enumeration scheme, as well as other heuristics based on tabu search and {GRASP} are proposed for locating hubs in a communications or transportation network. The {GRASP} greedy function takes into account the amount of originating and terminating traffic. The local search uses a $1-1$ swap neighborhood structure.", } @inproceedings{KumSriWanLanRam01a, author = {K. Kumaran and A. Srinivasan and Q. Wang and S. Lanning and K.G. Ramakrishnan}, title = {Efficient algorithms for location and sizing problems in network design}, booktitle = {Global Telecommunications Conference, 2001 (GLOBECOM '01)}, publisher = {IEEE}, volume = {4}, annote = {The authors develop algorithms based on linear programming and a slight modified {GRASP}, in which the costruction phase is performed at random. Given an initial solution, the local search procedure exhaustively evaluate objective function value for all possible single location changes.}, year = {2001}, pages = {2586--2590} } @techreport{ResWer03c, author = {M.G.C. Resende and R.F. Werneck}, title = {{A hybrid multistart heuristic for the uncapacitated facility location problem}}, institution = {Internet and Network Systems Research Center, AT\&T Labs Research}, address = {Florham Park, NJ}, year = {2003}, annote = {In this paper, a multistart heuristic is proposed based on an idea already proposed by the authors in Resende and Werneck (2004). The algorithm consists in two phases. The first phase is a multistart procedure that builds a randomized solution from which to apply a local search routine and a path relinking. The second is a post-optimization phase realized by applying path relinking over the whole elite set.}, note = {Submitted to {\em European J. of Operational Research}.} } @article{ResWer04a, author = {M.G.C. Resende and R.F. Werneck}, title = {A hybrid heuristic for the p-median problem}, journal = {Journal of Heuristics}, volume = {10}, pages = {59--88}, year = {2004}, annote = {Given a set of $m$ potential facilities and $n$ cosumers, the $p$-median problem consists in finding a subset of $p$ facilities ($p\leq m$) such that the cost of serving all costumers is minimized. The authors present in this paper a {GRASP} with path relinking as intensification and post-optimization phase. The greedy function chooses most profitable facilities, but several different constructive algorithms have been embedded into the {GRASP} framework: pure random, random plus greedy, randomized greedy, proportional greedy, proportional worst, and sample greedy. The methods are distinguishable much more by their computational time than the quality of the solutions they provide.} } @Article{SerCol01a, author = "D. Serra and R. Colom\'e", title = "Consumer choice in competitive location models: {F}ormulations and heuristics", journal = "Papers in Regional Science", volume = "80", pages = "439--464", year = "2001", annote = "This paper studies the importance of customer behavior with respect to distance or transportation costs in the optimality of locations obtained by traditional state-of-the-art competitive location models. The authors propose four models to represent the problem and propose a hybrid metaheuristic for solving it. The proposed method consists of two phases. In the first phase, a good initial solution is found by applying a {GRASP} procedure, while in the second phase the previous solution found is improved by applying a tabu search heuristic.", } @techreport{SilSer02a, author = {F. Silva and D. Serra}, title = {{Locating emergency services with priority rules: {T}he priority queuing covering location problem}}, institution = "Research group in management logistics, Department of Economics and Business, Universitat Pompeu Fabra", series = {Working Paper}, number = {1}, address = "Barcelona, Spain", annote = {The greedy criterion used by the {GRASP} proposed in this paper is based on distances. The local search iteratively for each server at a time de-allocates all demands allocated to it and move them to all possible unused canditates.}, year = "2002" } @Article{Urb98a, author = "T.L. Urban", title = "Solution procedures for the dynamic facility layout problem", journal = "Annals of Operations Research", vol = "76", pages = "323--342", year = "1998", annote = "The concept of incomplete dynamic programming is applied to the dynamic facility layout problem and a lower bound for the general problem is developed. A {GRASP} and an initialized multi-greedy algorithm are described to provide a solution methodology for large problems. The {GRASP} is the algorithm proposed by Li, Pardalos, and Resende (1994) for dense quadratic assignment problems.", } @Article{UrbChiRus00a, author = "T.L. Urban and W.-C. Chiang and R.A. Russel", title = "The integrated machine allocation and layout problem", journal = "International Journal of Production Research", volume = "38", pages = "2911--2930", year = "2000", annote = "{GRASP} is used to solve quadratic assignment sub-problems in a model that aggregates quadratic assignment problems with several network flow problems with side constraints. This model is used to produce machine layouts where machines are not required to be placed in a functional or cellular layout.", }