A Branch and Bound Algorithm for the Multi-period Capacitated Facilities Location Problem

Abstract

本 연구는 다계획기간동안 2단계 유통구조內에서의 창고의 입지선정을 다루고 있다. 2단계 유통구조란 物的 흐름이 공장에서 창고를 거쳐 소비지에 이르는 유통구조를 말한다. 여기서는 모든 공장과 창고의 생산 혹은 취급능력이 有限인 경우를 대상으로 한다.

계획기간도안의 모든 수요를 충족시키면서 관련 총 비용을 최소로 하는 창고의 입지를 선정하기 위해, 이를 혼합 정수계획모형으로 정식화하고 이 모형의 최적해를 구하기 위한 새로운 分段探索法(branch and bound algorithm)을 제시하였다. 이때 分段探索나무(b &b tree)의 크기를 줄이기 위해 4가지 유형의 마디의 간략화단계(node simplification steps)를 보였다.

This paper is concerned with the problem of locating warehouses in a two-stage distribution system, where commodities are delivered from capacitated plants to customers via capacitated warehouses over a relatively long planning horizon. We want to decide which of a set of warehouses to poen, when to poen them, and how to allocate the production of each plant to satisfy the known demands to minimize the oatal discounted costs.

This problem is formulated as a mixed integer linear programming model. To obtain the optimal solution of this model, a new branch and bound algorithm is presented. To reduce the size of branch and bound tree and the tatal computation time, four kinds of node simplification steps are devised through exploiting the economic charateristics of the model.

This paper is concerned with the problem of locating warehouses in a two-stage distribution system, where commodities are delivered from capacitated plants to customers via capacitated warehouses over a relatively long planning horizon. We want to decide which of a set of warehouses to poen, when to poen them, and how to allocate the production of each plant to satisfy the known demands to minimize the oatal discounted costs.

This problem is formulated as a mixed integer linear programming model. To obtain the optimal solution of this model, a new branch and bound algorithm is presented. To reduce the size of branch and bound tree and the tatal computation time, four kinds of node simplification steps are devised through exploiting the economic charateristics of the model.