论文部分内容阅读
摘 要：机组总成本是继航油成本之后航空公司的第二大成本项目，本论文在对机组排班恢复问题进行简单描述的基础上，通过设计一种新的解的表示方法构造了求解该问题的一种新的记忆搜索算法，并进行了实验计算。计算结果表明，用本文设计的模拟记忆搜索算法求解机组排班恢复问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也比较稳定，能较好的减少航空公司的成本浪费。
关键词：机组排班恢复问题；记忆搜索算法；成本；优化
1 引言
机组排班恢复问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，仅通过优化机组排班就可以将机组费用减少几个百分点，进而每年可以为航空公司节省成千上万美元的开支，他将直接影响航空公司的盈利问题。因此，机组排班问题受到了学术界和民航界的高度关注。航班计划在延误、取消和飞机重新调整之后，原计划机组任务对被破坏或出现机组超时现象，对被破坏了任务对的机组重新分配航班任务，对超时机组寻找替换机组，使航班尽快恢复正常，就是机组排班恢复。目前我国航空公司机组恢复还停留在手工恢复阶段，建立适合我国航空公司机组恢复实际需要的模型和算法，是本文研究机组恢复问题的意义。
2 机组恢复问题的数学模型
机组恢复问题中，因航班延误造成的机组资源浪费由三部分构成，一是因机组无法正常衔接后续航班而产生的机组闲置成本，二是加机组成本的浪费，三是使用备份机组造成的成本浪费。
以下是对模型中使用的参数的解释：
模型中，式（1）是机组资源浪费最小化的目标函数，第一项是机组闲置成本，第二项是使用加机组成本，第三项是使用备用机组成本；式（2）是航班覆盖约束；式（3）是机组回基地约束；式（4）是机组执照约束；式（5）是保证航班不能被延误的约束；式（6）是保证机组不超时的约束；式（7）是0，1整数约束。
3 模拟记忆搜索算法求解机组恢复问题
3.1 模拟记忆搜索算法
模拟记忆化搜索在算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。因此给出模拟记忆搜索的算法步骤如下：
（1）给定算法参数，随机产生初始解x，按照问题的时间特征，把问题分为若干个阶段。
（2）将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。
（3）以自底向上的记忆化方法，当各阶段处的值大于1时则将其减1，并且按自顶向下的顺序记录下来。
（4）重复步骤（3）直到最终存储在矩阵中的值均为1时则记录出所有可行解。
（5）每个可行解带入算法进行计算，若大于当前最优解则取代它成为新的当前最优解，否则继续计算。
（6）计算停止后输出结果。
3.2 基于模拟记忆搜索算法的机组恢复问题求解
鉴于机组恢复问题的NP难解性，在较短的时间内精确求解还存在困难。本文采用模拟记忆搜索算法求解机组恢复问题，是因为模拟记忆搜索算法鲁棒性强，解的表示十分直观且算法策略较为简单和易于理解，占用的计算机存储量小，计算效率高，有记忆性并且可制作成可视化程序界面，便于员工使用。
4 实例计算及结果分析
机组恢复是在飞机路线恢复完成之后进行的，这里使用航空公司要来的飞机路线优化输出结果作为输入数据。案例中共5架飛机，执行12个航班，执行过程中因部分飞机故障导致航班延误。飞机路线恢复之后，新的飞机执行方案打乱了原机组执勤计划，其中加机组一次按2000元，调用备用机组一次按10000元，机组空闲一分钟按50元计算，并计算出其最小成本为88500元。
从测试结果可以看出模拟搜索算法对求解机组恢复问题是有效的，对于小规模的问题可以在很短的时间内计算出最优结果，而且解的收敛性比较稳定。文中各组参数搭配是在经过多次重复性试验的基础上得出来的。结果显示随着数据规模的增大，虽然模拟搜索算法寻求最优解的时间也是成倍增大的，但是得到优化解的频率基本保持不变，进一步说明了本文算法的稳定性。
5 结果和未来研究展望
不正常航班机组恢复问题的准确建模和快速有效求解对民航资源优化利用，降低民航运输企业运营成本和提高旅客服务水平非常重要，但目前相关的研究很少。本文在求解过程中任何机组都满足所有飞机的执照要求，与实际当中部分机组不能执行某些机型存在差距，未来可以加入这部分研究内容提高机组恢复模型的应用性。随着经济和信息技术的发展，机组恢复等问题的研究也是当今市场的迫切需要。
参考文献
[1] Diana C.， Jose L.， Miguel A.， Andrés L.， and Nubia Velasco， A mathematical programming approach to airline crew pairing optimization， 2012.
[2] O. Weide， D. Ryan， and M . Ehrgott. An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers and Operations Research， 37（5）：833-844，2010.
[3] Zhao Xiuli， “Research on Modeling and Algorithm of Airline Irregular Recovery，” Nanjing China， Nanjing University of Aeronautics and Astronautics， 2010.
[4] J.W. Yen and J.R. Birge. A stochastic programming approach to the airline crew scheduling problem. Transportation Science， 40（1）：3-14，2006.
[5] B.C. Smith and E.L. Johnson. Robust airline fleet assignment： Imposting station purity using station decomposition. Transportation Science， 40（4）：497-516，2006.
关键词：机组排班恢复问题；记忆搜索算法；成本；优化
1 引言
机组排班恢复问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，仅通过优化机组排班就可以将机组费用减少几个百分点，进而每年可以为航空公司节省成千上万美元的开支，他将直接影响航空公司的盈利问题。因此，机组排班问题受到了学术界和民航界的高度关注。航班计划在延误、取消和飞机重新调整之后，原计划机组任务对被破坏或出现机组超时现象，对被破坏了任务对的机组重新分配航班任务，对超时机组寻找替换机组，使航班尽快恢复正常，就是机组排班恢复。目前我国航空公司机组恢复还停留在手工恢复阶段，建立适合我国航空公司机组恢复实际需要的模型和算法，是本文研究机组恢复问题的意义。
2 机组恢复问题的数学模型
机组恢复问题中，因航班延误造成的机组资源浪费由三部分构成，一是因机组无法正常衔接后续航班而产生的机组闲置成本，二是加机组成本的浪费，三是使用备份机组造成的成本浪费。
以下是对模型中使用的参数的解释：
模型中，式（1）是机组资源浪费最小化的目标函数，第一项是机组闲置成本，第二项是使用加机组成本，第三项是使用备用机组成本；式（2）是航班覆盖约束；式（3）是机组回基地约束；式（4）是机组执照约束；式（5）是保证航班不能被延误的约束；式（6）是保证机组不超时的约束；式（7）是0，1整数约束。
3 模拟记忆搜索算法求解机组恢复问题
3.1 模拟记忆搜索算法
模拟记忆化搜索在算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。因此给出模拟记忆搜索的算法步骤如下：
（1）给定算法参数，随机产生初始解x，按照问题的时间特征，把问题分为若干个阶段。
（2）将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。
（3）以自底向上的记忆化方法，当各阶段处的值大于1时则将其减1，并且按自顶向下的顺序记录下来。
（4）重复步骤（3）直到最终存储在矩阵中的值均为1时则记录出所有可行解。
（5）每个可行解带入算法进行计算，若大于当前最优解则取代它成为新的当前最优解，否则继续计算。
（6）计算停止后输出结果。
3.2 基于模拟记忆搜索算法的机组恢复问题求解
鉴于机组恢复问题的NP难解性，在较短的时间内精确求解还存在困难。本文采用模拟记忆搜索算法求解机组恢复问题，是因为模拟记忆搜索算法鲁棒性强，解的表示十分直观且算法策略较为简单和易于理解，占用的计算机存储量小，计算效率高，有记忆性并且可制作成可视化程序界面，便于员工使用。
4 实例计算及结果分析
机组恢复是在飞机路线恢复完成之后进行的，这里使用航空公司要来的飞机路线优化输出结果作为输入数据。案例中共5架飛机，执行12个航班，执行过程中因部分飞机故障导致航班延误。飞机路线恢复之后，新的飞机执行方案打乱了原机组执勤计划，其中加机组一次按2000元，调用备用机组一次按10000元，机组空闲一分钟按50元计算，并计算出其最小成本为88500元。
从测试结果可以看出模拟搜索算法对求解机组恢复问题是有效的，对于小规模的问题可以在很短的时间内计算出最优结果，而且解的收敛性比较稳定。文中各组参数搭配是在经过多次重复性试验的基础上得出来的。结果显示随着数据规模的增大，虽然模拟搜索算法寻求最优解的时间也是成倍增大的，但是得到优化解的频率基本保持不变，进一步说明了本文算法的稳定性。
5 结果和未来研究展望
不正常航班机组恢复问题的准确建模和快速有效求解对民航资源优化利用，降低民航运输企业运营成本和提高旅客服务水平非常重要，但目前相关的研究很少。本文在求解过程中任何机组都满足所有飞机的执照要求，与实际当中部分机组不能执行某些机型存在差距，未来可以加入这部分研究内容提高机组恢复模型的应用性。随着经济和信息技术的发展，机组恢复等问题的研究也是当今市场的迫切需要。
参考文献
[1] Diana C.， Jose L.， Miguel A.， Andrés L.， and Nubia Velasco， A mathematical programming approach to airline crew pairing optimization， 2012.
[2] O. Weide， D. Ryan， and M . Ehrgott. An iterative approach to robust and integrated aircraft routing and crew scheduling. Computers and Operations Research， 37（5）：833-844，2010.
[3] Zhao Xiuli， “Research on Modeling and Algorithm of Airline Irregular Recovery，” Nanjing China， Nanjing University of Aeronautics and Astronautics， 2010.
[4] J.W. Yen and J.R. Birge. A stochastic programming approach to the airline crew scheduling problem. Transportation Science， 40（1）：3-14，2006.
[5] B.C. Smith and E.L. Johnson. Robust airline fleet assignment： Imposting station purity using station decomposition. Transportation Science， 40（4）：497-516，2006.