“华为杯”第十五届中国研究生
数学建模竞赛
题 目 机场新增卫星厅对中转旅客影响的评估方法
摘 要
机场新增卫星厅对中转旅客的换乘可能会造成一定的影响，因此通过仿真分析卫星厅的存在对机场运营的影响具有十分重要的意义。本文对新增卫星厅后的机场登机口优化分配问题进行了一定的研究。首先对数据进行预处理，将研究范围限定在2018年1月20日，对其中的69个登机口、303个航班、863个换乘记录及对应的2751名乘客进行研究，逐步建立了考虑中转旅客换乘时间的航班-登机口优化分配模型，并针对这一高维度的组合优化问题提出了对应的求解算法，求解结果表明所提算法是有效的。具体的问题解决方案如下所述。
针对问题一，本文首先以最大化被分配到固定登机口的航班最为目标函数，考虑登机口与航班的匹配约束以及登机口时间占用约束，建立了整数规划模型，通过Gurobi求解器求解得到拥有固定登机口的飞机最多有256架。进一步以约束的形式逐步减小登机口的数量，从而得到登机口数量-拥有固定登机口飞机的Pareto前沿，从而得到登机口的最少数量
为65。
针对问题二，本文通过引入4个索引描述换乘过程，然而通过传统解析法建模将会导致“维数灾”，使得问题难以求解。因此本文提出了一种多阶段邻域搜索算法，首先设计了登机口内部航班交换、登机口内部航班平移、登机口-临时机位航班交换这三种邻域搜索策略，并证明了这三种策略能遍历所有的邻域，同时设计了对应的邻域约束判断函数，从而得到有效邻域，最后证明了邻域搜索算法具有优化目标函数的梯度，通过邻域搜索算法能够在不违反约束的条件下逐步的向目标函数更优的方向移动，从而得到合理的最优解。本文以问题一中得到的登机口分配作为初始解，从而确保有256架航班拥有固定登机口，以中转旅客流程时间最短作为第一阶段的目标，从而得到需考虑换乘的乘客数量为1709名，中转旅客的流程时间为54655分钟。在第二阶段中，将第一阶段中求得的最短流程时间最为约束条件，优化登机口的数量，从而得到登机口的最少数量为65。
1
针对问题三，本文进一步考虑中转旅客的换乘时间，将目标函数改变为最小化中转旅客的换乘紧张度，同样使用多阶段邻域搜索算法，最终得到拥有固定登机口的航班有256架，从而得到需考虑换乘的乘客数量为1718名，中转旅客的换乘紧张度为511.06，登机口的最少数量为66。
通过对结果的分析我们发现，卫星厅的建设可以缓解原有航站楼登机口不足的压力，但卫星厅的投运可能使游客的换乘时间增加，引起旅客换乘失败。根据计算，新建卫星厅后，旅客的平均换乘紧张度为0.297，没有换乘失败的旅客，因此卫星厅虽然在一定程度上增加了换乘时间，但旅客的平均换乘紧张度仍是一个较低的数字，同时并没有因为卫星厅的存在导致旅客出现换乘失败的现象，因此机场新增卫星厅对中转旅客影响在可以接受的范围内，卫星厅对于机场而言是利大于弊的。
关键词：航班-登机口分配；组合优化；多目标优化邻域搜索算法；分阶段优化
2
目 录
1 问题重述 ................................................ 5 1.1问题背景 ..................................................... 5 1.2 待解决问题 .................................................. 5 2 模型假设及符号说明 ....................................... 6 2.1 模型假设 .................................................... 6 2.2 符号说明 .................................................... 7 3 数据预处理及问题分析 ...................................... 8 3.1 冗余数据删除处理 ............................................ 8 3.2 时标处理 .................................................... 8 3.3 逻辑变量量化处理 ............................................ 8 3.4 19日到达20日出发的飞机处理 ................................. 9 3.5 飞机起飞时间延长处理 ........................................ 9 3.6 问题分析 .................................................... 9 4 问题一的模型建立与求解 ................................... 11 4.1 问题分析 ................................................... 11 4.2 不考虑登机口数量航班-登机口组合优化模型 ..................... 12 4.3 考虑登机口数量及逐次逼近求Pareto的方法 ..................... 13 4.4 求解结果 ................................................... 14 5 问题二的模型建立与求解 ................................... 19 5.1 算法描述 ................................................... 19 5.2 算法最优性证明 ............................................. 23 5.3 最小登机口处理方法 ......................................... 23 5.4 求解结果 ................................................... 24 6 问题三的模型建立与求解 ................................... 28 6.1 数学模型 ................................................... 28
3
2018年研究生数学建模F题一等奖获奖论文及程序 (1)
