서지주요정보
Development and investigation of an exact algorithm for the generalized vehicle routing problem : application to persistent UAV systems = 일반적인 차량 경로 문제의 최적해 알고리즘의 탐색 및 개발 : 지속적인 무인 항공기 시스템에의 응용
서명 / 저자 Development and investigation of an exact algorithm for the generalized vehicle routing problem : application to persistent UAV systems = 일반적인 차량 경로 문제의 최적해 알고리즘의 탐색 및 개발 : 지속적인 무인 항공기 시스템에의 응용 / Kyuree Ahn.
저자명 Ahn, Kyuree ; 안규리
발행사항 [대전 : 한국과학기술원, 2018].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8031926

소장위치/청구기호

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

MIE 18016

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

In this study, the exact algorithm of generalized vehicle routing problem for persistent UAV system is developed and investigated. Using the characteristics of UAVs a mixed linear integer programming is formulated. The MILP contains multiple depots, multiple trips, an initial condition, capacity, and distance constraints. The exact algorithm so solve MILP is developed based column generation. The master problem is a set partitioning problem which is identical with decomposition of VRPTW, while subproblem has more constraints which the UAV characteristics have to be reflected. The subproblem is a generalized version of elementary shortest path problem as it allows multiple reuse and initial condition. Solving subproblem spend most of the time in column generation. Therefore, we used a dynamic algorithm called label correcting algorithm. The branch-and-price showed a better performance than solving MILP directly, which was 50 times faster of execution time in best case. Branch-and-price showed better result in mixed type customer instance when problem size get bigger.

본 연구에서는 지속적인 무인항공기 시스템을 위한 일반 차량 경로 문제의 최적해 알고리즘을 개발하고 연구하였다. 기존의 차량 경로 문제와 차별화되는 무인 항공기 시스템의 특징이 정의되었고, 이 특성을 이용하여 혼합 선형 정수 계획법이 모델링된다. 혼합 선형 정수 계획법에는 다중 거점, 다중 경로, 초기 조건, 거리 및 용량 제약이 포함된다. 최적해를 찾는 알고리즘은 열 생성 기법을 기반으로 개발되었다. 마스터 문제는 시간제약이 있는 차량 경로 문제에서 일반적으로 정의되는 집합 파티셔닝 문제이며 하위 문제에는 무인 항공기 특성을 반영해야 하는 제약이 더 많다. 하위 문제는 다중 경로와 초기 조건을 허용하므로 기본 최단 경로 문제의 일반화 된 형태이다. 열 생성 기법의 대부부의 시간은 하위 문제에 소비되므로, 레이블 수정 알고리즘이라는 동적 알고리즘으로 하위 문제를 풀었다. 분지평가법은 혼합 선형 정수 모형을 직접 푸는 것보다 우수한 성능을 보였으며 최상의 경우 실행 시간이 50배 이상 빨랐다. 문제 규모가 커지면 분지평가법은 더 나은 결과를 보였다.

서지기타정보

서지기타정보
청구기호 {MIE 18016
형태사항 ix, 45 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 안규리
지도교수의 영문표기 : James R. Morrison
지도교수의 한글표기 : 제임스 모리슨
학위논문 학위논문(석사) - 한국과학기술원 : 산업및시스템공학과,
서지주기 References : p. 43-44
주제 Branch-and-Price
Vehicle Routing Problem
Unmanned Aerial Vehicle
Exact Algorithm
분지평가법
차량 경로 문제
무인항공기
최적해 기법
QR CODE qr code