增设卫星厅的登机口分配问题

借鉴借鉴十五届研究生数模F题的优秀论文

问题重述

航站楼$T$人流量过多，因此增设卫星厅$S$，这样可以缓解登机口不足的问题，但是对中转旅客的衔接有一定负面影响。

已知信息

1. $T$和$S$的布局设计、功能属性、换乘时间、分配规则、旅客流程
2. 三天出发、到达航班旅客数据、航班信息

问题

1. 航班-登机口分配：不考虑换乘，尽可能多分配航班到合适登机口，最小化登机口数量
2. 考虑中转旅客最短流程：在1基础上，考虑到达航班和出发航班飞机所在登机口对旅客中转流程影响。要求优先考虑航班分配成功数量最大和旅客中转时间总体最短
3. 考虑中转旅客换乘时间：换成时间=换乘最短流程时间+捷运时间+步行时间。要求航班分配数量最大以及换乘紧张度最小

$$
换乘紧张度=\dfrac{旅客换成时间}{航班连接时间}\
旅客换乘时间=最短流程时间+捷运时间+行走时间\
航班连接时间=后一班航班出发时间-前一班航班到达时间
$$

问题一

0-1规划

不考虑旅客中转情况下，就是航班和登机口停靠匹配，选择0-1整数规划求解。

$0-1$变量——航班$i$是否停靠登机口$j$为$x_{ij}$，$y_j$为登机口$j$是否开放

目标为最大航班停靠登机口数$\sum_{i=1}^I\sum_{j=1}^Jx_{ij}$，最小登机口$\sum_{j=1}^Jy_j$，因此目标为$\max \sum_{i=1}^I\sum_{j=1}^Jx_{ij}-\mu\sum_{j=1}^Jy_j$

限制条件：

• 每个航班只能停靠一个登机口$\sum_{j=1}^Jx_{ij}\le1$
• 每个航班与停靠登机口属性匹配
• 登机口航班时间不冲突
• 航班停靠登机口必须开放

模型求解

• Java调用CPLEX接口
• MATLAB中Yalmip工具箱建模并调用GUROBI求解器

遗传算法+模拟退火

仍然使用0-1规划，但求解使用遗传算法

NP困难组合优化问题，可以使用遗传算法求解，并引入模拟退火设计适应度函数

1. 个体编码设计

   用长度$n$个体记录$n$对航班分配到的登机位

2. 初始种群生成

   约束产生个体复核约束条件

   1. 随机产生配对航班优先级顺序
   2. 按优先级对每对航班分配登机口
   3. 对航班检测是否满足所有约束条件

3. 赌轮选择：生存力越强个体被选中概率越大

   1. 计算每个个体适应度$fitness(i)$
   2. 计算个体被遗传下一代概率$P_i=\dfrac{fitness(i)}{\sum_{j=1}^N fitness(j)}$
   3. 计算个体累积概率$P_i=\dfrac{\sum_{k=1}^ifitness(i)}{\sum_{j=1}^N fitness(j)}$

   在$[0,1]$内产生随机数$r$，若$P_{i-1}\le r<P_i$，则个体$i$被选择

4. 两点交叉

   由交叉概率$P_c$选择交叉的两个个体作为父代，随机产生两个交叉点进行交换，生成子代

5. 变异算子

   两点交叉后可能不满足约束，因此进行变异

   检查交叉起点之后所有编码，若不满足则按照生成规则重新取值

6. 精英保留

   子代中，选出适应度最高的个体和当前最优个体比较，适应度最高的成为当前最优个体

7. 满足终止条件（进化$N$次），否则返回3

为防止目标函数$z$作为适应度函数，值差别不大，导致算法收敛过慢，引入模拟退火：$fitness=\text e^{\lambda z_1}\times 10^\beta$

贪婪算法

排课问题

• 按照结束时间对所有飞机排序
• 选取结束时间最早的飞机，求出候选登机口集合，安排在任意登机口
• 按照优先级对登机口排序，选择优先级最低的一个子集
• 在改子集中按照忙碌时间对候选登机口排序，选择忙碌时间最大的登机口
• 重复2-4步

启发式贪婪算法

算法仍然是0-1规划

为了快速生成可行解，使用启发式搜索方式，对每一个到达航班，筛选出可用登机口和匹配的航班。启发式规则：

1. 到达和出发航班完全匹配的优先选择，仅有出发或到达航班类型完全匹配次之，DIDI最后
2. 当天已使用登机口优先，未被使用辞职。

为了保证找到全局最优，在此基础引入概率策略。在每个决策步中，以一定概率将航班分配到临时停机场作为分析。依照上述启发规则，量化评价可用固定登机口，依权重以轮盘赌方法选择对应登机口。该算法为启发式贪婪算法，但过于随机，难以收敛

因此，可以结合遗传、蚁群算法，在每一步中，保留优秀的进行变异。

BBO算法

非线性动态规划问题，含有多个约束条件，可以使用生物地理学算法BBO，具有较好收敛和稳定性

1. 初始化 BBO 算法的参数：最大物种数$$S_{\max}$$ ，最大的迁入率$I$，最大迁出率$E$，最大突变率$g_{\max}$
2. 初始化一组栖息地的适宜度向量（SIV），每个向量都对应着一个给定问题的潜在解
3. 计算某栖息地的适宜度指数（HSI），判断是否满足停止条件，若满足，停止并输出最优解；否则，进行步骤 4
4. 进行迁移操作，计算迁入率$\lambda$和迁出率$\mu$，修正 SIV，重新计算 HSI
5. 对栖息地执行突变操作，根据变异算子更新物种，重新计算 HSI
6. 跳转到步骤 3 进行下一次的迭代

问题二

在问题一基础上考虑中转旅客流程时间

在问题一的0-1规划之外，增添：航班是否停靠在$T$，是否停靠在$Q$

启发式邻域搜索

在第一问基础上，将某两个登机口单个或多个航班对换，从而改变旅客换乘时间

• 插入类移动：将登机口1中FlightC换到登机口k中空余时间
• 间隔类交换移动：某段时间内所有航班整体交换
• 与临时停机场交互移动

问题三

考虑换乘紧张度

禁忌搜索

规模和复杂性较大，无法用求解器在规定时间求解

1. 初始解生成

   采用CPLEX求解01规划求得一个满足最大化航班停靠数的可行解

2. 禁忌表和藐视规则

   当算法执行一次交换操作，即$i$通过交换停靠在$j$，记为操作$O_{ij}$，则$i$在$n$次迭代内不能从$j$中移出。禁忌表长度$n=10+10\rho$，$\rho$为0-1随机数。当处于禁忌表中操作执行时，可以得到比历史最优解更好的解则不受禁忌表限制。每次迭代，每项操作禁忌表长度-1

3. 邻域生成

   内交互操作：已安排航班之间的交换

   外交互操作：移出一个已安排航班，插入一个未安排成功航班

4. 解的评价

   对不可解进行惩罚

5. 移动选择

   每次迭代，选择邻域评价值最小的解