科技通报
科技通報
과기통보
Bulletin of Science and Technology
2015年
10期
235-238
,共4页
停机位分配%顶点着色问题%随机序列启发式搜索%蚁群算法
停機位分配%頂點著色問題%隨機序列啟髮式搜索%蟻群算法
정궤위분배%정점착색문제%수궤서렬계발식수색%의군산법
gate assignment%graph vertex coloring problem%sequential heuristic search%ant colony algorithm
通过分析机场停机位分配的特点,以停机位使用数量最少、航空器在机场滑行距离或时间最短且充分考虑机位均衡利用为目标,建立了机场停机位分配问题的优化模型.应用图论的原理将该问题转化为对图的顶点着色问题,在随机序列启发式搜索求解基础上,设计了基于蚂蚁径路搜索规则的迭代寻优算法,即通过设置邻接矩阵,使每只蚂蚁在可行域内一步步构建有化解,该算法有效地避免了启发式搜索易陷入局部最优的缺陷.最后构造了算例,验证了该模型与算法的合理性.
通過分析機場停機位分配的特點,以停機位使用數量最少、航空器在機場滑行距離或時間最短且充分攷慮機位均衡利用為目標,建立瞭機場停機位分配問題的優化模型.應用圖論的原理將該問題轉化為對圖的頂點著色問題,在隨機序列啟髮式搜索求解基礎上,設計瞭基于螞蟻徑路搜索規則的迭代尋優算法,即通過設置鄰接矩陣,使每隻螞蟻在可行域內一步步構建有化解,該算法有效地避免瞭啟髮式搜索易陷入跼部最優的缺陷.最後構造瞭算例,驗證瞭該模型與算法的閤理性.
통과분석궤장정궤위분배적특점,이정궤위사용수량최소、항공기재궤장활행거리혹시간최단차충분고필궤위균형이용위목표,건립료궤장정궤위분배문제적우화모형.응용도론적원리장해문제전화위대도적정점착색문제,재수궤서렬계발식수색구해기출상,설계료기우마의경로수색규칙적질대심우산법,즉통과설치린접구진,사매지마의재가행역내일보보구건유화해,해산법유효지피면료계발식수색역함입국부최우적결함.최후구조료산례,험증료해모형여산법적합이성.
By analyzing the characteristics of gate assignment in aerodrome, an optimization model of storage for gate assignment was established in this article. Then this problem was converted to graph vertex coloring problem by using graph theory. Based on the idea of sequential heuristic search, this paper proposes a new ant colony optimization algorithm for the classical graph coloring problem to effectively avoid the weakness of easily running into local minimum of heuristic research. Combined with the actual gate assignment in airport, computer simulation is used to approve the feasibility and practicality of the study.