2000 | OriginalPaper | Buchkapitel
Lagrangean/Surrogate Heuristics for p-Median Problems
verfasst von : Edson L. F. Senne, Luiz A. N. Lorena
Erschienen in: Computing Tools for Modeling, Optimization and Simulation
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The p-median problem is the problem of locating p facilities (medians) on a network so as to minimize the sum of all the distances from each demand point to its nearest facility. A successful approach to approximately solve this problem is the use of Lagrangean heuristics, based upon Lagrangean relaxation and subgradient optimization. The Lagrangean/surrogate is an alternative relaxation proposed recently to correct the erratic behavior of subgradient like methods employed to solve the Lagrangean dual. We propose in this paper Lagrangean/surrogate heuristics to p-median problems. Lagrangean and surrogate relaxations are combined relaxing in the surrogate way the assignment constraints in the p-median formulation. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). Lagrangean/surrogate relaxations are very stable (low oscillating) and reach the same good results of Lagrangean (alone) heuristics in less computational times. Two primal heuristics was tested, an interchange heuristic and a location-allocation based heuristic. The paper presents several computational tests which have been conducted with problems from the literature, a set of instances presenting large duality gaps, a set of time consuming instances and a large scale instance.