The hub-and-spoke network is widely used in various fields of industry, such as flight transportation, port logistics, postal and parcel, communication, energy, and so on. The hub-and-spoke network is composed of hubs and spokes which are connected to the hubs. There exist various types of the hub-and-spoke network, such as a pure hub-and-spoke network, a hybrid hub-and-spoke network, a single allocation hub-and-spoke network, and a multiple allocation hub-and-spoke network, according to the transportation strategy or the assignment of spokes to hubs.
In this thesis, strategic decision problems and operational decision problems for the hub-and-spoke network with data uncertainty are considered and stochastic programming and robust optimization approaches are suggested to deal with demand uncertainty.
First, we address a vehicle routing problem which decides both the transportation routes and the number and types of vehicles to be deployed to minimize the sum of costs to transport all quantities in a hybrid hub-and-spoke network with a single hub which allows direct transportation between spokes. We propose an extended formulation of the routing problem which yields a strong LP relaxation bound by introducing a set of feasible direct route patterns and the Dantzig-Wolfe decomposition approach. We develop an algorithm which incorporates column generation procedure at the root node and repeats iteratively a variable fixing and column generation procedure at the non-root nodes until an integral solution is found. For computational study, the proposed algorithm was applied to real transportation networks of Turkey and Korea Post. The results show that our algorithm can find near optimal solutions very efficiently.
Next, we investigate the vehicle routing problem with demand uncertainty in a hybrid hub-and-spoke network with a single hub. In this problem, daily changes in quantities are reflected with a finite number of scenarios. Regularly scheduled vehicles and temporarily scheduled vehicles are considered to meet the demand variation. We propose a Dantzig-Wolfe decomposition approach and develop an algorithm that applies a variable fixing procedure combined with the column generation. Finally, we present computational results using the well-known CAB data sets and real-life data from the Korea Post.
Lastly, we consider a robust version of the capacitated single allocation hub location problem with demand uncertainty in which hubs have capacity limits and a non-hub node has to be assigned to exactly one hub. The problem decides the hub nodes and the allocation of the non-hub nodes to the hubs such that the worst demand in the uncertainty set is satisfied with the minimum cost. We propose an approach that is robust with respect to the uncertain demand where no probability distribution is available on the parameters. We present computational results using the well-known AP data sets.
허브앤스포크 네트워크는 항공, 항만, 우편, 택배, 통신 등 산업의 여러 분야에서 널리 활용되는 네트워크이다. 허브앤스포크 네트워크는 허브와 이들 허브에 연결된 스포크들로 이루어져 있으며, 스포크들간 운송되어야 할 물량은 허브를 통해 운송이 이루어진다. 운송 전략이나 스포크의 허브 할당방법에 따라 모든 물량이 허브를 경유하는 순수 네트워크, 스포크들 사이에 직접 운송을 허용하는 하이브리드 네트워크, 각 스포크가 하나의 허브에 할당되는 단일 할당 네트워크, 각 스포크가 복수 개의 허브에 할당이 가능한 복수 할당 네트워크 등 다양한 형태가 존재한다.
본 연구는 허브 기반 네트워크에서 물량의 불학실성하에 전략적 측면 및 운영적 측면의 의사결정 문제를 다룬다. 또한 물량의 불확실성을 다루고자 추계적 계획법 및 강건 최적화 기법을 적용한다. 본 연구의 구체적인 기여는 다음과 같다.
1. 하나의 허브가 있는 하이브리드 허브앤스포크망에서의 차량경로계획 문제에 대해 단찌히 울프 분해 기법을 적용한 수리모형 제시 및 알고리즘 개발
2. 물량의 불확실성하에 고정적으로 운행하는 정기편 및 물량 수준에 따라 운행여부를 결정하는 임시편 차량경로계획 수립을 위한 추계 수리모형 제시 및 알고리즘 개발
3. 용량 제약이 있는 단일할당 허브위치 선정 문제에 대해 물량의 불확실성을 고려한 강건 최적화 수리모형 제시 및 알고리즘 개발
\indent 먼저, 하나의 허브가 있는 하이브리드 허브앤스포크 네트워크에서 스포크간 물량을 최소의 비용으로 운송하기 위해 운송구간별 차량 대수를 결정하는 차량경로계획 문제를 다룬다. 차량대수를 결정변수로 하는 수리모형은 문제 사이즈가 크기 때문에 스포크들 사이의 직송경로패턴을 이용하여 단찌히-울프 분해기법을 적용한 수리모형을 제안하였다. 이를 위한 알고리즘으로 열 생성 기법과 변수 고정법이 결합된 알고리즘을 제안하고, 터키 운송 네트워크 및 한국 우편 운송망을 대상으로 계산 실험 결과 빠른 시간 내에 좋은 해를 구할 수 있음을 보여주었다.
\indent 다음으로, 하나의 허브가 있는 하이브리드 허브앤스포크망에서 물량의 불확실성하에 정기편 및 임시편 차량경로계획 문제를 다룬다. 실제 운송환경에서는 물량이 매일 변화하기 때문에 이러한 운송 환경에 대응하고자 매일 고정적으로 운행하는 정기편 및 일별 물량 수준에 따라 운행 여부를 결정하는 임시편으로 구분하여 경로계획을 수립한다. 이에 물량 변화를 시나리오로 정의하여 반영한 추계 수리모형을 제시하고 문제 사이즈 감소를 위해 배낭문제 형태의 열 생성 문제를 이용해 직송경로패턴을 생성하는 단찌히-울프 분해기법을 적용하였다. 열 생성 기법과 변수 고정법이 결합된 알고리즘을 이용하여 미국 항공 네트워크 및 한국 우편 운송망을 대상으로 계산 실험 결과 제안한 알고리즘의 성능이 우수함을 보여주었다. 또한 확정적인 물량 데이터를 이용하는 경우보다 물량의 불확실성을 시나리오로 반영하는 경우 계획 단계와 운영 단계의 운송비용 차이가 줄어들어 더 현실적인 운송계획을 수립할 수 있음을 보여주었다.
\indent 마지막으로, 물량의 불확실성하에 용량 제약이 있는 단일할당 허브위치 선정 문제를 다룬다. 허브 처리용량 하에서 허브를 결정하고 각 노드들을 하나의 허브에 할당하는 문제로, 물량의 불확실성을 반영하였을 때 허브 운영비용 및 노드간 물량 운송비용을 최소화하는 것이 목적이다. 본 문제에서 물량의 불확실성은 허브 처리용량 제약 및 목적함수의 운송비용에 영향을 미치며 본 연구에서는 이 둘을 서로 독립적으로 고려하였다. 구간 불확실성 집합을 이용한 강건 최적화 수리모형을 제안하고 호주 우편 운송망을 대상으로 계산 실험을 수행하였다. 그 결과 물량의 불확실성이 증가할수록 총 비용 및 허브 수가 증가하며 강건 최적화 기법을 적용함으로써 물량의 불확실성에 대해 허브 용량 제약 및 운송비용을 높은 비율로 보장할 수 있음을 보여주었다.
