摘 要

机场摆渡车调度问题是保障机场航班正常运作的重要环节。一套好的机场摆渡车调度方案可以直接提高机场运行的效率以及质量。目前，我国机场的机场摆渡车调度方案主要还是依靠人工安排，效率以及成本还有很高的提升空间。

机场摆渡车调度问题可以视为一种特殊的FJSP问题。本文主要研究了遗传算法、蝙蝠算法在求解FJSP问题中的特点，并提出融合二者思想的混合蝙蝠算法，应用于解决FJSP问题。混合蝙蝠算法在粒子群算法的框架上,引入了遗传算法的交叉思想,种群中个体不断朝向种群最优解移动的同时，有概率与当前最优解发成染色体编码交叉操作，以增加种群基因多样性，增强了算法前期的收敛速度、能有效防止算法后期陷入局部最优解。本文使用上述三种算法，对国内某机场进行仿真，对比三者实验仿真结果，以验证混合蝙蝠算法在求解FJSP问题上有着优异的效果。

研究结果表明：遗传算法与蝙蝠算法在算法设计上有着原理性的缺陷，而混合蝙蝠算法因为引入了遗传算子而有效地提升了算法效率，在求解机场摆渡车调度问题这一FJSP问题上有着很好的适用性。

关键词：混合蝙蝠算法；FJSP问题；遗传算子

Abstract

The problem of airport shuttle bus scheduling is an important link to ensure the normal operation of airport flights. A good airport shuttle bus scheduling scheme can directly improve the efficiency and quality of airport operations. At present, the airport shuttle bus dispatching scheme of China's airports mainly relies on manual arrangements, and there is still high room for improvement in efficiency and cost.

The airport shuttle bus scheduling problem can be regarded as a special FJSP problem. This paper mainly studies the characteristics of genetic algorithm and bat algorithm in solving FJSP problem, and proposes a hybrid bat algorithm that combines the ideas of the two to apply to solve FJSP problem. Hybrid bat algorithm introduces the thought of cross of genetic algorithm in the framework of particle swarm algorithm. While individuals in the population continue to move toward the optimal solution of the population, there is a possibility that the current optimal solution will be sent into the chromosome coding cross operation to increase the genetic diversity of the population , Which enhances the convergence speed of the algorithm in the early stage and can effectively prevent the algorithm from falling into the local optimal solution in the later stage. This paper uses the above three algorithms to simulate a domestic airport, and compares the experimental results of the three experiments to verify that the hybrid bat algorithm has an excellent effect in solving the FJSP problem.

The research results show that genetic algorithm and bat algorithm have principle defects in algorithm design, and hybrid bat algorithm can effectively improve algorithm efficiency, and has good applicability in solving FJSP problem of airport shuttle bus scheduling problem.

Key Words：FJSP problem；Hybrid bat algorithm；Genetic arithmetic

目录

第1章 绪论 2

1.1 研究目的以及意义 2

1.2 国内外研究现状发展趋势 2

1.3 本论文的主要工作以及章节安排 3

第2章 数学模型 4

2.1 问题描述 4

2.2 符号说明 4

2.3 FJSP模型的构建 5

第3章 模型的求解 6

3.1 遗传算法求解 6

3.1.1 遗传算法定义 6

3.1.2 遗传算法描述 6

3.2 蝙蝠算法求解 7

3.2.1 蝙蝠算法定义 7

3.2.2 蝙蝠算法描述 8

3.3 混合蝙蝠算法求解 9

第4章 数值仿真 11

4.2 编码方式 11

4.3 种群初始化 13

4.4 各算法更新策略 13

4.4.1 蝙蝠算法描述 13

4.4.2 蝙蝠算法描述 14

4.4.3 混合蝙蝠算法描述 15

4.5 结果分析 16

第5章 结论 18

第1章 绪论

1.1 研究目的以及意义

随着中国经济的高速发展,搭乘飞机出行成为了许多人远程出行的选择。目前，中国已经是全球第二大航空运输市场。预计在2024年，中国将成为全球最大航空运输市场[1]。然而，随着高速增长的航空运输能力需求与有限的机场资源之间矛盾的不断加深，如何高效地利用机场资源成为机场运行的关键问题之一[2]。

机场摆渡车是用于机场候机楼与机坪之间接送旅客的专用车辆。尽管越来越多的机场逐渐引入廊桥来解决旅客运输的问题，廊桥在实际运用中仍存在着：廊桥数目有限、间接造成的费用损失过高、无法应对大流量航班等问题。机场摆渡车方案仍是目前的最优解决方案。目前我国民航机场对机场摆渡车的调度方案大多还是依靠人工调度[3]。

如何合理地调度机场摆渡车，在保证航班行程不被耽误的前提下，满足航班的人员运输问题、最大化节省运输开支，成为了机场急需解决的问题[4]。

机场摆渡车调度问题是一个经典的柔性作业车间调度问题（Flexible Job-shop Scheduling Problem, FJSP）的变型，是经典NP-hard问题中作业车间调度问题（Job-shop Scheduling Problem, JSP）的拓展[5]。一般类型的JSP问题可表达为：n个工件在m台机器上加工，每个工件有特定的加工工艺，每个工件加工的顺序及每道工序所花时间给定，安排工件在每台机器上工件的加工顺序，使得某种指标最优[6]。而FJSP问题中，每个工序允许在一组可用机器中的任何一个上进行处理。柔性作业车间调度问题着重于研究工件的加工顺序以及机器工作安排问题。在数学上，该问题是典型的NP-hard问题，复杂度高、解空间复杂，很难全面且高效地解决这一类问题。

在机场摆渡车调度问题中，机场摆渡车可以看作进行加工的机器，飞机以及机场的乘客便是需要加工的工件。我们需要合理安排机场摆渡车的运行表，保证乘客、航班时间不被耽误的同时，使机场摆渡车的运行总费用尽量最低。

如果能为机场摆渡车调度问题等FJSP问题求得一种更为方便且普适的解决算法，那么工业上的许多同类问题，如车床工作安排、人员工作时间安排等问题都可以使用相似方法加以解决，有利于维持我国工业快速稳定发展趋势。

1.2 国内外研究现状发展趋势

自1990年，P. Brucker与R. Schlie提出FJSP问题以来[7]，国内外相关研究人员提出了各种不同的优化算法来求解FJSP问题。早在2006年，彭传勇就引入了广义粒子群算法。其中，粒子的局部搜索策略采取了禁忌搜索来实现[8]。李俊使用了采取轮盘赌编码的模拟退火算法，其中采用基于互换的局部搜索方法能有效改善算法的求解性能[9]。姜天华在灰狼算法中引入遗传因子，以增强算法的全局搜索能力。此外，他还嵌入一种变邻域搜索策略,以加强算法的局部搜索能力[10]。Gao提出了一种经典的混合遗传算法和一种最新的带有变量邻域搜索的帝国主义竞争算法来求解FJSP[11]。

从国内外的研究发展趋势可以看出，目前对FJSP问题的研究已经不局限于使用单独一种智能算法进行求解，而是倾向于使用融合了多种算法思想的混合方法进行求解。

1.3 本论文的主要工作以及章节安排

遗传算法是John holland于20世纪70年代提出的一种智能算法[12]。该算法模拟了自然界中细胞增殖时染色体基因的变化，其本身具有很强的全局搜索能力。但其自身也存在着后期收敛速度较慢、进化效率低等问题。许多学者在其他算法中引入包含遗传算法的遗传因子，以增强原算法的全局搜索能力[5, 13-15]。

蝙蝠算法是yang于2010年提出的一种启发式搜索算法[16]。相较于神经网络算法而言,蝙蝠算法有更强的可解释性。作为一种较新的群智能算法，其具有更高的准确性和有效性，且没有许多参数要进行调整。但是蝙蝠算法自身存在着后期种群相似度高、后期收敛速度慢较等问题，仍有很大的提升空间。

由遗传算法、蝙蝠算法的特性以及自身局限性，本人提出在蝙蝠算法中加入遗传算法因子，以增强蝙蝠算法的全局搜索能力以及收敛速度。

本人计划采用遗传算法、蝙蝠算法、两者融合的变异蝙蝠算法进行试验，使用某机场数据进行仿真求解，以比较三种方法的效果优劣，得出更佳的FJSP问题解决方案。

本文将分在后续的章节中，依次解决模型构造、模型求解、数值仿真、总结归纳四个问题。

第2章 数学模型

2.1 问题描述

一般类型的FJSP问题可表述为：个工件在台机器上加工，每个工件有特定的道加工工艺，每道加工工艺可以在若干个机器上进行加工，每个工件加工的顺序及每道工序所花时间给定。我们的目标是调节各个工件在每台机器上的加工顺序，以使某种指标最优[5]。

机场摆渡车调度问题与传统的FJSP问题也存在细微不同之处。如机场摆渡车调度问题省去了一项加工工序需要多个机器进行加工这一特性，但也增加了加工工序有固定起始时间、加工工序所需时间非固定等限制。

在机场摆渡车调度问题中，机场摆渡车可以看作进行加工的机器，飞机以及机场的乘客便是需要加工的工件。每趟航班抵达机场后需要机场摆渡车进行对接，这一行为可以看作机器对工件进行加工。需要注意的是，机场摆渡车对接的航班不同，其往返于两个航班地点的道路也会不同。因此，机场摆渡车行驶时间与其负责的航班相关，可以看作工件加工时间与机器负责的工件有关。我们需要合理地安排机场摆渡车的运行表，保障乘客、航班时间不被耽误的同时，使摆渡车运行总费用尽量的低。

更为具体的数理描述如下：现有架航班，辆机场摆渡车，记航班集,摆渡车集。表示航班抵达机场的时间。对于每一辆摆渡车，用集合记录其所交接的趟航班。

2.2 符号说明

指标集：

：航班指标；

：机场摆渡车指标；

：一天的航班数目；

：机场摆渡车数目；

参数定义：

——航班抵达机场的时间；

——航班与机场摆渡车对接工作所需要的时间；

——机场摆渡车与航班对接后运行到下客点k所需要的时间；

——机场摆渡车一天所运行的道路长度；

——机场摆渡车平均每日维护费用；

——机场摆渡车运行每公里所消耗的费用；

——机场摆渡车所进行的第项任务所需要的时间，如：从下客点运行至航班处；

——机场摆渡车的运行总费用；