Abordagens complementares para problemas de p-medianas
Complementary approaches for p-median location problems
Senne, Edson Luiz F.; Lorena, Luiz Antonio N.
http://dx.doi.org/10.1590/S0103-65132003000300007
Prod, vol.13, n3, p.78-87, 2003
Resumo
A localização de p-medianas é um problema clássico de otimização combinatória. O objetivo é localizar em uma rede p nós (denominados medianas), de forma a minimizar a soma das distâncias de cada nó de demanda até sua mediana mais próxima. Neste trabalho aborda-se a relaxação lagrangeana/surrogate como técnica para resolver tais problemas. Discute-se a utilização desta relaxação em combinação com métodos de otimização por subgradientes e com métodos de geração de colunas. O trabalho apresenta testes computacionais que demonstram a eficiência dos algoritmos propostos, considerando problemas obtidos da literatura e problemas reais obtidos a partir de Sistemas de Informações Geográficas.
Palavras-chave
Problemas de localização, problemas de p-medianas, relaxação lagrangeana/surrogate, geração de colunas, programação inteira
Abstract
The search for p-median vertices on a network is a classical combinatorial optimization problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand vertex to its nearest facility is minimized. This work presents the lagrangean/surrogate relaxation as a technique for solving such combinatorial problems. The paper discusses the use of this relaxation combined with subgradient optimization methods and with column generation methods. Computational tests which demonstrate the eficiency of the proposed approaches for solving p-median instances taken from the literature and obtained from Geographical Information Systems are presented.
Keywords
Location problems, p-median problems, lagrangean/surrogate relaxation, column generation, integer programming
References
BARNHART, C.; JOHNSON, E.L.; NEMHAUSER, G.L.; SAVELSBERGH, M.W.P.; VANCE, P.H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46, 316-329.
BEASLEY, J.E. (1990). OR-Library: Distributing test problems by electronic mail. Journal of Operational Research Society, 41(11), 1069-1072.
BEASLEY, J.E. (1993) Lagrangean heuristics for location problems, European Journal of Operational Research, 65, 383-399.
BRANDEAU, M.L.; CHIU, S.S. (1989). An Overview of Representative Problems in Location Research. Management Science, 35(6), 645-674.
CHRISTOFIDES, N.; BEASLEY, J. E. (1982). A tree search algorithm for the p-median problems. European Journal of Operational Research, 10: 196-204.
COOPER, L. (1963). Location-allocation problems. Operations Research, 11, 331-343.
DANTZIG, G.B.; Wolfe, P. (1960) Decomposition principle for linear programs, Operations Research, 8, 101-111.
DESROCHERS, M.; DESROSIERS, J.; SOLOMON, M. (1992). A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows. Operations Research, 40, 342-354.
DU MERLE, O.; VILLENEUVE, D.; DESROSIERS, J.; HANSEN, P. (1999). Stabilized column generation. Discrete Mathematics, 194, 229-237.
ESRI (1996). Environmental Systems Research Institute, Inc. Avenue Customization and Application Development for ArcView.
GALVÃO, R.D. (1981). A Note on Garfinkel, Neebe and Rao's LP Decomposition for the p-Median Problem, Transportation Science, 15(3), 175-182.
GAREY, M. R. AND JOHNSON, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Co., San Francisco.
GARFINKEL, R.S.; NEEBE, W.; RAO, M.R. (1974). An Algorithm for the M-median Location Problem. Transportation Science, 8, 217-236.
GILMORE, P.C.; GOMORY, R.E. (1961). A linear programming approach to the cutting stock problem. Operations Research, 9, 849-859.
GILMORE, P.C.; GOMORY, R.E. (1963). A linear programming approach to the cutting stock problem - part ii. Operations Research, 11, 863-888.
GLOVER, F. (1968). Surrogate constraints, Operations Research, 16(4), 741-749.
HELD, M.; KARP, R. M. (1971). The traveling-salesman problem and minimum spanning trees: part II. Mathematical Programming, 1, 6-25.
ILOG (1999). Cplex Division, ILOG Inc., CPLEX 6.5.
KELLEY, J.E. (1960). The Cutting Plane Method for Solving Convex Programs. Journal of the SIAM, 8, 703-712.
LORENA, L. A. N.; PEREIRA, M. A. (2002). A Lagrangean/surrogate heuristic for the maximal covering location problem using Hillsman's edition, International Journal of Industrial Engineering, 9(1), 57-67.
LORENA, L. A. N.; SENNE, E. L. F. (1999). Improving Traditional Subgradiente Scheme for Lagrangean Relaxation: An Application to Location Problems, International Journal of Mathematical Algorithms, 1: 133-151.
MARSTEN, R. M.; HOGAN, W.; BLANKENSHIP, J. (1975). The Boxstep method for large-scale optimization. Operations Research, 23, 389-405.
MINOUX, M. (1987). A Class of Combinatorial Problems with Polynomially Solvable Large Scale Set Covering/Set Partitioning Relaxations. RAIRO, 21(2), 105-136.
NEAME, P. J. (1999). Nonsmooth Dual Methods in Integer Programming. Phd Thesis - Department of Mathematics and Statistics, The University of Melbourne.
NEMHAUSER, G.L.; WOLSEY, L.A. (1988). Integer and Combinatorial Optimization. Wiley, New York.
PIZZOLATO, N. D.; BARCELOS, F. B.; LORENA, L. A. N. (2002). School Location Methodology in Urban Areas of Developing Countries. IFORS2002 - The sixteenth triennial conference of the International Federation of Operational Research Societies.
REINELT, G. (1994). The traveling salesman problem: computational solutions for TSP applications. Lecture Notes in Computer Science 840, Springer Verlag, Berlin.
SENNE, E. L. F.; LORENA, L. A. N (2000) Lagrangean/Surrogate Heuristics for p-Median Problems. In: Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J. L. Gonzalez-Velarde (eds.) Kluwer Academic Publishers, 115-130.
SENNE, E. L. F.; LORENA, L. A. N. (2002). Stabilizing column generation using Lagrangean/surrogate relaxation: An application to p-median location problems. European Journal of Operational Research (submetido).
SWAIN, R.W. (1974). A Parametric Decomposition Approach for the Solution of Uncapacitated Location Problems, Management Science, 21, 955-961.
TAILLARD, E.D. (1996). Heuristic methods for large centroid clustering problems, Technical report IDSIA96-96, IDSIA.
VANCE, P. (1993). Crew scheduling, cutting stock and column generation: solving huge integer programs. PhD thesis, Georgia Institute of Technology.
VANCE, P. H.; BARNHART, C.; JOHNSON, E. L.; NEMHAUSER, G. L. (1994) Solving Binary Cutting Stock Problems by Column Generation and Branch-and-Bound. Computational Optimization and Applications, 3, 111-130.
WOLSEY, L. A. (1998). Integer Programming. John Wiley & Sons, New York; H. Freeman and Co., San Francisco.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email