The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
조회수
82
항공기 착륙 일정(ALS)은 항공 교통 관리에서 가장 중요한 과제 중 하나입니다. ALS의 목표는 착륙 일정 순서를 결정하고 터미널 지역의 각 항공기에 대한 착륙 시간을 계산하는 것입니다. 이러한 착륙 시간은 시간 범위 내에 있으며 항공기 간 안전 분리 거리를 유지해야 합니다. ALS는 특히 항공기 수가 많은 경우 복잡한 문제입니다. 본 연구에서는 ALS 문제를 해결하기 위해 CGIC라는 새로운 휴리스틱을 제안합니다. CGIC는 비용 기반 청킹 규칙, 랜딩 하위 시퀀스 생성 규칙, 청크 개선 휴리스틱, 연결 규칙의 네 가지 구성 요소로 구성됩니다. 이 알고리즘에서는 더 적은 수의 항공기로 ALS 문제를 두 개 이상의 하위 문제로 나누어 ALS 문제의 복잡성을 줄입니다. 먼저, 가능한 착륙 시퀀스가 생성되고 항공기 비용을 기반으로 한 청킹 규칙에 따라 청크로 여러 하위 시퀀스로 나뉩니다. 둘째, 각 청크는 건설적 휴리스틱에 의해 재생성되며, 청크를 개선하기 위해 섭동적 휴리스틱이 적용됩니다. 마지막으로 모든 청크는 연결 규칙을 통해 실행 가능한 착륙 시퀀스를 구성하고, 이 시퀀스를 기반으로 각 항공기의 착륙 시간을 계산합니다. 시뮬레이션은 (a) 비용을 기반으로 한 청킹 규칙이 많은 수의 항공기가 있는 정적 인스턴스에서 ALS에 대한 시간이나 무게를 기반으로 한 다른 청킹 규칙보다 성능이 우수하다는 것을 보여줍니다. (b) 제안된 CGIC는 최대 500대의 항공기까지 ALS 문제를 최적으로 해결할 수 있습니다. (c) 동적 인스턴스에서 CGIC는 고품질 솔루션을 얻을 수 있으며 CGIC의 계산 시간은 실시간 실행이 가능할 만큼 충분히 낮습니다.
Wen SHI
the Tianjin University of Commerce
Shan JIANG
the Tianjin Medical University
Xuan LIANG
the Tianjin University of Commerce
Na ZHOU
the Tianjin University of Commerce
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Wen SHI, Shan JIANG, Xuan LIANG, Na ZHOU, "A Heuristic Algorithm for Solving the Aircraft Landing Scheduling Problem with a Landing Sequence Division" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 8, pp. 966-973, August 2019, doi: 10.1587/transfun.E102.A.966.
Abstract: Aircraft landing scheduling (ALS) is one of the most important challenges in air traffic management. The target of ALS is to decide a landing scheduling sequence and calculate a landing time for each aircraft in terminal areas. These landing times are within time windows, and safety separation distances between aircraft must be kept. ALS is a complex problem, especially with a large number of aircraft. In this study, we propose a novel heuristic called CGIC to solve ALS problems. The CGIC consists of four components: a chunking rule based on costs, a landing subsequence generation rule, a chunk improvement heuristic, and a connection rule. In this algorithm, we reduce the complexity of the ALS problem by breaking it down into two or more subproblems with less aircraft. First, a feasible landing sequence is generated and divided into several subsequences as chunks by a chunking rule based on aircraft cost. Second, each chunk is regenerated by a constructive heuristic, and a perturbative heuristic is applied to improve the chunks. Finally, all chunks constitute a feasible landing sequence through a connection rule, and the landing time of each aircraft is calculated on the basis of this sequence. Simulations demonstrate that (a) the chunking rule based on cost outperforms other chunking rules based on time or weight for ALS in static instances, which have a large number of aircraft; (b) the proposed CGIC can solve the ALS problem up to 500 aircraft optimally; (c) in dynamic instances, CGIC can obtain high-quality solutions, and the computation time of CGIC is low enough to enable real-time execution.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.966/_p
부
@ARTICLE{e102-a_8_966,
author={Wen SHI, Shan JIANG, Xuan LIANG, Na ZHOU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Heuristic Algorithm for Solving the Aircraft Landing Scheduling Problem with a Landing Sequence Division},
year={2019},
volume={E102-A},
number={8},
pages={966-973},
abstract={Aircraft landing scheduling (ALS) is one of the most important challenges in air traffic management. The target of ALS is to decide a landing scheduling sequence and calculate a landing time for each aircraft in terminal areas. These landing times are within time windows, and safety separation distances between aircraft must be kept. ALS is a complex problem, especially with a large number of aircraft. In this study, we propose a novel heuristic called CGIC to solve ALS problems. The CGIC consists of four components: a chunking rule based on costs, a landing subsequence generation rule, a chunk improvement heuristic, and a connection rule. In this algorithm, we reduce the complexity of the ALS problem by breaking it down into two or more subproblems with less aircraft. First, a feasible landing sequence is generated and divided into several subsequences as chunks by a chunking rule based on aircraft cost. Second, each chunk is regenerated by a constructive heuristic, and a perturbative heuristic is applied to improve the chunks. Finally, all chunks constitute a feasible landing sequence through a connection rule, and the landing time of each aircraft is calculated on the basis of this sequence. Simulations demonstrate that (a) the chunking rule based on cost outperforms other chunking rules based on time or weight for ALS in static instances, which have a large number of aircraft; (b) the proposed CGIC can solve the ALS problem up to 500 aircraft optimally; (c) in dynamic instances, CGIC can obtain high-quality solutions, and the computation time of CGIC is low enough to enable real-time execution.},
keywords={},
doi={10.1587/transfun.E102.A.966},
ISSN={1745-1337},
month={August},}
부
TY - JOUR
TI - A Heuristic Algorithm for Solving the Aircraft Landing Scheduling Problem with a Landing Sequence Division
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 966
EP - 973
AU - Wen SHI
AU - Shan JIANG
AU - Xuan LIANG
AU - Na ZHOU
PY - 2019
DO - 10.1587/transfun.E102.A.966
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2019
AB - Aircraft landing scheduling (ALS) is one of the most important challenges in air traffic management. The target of ALS is to decide a landing scheduling sequence and calculate a landing time for each aircraft in terminal areas. These landing times are within time windows, and safety separation distances between aircraft must be kept. ALS is a complex problem, especially with a large number of aircraft. In this study, we propose a novel heuristic called CGIC to solve ALS problems. The CGIC consists of four components: a chunking rule based on costs, a landing subsequence generation rule, a chunk improvement heuristic, and a connection rule. In this algorithm, we reduce the complexity of the ALS problem by breaking it down into two or more subproblems with less aircraft. First, a feasible landing sequence is generated and divided into several subsequences as chunks by a chunking rule based on aircraft cost. Second, each chunk is regenerated by a constructive heuristic, and a perturbative heuristic is applied to improve the chunks. Finally, all chunks constitute a feasible landing sequence through a connection rule, and the landing time of each aircraft is calculated on the basis of this sequence. Simulations demonstrate that (a) the chunking rule based on cost outperforms other chunking rules based on time or weight for ALS in static instances, which have a large number of aircraft; (b) the proposed CGIC can solve the ALS problem up to 500 aircraft optimally; (c) in dynamic instances, CGIC can obtain high-quality solutions, and the computation time of CGIC is low enough to enable real-time execution.
ER -