Heuristicas de descomposicion lagrangiana para algunos problemas de localizacion discreta
Tóm tắt
En este trabajo se considera el Problema de Localización de Plantas Simple y el Problema de lap-Mediana Generalizado. Se construyen dos algoritmos heurísticos, uno para cada problema, basados en una técnica de descomposición lagrangiana para problemas binarios. Los algoritmos son implementados en un microordenador y ejecutados sobre una serie de problemas generados aleatoriamente. Los resultados computacionales son comparados con los de otros dos algoritmos heurísticos basados en la optimización subgradiente de la función dual.
Tài liệu tham khảo
BEASLEY, J. E. (1990): «Lagrangian heuristics for location problems»,Working paper, The Management School, Imperial College, Londres.
CHO, D. C.; JOHNSON, E. L.; PADBERG, M., y RAO, M. R. (1983): “On the uncapacitated Plant Location Problem. I: Valid inequalities and Facets. II: Facets and Lifting theorems»,Math. of. O. R., vol. 8, n°. 4, 579–612.
CONN, A. R., y CORNUEJOLS, G. (1990): «A Projection method for the uncapacitated facility location problem»,Math. Programming, 46, 273–298.
CORNUÉJOLS, G.; FISHER, M. L. y NEMHAUSER, G. L. (1977): «On the uncapacitated location problem»,Ann. Discrete Math., 1, 163–177.
DOMCHKE, W., y DREXH, A. (1985):Location and Layout Planning: An International Bibliography, Springer-Verlag.
ERLENKOTTER, D. (1978): «A Dual-Based Procedure for Uncapacitated Facility Location»Operations Research, 26, 992–1010.
FISHER (1981): «The Lagrangian relaxation method for solving integer programming problems»,Management Science, 27, 1–18.
GUIGNARD, M., y ROSENWEIN, M. B. (1989): «An application-oriented guide for designing Lagrangean dual ascent algorithms»,European Journal of O. R., 43, 197–205.
HOCHBAUM, D. J. (1982): «Heuristic for the fixed cost median problem»,Math. Programming, 22, 148–162.
KRARUP, J., y PRUZAN, P. M. (1983): «The simple plant location problem: Survey and synthesis»,European Journal of O. R., 12, 36–81.
SPÄTH, H. (1980):Cluster Analysis Algorithms for data reduction and classification of objects, Ellis Horwood Limited, Chichester.
TEITZ, M. B., y BART, P. (1968): «Heuristic Methods for Vertex Median of a Weighted Graph»,Operations Research, 16, 955–962.