본 논문은 지역으로 구분된 네트워크 상에 존재하는 수요지에서 발생한 수요를 만족시키기 위한 최적 설비의 입지 및 수요지의 할당 문제를 다룬다. 설비의 입지는 각 수요지에 대하여 운송시간(또는 거리)으로 평가되는 서비스 품질을 만족시켜야하며 또한 예산 제약을 고려하여야 만다. 문제의 목적은 최소의 운송비용으로 전체수요를 만족시키는 설비의 수 및 그 입지를 결정하고 이에 따른 수요지로의 운송방법을 결정하는 것이다. 고려된 문제는 정수계획법으로 정식화되었으며, 정수계획법 문제의 해결을 위하여 분단탐색법에 기초한 해법이 제안되었다. 또한, 선처리 과정을 통하여 해공간(solution space)을 감축시킴으로써 분단탐색법의 효율성을 증대시켰다. 선처리 과정은 원문제를 관련된 두 개의 부문제로 완화하여 얻어진 각 부문제의 해를 통하여 원문제의 실행가능해의 존재 여부 및 특정 후보지의 탈락 여부를 결정함으로써 분단탐색법의 효율성을 증대시켰다. 또한, 분단탐색법의 가장 중요한부분인 하한의 결정을 위하여 부문제와 라그랑지안 완화법을 이용한 하한을 제안하였다. 제안된 해법의 효율성 검증을 위하여 2430개의 무작위로 추출된 데이터 집합에 대하여 다양한 실험이 수행되었다.
This paper considers an optimal facility location problem which wants to satisfy all the demands at the demand nodes specified in a set of predetermined zones. The selected facilities should satisfy a required customer service quality, measured in terms of delivery time(distance), and an incorporated budget constraint. The objective is to locate the optimal number of facilities and to make the optimal allocation of each demand node to its supplying facilities such that the total delivery cost for all the demand nodes is minimized. The considered problem is formulated as an integer programming problem For this integer programming problem, a branch-and-bound based procedure is proposed Moreover, a preprocessing procedure, which reduces the solution space, is derived to promote the efficiency of the algorithm. The proposed algorithm is tested for its effectiveness with 243J randomly generated data sets.
요약
1. Introduction
2. Model Formulation
3. Solution Approach
4. Experimental Results
5. Concluding Remarks
REFERENCES
Abstract
저자소개