机场登机口分配问题的顶点着色模型与算法

Vertex Coloring Model and Algorithm for Airport Flight-Gate Assignment Problem

对航班-登机口分配问题进行研究,将其看成顶点着色问题进行求解,设计了简单有效的可以应用于具有卫星厅的登机口分配的贪婪算法策略。将按照“先到先服务”的原则,依次运用启发式规则为当前航班选择登机口,即优先使用可供航班类型种类数量少的登机口,并选择已空闲时间最长的登机口。这样有助于减少使用可供多种类型航班使用的登机口的数量,有助于将这些登机口分配给数量较多的航班类型使用。同时,极大的增加了分配的鲁棒性,有益于处理飞机不可避免的短时间的延误。最后将此算法应用于上海浦东国际机场69个登机口优化安排303个航班的问题中,对算法的有效性进行验证和分析。

The flight-gate assignment problem is studied,which is regarded as vertex coloring problem,and a simple and effective greedy algorithm strategy,which can be applied to the gate assignment with satellite hall,is designed.In this paper,according to the principle of“first come,first served”,then the heuristic rules is applied to use gates that are available for one,two and four flight types in turn,and the gate with the least number of available flight types is preferred,and select gates that have been idle for the longest time further.This helps to reduce the number of gates that can be used for multiple types of flights and helps to assign the gate with the most number of available flight types to the more flight types.At the same time,it greatly increases the robustness of allocation,which is beneficial to deal with t he inevitable short delay of aircraft.Finally,the algorithm is applied to the optimization of 303 flights at 69 gates of Shanghai Pudong International Airport,which proves that such algorithm is efficient.