A column generation approach to capacitated p-median problems

Nenhuma Miniatura disponível

Data

2004-05-01

Orientador

Coorientador

Pós-graduação

Curso de graduação

Título da Revista

ISSN da Revista

Título de Volume

Editor

Elsevier B.V.

Tipo

Artigo

Direito de acesso

Acesso restrito

Resumo

The Capacitated p-median problem (CPMP) seeks to solve the optimal location of p facilities, considering distances and capacities for the service to be given by each median. In this paper we present a column generation approach to CPMP. The identified restricted master problem optimizes the covering of 1-median clusters satisfying the capacity constraints, and new columns are generated considering knapsack subproblems. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. In this work the Lagrangean/surrogate relaxation is directly identified from the master problem dual and provides new bounds and new productive columns through a modified knapsack subproblem. The overall column generation process is accelerated, even when multiple pricing is observed. Computational tests are presented using instances taken from real data from Sao Jose dos Campos' city.

Descrição

Idioma

Inglês

Como citar

Computers & Operations Research. Oxford: Pergamon-Elsevier B.V., v. 31, n. 6, p. 863-876, 2004.

Itens relacionados

Financiadores