1. ¹Stanford University, Stanford, CA, USA
2. ²University of Southern California, Los Angeles, CA, USA

Correspondence: F Ordóñez, Department of Industrial and Systems Engineering, University of Southern California, 3715 McClintock Ave, GER 240, Los Angeles, CA 90089-0193, USA. E-mail: fordon@usc.edu

Received September 2005; Accepted September 2006; Published online 7 February 2007.

Abstract

In many applications, the network design problem (NDP) faces significant uncertainty in transportation costs and demand, as it can be difficult to estimate current (and future values) of these quantities. In this paper, we present a robust optimization-based formulation for the NDP under transportation cost and demand uncertainty. We show that solving an approximation to this robust formulation of the NDP can be done efficiently for a network with single origin and destination per commodity and general uncertainty in transportation costs and demand that are independent of each other. For a network with path constraints, we propose an efficient column generation procedure to solve the linear programming relaxation. We also present computational results that show that the approximate robust solution found provides significant savings in the worst case while incurring only minor sub-optimality for specific instances of the uncertainty.