AN ALGORITHM FOR SOLVING DYNAMIC CAPACITATED PLANT LOCATION-PROBLEMS WITH DISCRETE EXPANSION SIZES

• 成果类型: Article
• 署名作者: SHULMAN, A
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.3.423
• 发表日期: 1991
• 页码: 423-436
• 关键词: FACILITIES EQUIPMENT PLANNING; MULTIPERIOD FACILITIES LOCATION PLANNING; capacity expansion; programming; dynamic programming; Lagrangian relaxation

摘要

In the Dynamic Capacitated Plant Location Problem (DCPLP) the task is to find a time schedule and sizes for installing facilities at plant locations to minimize the discounted cost of capital expenditures over the planning horizon. The costs include setup cost for establishing facilities, volume dependent operational costs, and transportation costs for distributing demand from facilities to customers. We consider a class of the DCPLP in which the available facilities have finite capacities and the number of facility types is relatively small so that the expansion sizes cannot be modeled by continuous variables. The DCPLP is formulated as a combinatorial optimization problem that allows consideration of more than one facility type and finds the optimum mix of facilities in each location. We describe an optimization algorithm for solving the DCPLP based on the Lagrangian relaxation technique. Algorithms for converting infeasible optimal solutions of the Lagrangian to a feasible solution of the DCPLP are presented. The procedure has been tested on both randomly generated and real-life based problems. Computational results indicate that the algorithm produces solutions within 3% of the lower bounds for a wide range of input data.