The Multiregion Dynamic Capacity Expansion Problem, Part II
研究多区域产能扩张与运输调度问题，提出一种通过区域间产能交换改进可行解的启发式算法，计算高效且接近最优。
Consider the problem of determining a schedule of capacity expansions for m producing regions and a schedule of shipments from the regions to the n markets so as to meet the market demands over a T-period planning horizon at minimum discounted capacity expansion and shipment costs. The capacity expansion costs are assumed to be in the form of a fixed charge plus a cost proportional to the size of the expansion and the shipment costs are assumed to be proportional to the amounts involved. The heuristic algorithm of this paper improves on feasible solutions by the exchange of capacities between pairs of regions. The algorithm imbeds a branch and bound procedure to determine the optimal amounts for the pair-wise exchange of capacities and uses as a subroutine the corresponding algorithm for linear capacity expansion costs developed in an earlier paper. Computational results for both real and randomly generated problems show that the heuristic algorithm is computationally efficient and yields close to optimum solutions.