2021年全国研究生数学建模竞赛华为杯F题航空公司机组优化排班问题求解全过程文档及程序
2021年全国研究生数学建模竞赛华为杯
F题 航空公司机组优化排班问题
原题再现：
一、背景介绍
众所周知，一趟民航航班必须在满足特定的条件下才能起飞，这些条件包括国家法律法规，国际公约，政府的行政条例，和公司自身的政策利益，一些国家的工会组织还会对机组人员的福利偏好有规章约束。所有这些条件都是对保证飞航安全和旅客服务质量最重要的因素之一。
广义的机组人员包括飞行员（Pilot，或Flight Deck），乘务员（Cabin Crew）和空警（Air Marshal）。所谓机组排班问题，就是构造特定时间段的机组日程安排，包括每个机组人员在何时何地及哪个航班执行何种任务。一家100架飞机的航空公司，机组人员可以达到5000-7000之多。一个高质量的机组航班任务计划，不仅能给航空公司的运营节约成本，还能合理地考虑劳逸平衡（Work-life Balance），机组偏好（Crew Preference），组员同行（Teaming），培训（Training），时近性（Recency）和休假（Vacation Leave）等等。因为这三类机组人员不能互相通用，所以机组排班问题一般都是对他们分别求解。另外，不同机型之间的飞行员一般也不能通用，所以飞行员排班问题通常也是对不同机型分别求解。
机组排班问题是运筹学应用的最早典范之一，经过过去 ~60年的发展，虽然在计算速度和应用复杂度方面还不尽满意，但已经形成了比较成熟甚至通用的解决方案，该解决方案把机组排班问题分解成两个子问题求解：以满足规范和节约成本为主要目的任务环生成，和以满足公平合理为主要目的任务环分配，它们相对应的优化问题叫Pairing Optimization（PO）和Roster Optimization（RO）。该两问题的解决，都是通过建立网络流模型（Network Flow）然后列生成法（Column Generation）求解。列生成法易于处理各种复杂的约束条件，优化模型比较简单，在计算性能上有很大的优势，对解决分配问题非常有效，虽然算法效果的好坏也取决于子问题及算法部件的局部处理方法。
但另一方面，两阶段子问题求解法也有其明显的缺陷。比如实际排班过程中需要具备人工预排班功能，一个机组人员可能会乘坐指定航班到某地但回程却由系统安排。两阶段解法不能很好地处理这样的不完整任务环问题。而且理论上，两阶段解法缩小了优化空间，所谓的最优解其实是次优解。同时，对列生成法而言，各种规章约束参数主要是在列生成过程中考虑，优化模型本身缺乏这些约束参数的显性表达，通常的参数敏感性分析手段不能采用，因而难以对业务规则的制订起到指导作用。
本题的宗旨是建立线性优化模型，明确表达飞行时间、执勤时间、休息时间等约束，把航班直接分配给机组人员。
需要指出的是，实际应用的机组排班问题考虑因素非常繁杂。本题通过抽象合并，剔除非核心的琐碎概念和约束，但保留问题的核心复杂度。同时，学术界关于机组排班问题的各种文献只能作为对业界背景知识的了解。如果参赛者坚持参照文献中的模型及算法，敬请详列步骤。
注：Sabre公司是全球第一次采用计算机算法求解大型机组排班问题并在American Airline得以使用，也是全球第一家在任务环求解方案中对远程航段（Long Haul）引入机组增强（Augmentation）和降阶（Down Ranking）功能，并在Singapore Airline得到有效使用。中国国际航空公司（Air China）至今也一直在使用着Sabre的机组排班和管理系统Aircrews。
二、问题描述
航空公司的运营管理非常复杂，很多过程需要经过长期-中期-短期等多层次的往复循环。机组排班问题假设航班规划阶段已经完成，机型分配已经结束，对机组人员数量及资格的需求已经明确，而且可用机组人员也已经确定。机组优化排班问题的描述通过以下概念的介绍展开。
时间：航空公司的运营是跨时空的。本题时间的表达由年月日时分组成，秒以下的精度不计。所有时间均按单一指定时区定义（比如北京时区），相邻两天的时间分割点是给定时区的半夜零点。
机场：航班的起飞和到达，及机组人员的出发和到达，都是以机场为节点。机场的标识一般按照国际民航组织IATA标准。比如北京首都机场PEK，上海浦东国际机场PVG。
机组人员（Crew）：本题的描述只针对飞行员，但对乘务员和乘警完全适用。现代民航飞机的驾驶通常需要两种资格的飞行员：正机长（也叫机长或正驾驶，Captain）和副机长（也叫副驾驶，First Officer）。
1. 每个机组人员都有一个固定的基地，用所在地机场表达。
2. 每个机组人员都具有一个且仅有一个主要资格，但也可以具备其它的替补资格。机组排班优先安排主要资格，但当主要资格不足时，可以安排替补资格。本题假定具备正机长资格的飞行员其主要资格是正机长，否则其主要资格是副机长。部分正机长可以替补副机长执行飞行任务。机组人员按主要资格或替补资格执行的任务都叫飞行任务。
3. 机组人员除了执行飞行任务外，还可以执行乘机（Deadhead）任务。乘机任务是指机组人员乘坐正常航班从一机场摆渡到另一机场去执行飞行任务。注：乘机人数一般会有限制。
航班（Flight）：指飞机的一次起飞和降落。本题假定每个航班都是唯一的，虽然实际情况下的航班号可能按天或星期重复。注：当航班应用于机组人员排班时也叫航段（英文Leg或Sector）。
1. 每个航班都有给定的起飞日期、时间，和到达日期、时间。
2. 每个航班都有给定的起飞和到达机场。
3. 每个航班都有给定的最低机组资格配置（Composition），用格式C<数> F<数> 描述，其中C<数>为正机长数，F<数>为副机长数。一个航班只有满足了最低机组资格配置才能起飞。注：本题假定只有一种机型一种配置，实际情况可以有所不同。
duty: 一次执勤包括一系列飞行或乘机任务以及接续的时间间隔,类似于一天的工作状态。在同一次执勤任务中,相邻的航班之间需满足以下条件:
- 上一个航班抵达机场与下一个航班离港机场相同;
- 上个航班抵达时间和下个航班离港时间之间的衔接时长必须满足最短衔接时长的要求;
- 每个航班在同一时间段内起飞,但抵达时间不受此限制,因此同一时间段内可能执行多班次任务,这些任务分别归属于不同的天数编号。接续时间为计算总工作时长的重要组成部分,而单次航班的时间仅用于计算飞行时长。
根据航班起飞时间划分天数编号,从当天第一个航班起飞到当天最后一个航班降落所消耗的时间即为该天的工作时长范围。因此,某天结束工作的飞机可能不是当天最早起飞的任务飞机。
任务环（Pairing）：任务环包含一系列的执勤与休憩时间段，并以基地为起点并最终返回至基地。每个工作轮次须满足以下条件：上一工作轮次结束后的机场与下一工作轮次开始前的机场一致；相邻两次工作轮次之间的休憩时间需满足最低要求；每个工作轮次中的首次作业均始于基地，并于最后一次作业后返回至基地位置。
排班计划（Roster）及排班周期：每个机组人员在每个排班周期内都会有一个排班计划，在这个计划中包含了多个工作环和假期安排，并且工作环之间必须满足一定的休息天数。一个典型的排班周期通常是两个星期（双周计划）或一个月（月计划）。机组人员的排班计划按照排班周期进行编排出所，在每个周期开始前几天会完成编排出所工作并通知机组人员。
在各排班周期之间设置了明确的时间界限，在这种情况下，在给定时间段内的最后一项任务环节可能会越过分隔点而转入下一时间段。为了简化模型结构，在本次比赛中假设所有机组人员的起始位置以及在结束阶段所处的最终状态均位于其各自的基地，并适当延长了整个排班时间段以减少复杂性
三、赛题
本赛题由三个子问题组成，每个子问题均基于前一个子问题并与之兼容。若概念定义或过程描述与业界存在差异，则一律以本赛题规定为准。对于本赛题未作说明的内容，则不在考虑范围内。本题假设如下：
- 组长之间可自由组合；
- 也允许在无法满足最低组长资质配置的情况下出现无法起飞的航班；
- 任何不满足最低组长资质配置的航班都不允许配置组长；
- 组长可以乘机转运，即实际组员配置可超出最低要求，在职守期间计入值班时长但不计入飞行时长。
子问题Ⅰ：基础题。旨在为航班分配机组人员（亦即为机组人员分配航班），按照编号顺序满足目标
子问题二：引入执勤概念
子问题3：安排排班表。假设每个机组人员的每小时工作环成本固定（注：不计入执勤费用，请视作出差补贴）。本子问题除了需满足子问题1与2的所有目标外,还需实现以下目标（按编号排序）
本研究涉及两种检测方案。建议参与者应首先处理方案A，并随后执行方案B。
每套输入数据由三部分构成，并非仅限于给出的格式描述。
2. 航班计划数据格式
3. 机组人员信息数据格式：
参赛者需对题目内容进行详细阐述并提供充分的支持材料
参赛者需对题目内容进行详细阐述并提供充分的支持材料
为构建完整的数学模型，在建模过程中必须明确说明所涉及的所有变量与参数的具体含义与作用范围。其中：
- 变量一般采用单一的小写字母表示；
- 参数则可选用希腊字母或以单词形式表示；
- 同时要求简洁明了；
- 下标通常仅使用单个小写字母；
- 为了便于阅读和理解，在必要时可用上撇’或上横线̅来表示辅助标记符号。
所有定义在全文中应保持一致以确保逻辑连贯性
基于所构建的数学模型进行求解研究。论文需深入分析数学模型的特性,包括其规模特征及其结构特点,同时也要关注求解过程中的难易程度等关键指标;针对上述特性,算法的设计需基于数学模型的特点进行针对性设计,并需具有逻辑性和条理性;为了确保描述的准确性和完整性,论文应详细阐述所采用算法的具体实现思路以及其实现复杂度评估方法,其中包括对运行时间范围的具体估计;为使描述更加清晰易懂,建议采用简洁明了的语言对模型与算法的整体架构进行概述
实现程序算法，并通过给定数据进行实验
根据个人专长可以选择高级语言或脚本语言等技术手段进行编程实现，并采用多种方法结合以解决实际问题。
为了保证代码质量要求，请确保所编写的程序架构应具有良好的可扩展性和可维护性；
参赛选手需在报告附录中详细说明所编写的程序及其使用的数据结构。
论文报告应包含详细的数据信息，并鼓励作者采用其他图形表示方式来描述实验结果。要求设计布局简洁明了、线迹分明、颜色鲜明，并且重点突出显示注释内容。
5. 本次比赛还要求提交与程序实现相关的计算结果，并包括以下两个电子文件：
a. 按照起飞日期及时间、出发与到达机场的顺序列出无机组配置航班的信息及其最低配置需求。该数据需从Excel表格导出并整理为CSV格式文件（命名为"UncoveredFlights.csv"）。
b. 按照机组人员、日期以及航班段顺序罗列该机组人员的航班分配情况，并需标注航班号、起飞/到达日期时间及机场信息、任务性质（机长/副机长/替补/乘机员）等详细信息（包括休假日的相关标记）。这些数据也需从Excel表格中提取并按照CSV格式整理（命名为"CrewRosters.csv"）。
整体求解过程概述(摘要)
如何合理分配机组人员以满足航班需求的问题
模型假设：
1．当机组人员有空闲时间即可随时投入工作，并保证不会无故缺勤；
2．A方案和B方案的数据中航班信息保持稳定且不可更改；
3．机组人员的编排具有高度灵活性，并可进行任意组合；
4．允许存在因为无法满足最低机组资格配置而仍能起飞的航班；
5．不具备最低机组资格配置的标准航班将无法安排任何机组人员；
6．乘机摆渡意味着实际编组可能超出最低标准要求，并且安排在摆渡任务中的机组成员飞行时间仅用于执勤记录而不计入正式飞行时间。
问题分析：
针对第一个问题
第一个问题的主要目标是在满足连续飞行任务之间最短休息时间的基础上尽可能多地满足起飞飞机组配置需求的航班数量。本文将该问题是分为两个子问题：航班任务配对与机组人员指派两个方面展开研究。其中第一个子问题是实现航班任务配对，在满足约束条件下寻找从基地出发并最终返回基地的一条航线路径，并保证航线之间的连接时间不少于MinCT分钟；第二个子问题是实现机组人员指派，在满足约束条件下将已确定的任务分配给各组机组人员执行工作流程。
针对第二个问题
第二个问题是建立在第一个问题的基础上引入执勤安排的问题模型，并将其分解为两个子问题：每日航班线路安排以及机组人员分配两个方面展开研究。本文采用了与第一个问题相同的广度优先搜索方法来确定每日可行的航班线路组合，并在此基础上优化选择最优的航线组合方案；同时在机组人员分配过程中引入贪心算法思想以保证整体执勤成本最低化并且各机组人员之间的执勤时长能够均衡分布。
针对第三个问题
第三个问题是基于前两个子系统的扩展性设计，在原有系统的基础上构建了一系列连续性较强的执勤环线，并将这些环线间相互衔接形成完整的排班计划体系。具体而言就是按照一定的逻辑关系将多个独立环线连接成一个完整的排班计划系统。
论文缩略图：
全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可
程序代码：
%% 求解机组人员的排班
num=0;
while 1
flag = 1;
seq = round(rand(101,2)*15+1);
% if(seq(1,1)==seq(1,2))
%
flag=0;
% else
% emp(seq(1,1))=datetime(A(1,14),'InputFormat','HH:mm');
% emp(seq(1,2))=datetime(A(1,14),'InputFormat','HH:mm');
Fstartstoptime =
[0,5,11,17,24,30,37,44,52,59,66,73,80,87,94,101];
daynum = 1;
for i = 1:101
if(i-1==Fstartstoptime(daynum))
for j =1:21
emp(j)=datetime("00:00",'InputFormat','HH:mm');
end
daynum=daynum+1;
end
if(seq(i,1)==seq(i,2))
flag=0;
break;
end
if(datetime(A(i,2),'InputFormat','HH:mm')>emp(seq(i,1))&&datetim
e(A(i,2),'InputFormat','HH:mm')-emp(seq(i,1))>=duration(0,40,0))
%
if(datetime(A(i,2),'InputFormat','HH:mm')>emp(seq(i,2))&&datetim
e(A(i,2),'InputFormat','HH:mm')-emp(seq(i,2))>=duration(0,40,0))
emp(seq(i,1))=datetime(A(i,2),'InputFormat','HH:mm');
emp(seq(i,2))=datetime(A(i,14),'InputFormat','HH:mm');
else
flag=0;
break;
end
%
else
flag=0;
break;
end
end
% end
if(flag==1)
break;
else
num=num+1;
end
end
%% 导出结果表
result = strings(420,10);
for i=1:105
two = strsplit(p2t5(i,16));
if(strlength(two(1))==1)
two(1)=strcat('A000',two(1));
end
if(strlength(two(1))==2)
two(1)=strcat('A00',two(1));
end
if(strlength(two(2))==1)
two(2)=strcat('A000',two(2));
end
if(strlength(two(2))==2)
two(2)=strcat('A00',two(2));
end
result(i*4-3,1) = two(1);
result(i*4-2,1) = two(2);
result(i*4-1,1) = two(1);
result(i*4,1) = two(2);
result(i*4-3,2) = "1";
result(i*4-2,2) = "1";
result(i*4-1,2) = "2";
result(i*4,2) = "2";
result(i*4-3,3) = p2t5(i,2);
result(i*4-2,3) = p2t5(i,2);
result(i*4-1,3) = p2t5(i,10);
result(i*4,3) = p2t5(i,10);
result(i*4-3,4) = p2t5(i,1);
result(i*4-2,4) = p2t5(i,1);
result(i*4-1,4) = p2t5(i,9);
result(i*4,4) = p2t5(i,9);
result(i*4-3,5) = p2t5(i,3);
result(i*4-2,5) = p2t5(i,3);
result(i*4-1,5) = p2t5(i,11);
result(i*4,5) = p2t5(i,11);
result(i*4-3,6) = p2t5(i,4);
result(i*4-2,6) = p2t5(i,4);
result(i*4-1,6) = p2t5(i,12);
result(i*4,6) = p2t5(i,12);
result(i*4-3,7) = p2t5(i,5);
result(i*4-2,7) = p2t5(i,5);
result(i*4-1,7) = p2t5(i,13);
result(i*4,7) = p2t5(i,13);
result(i*4-3,8) = p2t5(i,6);
result(i*4-2,8) = p2t5(i,6);
result(i*4-1,8) = p2t5(i,14);
result(i*4,8) = p2t5(i,14);
result(i*4-3,9) = p2t5(i,7);
result(i*4-2,9) = p2t5(i,7);
result(i*4-1,9) = p2t5(i,15);
result(i*4,9) = p2t5(i,15);
result(i*4-3,10) = "C";
result(i*4-2,10) = "F";
result(i*4-1,10) = "C";
result(i*4,10) = "F";
end
load('DataACrew.mat');
load('DataAFlight.mat');
flightnum = 206;% 航班数量
crewnum = 21;% 机组人员数量¿
stnnum = 7;% 机场数
roster_start = 0;
roster_end = 21600;
roster_s_datetime = date(2021,8,11);
roster_e_datetime = date(2021,8,26);
year_e = 2021;
month_e = 8;
day_e = 25;
for i=1:length(DataAFlight)
roster_s = 0;
date_s = strcat(DataAFlight(i,2),DataAFlight(i,3));
date_s =
datetime(DataAFlight(i,2),'InputFormat','M/dd/yyyyHH:mm');
end
crewschedule = zeros(crewnum,roster_end);
crewinflight = strings(crewnum,1);
crewinstn = string(crewnum,1);
sortrows(DataAFlight,2); %% 求问题二的机组人员排班
load('dt.mat')
current_date =
datetime("08/11/2021",'InputFormat','dd/MM/yyyy');%% 开始日期
Fstartstoptime = [0,6,14,20,27,34,41,48,56,63,70,77,84,91,98,105];
firstOfficer = 12;%% 副机长
cheapcaptain = 5;%% 价格低的正机长
richcaptain = 1;%% 价格高的副机长
arrange = strings(105,1);
%%
for i=1:15
st = Fstartstoptime(i)+1;
ed = Fstartstoptime(i);
[B,I] = sort(dt(st:ed));
I=I+st-1;
cheapnum = 5;
for j=1:length(I)
str="A";
if(cheapnum<6)
str = strcat(str,num2str(cheapcaptain));
cheapcaptain = cheapcaptain + 1;
if(cheapcaptain>10)
cheapcaptain = 5;
end
str = strcat(str," A");
cheapnum = cheapnum + 1;
else
str = strcat(str,num2str(richcaptain));
richcaptain = richcaptain + 1;
if(richcaptain==5)
richcaptain = 11;
end
if(richcaptain==12)
richcaptain = 1;
end
str = strcat(str," A");
end
str = strcat(str,num2str(firstOfficer));
firstOfficer = firstOfficer + 1;
if(firstOfficer==22)
firstOfficer = 12;
end
arrange(I(length(I)-j+1)) = str;
end
load('FlightTableB1.mat');
result = strings(size(FlightTableB1));
[I,J]=size(FlightTableB1);
for i = 1:I
for j = 1:J
if(~(FlightTableB1(i,j)==0))
result(i,j) = Sheet1(FlightTableB1(i,j), 3);
end
end
end
xlswrite ('BDate.xlsx',result);