（交通信息工程及控制专业论文）飞机排班算法的研究与实现.pdf

南京航空航天大学硕士学位论文 i 摘摘 要要 民航飞机排班问题是航空公司生产运营过程中的一项重要工作，其解决的好坏直 接影响到航空公司的安全和效益。因此，在目前民航信息化的大背景下，如何使用合 适的算法实现飞机排班的计算机化，并合理有效的进行飞机排班，是国内航空公司提 高竞争力和成本控制的重要内容。 本文将进化算法引入飞机排班问题，研究并实现了基于离散型粒子群算法的飞机 排班系统。论文首先分析了飞机排班的基本过程，给出了飞机排班的基本数学模型以 及在多种因素限制下的数学模型。在分析目前几种典型飞机排班算法特点的基础上， 对其性能进行了分析对比。 考虑到各种算法的优缺点和飞机排班问题本身的各种特点， 本文选择了在解决组合优化问题方面具有较好效果的离散型粒子群算法对排班过程进 行优化，并着重研究了飞机排班（fleet assignment）算法的实现技术。根据目标函数 建立飞机排班的算法数学模型，利用离散型粒子群算法对其进行优化。首先，根据飞 机排班问题的属性以及各种限制和约束，定义了离散型粒子群算法中对应的各个参数 和进化过程中的运算规则，通过航班节交换操作来产生运动过程中粒子在各个维度上 的速度，同时通过引入排斥算子增加粒子的多样性，以保持个体的进化能力。然后建 立了基于离散型粒子群算法的飞机排班模型，并讨论了基于离散型粒子群算法的飞机 排班的流程、系统基本构成和各个功能模块的设计与实现。本文最后对系统性能进行 了分析和评估，并提出了进一步改进建议。 关键词：关键词：飞机排班，组合优化，离散型粒子群算法 飞机排班算法的研究与实现 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 company. 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 optimizer (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 technology 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 been 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 to 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 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 optimization, 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 图 5.1 飞机排班在 formax 系统中的作用.45 图 5.2 机队信息设置界面.47 图 5.3 飞机基本参数设置界面.47 图 5.4 航班信息管理界面.48 图 5.5 飞机排班主界面.49 图 5.6 gannt 图管理飞机排班计划.49 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅,可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 (保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 随着我国经济快速稳定的发展和人民生活水平的提高，中国民用航空业高速发展， 在国民经济建设中的地位也越来越重要。 中国民航也从 2002 年国务院进行的民航体制改 革后迎来了历史上发展最快的时期。 然而近年来，民航业不断出现新的趋势，民航运输业行政性垄断的打破，低成本航 空的兴起，国家开放程度的提高，市场竞争也日趋激烈。特别是中国加入wto后，根据 wto有关规定，中国需要逐步开放国际航权，多年来一直对中国航空市场虎视眈眈的国 际航空的巨头们将全面加入中国航空市场的竞争，而这些大牌的航空公司在资源、技术、 管理、人才等许多方面的实力远超过中国航空公司。 要想在未来的市场中赢得竞争趋势，就需要对民用航空运输业有一个清晰的把握。 知识经济的迅速发展和市场体系的逐渐开放带来了各个行业的市场一体化、 竞争国际化。 中国民航要想在国际竞争中占有一定优势，必须从提高自身的竞争力开始。除了提高优 质的服务，还需要通过降低成本，提高民航管理的信息化程度。对于航空公司运营而言， 飞机运行的费用占据总营运成本相当大比例，因此如何有效运用机队资源是各家航空公 司急需解决的问题。具体的说，就是在飞机排班过程中，既要符合民航总局相关飞行规 定以及飞机排班诸多限制条件，又要考虑尽量减低成本，编排可执行的飞行计划。 1.1 国内外研究现状及趋势 飞机排班一直是航空公司在生产计划方面的重要课题，是航空公司运行控制中的重 要内容之一。飞机飞行计划的制定涉及到飞行安全和航空公司机队资源的有效利用，同 时必须遵循中国民航和航空公司为飞机运行所制定的规章制度。 鉴于飞机排班数据量大、 规则限制多等特点，将飞机排班操作计算机化，使用计算机进行飞机排班，可以显著提 高排班效率和正确率，降低飞行成本，从而提高整个航空公司的航班运行效益和飞行管 理水平。 国外自 70 年代起，就开始有研究机构和团体对机组运行控制问题进行研究。目前 从事与机组控制有关的研究团体主要有三类1： (1) 国际性研究团体，主要包括国际航空运输协会（iata, international airline transport association） 、国际运筹学联合会的航空公司工作组（agifors, airline group for international federation of operation research）等。 (2) 科研机构和院校，如美国的麻省理工学院的交通运输研究中心（center for transportation studies） ，乔治亚工学院，瑞典的应用数学研究所（itm, the swedish institute of applied mathematics）等等。他们的研究范围包括从航空公司座位控制、收益 飞机排班算法的研究与实现 2 管理、运行控制和资源优化等有关航空公司的各个方面，而对飞机运行控制，他们的研 究内容主要集中在其在飞机排班算法这一核心问题的研究上，并取得了许多成果2。 (3) 航空公司中的研究及开发群体以及一些面向航空公司的专业 it 及咨询公司。如 saber，mercury systems，lufthansa 航空公司等。这些公司在应用方面有丰富的经验， 他们的工作更加注重系统实用性， 提出了一套面向航空公司的完整的、 集成的解决方案， 并且开发出较为成熟的产品，如 mercury system 的 nova crew planning 以及 lufthansa 的 lisline 等。 在国内， 1997 年南方航空公司与美利坚航空公司(american airlines)及美国世博公司 (sabre)合作， 引进了国外先进的 “航空公司运行控制系统” ( system operations control, soc )。 飞机排班系统是 soc 系统中功能最强大的软件系统， 也是整个 soc 中业务模式 最复杂、受制约因素最多的应用。目前几乎所有的航空公司都正在组建或者已经使用引 进的管理系统，如中国国际航空公司飞行总队航班生产综合系统，以及南方航空公司和 东方航空公司的飞行队信息管理系统。 1.2 研究目的及意义 飞机排班是航空公司生产运营过程中十分重要和关键的步骤， 对航空公司的正常运 作和整体效益有着决定性影响。合理、科学的安排飞机的飞行计划，有利于充分利用航 空公司机队资源，降低营运成本。 研究飞机排班的最终目的是为航空公司取得最大的经济效益。 本课题将重点讨论在 各个因素制约情况下选择出合理的并能达到最佳的经济效益的飞机排班算法。 目前国内各航空公司业务迅速增长，机队日益扩大，特别是航线网络日益大型化和 复杂化，人工设计航线网络耗时长、准确性差，无法使经济效益最大化。飞机排班算法 将实现飞机调度工作的自动化，降低排班的难度，最大程度的保证了航空公司的经济效 益。以飞机排班算法为理论依据的飞机排班管理系统即将成为航空公司规范运行管理、 提高飞行安全、节约运营成本、增加运营效益的一项重要措施。 一个好的航班飞行计划牵涉到中国民航和航空公司内部诸多章法制度，是一个十分 复杂繁重的任务集合。目前，大多数航空公司主要依靠手工排班。航空公司排班部门人 员在接到航班时刻表之后，根据经验，将航班时刻表中某些不可分割的航班，如使用同 一架飞机，同一组人员，连接成同一任务。再按照飞机的运行规定，组成一个以基地为 起始点的航班任务环。由于飞机与航班的组合数目众多，若要以人工方式执行，要求排 班人员必须有相当丰富的经验，在航班量很大的情况下，难以对排班计划作出快速准确 的安排和调整，更难保证排班结果的经济型、正确性和合理性，这种方式已经不能满足 快速发展的现代化航空运输需要；有的航空公司引进了国外计算机排班系统，但是国内 南京航空航天大学硕士学位论文 3 外的国情不同，国外的排班系统不能针对国内具体情况进行安排。 针对这个问题，我们开展了飞机排班系统研究，旨在利用先进的计算机技术，解决 航空公司飞机排班问题，以提高航班运营效率，降低成本。本课题主要内容包括对飞机 与航班进行配对和使用进化算法对飞机排班结果进行优化以帮助航空公司获得收益的最 大化。本课题是南京航空航天大学“十五 211”项目“航班优化与航线经济分析系统” (flight optimization min() ) jj pfpfi iiiji p p ffi fj f j i c xfaretfareb fare t + (1) ; () ll jjj ffliiiii ffi fj f j ii f j f j ii f cap xttb tll + (2) ; j iii j f j i ttif + (3) 1 pf ff x = (4) 1 pf p p x (5) (1) . iji j a dtimetastime + + (6) 在上面的排班数学模型中，除了基本模型中的耗费 pfpf p p ff c x 外，其他的费用由 两部分组成： ; () j i ij i i fj w j i faretfare t + 是代表由于机型载客量不够乘客改乘其他航班说 带来了损失； ; jj ij i i f j w j i b fare t 代表从别的航班改乘次航班所获得的利润。在限制条件 公式(2)里面， ; () l j ii i fj f j i tt + 代表已经预定了航班i但是由于载客量不足所损失的乘客 数量； ; jj ii i f j f j i b t 代表从其他航班改乘此航班的乘客数量。公式(3)是需求限制，确保 了预定该航班但是后来改乘其他航班的乘客数量不会超过这个航班的乘客需求量。 2.4 飞机排班常用方法 飞机排班问题属于组合优化问题，同时也是民航界著名的np问题。鉴于对一般的 组合优化问题的解决方式，主要有以下集中方法： (1)运筹学算法：例如动态规划9、整形规划10等。但是在处理大型问题时，变数与 飞机排班算法的研究与实现 10 限制式的增多将使得模式求解时间呈指数级增长，且无法保证一定能找到最佳解。 (2)启发式算法：近年来，一些人工智能算法越来越多的被用来求解组合优化问题， 例如蚂蚁算法5、模拟退火算法11、粒子群算法12、遗传算法13等。 鉴于两类算法的特点，我们选择将几种进化算法引入到飞机排班问题的求解过程 中，在下一章将会给出详细论述。 南京航空航天大学硕士学位论文 11 第三章 飞机排班算法 飞机排班问题是一个大规模的组合优化问题， 因此如何使用有效的算法提高飞机排 班工作的效率，是航空公司必须要解决的一个重要问题。 自上世纪九十年代开始，此领域的研究已经取得了很多的成果，先后有人将运筹学 算法和一些进化算法进入到飞机排班问题的解决过程中，并且取得了不错的成果。 3.1 飞机排班算法概述 严格意义上来说，此处的飞机排班算法的概念不是使用何种算法进行飞机排班，而 是首先产生飞机排班的初始解，然后在初始解的基础上采用该种算法对飞机排班的解进 行优化，从而降低航空公司的运营成本或提高航空公司的效益。 由上一章的分析可以看出，在飞机排班领域主要使用两种算法，运筹学算法和进化 算法。由于近年来进化算法在理论和应用方面都有了很大的发展，同时，已经有很多的 例子将进化算法引入到组合优化问题的求解中，并且都取得了不错的效果，所以，本文 将几种进化算法引入到飞机排班问题的求解过程中。 3.2 蚂蚁算法 3.2.1 蚂蚁算法原理 据昆虫学家的观察和研究，在蚂蚁群找到食物时，它们总能找到一条从食物到巢穴 之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素 (pheromone) 当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此 同时释放出与路径有关的信息素。路径越长，释放的激索浓度越低，当后来的蚂蚁再次 碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成了一个正反 馈。最优路径上的激索浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而 消减。最终整个蚁群会找出最优路径。 不仅如此，蚂蚁还能适应环境的变化，当蚁群运动路线上突然出现障碍物的，蚂蚁 能够很快地重新找到最优路径。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但 是通过激素的作用，整个蚁群之间交换着路径信息，最终找出最优路径14。 蚂蚁算法不仅能够智能搜索、全局优化，而且具有稳健性(鲁棒性)、正反馈、分布 式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算 使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不 容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性 飞机排班算法的研究与实现 12 强，故在基本蚂蚁算法模型的基础上进行修改，便可用于其它问题。因此，蚂蚁算法的 问世为诸多领域解决复杂优化问题提供了有力的工具。 mdorigo等人将蚂蚁算法先后应用于旅行商问题(tsp)，资源二次分配问题 (quadratic assignment problem，qap)等经典优化问题，得到了较好的效果。蚂蚁算法在 动态环境下也表现出高度的灵活性和健壮性，如其在电信路由控制方面的应用被认为是 目前较好的算法之一。此外，蚁群任务分工、打扫蚁巢分类蚁卵等行为也启发了相应的 协作和聚类算法14。 经典蚂蚁算法如下15： 初始化：a，b，c，m，n，t，o赋值，t0，v置空，u置结点全集。其中a表示 信息素强度重要性，b表示启发值的重要性，c为信息素挥发系数，nc为迭代次数，t 为当前迭代次数，m为蚂蚁数，n为城市数目，u为已加入节点集合，v为未加入节点 集合。 repeat k=1： repeat 将第k只蚂蚁随机放置在n个节点中的节点i上： 令 kk vvi=+ ， kk uui= ； 启发选择解： 根据概率( ) k ij pt选择下一个结点a， 令 kk vva=+， kk uua=， 其中( ) k ij pt 表示在时间t第k只蚂蚁从i到j的概率，( ) ij t表示在t时刻i到j的信息素 浓度， ij 是城市i到城市j边长度的倒数，称之为能见度。 记录当前最好解：置 0( ) ( ) i a ta t= ( 其中1,2,.,km，并且 0( ) min ( ( )|1,2,., i a tf a tim=) until k=m 信息素更新： 1 (1)(1)( )( ) m k ijijij k ttt = +=+ ( ) 0 k kij q ju lt other = 南京航空航天大学硕士学位论文 13 其中， k l为当前路径长度。根据此公式更新信息素浓度。 时间增长：t=t+1 until t=nc或者 0 ( )f a t优化趋势不明显。 输出 0( ) a t。 3.2.2 蚂蚁算法应用于飞机排班问题 将蚂蚁算法引入了飞机排班问题的求解，具体算法设计如下5： 初始化： ，cn，q，t，mnum赋值，cn0。其中，cn，nc与经典蚂 蚁算法意义相同，mnum为蚂蚁数。 读入待排飞机集合p和待排航班集合f的数据。 初始化蚂蚁，令每只蚂蚁包含待排飞机集合中的所有飞机，并且每只蚂蚁的已安排 航班集合v为空，未安排航班集合u置全集f。 income(bestant)=0， hours(bestant)=+ rapeat： 对于每只蚂蚁，在第1天的待排航班集合中随机选择一个航班f，令i=1。 若执行航班f要求的机型与第i架飞机的机型不相符或f的起飞航站不是第i架 飞机的所在地，则i=i+1，继续返回判断；否则，将f加入第i架飞机的已安排航班 集合v1，并令u1 = u1-f，第i架飞机的所在地更新为f的降落航站。 启发选择下一加入航班： repeat: 依照概率() k ij pcn选择加入第k只蚂蚁的航班 。 k () ju () () 0 other ijij k ijij ij l u cn cn pcn = 其中 i f表示上次加入航班。 ij 表示能见度， 在排班问题中体现为已排航班 i f 到待排航班 j f的“距离” ，( , )subtime i j为计算航班 i f和 j f之间的时间差函数， 具体表示如下： . . ( , ) ij flight j flyhourflight j profit subtime i j = 飞机排班算法的研究与实现 14 .45min. (1) ( , ) (2) ji f stimef ltime subtime i j t = 其中(1)为两航班时间间隔大于等于45min。(2)为其他(t为一个较大的值)。 若航班 j f要求的机型与第1架飞机的机型相符或 j f的起飞航站是第1架飞 机的所在地，则将 j f加入到第k只蚂蚁的第1架飞机的已分配航班集合中，则 u1= u1+f，v1= v1-f，否则判断是否可加入第2架飞机的已分配航班集合，依次 类推直至加入。 until 航班均以排完或有剩余航班，但无法进行安排。 信息素浓度更新： 分两步采用最优解信息素浓度加倍的方式对信息素浓度进行更新。具体表 示为： 1 (1)(1)()() m k ijijij k cncncn = +=+ (1) (其中i，j为任意航班节点) (1)(1)(cn) best ijijij cncn+=+ (2) (其中i，j为当前最优解中的顺序航班节点) 其中best表示获得当前最优解的蚂蚁。(cn) best ij 由如下表达式定义： q (cn)= hoursk incomek best ij 记录当前最优解： 将当前最优解与bestant相比较，若当前最优解优于bestant，则bestant=当 前最优解，否则bestant保持不变。 cn=cn+1； until cn=cn+l或bestant进化趋势不明显 输出bestant的排班结果。 3.2.3 蚂蚁算法应用于飞机排班问题流程图 使用蚂蚁算法求解飞机排班问题的流程如图3.1。 南京航空航天大学硕士学位论文 15 开始开始 得到航班信息和机队 信息 得到航班信息和机队 信息 将最优解置为0将最优解置为0 对于每只蚂蚁,随机产生一种 排班方式,即该蚂蚁的初始解 对于每只蚂蚁,随机产生一种 排班方式,即该蚂蚁的初始解 根据公式进行信息素浓度更新根据公式进行信息素浓度更新 记录当前最优解记录当前最优解 当前解优于历史最优解?当前解优于历史最优解? 用当前解更新历史最优解用当前解更新历史最优解 达到最大迭代数或进化趋势不明显?达到最大迭代数或进化趋势不明显? 输出排班结果输出排班结果 结束结束 t f t f 图 3.1 蚂蚁算法求解飞机排班问题流程图 3.3 模拟退火算法 3.3.1 模拟退火算法原理 模拟退火算法以monte carlo模型为基础， 该模型被metropolis等人用来在给定温度 飞机排班算法的研究与实现 16 下模拟达到平衡时原子的汇集情况。kirkpatrick(1983)是第1个使用模拟退火法求解组合 优化问题(combinatorial optimization)的人，经过20年的研究和应用，模拟退火算法已发 展成为非线性优化的有效工具。它是一种全局优化的数值计算方法，该算法最为显著的 特征是以一定的概率接受使目标函数值增大的移动，所以能够从局部最优解的“陷阱” 中爬出来而不会简单地终止于一局部最优解上，即具有全局收敛性16。 模拟退火算法起源于统计物理学中对固体退火过程的模拟，其基本思想是：模拟退 火算法将问题的解表示为物理退火中粒子的状态，而它的最优解即为能量的最低态。 metropolis抽样过程即为等温过程，目标函数为能量。sa由一较高的初温开始，利用具 有概率突跳特性的metropolis抽样策略在解空间中进行随机搜索， 伴着温度的不断下降， 算法重复抽样过程，最终得到问题的全局最优解。 物理退火过程由三部分组成16： (1) 加温过程：目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时， 固体将熔为液体，从而消除系统原先存在的非均匀状态； (2) 等温过程：对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发 变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡状态； (3) 冷却过程：使粒子热运动减弱，系统能量下降，得到晶体结构。 模拟退火算法的实验性能质量高，比较通用，而且容易实现。不过，为了得到最优 解算法通常要求较高的初温以及足够多次的抽样，这使算法的优化时间往往过长。从算 法结构知，新的状态产生函数、新状态接受函数、退温函数、抽样稳定准则和退火结束 准则，简称三函数两准则17，是直接影响算法优化结果的主要环节。 (1) 状态产生函数：设计状态产生函数应该要考虑到尽可能保证产生的候选解遍布 全部解空间。一般情况状态产生函数由两部分组成，即产生候选解的方式和候选解产生 的概率分布。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一 定概率方式产生，概率方式可以多样化设计，如：正态分布，指数分布等。 (2) 状态接受函数：状态接受函数是模拟退火算法实现全局搜索的最关键因素。但 根据具体实验得出结论，状态接受函数的具体形式对算法的影响并不显著。因此，算法 中通常采用 k minl,exp-(c(si)-c(s)/t 作为状态接受函数。 (3) 初温：温度t在算法中具有决定性的作用，它直接控制着退火的走向。由随机 移动的接受准则可知，初温越大，获得高质量解的几率越大，然而初温过高会使计算时 间增加。也可以均匀抽样一组状态，以各状态目标值的方差为初温。 (4) 退温函数：即温度更新函数，目前，最常用的温度更新函数为指数退温，即 1kk tt + =，其中01且其大小可以不断变化。 (5) metropolis抽样准则：用于决定在各温度下产生候选解的数目。 南京航空航天大学硕士学位论文 17 (6) 停止准则：用于决定算法何时结束。可以简单的设置温度终值。当t=tf 时算法 终止。 3.3.2 模拟退火算法应用于飞机排班问题 模拟退火算法应用于飞机排班问题，首先需要建立航班节的网络模型，然后随机产 生有向路径的分解方案，然后构造出目标函数，通过对温度参数的控制进行对飞机排班 解的优化11。 3.3.2.1 航班节的网络模型 应用模拟退火算法处理组合优化问题的一个关键技术在于寻找一种合适的解的表 现形式，它直接决定了算法的收敛性和效率18。为便于直观地描述航班节的编组方案， 本节首先构造一个描述航班节19间衔接关系的网络模型，该模型的构造主要基于以下原 则： (1)对于每个航班节的出发时刻和完备时刻，定义“出发事件”和“完备事件” ，根 据每个“事件”发生时间的先后顺序对事件进行排序，并依据“连续的完备事件与紧随 其后的连续出发事件为一个阶段”的原则，将所有事件划分为不同的阶段，以每个阶段 为节点，并将每个航班节的出发事件和完备事件所在的节点以有向弧相连，从而得到表 示该航班节的航班节弧，并将航班节弧的费用函数定义为该航班节中所包含的飞行小时 数； (2)对于起始节点v1， 只有出发航班节弧而没有到达航班节弧， 而最后节点vk则相反； (3)对于任一节点vi，如果该节点的出次d-i小于人次d+i (对于起始节点v1，则为小于 可用飞机数m)， 则说明在vi当前阶段有飞机未分配航班任务而在基地机场待命， 以连接 该节点vi及下一节点vi+1的相应数目的地面弧(ground arc)表示，其费用函数值为0； (4)对于任一节点vi，如果出次d-i大于人次d+i，则说明在当前阶段可用飞机数不足， 将有航班延误，即该节点的多余的航班节需要推后到下一节点，根据确定的航班节推后 规则选择需要后推的航班节弧，将其对应的出发时刻后推到下一个(或几个)到达航班节 弧所对应的完备时刻之后，并对后续的航班节网络做相应的调整。 按照上述规则构造的航班节网络如图3.2所示。显然，从节点v1到vk的一条有向路 径对应了一个航班节组，利用该网络模型，可以将航班节的编组问题转化为从节点v1到 vk的有向路径分解问题。 飞机排班算法的研究与实现 18 v1v3 v2v4v5 a(1,2,3) a(1,3,2) a(1,4,1) a(1,2,5) a(1,2,4)a(2,3,1) a(2,4,2) a(2,5,3) a(3,4,2) a(3,5,1) a(4,5,1) a(4,5,2) a(4,5,3) 图 3.2 航班节网络模型示意图 3.3.2.2 有向路径分解方案的随机生成 定义路径标号函数( ( , , ) r r a i j ki=以表示有向弧所在的路径显然有向路径的数目 应等于可用飞机数，即ir=1，2，m。设航班节网络的节点数为k，对于任一节点vi， il，k，其出次和人次均为di*。 对于节点v1，根据各航班节出发时刻的先后依次给各弧赋路径标号： ( (1, , )1,1,2,. .r aj llm= = (1) 对于节点vi，il，k，将各到达弧所对应的路径标号随机地分配给各出发弧即： 1 1122 ( ( , ,) ( ( , ,), ( ( , ,). ( ( , ,), 1, dd i r a i j lrandom r a l i lr a l i lr a l i l ld ijk + = =，但是该形式 所对应的温度下降太慢，计算效率不高使用以下降温方式： 1 1 (1) kkk ttt + =+ (6) 其中 00 /() ll ttmt t=，m为温度可下降的最大次数， l t为终止温度 满足下列条件之一时算法终止： (1)目标函数值取下界0； (2)选代次数达到m； 飞机排班算法的研究与实现 20 (3)当前最优状态在连续的选代循环中保持不变的次数达到了规定值 counterbeat c 3.3.2.5 算法的实现 算法实现如下： 构造航班节网络模型 根据模拟退火算法的描述，将航班节网络图的有向路分解方案视为“状态” ，记 初始状态为 0 s，相应的评估函数为 0 c，当前最优状态为 best s相应的评估函数为 best c，随 机生成一个有向路分解方案作为 0 s和 best s，将该方案对应的评估函数值作为初值赋给 0 c， best c 随机生成一个新的有向路分解“状态” 1 s，并求相应的评估函数 1 c。 状态转移如果存在 1 c 决定是否接受新状 态 1 s为当前状态 0 s。 更新当前最优状态记数器1 cntcnt cc=+。 温度下降 1 1 (1) kkk ttt + =+。 判断算法终止准则是否满足。若满足，则算法终止；否则转 整个算法的计算复杂性取决于迭代的次数及每步迭代的复杂性，而每步迭代计算中 的最大复杂度集中于生成新的有向路分解状态 1 s及对应于该状态的目标函数值 1 c的计 算 生成状态 1 s的过程实质上是在航班节网络图的前(k一1)个节点上随机地对出发弧赋 路径标号函数的过程， 由于每个节点 i v的出次 1 i d m， 节点总数kn， 所以生成状态 1 s 的计算量为(2 (2)o mm n+，即计算复杂性为()o mn；计算目标函数 1 c的过程，实质上 是利用hungarian算法求m架飞机对m个航班组的最小权最大匹配问题， 其计算复杂性 为 3 ()o m，所以整个算法的计算复杂性为 3 ()o m mmn+。 3.3.3 模拟退火算法应用于飞机排班问题流程图 模拟退火算法应用于飞机排班问题的主要流程如下： 步骤1：产生初始状态： 一般初始状态(s=s0)的产生都是随机的， 可以借助一个随机数产生器， 随机选取一优 南京航空航天大学硕士学位论文 21 化变量。 步骤2：产生初始温度： 初始温度(t=t0)不能过高也不能过低， 过高则以后的过程会有大量时间浪费在目标函 数值上升的移动上；过低又会使算法的“爬山”能力减弱而可能终止于局部最优解。一 般的t0确定方法是使初始温度t0下随机移动的接受比率落在某一给定的范围内。 步骤3：产生新状态： 由当前状态si产生新状态sj。可以从当前状态经过一次移动(进行一次扩大、缩小、 或对流程结构进行一次调整)所能达到的状态。然后根据公式判断 j i min1,exp-(c(s )() s ik j ifc strandom thens = 步骤4：随机移动接受准则： 采用metropolis准则，满足准则即进入步骤5，不满足准则回到步骤3。 步骤5：降温过程 1 ( ) kk tupdate t + =，并令k=k+1； 步骤6：停止准则 当满足停止准则时，算法流程结束。 模拟退火算法流程图如图3.3所示。 飞机排班算法的研究与实现 22 开始开始 确定初始温度,随机给 定初始解,令k=0 确定初始温度,随机给 定初始解,令k=0 随机产生一新状态 if min1,exp(-(c(sj)-c(si)/ tk) random then si=sj 随机产生一新状态 if min1,exp(-(c(sj)-c(si)/ tk) random then si=sj 满足metropolis准 则? 满足metropolis准 则? tk+1=update(tk) k=k+1 满足停止准则?满足停止准则? 输出结果输出结果 结束结束 t f t f 图 3.3 模拟退火算法流程图 3.4 离散型粒子群算法 3.4.1 离散型粒子群算法原理 粒子群优化算法是一种基于迭代的优化方法，最初由eberhart 博士和kennedy 博 士提出20，源于对鸟(鱼)群捕食行为的研究。自提出以来, 在国外得到了许多学者在理 论和应用等方面的研究，其研究大多集中在以下几个方面：首先，采用理论分析和仿真 实验等手段研究pso 算法中的参数选择问题，得出了许多很有指导性的结论；其次， 对pso 算法的标准版本进行改进，以提高算法效率, 如邻域算子21、nohope/rehope方 法22、簇分解方法23等；另外，对pso 算法的收敛性、计算效率等问题从数学角度进 南京航空航天大学硕士学位论文 23 行了一系列研究。在应用方面，针对约束非线性优化问题24、动态系统25、神经网络参 数和结构优化26等进行了许多研究。 由于pso 算法实现简单, 非常适合工程应用， 同时 在应用中取得了令人满意的效果，因而得到了国内外许多学者的关注。 但是基本粒子群算法是应用于连续优化问题的，在实际应用中许多工程难题都被描 述为组合优化问题，所以kennedy 和eberhart 提出了一种二进制离散粒子群算法。他 们在提出的模型中将每一维 id x和 id pbest限制为1或者为0， 而速度 id v不作这种限制。 用 速度来更新位置时,如果 id v高一些，粒子的位置 id x更有可能选1 ， id v低一点则选0， 阈值在 0 ,1 之间。而有这种特点的函数就是sigmoid 函数： ()1 (1 exp() kk idid sig vv=+ 二进制版本pso 的公式为: k+11k+1 idid k+1 id () then x1; x0 k id ifsig v else + t， 则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。 3.5.2 遗传算法应用于飞机排班问题 由遗传算法的原理和飞机排班问题的特点可以看出，将遗传算法应用到飞机排班问 题，主要需要解决以下几个问题： (1) 编码方案和群体的初始化 (2) 遗传算子的设计，包括选择算子、交叉算子和变异算子 3.5.2.1 编码方案和群体的初始化 使用遗传算法求解问题，首先就要确定遗传算法的编码方案。这里我们采用了“真 实值编码方法”, 在这种编码方法中, 个体染色体的各个基因座上所填的就是决策变量的 真实值。 则与 12 ,., m xx xx=相对应的染色体x 即表示为码串 12 ,., m x xx。 对于本文要 解决的飞机排班问题来说，真实值编码具有下面的优秀特性，即如果一个个体中性状优 良的基因片断被遗传到下一代，那么该片断在新个体中仍然是优良的。 群体的初始化即群体p (0) 的产生过程，应该随机产生。产生初始群体的原则是按 照飞机排班各种因素和约束的限制，随机产生n个染色体，每个染色体为一个m维向 量 12 ,., m xx xx