基于协同多任务分配的飞机排班模型与算法  

Optimization Model and Algorithm for Aircraft Scheduling Problem Based on Cooperative Multi-task Assignment

作　　者：周琨[1] 夏洪山[1] 

机构地区：[1]南京航空航天大学民航学院,江苏南京210016

出　　处：《航空学报》2011年第12期2293-2302,共10页Acta Aeronautica et Astronautica Sinica

基　　金：国家软科学研究计划(2008GXQ6B141)~~

摘　　要：航空公司的航班运行一直存在安全与成本的矛盾:既要严格按规定完成飞机例行检修,优先保障运行安全,又要尽可能提高飞机日利用率,以降低运行成本。为此,研究基于协同多任务分配的飞机排班问题。分析例行检修约束,建立最优化飞机日利用率的数学模型,运用分枝定价算法进行求解。分枝定价算法引入检修节点和虚拟飞机节点的定义,将分配的航班飞行任务和例行检修任务表示为飞机路径,通过迭代求解由部分飞机路径构成的限制主问题,以及寻找飞机路径以改进目标值的定价问题,获得线性松弛问题的最优解;基于最先失败原则选择路径变量,采用路径分枝策略划分解空间,从而删除分数解、生成飞机排班计划。实验结果表明,该方法能够有效求解飞机排班问题。The conflict between safety and cost is an outstanding problem during flight operation,i.e.,aircraft must accomplish maintenance tasks to establish a safe environment,and then the utilization of aircraft should be improved to reduce operational cost.In view of this,the aircraft scheduling problem based on cooperative multi-task assignment is studied.The approach applies branch-and-price algorithm to the cost optimization model with maintenance constraints,and mathematical model of daily utilization ratio is established.According to definitions of maintenance point and virtual aircraft point,the algorithm formulates assigned flights and maintenance tasks as routes.After several iterations of solving a restricted master problem containing a subset of routes and a pricing problem generating new routes with negative reduced cost,an optimal solution to the linear programming relaxation problem is obtained.To obtain the integer solution,a dedicated branching scheme based on fail first principle is proposed,and the branching decision is imposed on route variables.Then the aircraft scheduling is formed.Simulation results show that the proposed approach can solve the aircraft scheduling problem effectively.

关 键 词：空中交通管制 排班 多任务分配 分枝定价算法 列生成 约束满足 

分 类 号：V355.2[航空宇航科学与技术—人机与环境工程]