Abstract
Constructive greedy heuristics are algorithms that try to iteratively construct feasible solutions for combinatorial optimization problems from the scratch. For this they make use of a greedy scoring function, which evaluates the myopic impact of each possible element with respect to the solution under construction. Although fast, effective, and even exact for some problem classes, greedy heuristics might construct poor solution when applied to difficult (NP-hard) problems. To avoid such pitfalls we suggest the approach of parametrizing the scoring function by including several different myopic aspects at once, which are weighted against each other. This so-called pgreedy approach can be embedded into the metaheuristic concept of GRASP. The hybrid metaheuristic of GRASP with a parametrized scoring function is called parametrized GRASP heuristic (PGRASP). We present a PGRASP algorithm for the axial three index assignment problem (AP3) and computational results comparing PGRASP with the classical GRASP strategy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiex, R.M., Resende, M.G.C., Pardalos, P.M., Toraldo, G.: GRASP with Path Relinking for Three-Index Assignment. INFORMS Journal on Computing 17(2), 224–247 (2005), Software available at URL http://www.research.att.com/~mgcr/
Balas, E., Saltzman, M.J.: An Algorithm for the Three-Index Assignment Problem. Oper. Res. 39, 150–161 (1991)
Burkard, R.E., Rudolf, R., Woeginger, G.J.: Three-dimensional axial assignment problems with decomposable cost coefficients. Discrete Applied Mathematics 65, 123–139 (1996)
Crama, Y., Spieksma, F.C.R.: Approximation algorithms for three-dimensional assignment problems with triangle inequalities. European Journal of Oper. Res. 60, 273–279 (1992)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8, 67–71 (1989)
Fügenschuh, A.: The Integrated Optimization of School Starting Times and Public Transport. PhD Thesis, Logos Verlag Berlin, 165 pages (2005)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Glover, F.: Tabu Search and Adaptive Memory Programming - Advances, Applications and Challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research, pp. 1–75. Kluwer Academic Publishers, Dordrecht (1996)
ILOG CPLEX, ILOG, Inc., 1080 Linda Vista Ave. Mountain View, CA 94043. Information available at URL http://www.ilog.com/products/cplex/
Kaballo, W.: Einführung in die Analysis III (in German). Spektrum Akademischer Verlag, Heidelberg (1998)
Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7, 48–50 (1956)
Laguna, M., Marti, R.: GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization. INFORMS Journal on Computing 11, 44–52 (1999)
Pierskalla, W.P.: The Tri-Substitution Method for the Three-Dimensional Assignment Problem. Canadian Operational Research Society Journal 5(2), 71–81 (1967)
Pierskalla, W.P.: The Multi-Dimensional Assignment Problem. Operations Research 16(2), 422–431 (1968)
Prim, R.C.: Shortest connection networks and some generalizations. Bell System Tech. J. 36, 1389–1401 (1957)
Resende, M.G.C.: Test Data for the Three Index Assignment Problem, online available at URL http://www.research.att.com/~mgcr/data/
Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 219–249. Kluwer Academic Publishers, Dordrecht (2003)
Romeijn, H.E., Smith, R.L.: Simulated Annealing for Constrained Global Optimization. Journal of Global Optimization 5, 101–126 (1994)
Smith, R.L.: Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions. Operations Research 32, 1296–1308 (1984)
Zabinsky, Z.B.: Stochastic Adaptive Search for Global Optimization. Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Boston (2003)
Zabinsky, Z.B., Smith, R.L., McDonald, J.F., Romeijn, H.E., Kaufman, D.E.: Improving Hit-and-Run for Global Optimization. Journal of Global Optimization 3, 171–192 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fügenschuh, A., Höfler, B. (2006). Parametrized GRASP Heuristics for Three-Index Assignment. In: Gottlieb, J., Raidl, G.R. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2006. Lecture Notes in Computer Science, vol 3906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730095_6
Download citation
DOI: https://doi.org/10.1007/11730095_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33178-0
Online ISBN: 978-3-540-33179-7
eBook Packages: Computer ScienceComputer Science (R0)