서지주요정보
Airplane arrival scheduling using a set partitioning-based branch-and-price method = 집합 분할을 활용한 분지평가 해법 기반의 항공기 도착 스케줄링에 관한 연구
서명 / 저자 Airplane arrival scheduling using a set partitioning-based branch-and-price method = 집합 분할을 활용한 분지평가 해법 기반의 항공기 도착 스케줄링에 관한 연구 / Jae-Hoon Song.
저자명 Song, Jae-Hoon ; 송재훈
발행사항 [대전 : 한국과학기술원, 2018].
Online Access 비공개원문

소장정보

등록번호

8032561

소장위치/청구기호

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

DAE 18020

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This article presents an exact algorithm that is combined with a heuristic method to find the optimal solution for an airplane landing problem. For a given set of airplanes and runways, the objective is to minimize the accumulated deviations from the target landing time of the airplanes. A cost associated with landing either earlier or later than the target landing time is incurred for each airplane within its predetermined time window. In order to manage this type of large-scale optimization problem, a set partitioning formulation that results in a mixed integer linear program is proposed. One key contribution of this article is the development of a branch-and-price methodology, in which the column generation method is integrated with the branch-and-bound method in order to find the optimal integer solution. In addition to the exact algorithm, a simple heuristic method is also presented to tighten the solution space. Numerical experiments are undertaken for the proposed algorithm in order to confirm its effectiveness using public data from the OR-Library. As an application in the real-world situation of airplane landing, air traffic data from Incheon International Airport is employed to assure the efficiency of the proposed algorithm.

본 논문에서는 항공기 도착 문제에 대한 최적해를 구하기 위하여 휴리스틱 알고리즘을 결합한 최적 알고리즘을 제안하였다. 주어진 항공기와 활주로 집합에 대하여, 목적함수는 착륙하는 항공기들의 목표 도착시각에 대한 실제 도착시각의 누적 편차를 최소화하는 것이다. 착륙하는 모든 항공기에 대하여, 이미 정의된 시간 창 형태의 목표 도착시각보다 일찍 도착하거나 늦게 도착하였을 때 비용이 발생한다. 이러한 형태의 대형 최적화 문제를 해결하기 위하여, 집합 분할 개념을 활용한 혼합정수선형계획법에 기반하여 항공기 도착 문제를 새로이 설정하였다. 본 논문의 핵심적인 의의는 열 생성 기법과 분기한정법을 통합한 분지평가 해법을 구현한 것이라 할 수 있다. 제안된 최적 알고리즘 외에도 해 공간을 축소시키기 위하여 간단한 휴리스틱 기법도 제시하였다. 제안된 알고리즘의 유효성을 검증하기 위하여 '오알-라이브러리(OR-Library)'에서 제공되는 공용 데이터를 사용한 수치 실험을 수행하였다. 또한, 항공기 도착에 대한 실제 상황을 적용하기 위하여 인천국제공항에 착륙하는 항공교통 데이터를 적용하여 제안된 알고리즘의 효율성을 확인하였다.

서지기타정보

서지기타정보
청구기호 {DAE 18020
형태사항 vi, 109 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 송재훈
지도교수의 영문표기 : Han Lim Choi
지도교수의 한글표기 : 최한림
수록잡지명 : "Efficient airplane arrival scheduling using a set partitioning-based branch-and-price method". Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering
Including appendix.
학위논문 학위논문(박사) - 한국과학기술원 : 항공우주공학과,
서지주기 References : p. 77-81
주제 airplane landing problem
set partitioning
branch and bound
column generation
branch and price
항공기 도착 문제
집합 분할
분기한정법
열 생성
분지평가 해법
QR CODE qr code