不确定环境下机组调度问题的规划模型及算法

龙源期刊网 http://www.qikan.com.cn

不确定环境下机组调度问题的规划模型及算法

作者：张培

来源：《中国科技纵横》2015年第12期

【摘要】传统航空公司机组调度模型大多是确定的，然而实际上航班通常会受各种不确定因素影响而产生延误的影响。本文考虑随机因素，将机组排班的配对寻优建成以成本最小和旅客满意度最大为目标的多目标随机机会约束规划模型，并构造混合智能算法来寻找最优解。案例研究的结果显示，模型和算法对于实际中机组配对的寻优是可行的。 【关键词】机组配对不确定多目标机会约束规划混合遗传算法

【Abstract】For the traditional airlines ， crew scheduling models are usually deterministic，in fact the flight is usually affected by many uncertain factors and cause delays. This paper take the uncertain factors into consideration to build a multi-objective stochastic chance constrained

programming crew pairings model of minimum cost and maximum passenger satisfaction， and constructs a hybrid intelligent algorithm to find the optimal solution. the results of a case study show that the model and algorithm are feasible in practice for crew scheduling problems.

【Key words】crew pairings problems； uncertainty； multi-objective； chance constrained programming；hybrid intelligent algorithm 1 引言

由于民航业的特点和竞争的需要，航空公司的航班运行控制对运筹学的许多分支理论和方法，特别是最优化技术有着非常迫切的需求。航空公司计划和控制系统是围绕航班来运作的，运行控制部门通过使用辅助决策系统和利用各种现代优化技术建立符合实际问题的调度模型，采用有效的算法、软件来实现调度方案的快速生成。

在国内外的文献中，LOO[1]通过重新定义航班降落时间，建立一个用多目标遗传算法，（MOGA）来解决的多目标优化的模型。文献[2]则引入一个惩罚函数，模拟实际运营成本来进行不确定环境下的机组调度问题研究。张英楠等人[3]引入机会约束构建兼顾成本与航班运行安全及旅客随机需求的机型分配与机组排班模型。牟德一等人[4]提出机组延误概率这一概念，给出机组延误概率计算公式及方法，利用Matlab编程计算机组配对相关问题。Yen[5]一方面解决人员指派问题，另一方面加入惩罚函数来描述延误。文献[6]说明了确定性航班机组调度的综合论述。