１引言
　　
　　随着经济全球化发展，面对我国航空运输业的壮大和市场需求的持续增长，如何提高营运绩效，从而提升市场竞争力，获得更高的市场占有率，已成为航空公司规划发展的重要课题。现实中的机队指派问题往往涉及大量的需求点（航班）和候选点（飞机），很难得到最优解，而现代启发式算法（Ｍｅｔａ Ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ）能够在多项式时间内找到满足实际要求的解。
　　本文将经典的蚁群算法（Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ， ＡＣＡ）模型应用于我国航空公司的机队指派问题中，在单一机种的前提下，求出最小的机队数目，并求得各单机的巡航路线。本文研究的目的是使今后航空公司在处理机队指派问题时，避免依赖相关作业人员的主观判断，设计一个能够协调上述作业流程并适合国内航空运输特点的排程算法，以协助管理者解决日渐复杂的机队指派问题，兼具实际意义与理论价值。
　　
　　２基本理论
　　
　　意大利学者Ｍ． Ｄｏｒｉｇｏ于１９９１年首次提出了蚁群算法，并成功地用于求解旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ， ＴＳＰ）。ＴＳＰ 问题描述为：假设有ｎ个城市，要求找到一条遍历所有城市且每个城市只访问一次的路线，使得总的路线距离最短。
　　第一步：参数初始化。令循环次数Ｎｃ ＝ ０，设置最大循环次数Ｎｃmａｘ，将ｍ只蚂蚁置于ｎ个城市上，使得每只蚂蚁都能从任意一个城市出发。令有向图上每条边（ｉ，ｊ）的初始化信息量τｉｊ（ｔ） ＝ ｃｏｎｓｔ，其中ｃｏｎｓｔ表示常数，并且初始时刻Δτｉｊ（０）＝０。
　　第二步：循环次数Ｎｃ ＝ Ｎｃ ＋ １。
　　第三步：城市的初始禁忌表ｔａｂｕｋ ＝ １。
　　第四步：蚂蚁数目ｋ ＝ ｋ ＋ １。
　　第六步：修改禁忌表指针，对于蚂蚁己经访问过的城市就被记录在禁忌表里，并且不允许蚂蚁访问禁忌表里的城市，直到所有的城市都被访问完。
　　第七步：若集合Ｃ中城市未遍历完，即ｋ≤ｍ，则跳转到第四步； 否则执行第八步。
　　第八步：当蚂蚁遍历完所有的城市，它将在其经过的每条路径上留下信息素。公式（３）表示第ｋ个蚂蚁访问过路段（ｉ，ｊ）后释放的信息素，其中Ｑ为一个常数，表示蚂蚁释放的信息素总量，它在一定程度上影响着算法的收敛速度；Ｌｋ表示搜索到本轮最短路径的蚂蚁ｋ所走的路径总长度。根据公式（４）和公式（５）更新每条路径上的信息素，其中（１ － ρ）表示信息素挥发后的残留系数。
　　
　　３模型设计
　　
　　３．１概念定义
　　在运力严重紧张时，机队指派工作的基本目标就是用最少的飞机承担起尽可能多的航班任务。本着这个目标，本文采用一些更加合理的方法，设计出能够求解机队指派任务的蚁群算法（Ｆｌｅｅｔ Ａｓｓｉｇｎｍｅｎｔ Ｔａｓｋ ｓｏｌｖｅｄ ｂｙ Ａｎｔ Ａｌｇｏｒｉｔｈｍ， ＦＡＴ＿ＡＡ）。具体创新如下：
　　（１） 重新定义了城市的概念，把待排航班时刻表中的每一个航班抽象成一个城市。
　　（２） 改造了蚂蚁的初始状态，它们不是放置在随机任选的城市。
　　（３） 重点对城市之间的距离进行了改造，用ｄｉｊ表示第ｉ个航班到第ｊ个航班的距离，并定义该距离是一个向量，一般情况下ｄｉｊ≠ｄｊｉ。为了满足航班站衔接要求，并且要保证同一架飞机所执行的下一航班的起飞时间晚于前一航班的到港时间，设定公式（６）：
　　ｄｉｊ ＝ １００，第ｉ个航班和第ｊ个航班是同一个航班；１０，第ｉ个航班的降落机场和第ｊ个航班的起飞机场不相同， 或第ｉ个航班的降落时间晚于第ｊ个航班的起飞时间；１，第ｉ个航班的降落机场和第ｊ个航班的起飞机场相同， 并且第ｉ个航班的降落时间早于第ｊ个航班的起飞时间。 （６）
　　３．２算法流程
　　以集合Ｃ表示未被访问的城市集合，ｃｉ表示城市ｉ，ｃｊ表示城市ｊ，因此在ｔ时刻连接城市ｉ，ｊ，残留信息素的集合可表示为Γ ＝ ｛τｉｊ（ｔ） ｜ ｃｉ，ｃｊ∈Ｃ｝。在初始时刻，各条路径上的信息素相等，并表示为τｉｊ（０） ＝ ｃｏｎｓｔ。用禁忌表ｔａｂｕｋ（ｋ ＝ １，２，…，ｍ）来记录蚂蚁ｋ当前所走过的城市，剩余的能够被访问的城市集合ａｌｌｏｗｅｄｋ将随ｔａｂｕｋ的改变作动态调整。
　　第一步：参数初始化。令循环次数Ｎｃ ＝ ０，设置最大循环次数Ｎｃｍａｘ，将ｍ只蚂蚁置在需要被最早执行的ｍ个航班（城市）上，使得每只蚂蚁必须从这ｍ个城市出发。令有向图上每条边（ｉ，ｊ）的初始化信息量τｉｊ（ｔ） ＝ ｃｏｎｓｔ，其中ｃｏｎｓｔ表示常数，并且初始时刻Δτｉｊ（０） ＝ ０。
　　第二步：循环次数Ｎｃ ＝ Ｎｃ ＋ １。
　　第三步：城市的初始禁忌表ｔａｂｕｋ ＝ １。
　　第四步：蚂蚁数目ｋ ＝ ｋ ＋ １。
　　第五步：蚂蚁个体根据状态转移概率公式（１）计算的概率选择城市ｊ并前进，ｊ∈｛Ｃ － ｔａｂｕｋ｝。
　　第六步：修改禁忌表指针，将蚂蚁移动到新的城市，并把该城市放入禁忌表中。这样蚂蚁就找到了一条遍历所有城市且每个城市只访问一次的路线。
　　第七步：若集合Ｃ中城市未遍历完，即ｋ≤ｍ，则跳转到第四步，否则执行第八步。
　　第八步：当蚂蚁遍历完所有的城市，将会在其经过的每条路径上留下信息素。用公式（２）表示启发函数，它是由创新公式（６）决定的；公式（３）表示第ｋ个蚂蚁访问过路段（ｉ，ｊ）后释放的信息素；公式（４）和公式（５）表示更新每条路径上的信息素，其中（1 - ρ）表示信息素挥发后的残留系数。
　　第九步：若满足循环次数Ｎｃ≥Ｎｃｍａｘ，则循环结束并输出程序计算结果；否则清空禁忌表并跳转到第二步。
　　
　　４实际算例及结论
　　
　　本文选取的样本来自中国国际航空股份有限公司（Ａｉｒ Ｃｈｉｎａ Ｌｉｍｉｔｅｄ）于２０１０年４月份的航班时刻表，并从中选取了属于６个不同机场的４０个航班来进行机队指派任务。选取４０个航班的原因是，完成这４０个航班的飞行任务，可以有４０！种排程方法，共８．１５９ × １０４７种，如果只由人工而不用计算机辅助，势必将依赖相关作业人员的主观判断，并且工作质量无法保证。因此，如果ＦＡＴ＿ＡＡ算法能在可以接受的时间范围内，以尽可能少的飞机数目完成这４０个航班的排程任务，则足以证明算法的适用性和有效性。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）