In this thesis, we consider a facility location problem in a hierarchical delivery service network, which is composed of demand locations, terminals, and a hub. Delivery demands generated at the demand locations are gathered at terminals for a large-scale transportation to the hub, where the demands are classified according to the destinations. Deliveries are carried out by vehicles with a small capacity on paths between demand locations and terminals, while vehicles with a larger capacity are used on paths between terminals and the hub. In the network considered here, the hub can perform the function of terminals. We focus on the problem of allocating the demand locations to the terminals, and determining locations of terminals and the hub, with the objective minimizing the sum of the construction cost on facilities, and transportation cost on the path from origin to destination. We present algorithms using Benders decomposition, and two-phase heuristics, in which an initial assignment decision is constructed at the first phase and then it is improved in the second phase. Computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested algorithms give good solutions in a relatively short amount of computation time
본 논문은 계층이 있는 배달 서비스 네트워크에서의 시설 배치에 관하여 운송 비용과 시설 건설 비용의 합을 최소로 하는 시설 배치에 대한 알고리듬을 제안한다. 배달 서비스 네트워크는 크게 수요지, 터미널, 허브로 구성이 된다. 수요지에서 발생된 수요를 먼저 터미널에 규합한 후 터미널에서 허브까지의 대규모 운송으로 일어나는 단위 비용의 감소로 인하여 전체 운송 비용을 감소시킬 수 있다. 수요지에서부터 터미널 사이의 구간에서의 운송이 용량이 작은 차량으로 이루어지게 되고, 터미널과 허브 사이의 운송은 큰 용량을 지닌 차량이 사용된다. 이 논문에서 다루는 허브는 터미널의 역할을 수행할 수 있으며, 결정하고자 하는 것은 허브 및 터미널의 위치, 각각의 터미널에 대한 수요지의 배치이다. 문제를 풀기 위하여 수학적 모델이 제시 되었고, 벤더스 디컴포지션을 이용한 알고리즘과 빠른 시간 내에 최적에 가까운 비용을 산출해 내기 위한 두 가지 패이즈로 구성된 휴리스틱 알고리즘들을 제안한다. 제안된 알고리즘들을 다양한 문제에 대하여 실험하고 평가한 결과, 짧은 시간 안에 좋은 결과를 보여주는 것으로 나타났다.
