×

The multi-period incremental service facility location problem. (English) Zbl 1177.90242

Summary: 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.

MSC:

90B80 Discrete location and assignment
90C52 Methods of reduced gradient type

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Warszawski, A., Multi-dimensional location problems, Operational Research Quarterly, 24, 165-179 (1973) · Zbl 0256.90054
[2] van Roy, T. J.; Erlenkotter, D., A dual-based procedure for dynamic facility location, Management Science, 28, 1091-1105 (1982) · Zbl 0495.90033
[3] Daskin, M. S.; Hopp, W. J.; Medina, B., Forecast horizons and dynamic facility location planning, Annals of Operations Research, 40, 125-152 (1992) · Zbl 0787.90038
[4] Galvão, R. D.; Santibañez-González, E. R., A Lagrangean heuristic for the \(p_k\)-median dynamic location problem, European Journal of Operational Research, 58, 250-262 (1992) · Zbl 0764.90057
[5] Current, J. R.; Ratick, S.; ReVelle, C. S., Dynamic facility location when the total number of facilities is uncertain: a decision analysis approach, European Journal of Operational Research, 110, 597-609 (1997) · Zbl 0941.90045
[6] Chardaire, P.; Sutter, A.; Costa, M. C., Solving the dynamic facility location problem, Networks, 28, 117-124 (1996) · Zbl 0864.90073
[7] Drezner, Z., Dynamic facility location: the progressive \(p\)-median problem, Location Science, 3, 1-7 (1995) · Zbl 0917.90224
[8] Hinojosa, Y.; Puerto, J.; Fernández, F. R., A multiperiod two-echelon multicommodity capacitated plant location problem, European Journal of Operational Research, 123, 45-65 (2000) · Zbl 0967.90069
[9] Hinojosa, Y.; Kalcsics, J.; Nickel, S.; Puerto, J.; Velten, S., Dynamic supply chain design with inventory, Computers & Operations Research, 35, 373-391 (2008) · Zbl 1141.90021
[10] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems ii: the \(p\)-medians, SIAM Journal of Applied Mathematics, 37, 539-560 (1979) · Zbl 0432.90075
[11] Kennington, J.; Wang, Z., A shortest augmenting path algorithm for the semiassignment problem, Operations Research, 40, 178-187 (1992) · Zbl 0751.90050
[12] Beasley, J. E., OR-Library: distributing test problems by electronic mail, Journal of Operational Research Society, 41, 11, 1069-1072 (1990), (Available at: \( \langle\) http://people.brunel.ac.uk/ mastjjb/jeb/info.html \(\rangle )\)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.