Robust capacity expansion of a network under demand uncertainty: a bi-objective approach

This paper deals with the problem of capacity expansion of a network under independent uncertain demands defined by interval sets. In this context, decisions about capacity expansion must be made before the demands are revealed. Standard robust models require the definition of an uncertainty domain and look for the minimum cost solution able to satisfy any demand within this domain. We propose, justify, and illustrate an alternative robust model based on a bi-objective formulation. Therefore, in addition to the cost criterion, we consider a second criterion, related to the Quality of Service, which measures the ability of a solution to handle any demand. The decision-maker can be interested in efficient solutions offering a compromise between these criteria. We study the complexity of the enumeration of the corresponding nondominated set, and propose exact and approximation algorithms. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(3), 185–199 2016