Hub networks have played a prominent role in recent years in transportaion. and telecommunication systems. Hub facilities serve as switching, transshipment and sorting points and they allow a relatively small number of arcs to serve many origin-destination pairs. The problem of locating hub facilities and allocation of nonhub nodes to hubs arises frequently in the design of telecommumications traffic, data transmissions, airline passenger flow, and express packages delivery networks.
We consider the design of hub systems in the airline transportaion network . The basic form of the problems considered in this thesis models the situation where n nodes can interact only via a set of fully in terconnected hubs. The hubs are uncapacitated, and their number is initially predetermined. In the problems, the locations of nodes (cities) are given and the hubs are to be selected from the given node set. The flows between any pair of nodes are sent using the hubs as intermediate switching points and thee is the scale effects for inter-hub flows. Using the amount of flow and the cost per unit of flow between every two nodes in a network, one has to decide on the locations of hubs, and on the allocatioon of each nonhub node to the hubs so that the total transportation cost is minmized.
This thesis focuses on the allocation problems of assigning the nonhub nodes to the hubs when the hub locations are fixed. In the real airline hub networks, the hub locations are usually fixed for some time interval because of long term lease contract, cost of moving hubs, etc.. In this situation, the decision of optimally assigning the nonhub nodes to hubs is important for efficient operation of the networks. When the number of hubs is given, the total number of candidate hub combinations is a polynomial function of the number of candidate hubs. So, if the allocation problem with fixed p-hub locations can be solved efficiently, the problem of determining optimal p-hub locations with fixed costs for establishing hubs and opening Iinks can be solved efficiently when the number of hub candidates is small. As allocation ways, we consider the single allocation which restricts nonhub nodes to be connected exactly to a single hub and the multiple allocation which allows each node to interact with multiple hubs. In our models, we consider fixed costs for opening links between nonhub nodes and hubs. If there are fixed costs for establishing hubs, they can be treated as a constant term in the fixed hub model.
The first model considered the single allocation problem in the two-hub network. We transform the quadratic 0-1 integer program of the problem into a linear program and show that all extreme points of the polytope defined by the LP are integral. We also remark that it can be transformed into a minimum cut problem. As a result, we can observe that the two-hub location problem cab be solved in polynomial time.
The second model considers the single allocation problem in the three-hub network. We show that the single allocation problem of p-hub network is NP-hard as soon as the number of hubs is three. We provide a mixed integer formulation and consider the polyhedral properties of it. Computational experiments for the LP relaxation of the formulation on the data given in literature show that in almost all instances it provided integral solutions. The formulation can be also used for the 3-way cut problem and 3-processor distribution problem. Next, we also provide another mixed integer formulation which can be used for the cases with hubs are more than three.
The final model considers the multiple allocation problems in the p-hub network. We observe that the multiple allocation problem with no fixed costs can be solved efficiently by using the shortest path algorithm. We also observe that the multiple allocation problem with fixed costs for opening links can be thought as one of the uncapacitated network design problem. We modify the formulation of uncapacitated network design problem to be appropriate to our problem and show that when the number of hubs is two the LP relaxation of it provides integral optimal solutions. We also provide another mixed integer formulation based on path. Computational experiences of the formulation were performed on the modified data added fixed costs for opening links to the data given in literature.
최근에 수송시스템, 통신시스템 등에서 허브망이 중요한 역할을 하고 있다. 허브노드는 두 지점간의 흐르는 물량을 전환, 분류 및 옮겨 싣는 거점의 역할을 하며, 이러한 허브노드를 이용함으로써 상대적으로 적은 수의 호를 개설하여 모든 노드 간의 물량을 수송할 수 있어 전체 물류비용의 감소를 가져 올 수 있다. 이러한 허브의 위치설정과 일반(허브가 아닌)노드를 어느 허브에 연결할 것인가 하는 문제는 통신망, 데이터 전송망, 항공여객 및 소화물 운송망 등의 설계에 자주 발생하게 된다.
본 연구에서는 항공운송망에서의 허브시스템의 설계를 고려한다. 연구대상 문제의 기본적인 형태로 허브들은 상호간에 완전히 연결되어 있으며 모든 노드간의 물량은 이러한 허브를 경유하여 흐르는 것으로 가정한다. 허브간의 물량흐름에는 상대적으로 많은 물량이 흐름으로써 비용효과가 존재할 수 있으며, 각 노드의 위치와 노드간에 흐르는 물량은 주어져 있고 허브는 주어진 노드들 중에서 선택되어 지는 것으로 보고 있다. 문제는 각 노드간의 물량과 단위당 물류비용을 고려하여 전체 물류비용을 최소화시키는 허브의 위치와 일반 노드가 할당될 허브를 정하는 것이다.
본 논문은 허브의 위치가 주어진 상태에서 일반노드를 어느 허브에 할당할 것인가 하는 문제에 중점을 두고 있다. 일반적으로, 실제 항공운송망에서 허브의 위치는 허브공항의 시설과 임대계약 등으로 장기간 고정되어 있다. 이러한 상황하에서는 운송망의 효율적인 운용을 위하여 일반노드를 허브에 최적으로 할당하는 것이 중요하다. 한편, 허브의 수가 주어진 경우 후보 허브공항 조합의 총 수는 허브 후보지 수의 다항식으로 나타난다. 따라서, 허브의 위치가 고정되었을 경우의 할당문제가 효율적으로 풀리면, 허브 후보지의 수가 작을 경우 허브의 위치를 정하는 문제도 효율적으로 풀 수 있게 된다. 일반노드를 허브에 할당하는 방식으로, 본 연구에서는 각 노드를 오직 하나의 허브에만 연결시키는 단일할당과 여러 허브에 연결시키는 복수할당을 고려한다. 아울러, 본 논문에서는 기존의 연구에서 고려되지 않았던 일반노드와 허브간의 통로를 개설하는데 따르는 고정비용을 고려하고 있다. 한편, 허브가 고정된 상황에서는 허브공항의 개설에 따른 고정비용이 존재하여도 그 비용들은 상수로 처리될 수 있다.
첫 번째 모델로 두 개의 허브를 가진 망에서 단일할당문제를 고려한다. 본 연구에서는 이 문제의 이차계획식을 선형계획식으로 변형하고, 주어진 선형계획식의 실행가능해 영역의 극점들이 정수해임을 보인다. 또한, 이 문제가 최소절단문제로 변환될 수 있음을 보인다. 결과적으로, 이전의 연구와 달리 두 개의 최적 허브위치와 최적 단일할당을 결정하는 문제는 다항시간 안에 풀릴 수 있음을 보이는 것이다.
두 번째 모델로 세 개의 허브를 가진 망에서의 단일할당문제를 고려한다. 본 논문에서는 고정도니 허브의 수가 세 개이상인 경우의 단일할당문제가 다항시간 안에 풀릴 수 없는 문제(NP-hard)임을 보이는 증명을 제시한다. 아울러, 세 개의 허브를 가진 문제의 해결을 위하여 혼합 정수계획식을 제공하고 주어진 식의 다면체적인 성격을 살펴본다. 이 식은 지정된 세 개의 노드를 최소의 값으로 절단시키는 문제와 세 개의 처리기에 프로그램을 분배시키는 문제에도 적용시킬 수 있다. 다음으로 허브의 수가 세 개보다 많은 경우에도 적용 시킬 수 있는 혼합 정수계획식을 제공한다.
마지막으로, 허브의 위치가 주어진 상태에서 일반노드를 다수의 허브에 할당시킬 수 있는 복수할당문제를 고려한다. 기존의 논문들에서 호의 개설에 따른 고정비용이 없는 경우에 대한 많은 발견적 해법들이 연구되었지만, 본 연구에서는 이러한 문제가 최단경로문제의 해법을 사용하여 효율적으로 풀릴 수 있음을 보인다. 또한, 호의 개설에 따른 고정비용이 있는 경우의 복수할당문제가 다른 논문에서 논의된 용량제한이 없는 망설계문제로 볼 수 있음을 보인다. 본 논문에서는 이러한 망설계문제에서 주어진 식을 본 연구의 문제에 맞도록 변형하고, 허브가 두 개인 경우 변형된 식의 실행가능영역의 극점들이 정수해임을 보인다. 아울러, 변수와 제약식의 수가 더 작은 식을 제공한다.
주어진 식들의 선형완화식을 기존 문헌에서 얻은 데이터와 임의로 만든 데이터에 적요한 결과 주어진 식들이 정수최적해를 얻는데 효과적임을 보여준다.
