A Model for Optimal Multicommodity Network Flows with Resource Allocation

摘要

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming. However, the number of arcs and resources in many applications is such that the standard formulation becomes very costly. This paper describes an approach-an extension of the column generation technique used in the multicommodity network flow problem-that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal in the sense that flow attainable is constrained by resource availability and network capacity. Extension to the minimum-cost formulation is proposed and computational experience is discussed. (Author)