A Study on the Hub Network Design Problem by Link Opening Cost

링크 개설 비용을 고려한 허브 네트워크 설계 문제 연구 진 현 웅*허브 네트워크는 항공망, 운송망, 통신망 등 다양한 분야에서 사용되고 있는 네트워크 구성 방식으로 최근 많은 연구자들에 의해 주목을 받아왔다. 본 논문에서는 지역적으로 구분되어 있는 네트워크 상에서 허브 설비의 입지 및 수요지와의 운송 방법을 결정하는 문제를 다룬다. 이 때 목적함수는 허브 설비 개설 비용, 허브 간의 링크 개설 비용, 허브와 수요지 간의 링크 개설 비용, 운송 비용으로 구성되는 총 네트워크 비용을 최소화하는 것이다. 이 문제는 정수 계획법으로 모델링 되었으며 네트워크 설계 문제에서 좋은 성능을 보여 왔던 쌍대 기반 접근법을 이용한 해법이 제안되었다. 제안된 해법의 효율성 검증을 위하여 scale parameter, 군집의 수, 수요지 및 후보지의 수를 변경하며 135개의 데이터 집합을 생성하고 이에 대한 실험을 수행하였다. 실험결과, 제안된 해법에 의해 구해진 해와 최적해와의 차이는 평균 4.931% 이내로 나타났으며 평균 소요 시간은 3.437초로 측정되었다. 攀 * 한남대학교 경영학과攀攀