The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproble...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2009-05, Vol.36 (5), p.1356-1375
Main Authors: Albareda-Sambola, Maria, Fernández, Elena, Hinojosa, Yolanda, Puerto, Justo
Format: Article
Language:English
Subjects:
Applied sciences
Discrete facility location
Exact sciences and technology
Facilities planning
Heuristic
Hierarchies
Investigació operativa
Lagrange multiplier
Lagrange problem
Lagrange, Equacions de
Lagrangean dual
Location analysis
Logistics
Matemàtiques i estadística
Multiperiod location
Operational research and scientific management
Operational research. Management science
Operations research
Optimització matemàtica
Optimization techniques
Studies
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2008.02.010