Selecting hierarchical facilities in a service-operations environment. (English) Zbl 1026.90022
Summary: This paper presents and solves a hierarchical model for the location of service facilities and further looks at the operational issues associated with managing such facilities. By the very nature of the demand they serve, service systems require that timely service be readily available to those who need it. We argue that the location–allocation of such facilities often involves several layers of service. When all of a facility’s resources are needed to meet each demand for service, and demand cannot be queued, the need for a backup unit may be required. Effective siting decisions must address both the need for a backup response facility for each demand point and a reasonable limit on each facility’s workload. The paper develops an integer linear programming model for locating facilities offering several layers of service. A Lagrangian relaxation methodology coupled with a heuristic is employed. Results of extensive computational experiments are presented to demonstrate the viability of the approach.
MSC:
| 90B22 | Queues and service in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Batta, R.; Mannur, N., Covering-location models for emergency situations that require multiple response units, Management Science, 36, 16-23 (1990) · Zbl 0694.90046 |
| [2] | Bianchi, G.; Church, R., A hybrid fleet model for emergency medical service systems design, Social Sciences Medicine, 26, 163-171 (1988) |
| [3] | Brandeau, M.; Chiu, S., An overview of representative problems in location research, Management Science, 35, 527-552 (1989) |
| [4] | Church, R.; Current, J.; Storbeck, J., A bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand, Decision Sciences, 22, 38-52 (1991) |
| [5] | Church, R.; ReVelle, C., The maximal covering location problem, Papers of Regional Science Association, 32, 101-118 (1974) |
| [6] | CPLEX, 1993. CPLEX Optimization, Inc. NV; CPLEX, 1993. CPLEX Optimization, Inc. NV |
| [7] | Current, J.; Storbeck, J. E., Capacitated covering models, Environment and Planning B, 14, 183-192 (1988) |
| [8] | Daskin, M., Application of an expected covering model to emergency medical service system design, Decision Sciences, 13, 416-439 (1982) |
| [9] | Daskin, M., Network and Discrete Location: Models, Algorithms, and Applications (1995), John Wiley & Sons: John Wiley & Sons New York · Zbl 0870.90076 |
| [10] | Eaton, D.; Daskin, M.; Simmons, D.; Bullock, B.; Jausma, G., Determining emergency medical service vehicle deployment in Austin, Texas, Interfaces, 15, 96-108 (1985) |
| [11] | Fisher, M., An applications oriented guide to Lagrangian relaxation, Interfaces, 15, 10-21 (1985) |
| [12] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [13] | Holmberg, K., A Lagrangian heuristic based brunch-and-bound approach for the capacitated network design problem, Operations Research, 48, 461-481 (2000) · Zbl 1106.90381 |
| [14] | Hunting, M.; Faigle, U.; Kern, W., A Lagrangian relaxation approach to the edge-weighted clique problem, European Journal of Operational Research, 119-131 (2001) · Zbl 1039.90044 |
| [15] | Jack, C.; Kai, S. R.; Shulman, A., NETCAP: An interactive optimization system for GTE telephone network planning, Interfaces, 22, 72-89 (1992) |
| [16] | Jain, K.; Vazirani, V., Approximation algorithms for metric facility location and kappa-median problems using the primal-dual schema and Lagrangian relaxation, Association of Computing Machinery, 274-296 (2001) · Zbl 1138.90417 |
| [17] | Johnson, E.; Padberg, M., A note on the knapsack problem with special ordered sets, Operations Research Letters, 1, 18-22 (1981) · Zbl 0493.90062 |
| [18] | Keenan, P., Spatial decision support systems for vehicle routing, Decision Support Systems, 22, 1, 65-71 (1998) |
| [19] | Mandell, M., Covering models for two-tiered emergency medical service systems, ISOLDE VII, Edmonton, Canada (1996) |
| [20] | Marianov, V.; Serra, D., Hierarchical location-allocation models for congested systems, European Journal of Operational Research, 135, 195-208 (2001) · Zbl 1077.90548 |
| [21] | Narasimhan, S., The concentrator location problem with varying coverage, Computer Networks ISDN Systems, 19, 1-10 (1990) |
| [22] | Narasimhan, S.; Pirkul, H.; Schilling, D., Capacitated emergency facility siting with multiple levels of backup, Annals of Operations Research, 40, 235-248 (1992) · Zbl 0782.90062 |
| [23] | Narula, S., Hierarchical location-allocation problems: A classification scheme, European Journal of Operational Research, 15, 93-99 (1984) · Zbl 0525.90038 |
| [24] | Narula, S., Minisum hierarchical location-allocation problems on a network, Annals of Operations Research, 6, 257-272 (1986) |
| [25] | Papadimitriou, C.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [26] | Pirkul, H.; Jayaraman, V., Production, transportation and distribution planning in a multi-commodity tri-echelon system, Transportation Science, 30, 4, 291-302 (1996) · Zbl 0879.90129 |
| [27] | Pirkul, H.; Schilling, D., The maximal covering location problem with capacities on total workload, Management Science, 37, 2, 233-248 (1991) · Zbl 0732.90045 |
| [28] | Pirkul, H.; Gupta, R.; Rolland, E., VisOpt: A visual interactive optimization tool for P-median problems, Decision Support Systems, 26, 3, 209-223 (1999) |
| [29] | Schilling, D.; Jayaraman, V.; Barkhi, R., A review of covering problem in facility location, Location Science, 1, 25-55 (1993) · Zbl 0923.90108 |
| [30] | Serra, D., The coherent covering location problem, The Journal of RSAI, 75, 1, 79-101 (1996) |
| [31] | Serra, D.; ReVelle, C., The pq-medial problem: Location and districting of hierarchical facilities, Location Science, 1, 4, 299-312 (1993) · Zbl 0926.90058 |
| [32] | Serra, D.; ReVelle, C., The pq-medial problem: Location and districting of hierarchical facilities-II, Location Science, 2, 1, 63-82 (1994) · Zbl 0919.90103 |
| [33] | Simpson, N.; Erenguc, S., Modeling the order picking function in supply chain systems: Formulation, experimentation and insights, IIE Transactions, 33, 119-130 (2001) |
| [34] | Sprague, R. H.; Carlson, E. D., Building Effective Decision Support Systems (1982), Prentice Hall: Prentice Hall Englewood Cliffs, NJ |
| [35] | Tien, J. M.; El-Tell, K.; Simons, G. R., Improved formulations to the Hierarchical health facility location-allocation problems, IEEE Transactions on Systems, Man, and Cybernetics, 13, 1128-1132 (1983) |
| [36] | Tracey, M.; Dror, M., Interactive graphical computer application for large scale cattle feed distribution management, Decision Support Systems, 19, 61-72 (1997) |
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.
