Best and Worst Values of the Optimal Cost of the Interval Transportation Problem

We address the Interval Transportation Problem (ITP), that is, the transportation problem where supply and demand are uncertain and vary over given ranges. We are interested in determining the best and worst values of the optimal cost of the ITP among all the realizations of the uncertain parameters. In this paper, we prove some general properties of the best and worst optimum values from which the existing results derive as a special case. Additionally, we propose an Iterated Local Search algorithm to find a lower bound on the worst optimum value. Our algorithm is competitive compared to the existing approaches in terms of quality of the solution and in terms of computational time.