This thesis considers three network design problems for a given network service area partitioned into a certain number of predetermined zones, which arise in many network service areas including telecommunications, logistics, and transportations. Chapter 2 and Chapter 3 deal with a hub-and-spoke network which has played an important role in modeling many practical networks in recent decades. Chapter 4 considers an uncapacitated facility location problem subject to the distance constraints.
In Chapter 2, a hub-and-spoke network design problem is considered under the nonrestrictive policy. The objective is to design a hub-and-spoke network by determining all the required hub locations in the predetermined zones and also all the terminal routes such that the sum of hub construction cost and flow transportation is minimized. The complexity of the problem is proved to be NP-complete in the chapter. By characterizing a special structure of the problem, a dual-based solution approach (known to be effective for network design) is derived.
Chapter 3 considers a hub-and-spoke network design problem with link opening cost allowed. The problem is divided into two subproblems each to be solved independently. With the solution obtained from each subproblem, a combining procedure of the two solutions is then proposed to improve the whole solution.
Chapter 4 describes an uncapacitated facility location problem subject to distance and budget constraints. In the problem, the quality of service is measured in terms of delivery time (or distance) required from its nearest supplying facility. The objective of the problem is to determine the appropriate number of the required supplying facilities and their locations so as to minimize the total delivery cost under the service quality and budget constraints on setting up the supplying facilities. To solve the problem, a branch and bound algorithm using the Lagrangean Relaxation bound is proposed with a preprocessing procedure incorporated to reduce the solution space.
본 논문은 수요자 군집이 주어진 네트워크 상에서의 최적의 설비 입지 결정 문제를 다룬다. 본 논문에서 네트워크는 미리 결정된 몇 개의 소비자 군집으로 구성되어 있으며 각 소비자는 해당 군집에 속하는 설비로부터 서비스를 받아야 하는 지역 제약식(zonal constraint)을 가진다. 논문의 2장과 3장은 통신 네트워크 및 물류 네트워크의 모델링에 널리 이용되는 허브 네트워크의 디자인 문제를 다루고 있으며 4장은 배송시간으로 규정되는 서비스 품질에 관한 제약식이 주어진 상황에서의 물류 네트워크 디자인 문제를 다룬다.
2장에서는 순수 허브 서비스 및 논스톱 서비스를 모두 고려할 때의 허브 네트워크 디자인 문제를 다룬다. 이 문제의 목적은 관련 네트워크 비용을 최소로 하는 허브 설비 위치 및 트래픽 운송 경로의 결정이다. 네트워크 비용은 허브 설립 비용 및 트래픽 전송 비용으로 구성된다. 이 문제는 정수계획 문제로 표현이 되며, 본 연구에서 NP-hard 문제임이 밝혀졌다. 문제의 해결을 위해 네트워크 디자인 분야에서 좋은 결과를 보여왔던 쌍대 기반 해법을 이용하였다. 쌍대 기반 해법은 본 문제의 쌍대 문제를 구성하고 쌍대 문제와 본 문제간의 관계를 이용하여 본 문제의 해를 찾아가는 방법이다. 주어진 문제의 특수한 구조를 이용하여 효율적인 해법이 제안되었다.
3장에서는 링크 설립 비용을 고려한 허브 네트워크 디자인 문제를 다루고 있다. 이 문제는 두 개의 부문제(subproblem)으로 분해가 되며 각 문제는 서로 독립적으로 해결된다. 그러나, 각 부문제에서 얻어진 효율적인 해는 본 문제의 효율적인 해를 제공하는 것은 아니다. 이를 해결하기 위하여 본 논문에서는 각각의 해로부터 본 문제의 효율적인 해를 유도하는 연합 프로시져(combining procedure)를 제안하였다.
4장은 소비자 품질에 관한 제약식 및 예산 제약식이 주어진 경우에의 서비스 설비의 최적 입지 문제를 다룬다. 이 문제에서 서비스 품질은 해당 수요지로 배송할 수 있는 최단 배송시간으로 정의되며, 배송시간이 주어진 시간을 초과할 경우 수요가 손실되는 것으로 가정한다. 또한 각 서비스 설비 설립 비용의 합은 주어진 예산을 초과할 수 없다. 이러한 상황에서 최소의 배송 비용으로 발생한 수요를 모두 만족시키기 위한 서비스 설비의 입지 및 배송 방법을 결정한다. 최적해를 구하기 위하여 브랜치 앤 바운드 방법이 제안되었다. 이를 위하여 라그랑지안 방법을 응용한 바운드가 제안되었다. 또한 브랜치 앤 바운드 방법의 효율성을 높이기 위하여 해의 영역을 줄여 나가는 방법(preprocessing procedure)이 제안되었다.
