%0 Journal Article
%@holdercode {isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}
%@nexthigherunit 8JMKD3MGPCW/3ESGTTP
%@archivingpolicy denypublisher denyfinaldraft12
%@dissemination PORTALCAPES; COMPENDEX.
%3 10-1.1023_A_1027353520175.pdf
%X The search for p-median vertices on a network (graph) is a classical location problem. The p facilities (medians) must be located so as to minimize the sum of the distances from each demand vertex to its nearest facility. The Capacitated p-Median Problem (CPMP) considers capacities for the service to be given by each median. The total service demanded by vertices identified by p-median clusters cannot exceed their service capacity. Primal-dual based heuristics are very competitive and provide simultaneously upper and lower bounds to optimal solutions. The Lagrangean / surrogate relaxation has been used recently to accelerate subgradient like methods. The dual lower bound have the same quality of the usual Lagrangean relaxation dual but is obtained using modest computational times. This paper explores improvements on upper bounds applying local search heuristics to solutions made feasible by the Lagrangean/surrogate optimization process. These heuristics are based on location-allocation procedures that swap medians and vertices inside the clusters, reallocate vertices, and iterate until no improvements occur. Computational results consider instances from the literature and real data obtained using a geographical information system.
%N 4
%T Local search heuristics for capacitated p-median problems
%@electronicmailaddress lorena@lac.inpe.br
%K location problems, capacitated p-median problems, clustering, Lagrangean/surrogate relaxation, subgradient method.
%@secondarytype PRE PI
%@usergroup administrator
%@usergroup jefferson
%@group LAC-INPE-MCT-BR
%@secondarykey INPE-10885-PRE/6341
%@copyholder SID/SCD
%@issn 1566-113X
%@issn 1572-9427
%2 sid.inpe.br/marciana/2004/01.19.11.25.17
%@affiliation Instituto Nacional de Pesquisas Espaciais (INPE)
%@affiliation FEG/UNESP, Universidade Estadual Paulista, Faculdade de Engenharia, Departamento de Matemática
%@project FAPESP (proc. 96/04585-6); CNPq (proc. 350034/91-5 and 302408/88-6).
%B Networks and Spatial Economics
%@versiontype publisher
%P 407-419
%4 sid.inpe.br/marciana/2004/01.19.11.25
%@documentstage not transferred
%D 2003
%V 3
%A Lorena, Luiz Antonio Nogueira,
%A Senne, Edson Luiz França,
%@area COMP