机组排班优化建模：从数据清洗到约束求解的备赛指南

简介2021年华为杯中国研究生数学建模竞赛F题航空公司机组排班优化问题的思路与代码资料包面向已完成选题、需要快速搭建解题框架的参赛研究生团队。压缩包共16个文件、211KB主体为9个Python脚本对应第1至第3题的建模与求解另含4个CSV数据文件A/B两组机组与航班排班数据、1个Word版赛题说明、1份Markdown思路笔记和1个txt注释说明覆盖数据读取、整数规划建模、启发式求解与结果输出全流程。赛题综合难度较大代码注释较详细md笔记按问题拆分思路docx可对照原题要求适合初次参加数模竞赛、希望借鉴成熟代码风格的同学也可作为后续算法优化的起点。资料按代码、数据、文档分目录存放路径清晰便于逐步复现各问结果。目前已有135人学习资源轻量但结构完整能节省整理公共数据与赛题的时间让团队更专注于算法设计与论文撰写。1. F题到底在考什么反直觉的拿分顺序研究生数学建模竞赛F题“航空公司机组优化排班”看起来很像一个调度题但真正拉开差距的并不是算法复杂度。很多参赛队一上来就翻最优化教材想用高端求解器直接出答案结果第三天发现连“每个航班都有人飞”这个基本约束都保证不了。这道题反直觉的拿分顺序是数据清洗 → 约束建模 → 算法落地。换句话说先把机组表、航班表里的字段吃透把“谁能飞哪班、几点能接哪班”的匹配逻辑写成约束后续优化才有意义。这个顺序也解释了为什么每份高分文档的第一章都是数据口径说明而不是算法综述。备赛研究生可以按这条主线复现赛前突击的人则能快速抓住三问的得分重心。2. 第一问分值怎么抓机组与航班两张表的数据口径F题给的是某航司的真实运行数据形态常见的文件包括航班表与机组表两类CSV比如A-Flight.csv、A-Crew.csv、B-Flight.csv、B-Crew.csv。第一问看起来只是让做一个“简化排班”实际上检验的是你把数据结构转化为模型参数的能力。航班表里藏着航班号、起降城市、起降时刻、机型等字段机组表里藏着工号、基地城市、可飞资质、岗位等字段。这两张表一旦没有对齐后面所有约束都会建立在错误基础上。很多队第一问就漏了“基地”字段直到第三问要做回场约束才发现某组机组根本回不了基地这就是典型的数据建模脱节。2.1 两张表要抠出的字段与合并口径拿到航班表和机组表后第一件事不是建模而是做字段映射。航班表的核心是航班标识、出发时刻、到达时刻、起降城市机组表的核心是工号、基地、资质与在岗状态。读表后建议强制做三件事统计航班数量与城市分布确认是否存在多个基地、是否需要按执飞城市拆分数据统计机组数量和资质类型确认每个基地的可用人数这是第二问“基地覆盖率”的原始依据把航班按起飞时间排序形成一条完整的时间轴。排序这一步看起来平凡却是判断“两个航班能否被同一机组连续执行”的基础。这里还有一个容易被忽略的合并口径原始CSV的列名可能是中文也可能存在编码不兼容问题。读入后先另存一份UTF-8版本检查表头再写字段映射能省下大量返工时间。某参赛队曾在航班表里看到两个时间列直接选了最后一列做衔接计算结果那列是计划时间而不是实际起降时间整个第一问全部返工。从那以后每次读表先打印每列的最小值和最大值确认时间列落在合理区间再往下走。这段流程虽然是数据预处理但在评阅人眼中第一问的分值主要就看字段是否对齐、口径是否统一。2.2 时间处理是第一个分水岭跨午夜航班的分钟化机组排班数据里最容易翻车的字段是时间。航班里会出现23:55起飞、次日01:10到达的跨午夜情况如果直接用字符串比较程序会认为到达早于起飞导致“上一班降落后赶不上下一班”的判断全部失效。正解是所有时间统一转成从0点起算的分钟数例如23:50转换为1430次日01:10转换为70如果到达时刻小于起飞时刻则给到达加1440分钟。这套口径一旦统一后续的衔接条件、休息时间、任务时长全部用数值计算不再碰字符串。第二问的休息期约束也依赖同一个分钟口径。机组连续执行两个航班时前一班到达时刻加最低过站时间必须小于等于后一班起飞时刻一天内累计任务时长超过阈值时还要插入休息段。这类计算本身不难但时间列没做分钟化后面的约束就会连锁出错。把“时间统一分钟化”写进模型假设评阅人会认为你确实考虑了真实运行细节。这一步不需要任何算法基础属于纯数据功夫却是整道题能否继续推演的命门。2.3 Matlab数据预览代码先搭好字段骨架再做模型下面这段Matlab代码是读取航班表并做分钟化处理的最简骨架实际列名以你拿到的赛题数据为准这里用占位名演示整个流程。% 读入航班表并做分钟化处理 flights readtable(A-Flight.csv); % 实际列名按赛题表头修改 % 统一口径从0点起算的分钟数 time2min (s) str2double(extractBefore(s, :)) * 60 ... str2double(extractAfter(s, :)); flights.depMin cellfun(time2min, flights.DepTime, UniformOutput, true); flights.arrMin cellfun(time2min, flights.ArrTime, UniformOutput, true); % 处理跨午夜到达时刻小于起飞时刻则加一天 overNight flights.arrMin flights.depMin; flights.arrMin(overNight) flights.arrMin(overNight) 1440; % 展示统计概览 summary(flights);这里的两个参数需要说明。extractBefore和extractAfter按冒号切分时间字符串得到小时和分钟加1440的操作只在到达时刻小于起飞时刻时触发也就是只处理跨午夜航班。summary会输出每列的最小值、最大值与缺失情况能快速发现时间列是否全部落在0到1440区间。如果发现某行的到达时刻大于2000说明跨午夜处理被重复执行了要检查是否也错误地对起飞时刻加了1440这是典型的“只处理到达端、没检查起飞端”的误用。备赛时把这条写在代码注释里能减少调试时间。机组表同样需要读入并做唯一值检查工号是否唯一、基地城市有多少个、资质字段是否含缺失。建议把两张表整理成三个后续建模集合航班集合、机组集合、航班与机组的资质匹配关系。这一步不产出任何模型但把后续所有约束的判断条件准备齐全。第一问的分值大多落在“数据字段是否对齐”和“时间口径是否统一”上模型复杂度反而是次要的。3. 第二问模型核心机组排班的约束条件与目标函数第一问把数据理顺之后第二问才是真正的建模题。机组排班的本质是在满足“每个航班都有合适机组执行”的前提下用尽量少的机组完成全部航班同时兼顾基地、资质、休息等限制。评阅时看重的不是决策变量定义得有多新颖而是约束有没有列全、每条约束能否对应一句可解释的话。常见翻车是只写了“航班覆盖约束”就开始求解结果解出来一堆同一机组同一天飞四五个不相邻城市的航班明显不符合运行常识。3.1 第一问的简化模型先保证每个航班有人飞第二问之前通常有一个简化版本作为第一问。这一问把机组视为同质资源只要求每个航班至少被一个机组覆盖、同一时刻一个机组只能执行一个航班。建模先定义决策变量x(i,j)表示机组j是否执行航班i再写两个约束航班覆盖约束以及同一机组不能同时执行两个航班的时间冲突约束。目标函数取最小化使用的机组总数或总任务时长具体看题面描述。这一问的易错点是时间冲突约束的写法。很多队把同机组两个航班限制成“起飞时间不能相同”但真正该写的是前一班到达时刻加过站时间小于后一班起飞时刻否则会把刚落地就接着起飞的排班判为合法。这类错误在第一问出现意味着一开始的时间口径就没统一。建议把建模流程固定成三段式先写决策变量及取值范围再按覆盖约束、冲突约束逐条列出每条后面补一行中文注释说明实际含义最后写目标函数并指出对应题面哪一句要求。这套写法在第二问原样复用只是约束列表不断加长。3.2 第二问的三类硬约束与一个软目标第二问把机组属性放开不同基地、不同资质、不同岗位、可能的休息期要求都会出现。约束随之分成三类。第一类是覆盖与资质约束每个航班必须被指定数量的机组覆盖且每个机组的资质必须匹配航班要求。第二类是时间衔接约束同一机组连续执行两个航班时前班到达城市必须等于后班出发城市且到达加过站时间小于后班起飞如果任务累计时长超过阈值中间必须插入休息段。第三类是基地约束机组最终要回到基地城市通常写成“当天最后一个航班的到达城市等于基地”或“次日首个航班的出发城市等于基地”。软目标要看题面怎么描述。常见的目标是最小化总任务时长也有最小化使用机组数、最小化在外过夜次数的版本。建模时先写清楚硬约束再写目标函数。不要用罚函数把硬约束混进目标里一起优化罚系数一旦设置不当解出来的方案会悄悄违反某条硬约束评阅逐条核对时直接失分。硬约束与软目标分开写代码里也分开检查这是被反复验证过的稳妥做法。下面这张表可以当自查清单用约束类型核心写法常见漏写覆盖与资质每航班覆盖人数 要求值资质集合取交集只写覆盖漏资质匹配时间衔接前班到达 过站 后班起飞漏过站时间或只用日期不用分钟基地约束末班到达城市 基地或隔日首班出发城市 基地把约束写成“当天必须回基地”3.3 答题模板评阅人最想看到的建模表述这里给出一套可以直接套用的表述模板。模型部分按“集合—参数—变量—约束—目标”组织。集合写航班集合F、机组集合C、资质集合Q参数写每个航班的最早起飞时刻、最晚到达时刻、所需资质以及每个机组的基地与资质变量写x(i,j)和辅助变量y(j)表示机组j是否被使用约束按上一节的三大类编号目标函数放最后。每条约束都配一行白话解释例如“约束(3)表示同一机组的相邻两航班必须满足最小过站时间”。评阅人在几分钟内评判一份文档最在意的是约束有没有漏其次是目标函数与题面要求对不对得上最后才看求解结果。所以不要把半天时间耗在跑算法上先花两小时把模型写全。往年出现过用遗传算法跑出漂亮目标值的队伍模型里却没有资质约束解中大量排班资质不匹配这类答卷通常只能拿到部分分。资源里的第二问代码带详细注释正好可以对照这套模板逐行核对确认每一条约束在代码里都有对应实现。4. 第三问算法实战从衔接矩阵到迭代搜索的实现细节第三问通常是第二问模型的求解题难度从“写对约束”升级到“跑出可行解”。很多队在这一问盲目换成复杂元启发式但真正的得分关键是解是否可行、目标函数是否有可解释的改进链。最稳妥的路线是先做一组贪心可行排班再做邻域搜索局部改进。代码框架建议复用第二问已验证的约束函数把改动集中在求解逻辑上。这个问答环节里面试官最想听到的并不是你用了哪种算法而是你如何保证解在每一步都满足全部硬约束。4.1 衔接矩阵把“能否连续执行”变成0/1判断第三问求解的第一步不是写优化器而是计算航班衔接矩阵。矩阵元素link(i,j)表示航班i之后能否由同一机组执行航班j判断条件是三条起降城市匹配、过站时间满足、资质与机组能力不冲突。前两条只依赖航班数据第三条依赖机组数据因此分开计算。航班数量在几十到几百的量级时双重循环完全可接受不需要任何并行化技巧。构建衔接矩阵后问题被拆成两个子问题选择一组航班序列每条序列由同一个机组执行再把这些序列分配给机组满足基地与资质约束。拆解之后贪心算法的思路很自然按起飞时间排序每次找一个最早出发且未被覆盖的航班把它接到当前机组序列的末尾如果当前没有可接的航班就新开一个机组序列。这样得到的初始解虽然不一定最优但一定可行第三问的后续轮次只需要在这个可行解上做改进。4.2 贪心加交换搜索的代码骨架与参数说明下面这段Matlab代码实现“按时间排序贪心构造 两航班交换的邻域搜索”可作为第三问的起点。核心数据结构是assignment数组记录每个航班由哪个机组执行。% 第三问求解骨架贪心构造 交换邻域搜索 nF height(flights); nC height(crews); assign zeros(nF, 1); % 每个航班分配的机组编号 [~, order] sort(flights.depMin); for i 1:nF f order(i); if assign(f) 0, continue; end % 该航班已被覆盖 for c 1:nC if feasible(crews(c, :), f, assign, flights) assign(f) c; % 满足全部硬约束则分配 break; end end end % 交换搜索任取两个不同机组的航班交换后仍可行且目标更优则接受 maxIter 200; for iter 1:maxIter i randi(nF); j randi(nF); if assign(i) assign(j), continue; end if swapFeasible(i, j, assign, flights, crews) oldCost currentCost(assign); % 交换两个航班对应的机组编号 tempCi assign(i); assign(i) assign(j); assign(j) tempCi; newCost currentCost(assign); if newCost oldCost % 目标值变大则回退交换 assign(i) assign(j); assign(j) tempCi; end end end两个核心函数需要说明。feasible入参是机组信息、当前航班号、当前归属表和航班表内部调用第二问写好的约束函数只有约束全部满足才返回真这样求解器不需要知道约束细节后续改模型时只动第二问的代码。swapFeasible检查交换两个航班后各自机组序列的衔接是否仍然合法。交换回退逻辑保证了目标函数只降不升避免在可行域里来回震荡。迭代轮数maxIter是核心参数。问题规模小的时候200轮足够航班超过300个时建议调到1000以上每轮打印当前目标值。如果连续多轮无下降说明邻域已经搜尽可以提前停止。这里有个常见误用把交换条件写成“只要满足约束就交换”结果目标函数来回震荡输出的解不比贪心初始解好多少。正确写法是只接受目标值下降的交换想进一步改进可考虑模拟退火但那需要额外调温度参数备赛时间紧张时不必强求。代码里保留了“目标变差则回退”的逻辑正是为了把爬山策略写死在框架内。4.3 第三问代码注释里的隐藏提示拿到这份资源后会发现一个值得注意的细节第3题代码自身注释很少而第2题代码带详细注释实际上第3题的实现大量复用了第2题写好的数据结构和约束函数。备赛时正确的打开方式是先读第2题代码确认约束函数的输入输出格式再看第3题代码把第二问已经封装好的函数逐一对应回去。不要从第3题开始看否则遇到未注释的函数就像看黑匣子既不知道参数含义也不知道返回值结构更谈不上改成自己的模型。这个设计思路本身就是参赛策略第二问是建模核心第三问是求解验证把注释集中在模型层求解层保持简洁。你在文档里也可以沿用这个结构先完整呈现模型再描述求解器如何调用模型约束函数评阅人一眼就能看出代码与模型的对应关系。很多队在第三问花大把时间重写代码最后却没时间整理文档反而丢掉了最容易拿分的结果陈述部分。5. 易错点复盘四个集中翻车的建模细节这一章复盘的是备赛与正式比赛里反复出现的失分操作按“错在哪、为什么错、怎么答对”展开。建议把下面几条检查步骤直接背下来比赛时逐条对照题面执行。这四类问题几乎在每个排班题都可能出现属于通用性很强的坑。5.1 四个高频翻车现场与错误根源第一个翻车点是跨午夜时间只处理航班、不处理机组任务时长。错在给到达时刻加了1440后直接计算任务时长某机组执飞的跨度明明只有3小时软件却算出27小时。根因是时间口径没有统一到同一个基准。怎么答对先定义所有时刻基于0点起算的分钟数机组任务时长统一用“到达分钟减起飞分钟”跨午夜航班在分钟化阶段已经加过1440后续任何时长计算都不要重复加。把这个规则写进模型假设整个求解过程就再也不会出现负时长或超长任务的假象。第二个翻车点是资质约束只存在于代码某个函数模型文档里只写了覆盖约束和时间约束。错在文档与代码脱节评阅只看文档而代码里的资质判断再严密也无法给模型分。根因是认为“代码实现了就算数”。怎么答对把资质约束作为显式约束写入模型并标注“本约束在代码中由checkQualification函数实现”做到文档与代码一一对应。这道题三个问都涉及资质匹配漏一次就会在连续两问里重复失分。第三个翻车点是基地约束写成“机组当天必须回基地”结果大部分航班序列都不真正回基地可行解直接为空。为什么错真实排班里机组通常不要求当天回基地而是要求一个连续任务段结束后回基地或在外过夜不超过限定次数。怎么答对反复读题面确认“回基地”到底是以“当日”为单位还是以“整个任务段”为单位不同届题目的口径确实不同不要拿前一年的理解直接套用。第四个翻车点是目标函数方向写反。错在把最小化总任务时长写成最大化还因为复制了模板没检查符号跑出来的“最优解”其实是让机组飞得最久的解。为什么错模板复用时漏改目标方向。怎么答对交卷前用五个航班做手工验算算出期望的目标值再和代码输出对比。这道工序五分钟就能完成却能拦住最基础也最致命的方向错误。5.2 赛前对着题面逐条勾约束的自查清单怎么答对这类失分不能等最后检查时才想起而是在建模阶段就建立约束自查清单。第一步把题面里每个“必须”“不得”“应在”圈出来逐条翻译成约束第二步把每个约束对应到模型中的一行翻译后没有对应行的直接标红第三步用三到五个手工小例子验证约束是否正确表达优先覆盖跨午夜航班与过站时间两个边界场景。这套流程每天比赛结束前花二十分钟做一遍能拦截大部分隐藏错误。清单建议放在模型文档开头用“约束编号—题面原文—模型表达式—代码函数”四列表格呈现。这个小表篇幅不大却能直观展示建模严谨度。往届参赛方案里文档结构清晰的队伍最终成绩往往比只深挖算法的队伍更高原因就是评阅能在更短时间内确认模型完整性。这道题的收益完全分布在细节里多花在自查清单上的每一分钟都可能换来一个奖项档次的提升。6. 从建模到交卷三个被低估的答题习惯最后聊聊最容易被忽视的答题节奏这部分不产生公式但直接影响结果稳定性。第一个习惯是时间分配第一天下午前完成数据整理与字段对齐第二天中午前完成模型与第一问第二天下午到第三天中午推进第二问和第三问最后留出至少半天整理文档与验算。机器求解时间不要挤占人工检查时间很多队伍把大量时间花在调参上最后交出一份没有验算的结果这是最不划算的时间用法。第二个习惯是结果验核。每次修改约束后跑一遍小样本验证记录目标值比较版本优劣不要凭感觉而是用同一份数据跑出的数字。打印一行运行摘要包含迭代次数、航班覆盖数、未覆盖数、总任务时长方便快速回看每次改动的影响。第三个习惯是在文档里保留一条手工验算示例抽出一个机组一天的三段航班写出时间轴对照模型表达式逐项打勾。这一条看起来简单却能向评阅证明所有约束不是摆设而是真实可执行的逻辑。我认识一支队伍第三问的启发式算法跑得比谁都漂亮交卷当天才发现模型里漏了过站时间约束所有方案都建立在两分钟换乘这种不现实前提上最终结果被判定无效。从那以后我每次提交前都强制走一遍小样本手工验算流程很枯燥但总能拦住大错。把这份资源里的第二问注释代码当作检索引擎第三问当作验证引擎按这个顺序练习奖项会比你预想的更近。希望帮到你。本文还有配套的精品资源点击获取