Mathematical models and algorithms for the vehicle routing problems with data uncertainty in the hub-and-spoke networks

Abstract

허브앤스포크 네트워크는 항공, 항만, 우편, 택배, 통신 등 산업의 여러 분야에서 널리 활용되는 네트워크이다. 허브앤스포크 네트워크는 허브와 이들 허브에 연결된 스포크들로 이루어져 있으며, 스포크들간 운송되어야 할 물량은 허브를 통해 운송이 이루어진다. 운송 전략이나 스포크의 허브 할당방법에 따라 모든 물량이 허브를 경유하는 순수 네트워크, 스포크들 사이에 직접 운송을 허용하는 하이브리드 네트워크, 각 스포크가 하나의 허브에 할당되는 단일 할당 네트워크, 각 스포크가 복수 개의 허브에 할당이 가능한 복수 할당 네트워크 등 다양한 형태가 존재한다.

본 연구는 허브 기반 네트워크에서 물량의 불학실성하에 전략적 측면 및 운영적 측면의 의사결정 문제를 다룬다. 또한 물량의 불확실성을 다루고자 추계적 계획법 및 강건 최적화 기법을 적용한다. 본 연구의 구체적인 기여는 다음과 같다.

1. 하나의 허브가 있는 하이브리드 허브앤스포크망에서의 차량경로계획 문제에 대해 단찌히 울프 분해 기법을 적용한 수리모형 제시 및 알고리즘 개발

2. 물량의 불확실성하에 고정적으로 운행하는 정기편 및 물량 수준에 따라 운행여부를 결정하는 임시편 차량경로계획 수립을 위한 추계 수리모형 제시 및 알고리즘 개발

3. 용량 제약이 있는 단일할당 허브위치 선정 문제에 대해 물량의 불확실성을 고려한 강건 최적화 수리모형 제시 및 알고리즘 개발

\indent 먼저, 하나의 허브가 있는 하이브리드 허브앤스포크 네트워크에서 스포크간 물량을 최소의 비용으로 운송하기 위해 운송구간별 차량 대수를 결정하는 차량경로계획 문제를 다룬다. 차량대수를 결정변수로 하는 수리모형은 문제 사이즈가 크기 때문에 스포크들 사이의 직송경로패턴을 이용하여 단찌히-울프 분해기법을 적용한 수리모형을 제안하였다. 이를 위한 알고리즘으로 열 생성 기법과 변수 고정법이 결합된 알고리즘을 제안하고, 터키 운송 네트워크 및 한국 우편 운송망을 대상으로 계산 실험 결과 빠른 시간 내에 좋은 해를 구할 수 있음을 보여주었다.

\indent 다음으로, 하나의 허브가 있는 하이브리드 허브앤스포크망에서 물량의 불확실성하에 정기편 및 임시편 차량경로계획 문제를 다룬다. 실제 운송환경에서는 물량이 매일 변화하기 때문에 이러한 운송 환경에 대응하고자 매일 고정적으로 운행하는 정기편 및 일별 물량 수준에 따라 운행 여부를 결정하는 임시편으로 구분하여 경로계획을 수립한다. 이에 물량 변화를 시나리오로 정의하여 반영한 추계 수리모형을 제시하고 문제 사이즈 감소를 위해 배낭문제 형태의 열 생성 문제를 이용해 직송경로패턴을 생성하는 단찌히-울프 분해기법을 적용하였다. 열 생성 기법과 변수 고정법이 결합된 알고리즘을 이용하여 미국 항공 네트워크 및 한국 우편 운송망을 대상으로 계산 실험 결과 제안한 알고리즘의 성능이 우수함을 보여주었다. 또한 확정적인 물량 데이터를 이용하는 경우보다 물량의 불확실성을 시나리오로 반영하는 경우 계획 단계와 운영 단계의 운송비용 차이가 줄어들어 더 현실적인 운송계획을 수립할 수 있음을 보여주었다.

\indent 마지막으로, 물량의 불확실성하에 용량 제약이 있는 단일할당 허브위치 선정 문제를 다룬다. 허브 처리용량 하에서 허브를 결정하고 각 노드들을 하나의 허브에 할당하는 문제로, 물량의 불확실성을 반영하였을 때 허브 운영비용 및 노드간 물량 운송비용을 최소화하는 것이 목적이다. 본 문제에서 물량의 불확실성은 허브 처리용량 제약 및 목적함수의 운송비용에 영향을 미치며 본 연구에서는 이 둘을 서로 독립적으로 고려하였다. 구간 불확실성 집합을 이용한 강건 최적화 수리모형을 제안하고 호주 우편 운송망을 대상으로 계산 실험을 수행하였다. 그 결과 물량의 불확실성이 증가할수록 총 비용 및 허브 수가 증가하며 강건 최적화 기법을 적용함으로써 물량의 불확실성에 대해 허브 용량 제약 및 운송비용을 높은 비율로 보장할 수 있음을 보여주었다.