A Dual-Based Procedure for Dynamic Facility Location
提出一种结合对偶上升法的分支定界过程，用于求解动态设施选址问题，计算测试表明该方法优于已有方法，能在一秒内求解25个潜在设施、50个客户和10个时间周期的问题。
In dynamic facility location problems, one desires to select the time-staged establishment of facilities at different locations so as to minimize the total discounted costs for meeting demands specified over time at various customer locations. We formulate a particular dynamic facility location problem as a combinatorial optimization problem. The formulation permits both the opening of new facilities and the closing of existing ones. A branch-and-bound procedure incorporating a dual ascent method is presented and shown, in computational tests, to be superior to previously developed methods. The procedure is comparable to the most efficient methods for solving static (single-period) location problems. Problems with 25 potential facility locations, 50 customer locations, and 10 time periods have been solved within one second of CPU time on an IBM 3033 computer. Extensions of the dynamic facility location problem that allow price-sensitive demands, linearized concave costs, interdependent projects, multiple stages, and multiple commodities also can be solved by the dual ascent method. The method can serve as a component of a solution process for capacitated dynamic location problems.