서지주요정보
Capacitated multiple-assignment p-hub center location problem = 허브 용량 제약과 다중할당이 허용되는 p-hub 센터의 위치 선정 문제
서명 / 저자 Capacitated multiple-assignment p-hub center location problem = 허브 용량 제약과 다중할당이 허용되는 p-hub 센터의 위치 선정 문제 / Min-Taek Hong.
발행사항 [대전 : 한국과학기술원, 2007].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8018662

소장위치/청구기호

학술문화관(문화관) 보존서고

MIE 07026

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

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 데이터 셋을 이용하여 실험을 수행하였고, 그 결과 제안된 알고리즘이 빠른 시간 안에 주어진 문제의 최적해를 주는 것을 확인하였다.

서지기타정보

서지기타정보
청구기호 {MIE 07026
형태사항 ii, 37 p. : 삽화 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 홍민택
지도교수의 영문표기 : Chang-Sup Sung
지도교수의 한글표기 : 성창섭
공동교수의 영문표기 : Su-Ken Park
공동교수의 한글표기 : 박수근
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 32-35
QR CODE qr code