一种基于遗传和涟漪扩散模型的机场停机位分配混合算法  

A Hybrid Algorithm for Airport Gate Assignment Problem Based on Genetic Algorithm and Ripple Spreading Model

作　　者：张可 胡小兵[2] 冷甦鹏[3] 徐硕 刘浩 

机构地区：[1]北京市交通运行监测调度中心,北京100073 [2]北京师范大学减灾与应急管理研究院,北京100875 [3]电子科技大学通信与信息工程学院,四川成都611731 [4]北京市交通信息中心,北京100073

出　　处：《公路交通科技》2013年第12期138-146,共9页Journal of Highway and Transportation Research and Development

基　　金：北京市交通行业科技项目(2012kj-035)

摘　　要：机场停机位分配问题是一个组合优化问题,在遗传算法的实现中通常使用基于飞机停泊顺序的排列表示法。该类遗传算法的设计时常需要考虑求解时的可行性和内存效率问题。本文提出了一种混合遗传算法,将GAP的原顺序解转换为数值解,使基本的二进制表示法和所有的经典进化算子都可用于以上问题。在混合遗传算法中,等待停机位的飞机被映射为特定参数化空间中的点。受液体表面涟漪扩散的自然现象启发,本文提出了一种确定性模型,将相关空间参数作为输入,连接所有飞机的映射点而构建飞机到停机位的队列,由此,本文采用了一种可兼容所有经典进化算子的二进制遗传算法,可利用这些空间参数求得最优或逼近最优解。仿真试验验证了为解决机场停机位分配问题提出的基于涟漪扩散模型的混合遗传算法的有效性。Since the Gate Assignment Problem （GAP） at airport terminals is a combinatorial optimization problem, permutation representations based on aircraft dwelling orders are typically used in the implementation of Genetic Algorithm （GA）. The design of such GA is often confronted with feasibility and memory-efficiency problems. A hybrid GA which transforms the original order based GAP solutions into value based ones is proposed, so that the basic binary representation and all classic evolutionary operators can be applied in the above problems. In the hybrid GA scheme, aircraft queues to gates are mapped as points into a parameterized space. Inspired by the phenomenon of natural ripple-spreading on liquid surface, a deterministic model which uses relative spatial parameters as input to connect all aircraft points to construct aircraft queues to gates is developed. Thus, a traditional binary GA compatible to all classic evolutionary operators is used to evolve these spatial parameters to find an optimal or near-optimal solution. The effectiveness of the new hybrid GA based on the ripple-spreading model for the GAP problem are verified bysimulation experiments.

关 键 词：交通工程 停机位分配问题 计算机仿真 遗传算法 涟漪扩散模型 组合优化 

分 类 号：V351.11[航空宇航科学与技术—人机与环境工程] U491.123[交通运输工程—交通运输规划与管理]