A decomposition approach for an equipment selection and multiple product routing problem incorporating environmental factors

We address a medium- to long-term planning problem concerned with choosing manufacturing and waste mitigation equipment, and routing products, while accounting for environmental effects such as process waste streams and energy consumption. We formulate the problem as a mixed-integer program with an embedded multi-commodity network flow structure. A distinguishing feature of our model is that we allow each machine to be operated in different modes that may affect environmental impacts and costs. Because of this feature, we need a more general type of bundle constraint to model resource capacities. We also require constraints that apply across the network to limit waste generation and energy usage. In network terminology, this is equivalent to allowing bundle constraints to span fairly arbitrary sets of arcs. We develop a new procedure based on Benders' decomposition and column generation to solve the problem. We also present computational experience with this procedure and related insights. (C) 2003 Elsevier B.V. All rights reserved.