항공교통의 수요 증가에 따른 혼잡한 교통상황과 부족한 공항 운항 능력을 해결하고자 항공교통관제(ATM : Air Traffic Management)의 다양한 분야에서 연구가 진행 되고있다. 본 논문에서는 공항 관제 영역에서 공항으로 접근하는 항공기 교통 스케줄링에 대해 연구를 진행하였다. 본 연구의 ATM 문제에서는 안전을 위한 운용 제한 조건인 항공기간의 분리 구간과 추월을 고려하여 접근하였으며, 특정 공항의 문제가 아닌 일반적인 공항의 항공경로와 경로 결합지점을 정의하여 접근하였다. 또한, 항공교통관제 문제를 스케줄링문제로 정의하여 dispatching 휴리스틱기법들을 통해 해결하고자 하였으며, 기존 기법들을 보완한 새로운 기법을 제안하였다. 스케줄링기법 효율성을 분석하고자 항공교통 시뮬레이션 환경을 모사하였으며, 항공 교통 흐름을 정적인 상황과 동적인 상황으로 정의하여 각 스케줄링 기법들에 대해 Monte Carlo Simulation을 수행하였다.
항공교통의 수요 증가에 따른 혼잡한 교통상황과 부족한 공항 운항 능력을 해결하고자 항공교통관제(ATM : Air Traffic Management)의 다양한 분야에서 연구가 진행 되고있다. 본 논문에서는 공항 관제 영역에서 공항으로 접근하는 항공기 교통 스케줄링에 대해 연구를 진행하였다. 본 연구의 ATM 문제에서는 안전을 위한 운용 제한 조건인 항공기간의 분리 구간과 추월을 고려하여 접근하였으며, 특정 공항의 문제가 아닌 일반적인 공항의 항공경로와 경로 결합지점을 정의하여 접근하였다. 또한, 항공교통관제 문제를 스케줄링문제로 정의하여 dispatching 휴리스틱기법들을 통해 해결하고자 하였으며, 기존 기법들을 보완한 새로운 기법을 제안하였다. 스케줄링기법 효율성을 분석하고자 항공교통 시뮬레이션 환경을 모사하였으며, 항공 교통 흐름을 정적인 상황과 동적인 상황으로 정의하여 각 스케줄링 기법들에 대해 Monte Carlo Simulation을 수행하였다.
An air traffic management (ATM) has been studied in a variety of fields to utilize an air traffic capacity efficiently and solve a congested air traffic situation due to an increment of an air traffic demand. In this paper, an air traffic management, which is related with controlling and determining...
An air traffic management (ATM) has been studied in a variety of fields to utilize an air traffic capacity efficiently and solve a congested air traffic situation due to an increment of an air traffic demand. In this paper, an air traffic management, which is related with controlling and determining the sequencing of an aircraft approaching to an airport, in terminal control area is studied. This paper focuses on scheduling algorithms with a given problem for the air traffic management with operational constraints, such as a space separation, an overtaking on the same air-route, and a route merge point (a scheduling point). For a real-time calculation, the presented algorithms focus on dispatching heuristic rules which are able to assign tasks in a fast time period with an adequate performance, which can be demonstrated as a proper and realistic scheduling algorithm. A simulation result is presented to illustrate the validity and applicability of the proposed algorithm. Each scheduling rule is analyzed on the same static and dynamic air traffic flow scenario with the ATM Monte-Carlo simulation.
An air traffic management (ATM) has been studied in a variety of fields to utilize an air traffic capacity efficiently and solve a congested air traffic situation due to an increment of an air traffic demand. In this paper, an air traffic management, which is related with controlling and determining the sequencing of an aircraft approaching to an airport, in terminal control area is studied. This paper focuses on scheduling algorithms with a given problem for the air traffic management with operational constraints, such as a space separation, an overtaking on the same air-route, and a route merge point (a scheduling point). For a real-time calculation, the presented algorithms focus on dispatching heuristic rules which are able to assign tasks in a fast time period with an adequate performance, which can be demonstrated as a proper and realistic scheduling algorithm. A simulation result is presented to illustrate the validity and applicability of the proposed algorithm. Each scheduling rule is analyzed on the same static and dynamic air traffic flow scenario with the ATM Monte-Carlo simulation.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
또한, 각 항공기는 고정된 예정 도착시간(STA : Scheduled Time of Arrival)을 가지고 있으며 스케줄에 따라 변화하는 도착 예상시간(ETA : Estimated Time of Arrival)을 최소화함으로서 지연 및 항공기 운용에 대한 효율성을 높일 수 있다[6,7]. 따라서 본 연구 목적은 스케줄링을 통해 관제영역 내 항공기들의 도착완료 시간과 지연 정도를 최소화하는 것으로 정의할 수 있다.
본 연구에서 접근하고자 하는 항공교통 문제에서는 안전을 위한 운용 제한 조건인 항공기간의 분리 구간과 추월을 고려하여 접근하였으며, 특정 공항의 문제가 아닌 일반적인 공항의 항공 경로와 경로 결합 지점(merge point)를 정의하여 접근하였다. 또한 항공교통관제 문제를 스케줄링 문제로 정의하였으며, 이를 dispatching 휴리스틱 기법들을 통해 해결하고자 하였다. 본 연구를 통해 sequence dependent setup time 스케줄링문 제에 대한 새로운 휴리스틱 기법을 제안하였으며, 제안한 기법을 시뮬레이션을 통해 기존 기법들과 비교․분석하였다.
스케줄링의 목적은 주어진 일정 시간 동안 주어진 자원의 배치 또는 재배열을 통한 성능의 효율성을 증가시키거나 목표를 달성하는 데 있다. 본 논문에서 다루고자 하는 스케줄링은 정해진 상황에서 항상 같은 결과를 내는 결정론적인 모델 (deterministic model) 시스템의 문제에 한정하여 접근하고자 한다. 이러한 결정론적인 스케줄링 모델의 연구는 오랜 기간 많은 연구가 진행되어 왔으며, 일정 범위의 스케줄링 문제에서는 다항 시간(polynomial time)안에 효과적인 해를 찾을수 있는 알고리즘을 찾기도 하였다.
따라서 실시간성을 고려한 문제에서는 휴리스틱(heuristic) 알고리즘을 사용하여 적절한 해를 주어진 시간 안에 구하는 접근 방법을 사용하여야 한다. 본 논문에서는 실시간성과 제한된 처리 능력 한계를 고려해야 짧은 시간 안에 적절한 성능의 해를 구하는데 효율적인 휴리스틱 중 짧은 시간에 수 많은 작업들을 처리하는데 유리한 dispatching기법을 통하여 스케줄링 문제에 접근하고자 한다. 또한, dispatching 기법을 이용한 항공기 순서 배치의 효율성을 분석하고자 항공기 정보가 고정된 상황 (scenario)과 계속적인 업데이트 상황으로 나누어 시뮬레이션 환경을 모사하였으며, Monte Carlo simulation을 이용하여 각 기법들에 대해 시뮬레이션을 수행하였다.
이전 연구논문[12]에서는 추월 제한조건과 merge point가 없으며, 스케줄링이 진행되는 동안 환경 변화가 없는 고정된 상황으로 간단한 TSP문제로 접근하여 각 스케줄링 기법들을 확인해보았다. 본 논문에서는 추월조건과 merge point 제한조건을 고려하여 실제의 관제 운영 제한조건을 표현하였다. 이는 고정된 항공기 분포조건 이외에 스케줄링 중 관제레이더 영역에 임의의 항공기들이 접근하여 정보가 주기적으로 변화하는 시나리오를 추가하여 실제의 공항 관제에 가까운 환경으로 시뮬레이션을 모사하였 다.
ATM은 항공기간의 충돌방지, 교통질서 유지를 위한 교통 흐름조절과 촉진을 목적으로 하므로 ATM과 관련된 스케줄링문제는 안전과 운영 효율성을 고려하여 항공기에 따른 분리(separation)과 추월(overtaking)의 제한 조건을 고려하여야 한다. 본 연구의 공항 접근 항공기 스케줄링 문제에서도 운영제한 조건(separation for safety, air route, cruise speed)을 고려하여 현실적인 문제로 접근 하고자 하였으며, 항공기들간의 추월 제한조건을 설정하여 운용 현실성을 강조하였다. 또한, 일반적인 공항 접근 영역과 항공기 접근 경로를 형식화(formulation)하여 스케줄링문제로 접근하였다.
본 연구의 스케줄링문제는 영역내의 항공기들을 효과적으로 배치하여 마지막 통과지점 항공기 들의 지연정도(delay)과 도착시간(completion time) 최소화함을 목적으로 한다. 항공교통스케줄링 문제의 목적은 공항의 효율적인 운용이며, 이를 위해 일정 시간 동안 FAF지점을 지나는 항공기의 수(throughput)를 최대화하여야 한다.
스케줄링의 목적은 주어진 일정 시간 동안 주어진 자원의 배치 또는 재배열을 통한 성능의 효율성을 증가시키거나 목표를 달성하는 데 있다. 본 논문에서 다루고자 하는 스케줄링은 정해진 상황에서 항상 같은 결과를 내는 결정론적인 모델 (deterministic model) 시스템의 문제에 한정하여 접근하고자 한다.
일반적으로 알려진 휴리스틱 기법들 중 기본적인 dispatching 기법들로는 EDD(Earliest Due Date), MS(Minimum Slack first), SPT(Shortest Processing Time first) 등이 있으며, 이 절에서는 기법들 특성과 본 연구를 위해 제안한 알고리즘을 소개하고자 한다.
항공교통 흐름의 고정된 상황과 계속적인 항공기 접근 상황을 시뮬레이션 환경으로 모사하였으며, 휴리스틱 기법 효율성을 확인하기 위해 Monte Carlo Simulation으로 각 기법들의 결과를 도출하였다. 항공교통문제는 안전을 기본조건으로 흐름을 통제하여 효율성을 높이는 데 있으므로, 항공기 예상도착시간(ETA)를 이용하여 최종항공기들의 도착 시간과 항공기들의 지연정도를 목적함수로 설정하였다. 항공기 경로와 경로 결합 지점을 이용하여 스케줄링 시점을 정의하였으며, 항공기 순서 재배치의 효율성을 판단하고자 하였다.
항공교통문제를 스케줄링 문제로 정의하였으며, 문제 접근에 대한 휴리스틱 스케줄링기법들 효율성을 확인하고자 시뮬레이션을 수행하였다. 시뮬레이션은 MATLAB을 이용하여 임의의 시나리오들을 확률변수(random variables)들로 모사하였으며, Monte Carlo simulation을 통하여 각기법들에 대한 효율성을 분석하고자 하였다.
항공교통에 대한 수요 증가에 따른 혼잡한 상황과 부족한 공항 운항 능력을 해결하고자, 본 논문에서는 공항주위 영역에 접근하는 항공기관제 통제에 대해 연구를 진행하였다. 항공교통관 제의 목적은 항공기간의 충돌방지, 항공 교통 질서 유지 등의 안전에 주목적이 있으며, 효과적인 교통흐름을 조절하고 촉진 시키는데도 목적이 있다.
항공교통문제는 안전을 기본조건으로 흐름을 통제하여 효율성을 높이는 데 있으므로, 항공기 예상도착시간(ETA)를 이용하여 최종항공기들의 도착 시간과 항공기들의 지연정도를 목적함수로 설정하였다. 항공기 경로와 경로 결합 지점을 이용하여 스케줄링 시점을 정의하였으며, 항공기 순서 재배치의 효율성을 판단하고자 하였다. 각 스케줄링 기법들은 실제 항공관제에서 사용하는 FCFS기법을 기반으로 비교․분석 하였다.
가설 설정
마지막으로 접근하는 항공기들에 대한 거리정보는 항공기들 간의 고도 정보를 제외한 평명상(2-dimension : X-Y)의 Euclidean distance 정보만을 이용한다고 가정하였다.
Air route는 AIP(Aeronautical Information Publication)의 STAR(standard Arrival Chart)에 표기된 운영항로와 지점(fix)들을 기준으로 결정되며 공항이 가지는 환경에 따라 상이하게 된다. 본 연구에서는 NASA Ames Aviation System 에서 사용하는 TMA(Traffic Management Advisor)의 교통흐름을 참고하여 공항 주위의 영역을 4개영역(동북, 동남, 서남, 서북)으로 나누었으며, 각 영역마다 2개 route씩, 총 8개의 공항 접근 air route를 가정하였다. 또한 하나의 FAF 지점으로 최종 air route 결합을 모사하기 위해 2개의 route 가 하나의 route로 결합되는 merge point 를 3개 그룹으로 정의하였다.
또한 항공기들 간의 간격을 최소 안전거리 간격만을 유지할 수 있도록 항공기들의 지점 접근 속도에 대한 lower bound를 고려하지 않았다. 지점을 통과하는 항공기 순서 결정시 임의의 항공기에 의해 다른 항공기가 속도를 줄여야 하는 경우 문제가 발생할 수 있지만, 실제 관제시스템에서 사용하는 레이더 vectoring기법으로 지점을 통과하는 시간을 지연시킬 수 있으므로 접근 속도에 대한 lower bound는 무시한다고 가정할 수 있다.
첫 번째 가정은 통제받는 항공기간의 간격으로 항공기의 안전과 접근 절차 규정[5]을 고려하여, 최소한의 분리(minimum separation)에 의한 안전거리 간격을 가진다고 가정하였다. 항공기간의 간격 정보는 논문[6]에서 사용한 방식을 인용하여 사용한다.
제안 방법
기존의 MDD와 ATCS 기법들은 스케줄링 환경에서 우수한 결과를 가지며[2], 이러한 기법 들의 형태를 sequence dependent setup time 스케줄링문제 환경에 적절하게 융합한 새로운 휴리 스틱 기법 MDDS(Modified Due date for Setup time)을 제안한다. MDD의 마감 시간 분포와 처리시간을 비교하는 방식을 기반으로 ATCS의 setup time과 관련된 요소들[2]을 스케줄링 문제에 적절하게 융합하여 하나의 알고리즘으로 제안 하였다. 기존의 MDD는 현시점의 마감 시간과 처리 시간을 비교한 반면, 제안한 알고리즘은 스케줄링 시점마다 남아 있는 작업들의 마감 시간과 setup time 합을 추정하고 비교하여 큰 것을 마감 시간처럼 사용하는 것이 특징이다.
항공기 경로와 경로 결합 지점을 이용하여 스케줄링 시점을 정의하였으며, 항공기 순서 재배치의 효율성을 판단하고자 하였다. 각 스케줄링 기법들은 실제 항공관제에서 사용하는 FCFS기법을 기반으로 비교․분석 하였다. 동적 상황 시뮬레이션에서 일반적인 항공기 복잡도를 표현하기 위해 steady state 시간 구간을 정의하고 기법들간의 결과를 분석하였다.
고정된 상황에서의 이전 시나리오와 달리 본시나리오에서는 주기적으로 새로운 항공기들을 생성하여 실제 공항교통 관제와 동일하게 교통 스케줄링동안 관제 영역내에 항공기들이 접근하는 상황을 표현하였다. 공항 레이더 주기에 따라 10초 단위로 관제 영역내의 항공기 정보들을 업데이트하며, 일정한 주기에 스케줄링 기법들을 이용하여 각 merge point를 통과할 항공기들 순서를 재배치하게 된다.
MDD의 마감 시간 분포와 처리시간을 비교하는 방식을 기반으로 ATCS의 setup time과 관련된 요소들[2]을 스케줄링 문제에 적절하게 융합하여 하나의 알고리즘으로 제안 하였다. 기존의 MDD는 현시점의 마감 시간과 처리 시간을 비교한 반면, 제안한 알고리즘은 스케줄링 시점마다 남아 있는 작업들의 마감 시간과 setup time 합을 추정하고 비교하여 큰 것을 마감 시간처럼 사용하는 것이 특징이다.
기본 휴리스틱 기법에서 파생된 형태로 SPT와 MS의 결합형태 ATCS(Apparent Tardiness Cost rule with Setup time)[2],min [max(D i - t, P i )]로 선택된 임무를 먼저 처리하는 MDD(Modified Due Date) 기법들이 있다. 기존의 MDD와 ATCS 기법들은 스케줄링 환경에서 우수한 결과를 가지며[2], 이러한 기법 들의 형태를 sequence dependent setup time 스케줄링문제 환경에 적절하게 융합한 새로운 휴리 스틱 기법 MDDS(Modified Due date for Setup time)을 제안한다. MDD의 마감 시간 분포와 처리시간을 비교하는 방식을 기반으로 ATCS의 setup time과 관련된 요소들[2]을 스케줄링 문제에 적절하게 융합하여 하나의 알고리즘으로 제안 하였다.
각 스케줄링 기법들은 실제 항공관제에서 사용하는 FCFS기법을 기반으로 비교․분석 하였다. 동적 상황 시뮬레이션에서 일반적인 항공기 복잡도를 표현하기 위해 steady state 시간 구간을 정의하고 기법들간의 결과를 분석하였다. 시뮬레이션 결과를 통해 기존 항공관제에 사용하는 FCFS기법 보다 제안한 MDDS기법이 효과적인 기법임을 확인하였다.
동적 환경에서 각 기법들에 대한 결과를 steady state의 completion time과 delay를 확인 하였다. Fig.
초기 시간에는 관제 영역 내 접근 항공기가 존재하지 않으므로 스케줄링이 여유로운 상황이며, 일정 시간이 지나면 관제영역 내에 항공기들이 조밀하게 배치되고 실제 관제환경과 비슷한 양상을 보여주는 상황이 나타나게 된다. 따라서 관제영역 내 항공기들이 주기적으로 생성되는 동적 상황에서의 결과를 확인하고자 본 시뮬레이션에서는 일정 양상을 나타내는 안정상태를 일정시간(10000 to 17200 sec = 2hrs)으로 정의 하였다.
본 연구에서는 NASA Ames Aviation System 에서 사용하는 TMA(Traffic Management Advisor)의 교통흐름을 참고하여 공항 주위의 영역을 4개영역(동북, 동남, 서남, 서북)으로 나누었으며, 각 영역마다 2개 route씩, 총 8개의 공항 접근 air route를 가정하였다. 또한 하나의 FAF 지점으로 최종 air route 결합을 모사하기 위해 2개의 route 가 하나의 route로 결합되는 merge point 를 3개 그룹으로 정의하였다.
본 논문에서는 실시간성과 제한된 처리 능력 한계를 고려해야 짧은 시간 안에 적절한 성능의 해를 구하는데 효율적인 휴리스틱 중 짧은 시간에 수 많은 작업들을 처리하는데 유리한 dispatching기법을 통하여 스케줄링 문제에 접근하고자 한다. 또한, dispatching 기법을 이용한 항공기 순서 배치의 효율성을 분석하고자 항공기 정보가 고정된 상황 (scenario)과 계속적인 업데이트 상황으로 나누어 시뮬레이션 환경을 모사하였으며, Monte Carlo simulation을 이용하여 각 기법들에 대해 시뮬레이션을 수행하였다.
본 연구의 공항 접근 항공기 스케줄링 문제에서도 운영제한 조건(separation for safety, air route, cruise speed)을 고려하여 현실적인 문제로 접근 하고자 하였으며, 항공기들간의 추월 제한조건을 설정하여 운용 현실성을 강조하였다. 또한, 일반적인 공항 접근 영역과 항공기 접근 경로를 형식화(formulation)하여 스케줄링문제로 접근하였다.
항공기간의 간격 정보는 논문[6]에서 사용한 방식을 인용하여 사용한다. 미연방항공청(FAA : Federal Aviation Administration)에서 항공기를 이륙(takeoff) 중량을 기준으로 3가지 분류(heavy, large and small)로 구분하여[4] 착륙(landing) 항공기들에 대한 안전거리를 규정하였으며, 본 연구에서도 이 분류를 그대로 사용하였다. FAA에서는 최소 안전거리 요구 조건을 nm 단위로 정의하고 있으며, 이 조건들을 시간 단위(sec)로 변환하여 사용하였다.
이륙 전부터 공항에서 약 10nm(nautical miles)안은 관제탑(control tower)의 관제를 받게 되며, 이후 공항 주위영역의 비행은 공항접근(APP:Approach Control Center)영역으로 TMA(Terminal Control Area)이라고 하며 공항 주위 약 60 nm 영역의 항공기들을 통제한다[5]. 본 연구는 공항에 접근하는 항공기들에 대한 교통관제통제 연구이므로 TMA영역으로 통제 범위를 제한하였으며, 통제 범위 내에서 최종접근지점 FAF(Final Approach Fix)을 통과하는 항공기 순서를 배열하는 스케줄링 문제로 정의하여 교통관제문제에 접근하였다.
또한 항공교통관제 문제를 스케줄링 문제로 정의하였으며, 이를 dispatching 휴리스틱 기법들을 통해 해결하고자 하였다. 본 연구를 통해 sequence dependent setup time 스케줄링문 제에 대한 새로운 휴리스틱 기법을 제안하였으며, 제안한 기법을 시뮬레이션을 통해 기존 기법들과 비교․분석하였다.
항공교통관 제의 목적은 항공기간의 충돌방지, 항공 교통 질서 유지 등의 안전에 주목적이 있으며, 효과적인 교통흐름을 조절하고 촉진 시키는데도 목적이 있다. 본 연구에서 접근하고자 하는 항공교통 문제에서는 안전을 위한 운용 제한 조건인 항공기간의 분리 구간과 추월을 고려하여 접근하였으며, 특정 공항의 문제가 아닌 일반적인 공항의 항공 경로와 경로 결합 지점(merge point)를 정의하여 접근하였다. 또한 항공교통관제 문제를 스케줄링 문제로 정의하였으며, 이를 dispatching 휴리스틱 기법들을 통해 해결하고자 하였다.
항공교통문제를 스케줄링 문제로 정의하였으며, 문제 접근에 대한 휴리스틱 스케줄링기법들 효율성을 확인하고자 시뮬레이션을 수행하였다. 시뮬레이션은 MATLAB을 이용하여 임의의 시나리오들을 확률변수(random variables)들로 모사하였으며, Monte Carlo simulation을 통하여 각기법들에 대한 효율성을 분석하고자 하였다. 시나리오는 공항 접근영역 주위 항공기들이 경로를 따라 공항에 진입하게 되며, 각 경로들이 결합되는 merge point 통과 순서를 조정하여 최종적으로 항공기들의 FAF 통과 순서를 결정하는 상황 이다.
본 논문에서는 추월조건과 merge point 제한조건을 고려하여 실제의 관제 운영 제한조건을 표현하였다. 이는 고정된 항공기 분포조건 이외에 스케줄링 중 관제레이더 영역에 임의의 항공기들이 접근하여 정보가 주기적으로 변화하는 시나리오를 추가하여 실제의 공항 관제에 가까운 환경으로 시뮬레이션을 모사하였 다.
초기 항공기 배치는 관제 관례에 따라 FCFS(First Come First Service)로 결정되며 이를 기반으로 항공기 순서 재배치가 적용된다. 이전 연구논문[12]에서는 추월 제한조건과 merge point가 없으며, 스케줄링이 진행되는 동안 환경 변화가 없는 고정된 상황으로 간단한 TSP문제로 접근하여 각 스케줄링 기법들을 확인해보았다. 본 논문에서는 추월조건과 merge point 제한조건을 고려하여 실제의 관제 운영 제한조건을 표현하였다.
접근 항공기의 STA는 FAF까지의 평균 이동시간 1700초를 기준으로 생성시점의 현재시간 (present time)을 이용하여 정의하였으며, 결과 분석을 위한 안정상태(steady state) 시간 구간을 정의하였다. 초기 시간에는 관제 영역 내 접근 항공기가 존재하지 않으므로 스케줄링이 여유로운 상황이며, 일정 시간이 지나면 관제영역 내에 항공기들이 조밀하게 배치되고 실제 관제환경과 비슷한 양상을 보여주는 상황이 나타나게 된다.
항공교통 흐름의 고정된 상황과 계속적인 항공기 접근 상황을 시뮬레이션 환경으로 모사하였으며, 휴리스틱 기법 효율성을 확인하기 위해 Monte Carlo Simulation으로 각 기법들의 결과를 도출하였다. 항공교통문제는 안전을 기본조건으로 흐름을 통제하여 효율성을 높이는 데 있으므로, 항공기 예상도착시간(ETA)를 이용하여 최종항공기들의 도착 시간과 항공기들의 지연정도를 목적함수로 설정하였다.
각 항공 기들은 확률변수를 사용하여 임의의 위치에 분포하게 되며, 접근 경로정보, 순항속도, 초기위치및 정해진 도착시각인 STA를 임의적으로 가지게 된다. 항공기들의 통과 순서를 결정하기 위해 스케줄링 기법들을 적용하게 되며, 동일한 시나리 오에 대하여 각 기법들을 적용하여 최종 항공기의 도착시간과 지연정도(delay)를 계산하여 기법별 효율성을 판단한다. 스케줄링 기법의 적용 시점은 두 개의 경로가 결합되는 merge point에서 적용되며, 같은 경로의 항공기들은 추월이 불가 능하다는 제한조건이 고려된다.
대상 데이터
시뮬레이션 환경은 공항으로부터 60nm 떨어진 임의의 위치에서 항공기들이 8개의 route를선택하여 접근하는 상황이며, 항공기수는 20대로 고정하였다. 접근 순항속도는 0.
항공기 초기 위치와 속도 등의 변수들을 확률 변수로 사용하였기에 Monte Carlo 시뮬레이션을 통하여 각 스케줄링 기법들에 대한 평균값 결과를 통계적으로 분석하고자 하였다. 시뮬레이션에 사용한 스케줄링 기법들은 6개 기법들(FCFS, ETA, ATCS, EDD, MDD, MDDS) 이며, ETA 기법은 항공기의 속도와 초기 위치를 고려한 스케줄링 지점의 도착 시간을 예측한 시간인 ETA가 짧은 순으로 항공기를 배열하는 기법으로 앞서 소개한 스케줄링 기법 중 SPT 와 동일한 기법이다. 1st craft arrival 은 항공기를 재배치하여 가장 먼저 도착한 항공기의 시간을 의미한다.
데이터처리
Table 6에는 steady state 시간 동안 항공기들의 도착한 시간과 지연 정도 평균을 결과로 나타내었다. 동적 상황 steady state 동안 도착한 항공기들의 생성 시점부터 도착까지 소요된 시간의 합을 완료 시간으로 나타내었으며 결과는 항공기들의 평균값이다. 관제영역 내의 계속적인 항공기 생성으로 스케줄링상 지연이 발생하기 시작하면 뒤따르는 항공기들의 지연은 누적되어 커지게 된다.
접근영역 외곽의 merge point A에서부터 스케줄링이 단계적으로 시행되는 시나리오의 결과이다. 항공기 초기 위치와 속도 등의 변수들을 확률 변수로 사용하였기에 Monte Carlo 시뮬레이션을 통하여 각 스케줄링 기법들에 대한 평균값 결과를 통계적으로 분석하고자 하였다. 시뮬레이션에 사용한 스케줄링 기법들은 6개 기법들(FCFS, ETA, ATCS, EDD, MDD, MDDS) 이며, ETA 기법은 항공기의 속도와 초기 위치를 고려한 스케줄링 지점의 도착 시간을 예측한 시간인 ETA가 짧은 순으로 항공기를 배열하는 기법으로 앞서 소개한 스케줄링 기법 중 SPT 와 동일한 기법이다.
이론/모형
이를 고려하여 동일시간대에 접근하는 항공기에 대한 STA를 ETA보다 빠르게 20±5분로 정의하여 항공기들의 적당한 혼잡도 환경을 나타내었다. 시뮬레이션의 확률변수는 균일분포(uniform distribution)을 사용하였으며, 분포수준과 평균은 Table 3에 정의하였다. 항공기 분류와 STA은 균일분포 확률변수기반으로 이산적으로 표현하였다.
첫 번째 가정은 통제받는 항공기간의 간격으로 항공기의 안전과 접근 절차 규정[5]을 고려하여, 최소한의 분리(minimum separation)에 의한 안전거리 간격을 가진다고 가정하였다. 항공기간의 간격 정보는 논문[6]에서 사용한 방식을 인용하여 사용한다. 미연방항공청(FAA : Federal Aviation Administration)에서 항공기를 이륙(takeoff) 중량을 기준으로 3가지 분류(heavy, large and small)로 구분하여[4] 착륙(landing) 항공기들에 대한 안전거리를 규정하였으며, 본 연구에서도 이 분류를 그대로 사용하였다.
성능/효과
결과에서는 ATCS 와 MDDS 기법이 다른 기법들보다 completion time과 delay에서 적절한 효과를 보여주고 있다. 본 연구에서 제안한 MDDS기법은 다른 기법들보다 항공기들을 가장 먼저 도착하게 하며, completion time에서 기존 관제기법인 FCFS와 비교하여 약3%의 감소 효과를 delay에서 약 16%의 감소 효과를 나타냄을 확인할 수 있다.
결과에서는 ATCS 와 MDDS 기법이 다른 기법들보다 completion time과 delay에서 적절한 효과를 보여주고 있다. 본 연구에서 제안한 MDDS기법은 다른 기법들보다 항공기들을 가장 먼저 도착하게 하며, completion time에서 기존 관제기법인 FCFS와 비교하여 약3%의 감소 효과를 delay에서 약 16%의 감소 효과를 나타냄을 확인할 수 있다.
동적 상황 시뮬레이션에서 일반적인 항공기 복잡도를 표현하기 위해 steady state 시간 구간을 정의하고 기법들간의 결과를 분석하였다. 시뮬레이션 결과를 통해 기존 항공관제에 사용하는 FCFS기법 보다 제안한 MDDS기법이 효과적인 기법임을 확인하였다.
즉, 항공교통관제에서 항공기들의 지연이 시작되면 지연 정도가 누적적으로 더 커지는 상황으로 효율적인 스케줄링이 강조된다. 이러한 지연 정도가 누적되는 상황에서 본 연구에서 제안한 MDDS 기법이 일반적으로 사용되는 휴리스틱 기법들보다 적절한 성능을 보임을 확인할 수 있다. 제안한 기법이 completion time에서 기존 관제기법인 FCFS와 비교하여 약 2.
이러한 지연 정도가 누적되는 상황에서 본 연구에서 제안한 MDDS 기법이 일반적으로 사용되는 휴리스틱 기법들보다 적절한 성능을 보임을 확인할 수 있다. 제안한 기법이 completion time에서 기존 관제기법인 FCFS와 비교하여 약 2.4%의 감소 효과를 delay에서 약 6.9%의 감소 효과를 나타냄을 확인하였다.
세로축은 항공기들의 대한 정보(STA, final arrival time)이며, 가로축은 시간을 나타내며 직선의 양(positive)기울기는 기존 계획시간보다 빨리 도착한 항공기를 의미하며 음의 기울기는 늦어진 항공기를 의미한다. 표본 시간에서 양상은 초기 접근 상황에서 관제 영역 내의 항공기들의 여유로운 상황으로 빨리 도착하는 항공기들이 있는 반면 시간이 지남에 따라 항공기들의 지연이 생겨 전체적으로 지연됨을 확인할 수 있다. 안정된 항공기 접근상태인 steady state의 결과에서도 이러한 지연을 확인할 수 있다.
후속연구
본 연구를 통하여 공항 관제 영역에서의 항공기 스케줄링에 대한 시뮬레이션 환경을 구축하였으며, 다양한 운용제한 조건과 항공사간의 중요도를 반영한 항공기 정보를 이용하여 다양한 연구를 발전시킬 수 있을 것이라고 기대한다.
질의응답
핵심어
질문
논문에서 추출한 답변
항공교통의 수요 증가와 혼잡에 의해 예상되는 결과는 어떠한가?
오늘날의 항공교통(air traffic) 수요 증가와 혼잡으로 2035년까지 유럽과 미국의 교통량 수요는 약 2배 가까이 증가할 것으로 예상되며, 지역적으로는 약 3배의 수요 증가를 예측하고 있다 [1,6,9]. 이러한 교통량 증가와 달리 이미 많은 공항과 공항 주위의 항공 경로(air route)는 혼잡해진 상황[1]이며 교통수요량을 충족시키기에는 부족해지고 있다.
증가한 교통수요량을 충족시키기 위해 어떤 해결책이 연구되고 있는가?
교통량 증가를 충족시키기 위한 공항 인프라구축은 수용 능력을 확장 시킬 수 있지만, 많은 시간과 자원이 필요하다. 따라서 기존의 인프라를 이용한 효율적인 운용방법들이 시도되고 연구되고 있으며 항공 운영계획과 스케줄링 (scheduling)은 중요한 해결책으로 대두 되고 있다[1,6,9,10]. 항공 교통 효율성을 위한 연구로서는 공항 내의 수용 능력을 향상시키는 연구[1,13]와이․착륙하는 항공기들의 공항 활주로의 효과적인 운용계획 및 항공기 스케줄링 연구 등 다양한 분야에서 연구되었다[1,10,13-16].
스케줄링의 목적은 무엇인가?
또한, 일반 적인 공항 접근 영역과 항공기 접근 경로를 형식화(formulation)하여 스케줄링문제로 접근하였다. 스케줄링의 목적은 시스템의 운용에서 제한된 자원을 효율적으로 운영함으로써 효과적인 성능 향상을 얻는 것으로 주어진 일정 시간 동안 제한된 자원을 배치하거나 재배열을 통해 성능을 향상 시켜야 한다. 특히, 작업의 순서와 시간 제약 조건에 따라 시스템의 효율성이 결정되며, 시간 임계성(time-critical)을 가진 시스템에서는 실시간 성이 고려되어 제한적인 계산시간 또한 중요한 요소로 작용하게 된다.
참고문헌 (16)
Bennell, Julia A., Mohammad Mesgarpour, and Chris N. Potts. "Airport runway scheduling." 4OR 9.2 2011, pp. 115-138.
M. L. Pinedo. "Scheduling : Theory, Algorithms, and Systems," Springer, New York, 2012.
Y.H. Lee, K. Bhaskaran, M. Pinedo, "A heuristic to minimized the total weighted tardiness with sequence-dependent setups," IIE transactions 29.1, 2012, 45-52.
Administration, F. A. Air Traffic Control. FAA Order, 7110, 2006. 65.
CIVIL AVIATION SAFETY AUTHORITY MINISTRY OF LAND, TRANSPORT & MARITIME AFFAIRS REPUBLIC OF KOREA, 2008, "Air Traffic control Precedures"
Lee, H., & Balakrishnan, H. "A study of tradeoffs in scheduling Terminal-Area operations," Proceedings of the IEEE, 96(12), 2008, pp. 2081-2095.
Carr, Gregory C., Heinz Erzberger, and Frank Neuman. "Airline arrival prioritization in sequencing and scheduling." 2nd USA/Europe Air Traffic Management R&D Seminar, Orlando. 1998.
Jeong, S. J., Jang, D. S., Choi, H. L. and Roh, J. E., "Statistical Analysis of Task Scheduling Rules for Airborne Radar," KSAS Conference 2012.11, pp. 300-306.
http://www.jpdo.gov/index.asp
Brinton, Chris, et al. "Ration by Schedule for airport arrival and departure planning and scheduling." Integrated Communications Navigation and Surveillance Conference (ICNS), 2010. IEEE, 2010. pp. I3-1.
De Neufville, Richard, and Amedeo Odoni. "Airport Systems. Planning, Design and Management," McGraw-Hill, New York, 2003.
Jeong, S. J., Jo, D. H., Choi, H. L. "Heuristic algorithms for Air Traffic Scheduling in Terminal Airspace," KSAS Conference 2014.4, pp. 60-63.
Gilbo, Eugene P. "Airport capacity: Representation, estimation, optimization." Control Systems Technology, IEEE Transactions on 1.3 1993, pp. 144-154.
Atkin, Jason AD, et al. "A metaheuristic approach to aircraft departure scheduling at London Heathrow airport." Computer-aided Systems in Public Transport. Springer Berlin Heidelberg, 2008. pp. 235-252.
Saraf, Aditya P., and Gary Slater. "Optimal dynamic scheduling of aircraft arrivals at congested airports." Journal of guidance, control, and dynamics 31.1 2008. pp. 53-65.
Zhang, Xie, et al. "Optimization of sequencing for aircraft arrival based on approach routes." Intelligent Transportation Systems Conference(ITSC). IEEE., 2007. pp. 592-596
※ AI-Helper는 부적절한 답변을 할 수 있습니다.