This thesis considers a capacitated multiple-assignment p-hub center problem with fractional flow allowed. The problem is formulated as an MIP (Mixed Integer Programming), for which a solution algorithm is derived. The algorithm is based on the approach of covering problem combined with the binary search which is a well-known and successful approach for continuous center location problems. Moreover, valid inequalities are proposed to reduce the associated covering problem. Computational experiments on an Australian Post data set are conducted to evaluate the effectiveness of the proposed algorithm, and the results show that it performs well.
본 논문에서는 허브 용량 제약이 주어진 Hub-and-Spoke 네트워크에서 수송 시간에 대한 worst case 시나리오를 고려해 최대 수송시간을 최소화 시키는 허브의 최적 위치 선정과 다중할당에 대한 연구를 수행하였다. 허브 네트워크는 결정된 허브 노드를 통해서만 flow를 이동 시킬 수 있는 네트워크로 이를 사용함으로써 전체 네트워크의 가격을 크게 줄일 수 있어 항공 운송, 통신 시스템 등에서 널리 이용되고 있다. 제안된 문제를 풀기 위해 정의된 허브 네트워크 문제를 MIP (Mixed Integer Programming)로 모델링하였고, 이 모델을 위한 최적 알고리즘을 제안하였다. 최적 알고리즘은 위치 선정 문제에서 covering 문제를 반복적으로 풀어 center 문제의 해를 binary search를 이용해 탐색하여 최적해를 주는, 많이 알려진 알고리즘을 기반으로 구성됐다. 또한 알고리즘의 보다 효율적인 진행을 위해서 covering 모델에 추가할 몇 가지 valid inequality 들이 고려되었다. 이렇게 구성된 알고리즘의 성능을 평가하기 위해 AP 데이터 셋을 이용하여 실험을 수행하였고, 그 결과 제안된 알고리즘이 빠른 시간 안에 주어진 문제의 최적해를 주는 것을 확인하였다.
