×

zbMATH — the first resource for mathematics

Robust weighted vertex \(p\)-center model considering uncertain data: an application to emergency management. (English) Zbl 1317.90166
Summary: This paper presents a generalized weighted vertex \(p\)-center (WVPC) model that represents uncertain nodal weights and edge lengths using prescribed intervals or ranges. The objective of the robust WVPC (RWVPC) model is to locate \(p\) facilities on a given set of candidate sites so as to minimize worst-case deviation in maximum weighted distance from the optimal solution. The RWVPC model is well-suited for locating urgent relief distribution centers (URDCs) in an emergency logistics system responding to quick-onset natural disasters in which precise estimates of relief demands from affected areas and travel times between URDCs and affected areas are not available. To reduce the computational complexity of solving the model, this work proposes a theorem that facilitates identification of the worst-case scenario for a given set of facility locations. Since the problem is \(NP\)-hard, a heuristic framework is developed to efficiently obtain robust solutions. Then, a specific implementation of the framework, based on simulated annealing, is developed to conduct numerical experiments. Experimental results show that the proposed heuristic is effective and efficient in obtaining robust solutions. We also examine the impact of the degree of data uncertainty on the selected performance measures and the tradeoff between solution quality and robustness. Additionally, this work applies the proposed RWVPC model to a real-world instance based on a massive earthquake that hit central Taiwan on September 21, 1999.

MSC:
90B80 Discrete location and assignment
PDF BibTeX Cite
Full Text: DOI
References:
[1] Albareda-Sambola, M.; Dı́az, J. A.; Fernández, E., Lagrangean duals and exact solution to the capacitated p-center problem, European Journal of Operational Research, 201, 71-81, (2010) · Zbl 1177.90241
[2] Altay, N.; Green, W. G., OR/MS research in disaster operations management, European Journal of Operational Research, 175, 475-493, (2006) · Zbl 1137.90574
[3] Altiparmak, F.; Gen, M.; Lin, L.; Paksoy, T., A genetic algorithm approach for multi-objective optimization of supply chain networks, Computers and Industrial Engineering, 51, 196-215, (2006)
[4] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and approximation - combinatorial optimization problems and their approximability properties, (1999), Springer Verlag · Zbl 0937.68002
[5] Averbakh, I.; Berman, O., Minimax regret p-center location on a network with demand uncertainty, Location Science, 5, 247-254, (1997) · Zbl 0928.90042
[6] Averbakh, I.; Berman, O., Algorithms for the robust 1-center problem on a tree, European Journal of Operational Research, 123, 292-302, (2000) · Zbl 0967.90065
[7] Averbakh, I., Complexity of robust single facility location problems on networks with uncertain edge lengths, Discrete Applied Mathematics, 127, 505-522, (2003) · Zbl 1038.90041
[8] Balcik, B.; Beamon, B. M., Facility location in Humanitarian relief, International Journal of Logistics: Research and Applications, 11, 101-121, (2008)
[9] Burkard, R. E.; Dollani, H., A note on the robust 1-center problem on trees, Annals of Operations Research, 110, 69-82, (2002) · Zbl 1013.90075
[10] Campbell, A. M.; Jones, P. C., Prepositioning supplies in preparation for disasters, European Journal of Operational Research, 209, 156-165, (2011) · Zbl 1208.90102
[11] Chang, M.-S.; Tseng, Y.-L.; Chen, J.-W., A scenario planning approach for the flood emergency logistics preparation problem under uncertainty, Transportation Research Part E, 43, 737-754, (2007)
[12] Current, J.; Daskin, M. S.; Schilling, D., Discrete network location models, (Drezner, Z.; Hamacher, H. W., Facility Location: Applications and Theory, (2002), Springer New York), 81-118 · Zbl 1061.90070
[13] Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications, (1995), John Wiley and Sons New York · Zbl 0870.90076
[14] Huang, R.; Kim, S.; Menezes, M. B.C., Facility location for large-scale emergencies, Annals of Operations Research, 181, 271-286, (2010) · Zbl 1209.90236
[15] Jia, H.; Ordonez, F.; Dessouky, M. M., A modeling framework for facility location of medical services for large-scale emergencies, IIE Transactions, 39, 41-55, (2007)
[16] Jia, H.; Ordonez, F.; Dessouky, M. M., Solution approaches for facility location of medical supplies for large-scale emergencies, Computers and Industrial Engineering, 52, 257-276, (2007)
[17] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems I: the p-centers, SIAM Journal on Applied Mathematics, 37, 513-538, (1979) · Zbl 0432.90074
[18] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer Academic Publishers Boston · Zbl 0873.90071
[19] Majumdar, J.; Bhunia, A. K., Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, Journal of Computational and Applied Mathematics, 235, 3063-3078, (2011) · Zbl 1210.65113
[20] Mete, H. O.; Zabinsky, Z. B., Stochastic optimization of medical supply location and distribution in disaster management, International Journal of Production Economics, 126, 76-84, (2010)
[21] Ministry of the Interior, Taiwan, 2000. National Earthquake Preparedness Report, Taipei.
[22] Mirchandani, P. B.; Francis, R. L., Discrete location theory, (1990), Wiley New York · Zbl 0718.00021
[23] Sheu, J.-B., An emergency logistics distribution approach for quick response to urgent relief demand in disasters, Transportation Research Part E, 43, 687-709, (2007)
[24] Sheu, J.-B., Dynamic relief-demand management for emergency logistics operations under large-scale disasters, Transportation Research Part E, 46, 1-17, (2010)
[25] Snyder, L. V., Facility location under uncertainty: a review, IIE Transactions, 38, 547-564, (2006)
[26] Suman, B.; Kumar, P., A survey of simulated annealing as a tool for single and multiobjective optimization, Journal of the Operational Research Society, 57, 1143-1160, (2006) · Zbl 1121.90065
[27] Yi, W.; Ozdamar, L., A dynamic logistics coordination model for evacuation and support in disaster response activities, European Journal of Operational Research, 179, 1177-1193, (2007) · Zbl 1163.90377
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.