Multilocation facility modernization: Models and heuristics

The problem of multilocation facility modernization is described. As integer multicommodity flow formulation is presented. Because of the problem size, exact solutions are not practical, and approximate solution methods are examined. Upper bounds are obtained by LP and Lagrangian relaxation. Near-optimal feasible solutions are obtained by heuristic procedures. The relaxation methods and the heuristics are compared in terms of the computation cost and the quality of the modernization policies produced, where quality is measured by the net present value of cash flows for a number of test problems. Also included is an evaluation of an aggregate modeling approach to multilocation planning, where average costs are employed in a single-location model to determine a homogeneous multilocation modernization policy. This assessment is important, as aggregate models have been employed widely in practice.