Complexity of robust single facility location problems on networks with uncertain edge lengths

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 epsilon-optimal for any possible realization of edge lengths, with epsilon 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. (C) 2002 Elsevier Science B.V. All rights reserved.