《飞机排班算法的研究与实现》由会员分享，可在线阅读，更多相关《飞机排班算法的研究与实现（60页珍藏版）》请在金锄头文库上搜索。
1、南京航空航天大学硕士学位论文飞机排班算法的研究与实现姓名：于海波申请学位级别：硕士专业：交通信息工程及控制指导教师：夏洪山20070101南京航空航天大学硕士学位论文 i 摘摘 要要 民航飞机排班问题是航空公司生产运营过程中的一项重要工作，其解决的好坏直接影响到航空公司的安全和效益。因此，在目前民航信息化的大背景下，如何使用合适的算法实现飞机排班的计算机化，并合理有效的进行飞机排班，是国内航空公司提高竞争力和成本控制的重要内容。 本文将进化算法引入飞机排班问题，研究并实现了基于离散型粒子群算法的飞机排班系统。论文首先分析了飞机排班的基本过程，给出了飞机排班的基本数学模型以及在多种因素限制下的数
2、学模型。在分析目前几种典型飞机排班算法特点的基础上，对其性能进行了分析对比。 考虑到各种算法的优缺点和飞机排班问题本身的各种特点，本文选择了在解决组合优化问题方面具有较好效果的离散型粒子群算法对排班过程进行优化，并着重研究了飞机排班（Fleet Assignment）算法的实现技术。根据目标函数建立飞机排班的算法数学模型，利用离散型粒子群算法对其进行优化。首先，根据飞机排班问题的属性以及各种限制和约束，定义了离散型粒子群算法中对应的各个参数和进化过程中的运算规则，通过航班节交换操作来产生运动过程中粒子在各个维度上的速度，同时通过引入排斥算子增加粒子的多样性，以保持个体的进化能力。然后建立了基于
3、离散型粒子群算法的飞机排班模型，并讨论了基于离散型粒子群算法的飞机排班的流程、系统基本构成和各个功能模块的设计与实现。本文最后对系统性能进行了分析和评估，并提出了进一步改进建议。 关键词：关键词：飞机排班，组合优化，离散型粒子群算法 飞机排班算法的研究与实现 ii ABSTRACT Fleet Assignment is one of the most important parts of the management of Airline Company. The result of the assignment directly affects the profit of the comp
4、any. Therefore, how to automate the fleet assignment using appropriate algorithm and solving the fleet assignment problem more reasonable and effectively comes to be an important job of domestic airline to enhance competition and to control cost. This thesis introduces Discrete Particle Swarm Optimi
5、zer (DPSO) Algorithm to solve the fleet assignment problem. Firstly, the characterization of the fleet assignment is analyzed. Then it presents the basic mathematical model of the fleet assignment problem and some other mathematical models with different constraints, and especially the realization t
6、echnology of fleet assignment. Then the thesis analyzes several typical algorithms which have been used to solve the fleet assignment problem and contrast them with each other. In consideration of the data size and the constraints of fleet assignment problem, we choose the DPSO algorithm which has b
7、een used to solve many Combinatorial Optimization problems and was proved to be effectively. Firstly, we define the parameters and the operating principles of DPSO algorithm in view of the attributes and constraints of the fleet assignment problem. Then we make use of the flight-swapping operation t
8、o generate the speed of particle in every dimension, and introduce the repulsion operator to make the particle more various and keep the evolutionary ability of the particle. After these definitions, we build the mathematical model of the fleet assignment system using DPSO algorithm and realize the
9、system. Then we present the main frame of the system and introduce the realization and design of every module. In the end of the dissertation, we analyze and assess the performance of the system and give some further suggestions to improving the system. Key Words: Fleet Assignment, Combinatorial Opt
10、imization, Discrete Particle Swarm Optimizer Algorithm 南京航空航天大学硕士学位论文 v 图清单图清单 图 2.1 航空运输生产计划生成流程图.4 图 3.1 蚂蚁算法求解飞机排班问题流程图.15 图 3.2 航班节网络模型示意图.18 图 3.3 模拟退火算法流程图.22 图 3.4 粒子群算法求解飞机排班问题流程图.25 图 3.5 遗传算法基本原理图.26 图 3.6 遗传算法求解飞机排班问题流程图.29 图 4.1 航班节交换示意图.39 图 4.2 航班节交换流程图.40 图 4.3 基于离散型粒子群算法的飞机排班系统流程图.44
11、 图 5.1 飞机排班在 FORMAX 系统中的作用.45 图 5.2 机队信息设置界面.47 图 5.3 飞机基本参数设置界面.47 图 5.4 航班信息管理界面.48 图 5.5 飞机排班主界面.49 图 5.6 GANNT 图管理飞机排班计划.49 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人享有著作权的内容。对论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查阅和借阅,可以将学位论
12、文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 随着我国经济快速稳定的发展和人民生活水平的提高，中国民用航空业高速发展，在国民经济建设中的地位也越来越重要。 中国民航也从 2002 年国务院进行的民航体制改革后迎来了历史上发展最快的时期。 然而近年来，民航业不断出现新的趋势，民航运输业行政性垄断的打破，低成本航空的兴起，国家开放程度的提高，市场竞争也日趋激烈。特别是中国加入WTO后，根据WTO有关规定，中国需要逐步开放国际航权，多年来一直对中国航空市场虎视眈眈的国际航空的巨头们将全面加入中国航空市场的竞争，而这些大牌的航空公司在资源、技术、管理、人才等许多方面的实力远超过中国航空公司。 要想在未来的市场中赢得竞争趋势，就需要对民用航空运输业有一个清晰的把握。知识经济的迅速发展和市场体系的逐渐开放带来了各个行
