zbMATH — the first resource for mathematics

Complexity of robust single facility location problems on networks with uncertain edge lengths. (English) Zbl 1038.90041
Summary: We consider single-facility location problems on a network with uncertain edge lengths. Specifically, the lengths of edges are assumed to be random with unknown distributions and can take on any values within prespecified intervals of uncertainty. Uncertainty in edge lengths reflects uncertainty in transportation times, or transportation costs, along the edges. It is required to find a robust (minmax regret) solution, that is, a location which is \(\varepsilon\)-optimal for any possible realization of edge lengths, with \(\varepsilon\) as small as possible. We show that such robust location problems are strongly NP-hard, in contrast with robust location problems with only node weights uncertainty that are known to be polynomially solvable.

90B80 Discrete location and assignment
90C35 Programming involving graphs or networks
90C47 Minimax problems in mathematical programming
Full Text: DOI
[1] Averbakh, I., Minmax regret solutions for minimax optimization problems with uncertainty, Oper. res. lett., 27, 2, 57-65, (2000) · Zbl 0988.90026
[2] I. Averbakh, O. Berman, Algorithms for robust center problems. Presented at INFORMS Conference, Dallas, October, 1997. · Zbl 0879.68077
[3] Averbakh, I.; Berman, O., Minmax regret robust Median location on a network under uncertainty, INFORMS J. comput., 12, 2, 104-110, (2000) · Zbl 1034.90007
[4] Averbakh, I.; Berman, O., Algorithms for the robust 1-center problem, Eur. J. oper. res., 123, 292-302, (2000) · Zbl 0967.90065
[5] Chen, B.; Lin, C., Robust one-Median location problem, Networks, 31, 93-103, (1998)
[6] Frank, H., Optimum locations on a graph with probabilistic demands, Oper. res., 14, 409-421, (1966) · Zbl 0142.17704
[7] Frank, H., Optimum locations on a graph with correlated normal demands, Oper. res., 14, 552-557, (1967) · Zbl 0152.38204
[8] Gary, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco
[9] Goldman, A.J., Optimal center location in simple networks, Transportation sci., 5, 212-221, (1971)
[10] P. Kouvelis, G. Vairaktarakis, G. Yu, Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty, Working Paper 93/94-3-4, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas, Austin.
[11] Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer Academic Publishers Boston · Zbl 0873.90071
[12] M. Labbe, D. Peeters, J.-F. Thisse, Location on networks, in: Handbooks in Operations Research and Management Science, Vol. 8, Elsevier, Amsterdam, 1995, pp. 551-624. · Zbl 0862.90088
[13] Labbe, M.; Thisse, J.-F.; Wendell, R., Sensitivity analysis in minisum facility location problems, Oper. res., 39, 961-969, (1991) · Zbl 0748.90037
[14] P.B. Mirchandani, R.L. Francis (Eds.), Discrete Location Theory, Wiley, New York, 1990. · Zbl 0718.00021
[15] Mirchandani, P.B.; Odoni, A.R., Location of medians on stochastic networks, Transportation sci., 13, 85-97, (1979)
[16] Mulvey, J.M.; Vanderbei, R.J.; Zenios, S.A., Robust optimization of large scale systems, Oper. res., 43, 2, 264-281, (1995) · Zbl 0832.90084
[17] B. Tansel, G. Scheuenstuhl, Facility location on tree networks with imprecise data, Research Report IEOR-8819, Bilkent University, 1988.
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.