多目标飞机和旅客恢复分阶段启发式算法  

Heuristic algorithm in stages of multi-objective aircraft and passenger recovery

作　　者：李晓岚[1] 乐美龙[2] 

机构地区：[1]上海海事大学物流研究中心,上海201306 [2]上海海事大学科学研究院,上海201306

出　　处：《计算机应用研究》2014年第8期2270-2274,共5页Application Research of Computers

基　　金：上海市自然科学基金创新行动计划资助项目(10190502500);上海海事大学启动基金资助项目;上海市科委工程中心资助项目(09DZ2250400)

摘　　要：为了恢复非正常航班,同时降低成本和提高恢复效率,为航空公司进一步提升利润空间,从整体角度考虑建立了飞机和旅客流综合恢复模型。模型不仅以最小化显性恢复成本为目标,并且从旅客心理角度出发,以隐性旅客失望溢出成本最小化为第二目标。该多目标规划模型考虑多机型、航班串指派、航班序列时间限制、飞机定检、旅客OD对、旅客行程安排等条件。针对模型特点设计分阶段启发式算法,分为构建初始解、修复可行解和改善优化解三个阶段,通过不断迭代寻求较优解。引用上海航空公司数据进行算例测试,并设计两种不同干扰情景有针对性地加以恢复。结果和手动顺延方案相比,恢复成本分别降低20.482%、39.852%,恢复效率分别提高33.33%、51.22%,表明该算法和模型能有效整合飞机和旅客两种资源,为航空公司自动化恢复系统服务。In order to recover the irregular flights,reduce the costs,improve the efficiency,and further promote the space of profits for airlines,from the perspective of the overall consideration,this paper built a comprehensive model of aircraft and passenger recovery,which pursued the minimum explicit costs as the first goal and also sought the lowest implicit overflow cost of passengers who were disappointed as the second goal considering the psychology of passengers. Taking into account of multiple types of aircraft,flight string assignment,time limits of flight sequence,regular examination of aircraft,origin-destination（ OD） pairs,passenger arrangement and other conditions in the multi-objective programming model,this paper designed heuristic algorithm in stages which consisted of building the initial solution,repairing the feasible solution and improving the optimization solution. It applied the Shanghai Airline data in the experiment,and designed two different interference scenarios to recover the abnormal flights pertinently. It turns out that the recovery costs are reduced by 20. 482%,39. 852%,and the efficiency are improved by 33. 33%,51. 22%,compared with the manually extended program. It shows that the model and the algorithm can effectively integrate the two resources of aircraft and passenger,and serve for the automated recovery system of airlines.

关 键 词：非正常航班 飞机和旅客 多目标规划 综合恢复模型 分阶段启发式算法 自动化恢复系统 

分 类 号：N945.15[自然科学总论—系统科学] TP301.5[自动化与计算机技术—计算机系统结构]