简介：这是一份基于Python调用Gurobi实现列生成算法、求解航班人员调度分配问题的完整代码包，适合运筹优化初学者、航空调度研究人员以及希望掌握Gurobi高级建模与分解算法的开发者。资源共567个文件，以559个lp格式模型文件为主体，配合3个csv输入数据表、2个Python求解脚本，并附英文说明文档与结构图；lp文件对应主问题或子问题的迭代快照，csv文件涵盖航班时刻、执勤期与酒店成本等输入数据，压缩包仅5.03MB。代码均带详细注释且经过反复调试，可直接运行，读者既能沿完整模型梳理列生成算法的定价机制、主问题与子问题交替求解逻辑，也能结合航班排班场景掌握人员分配建模要点；数量众多的lp快照还可用于复盘各轮迭代中列池与约束的变化。已有6118人学习下载，是一份兼具理论完整性与工程实用性的Gurobi列生成学习资料。
1. 航班人员调度为什么绕不开列生成算法
做航空排班系统的工程师应该都有过这种体验：航线一多、人员一多，直接给 Gurobi 扔一个整数规划模型，求解器转上半小时，最后告诉你内存不够或者 MIP gap 卡在 20% 下不去。航班人员调度分配问题不是普通的指派问题，它的变量数量不是几百几千，而是指数级的候选排班方案。每个乘务员连续值飞几个航班、中间怎么衔接、什么时候回基地，组合起来天文数字。而列生成算法（column generation algorithm）之所以成为这类问题的主流方案，是因为它不提前枚举所有排班，而是让 LP 松弛的价格信号告诉你去哪里找有潜力的新排班，边找边加，直到没有更好的候选为止。这套“先解一个小子集，再按需补列”的思路，配合 Python 里调用 Gurobi 求解器，正好把指数爆炸压成可收敛的迭代过程。这篇文章要讲的，就是这条路径的完整落地：模型怎么拆、RMP 怎么写、定价子问题怎么解、收敛判据怎么设、工程上有哪些坑。
2. 建模先行：航班调度分配问题的数学形式与列生成拆解
2.1 航班人员调度分配的问题定义与三类约束
航班人员调度分配，通俗说就是一组乘务员或飞行员，要值飞一组已知的航班任务，每个航班必须有足够的人员覆盖，同时每个人得到的排班方案必须合法可执行。日常运营里，这个问题通常拆成两个层级：上层叫 crew pairing，只管把航班拼接成一条条“任务串”（pairing），不关心具体是哪个员工；下层叫 crew rostering，把 pairing 分配给具体员工并考虑个人偏好、休假、资质。
本文聚焦的是上层 pairing 问题中最核心的调度分配环节，它的输入很简单：一个航班列表，每个航班有航班号、出发机场、到达机场、起飞时刻、到达时刻、机型/资质要求。输出是一组排班方案，每条排班要满足三类约束。第一类是覆盖约束：每个航班必须被至少一条排班覆盖，这是硬性需求，漏掉任何一个航班整个方案不可用。第二类是合法性约束：同一条排班里的航班在时间顺序上要能衔接——前一航班到达机场要和后一航班出发机场相同，而且要留有最小中转时间；连续工作不能超过规定的最大执勤时长，比如单日执勤上限 12 小时或 14 小时。第三类是结构约束：排班通常要求从某个基地出发，最终回到这个基地，形成一个闭环，否则乘务员无法回驻地休息。
目标函数常见的是最小化总成本，这里的成本不只是工资。每个航班的成本本身固定，调度分配环节真正优化的是“不执勤成本”，比如两人同飞一段产生的住宿、差旅、补贴，以及排班数越少越好的折算惩罚。换句话说，你希望用尽量少的排班、尽量紧凑的衔接覆盖全部航班，把人员闲置成本压到最低。
2.2 为什么直接建模会指数爆炸
直觉上最自然的建模方式，是用二元变量表示“某人是否执行某条排班”，然后写覆盖约束和资源约束。但问题的难点恰恰在“排班”这个东西不是现成的。一个乘务员从早上 6 点基地出发，可以飞 A 到 B，也可以飞 C 到 D，然后接哪一班，中间哪个衔接合法，组合起来是排列问题。
假设一天有 20 个航班，平均每个航班前后各有 3 个可衔接的后续航班，那么一条排班的可能序列数量大约是 20×3×3×...，在 8 小时的执勤窗口内，可能的路径数就已经是百万量级。如果直接枚举所有合法排班作为列，再交给 Gurobi 去选，光是把所有列生成出来的时间就不现实，更不用说每个列还要预计算成本、检查资质和时长约束。这是我第一次做排班系统时的血泪教训：我按乘务员工号建变量，把航班长串约束全写进模型，20 个航班的小算例能跑，50 个航班直接内存爆炸，Gurobi 的 preprocess 就把模型翻了好几倍。
这个现象的根因在于：直接建模的变量维度是“人员 × 航班组合”，本质上是把路径的枚举问题藏进了约束里。而列生成换了一个视角，把变量定义成一条完整的排班方案。本质上，这不改变问题本身的计算复杂度，但它让每一步只处理一小部分显式变量，让 LP 松弛在合理时间内可解，这才是它能落地的核心原因。
2.3 列生成的核心思想：主问题拆出定价子问题
列生成用于航班人员调度时，通常把问题写成集合覆盖或集合分割的形式。设航班集合为 F，每一条候选排班 j 用一个向量 a_j 表示，a_{ij}=1 表示该排班覆盖航班 i。变量 y_j 表示是否选择这条排班。那么数学模型可以写成：
min Σ c_j y_j s.t. Σ a_{ij} y_j ≥ 1, 对每个航班 i y_j ∈ {0, 1}
如果直接枚举所有 j，模型本身很小，但候选 j 太多。列生成的做法是：先给一个极小的列集合（初始排班），求解这个“受限主问题”的 LP 松弛，得到每个航班覆盖约束的对偶价格 π_i。然后问一个关键问题：在当前对偶价格驱动下，是否存在一条新的合法排班 j，使得它的“修正成本”减少，也就是检验数 reduced cost 为负。这个寻找新列的问题被单独拆出来，就是定价子问题。
对偶价格 π_i 的经济学含义很直观：如果航班 i 的对偶价格越高，说明在当前排班方案里这个航班越“稀缺”，那么新生成的排班越应该优先覆盖它。子问题在一个航班衔接网络上找一条“成本= 排班自身成本 - 覆盖航班的对偶价格之和”的路径，如果这条路径的总修正成本为负，就说明把这条排班加进 L P 能改善目标值。反复迭代，直到没有负检验数的列出现，当前 LP 就是原问题 LP 松弛的最优解。
这套拆法对航班人员调度特别合适，因为子问题天然是一个带时间窗、带资源约束的最短路问题，航班网络本身规模不大，但对偶价格的引导让搜索只聚焦在“有潜力改善解”的方向上，省掉了全量枚举。
3. 受限主问题的 Gurobi 实现：覆盖约束与列变量怎么建模
3.1 受限主问题的数学形式与列的表达方式
受限主问题（Restricted Master Problem，RMP）指的是只用当前已有排班子集做 LP 松弛求解。代码层面，怎么表达“一条排班”很关键。常见做法是把一条排班存成一个列表，列表元素是这条排班按时间顺序覆盖的航班 ID。RMP 的每一列就是一个这样的列表，目标函数系数是这条排班的成本，覆盖矩阵的每一行对应一个航班。因为航班数量几百个、初始列几十条，矩阵非常稀疏，Gurobi 在建模时不需要显式构建二维矩阵，直接用 addVar 加列、然后用覆盖约束逐个点系数即可。
建模时还要考虑覆盖约束用 ≥ 还是 =。集合覆盖（≥1）允许一个航班被多条排班重复覆盖，这在 LP 松弛阶段能给更松的界，而且实际运营里重复覆盖可以理解为备份人员，后期整数化时再消冗余；集合分割（=1）更强，要求每个航班恰好覆盖一次，但会让 LP 更紧，整数解质量更高但求解更慢。我的习惯是先跑集合覆盖版本做定价，最后一轮整数化时再切成恰好覆盖约束，这样兼顾定价效率和最终解的可用性。
RMP 的目标项还要额外加一个“排班数惩罚系数”，常见做法是给每条排班成本里加入一个固定值 ρ，例如 100 元。因为纯航班成本下，LP 松弛容易把一条排班拆成碎片、每条只覆盖一个航班，对偶值会零散分布，加入排班数惩罚能让子问题倾向于生成更长的链，收敛更快。这个 ρ 不是模型参数，是工程调参出来的，我一般先设成单条排班平均变动成本的 30%，再根据列生成迭代次数调整。
3.2 Gurobi 建模代码：从零构造 RMP
下面是一段可运行的最小 RMP 构建代码。输入是航班列表、初始排班列集合，输出是建好的 Gurobi 模型、列变量索引。
import gurobipy as gp from gurobipy import GRB def build_rmp(flight_ids, columns, col_costs, rho=100.0): """ 构建受限主问题模型 :param flight_ids: 全部航班ID列表，例如 ['F001', 'F002', ...] :param columns: 初始排班列表，每个元素是覆盖的航班ID列表 :param col_costs: 每条排班的航班总成本列表 :param rho: 每条排班的固定成本惩罚 :return: 模型、列变量字典 """ m = gp.Model("RMP") # 关闭 Gurobi 的默认输出，迭代阶段不需要刷屏 m.setParam("OutputFlag", 0) # 决策变量：每条排班 0-1，但在 LP 松弛阶段用连续变量 col_vars = {} for idx, col in enumerate(columns): v = m.addVar( lb=0.0, ub=1.0, vtype=GRB.CONTINUOUS, # 定价阶段先松弛成 LP name=f"col_{idx}" ) col_vars[idx] = v # 覆盖约束：每个航班至少被覆盖一次 cover = {} for f in flight_ids: col_idx_with_f = [j for j, col in enumerate(columns) if f in col] if not col_idx_with_f: # 初始列集合必须能覆盖所有航班，否则模型不可行 raise ValueError(f"航班 {f} 没有任何初始列覆盖") c = m.addConstr( gp.quicksum(col_vars[j] for j in col_idx_with_f) >= 1, name=f"cover_{f}" ) cover[f] = c # 目标：排班航班成本 + 固定成本惩罚 m.setObjective( gp.quicksum((col_costs[j] + rho) * col_vars[j] for j in range(len(columns))), GRB.MINIMIZE ) m.update() return m, col_vars这段代码的核心逻辑分三层：变量层把每条排班定义成连续变量，约束层把每个航班的覆盖关系用 quicksum 聚合出来，目标层把航班成本和排班惩罚叠加。不是把覆盖矩阵写成二维数组，而是直接在每个航班的约束里检索哪些列包含它，这样航班多、列多时内存友好。
参数说明里最值得留意的是 vtype=GRB.CONTINUOUS。很多人第一次写 RMP 会直接设成 BINARY，这是最常见的错误。列生成迭代过程中要求解的是 LP 松弛，只有连续变量才能提供对偶价格；整数约束必须留到最后一轮，否则子问题找不到有意义的列。lb=0.0、ub=1.0 表示每条排班最多选择一次，这是集合分割问题的标准界，也更符合实际运营语义。
rho 参数的作用前面说过，它是排班链长度的调节器。可以做一个简单实验：rho=0 时，列生成会倾向于生成大量短排班；rho 调大后，生成的长链多，RMP 的列数收敛更快，但整数化后冗余覆盖也可能变多。rho 不需要进模型的最优解，它只是启发式引导。
3.3 从 RMP 拿到对偶价格：取值的三个细节
RMP 求解完成后，取对偶价格用到是 Gurobi 的 Pi 属性。对覆盖约束 cover_{f} 来说，m.getConstrByName(f"cover_{f}").Pi 就是该航班的对偶价格 π_f。取值时有三个细节值得注意。
第一，对偶价格只有在 RMP 最优时才有意义。求解状态不是 GRB.OPTIMAL 时不要继续往下走，否则定价子问题得到的信号是错的。第二，≥ 约束的对偶价格在 Gurobi 里是非负的，值越大代表航班越约束紧张；理论上它不会超过该航班覆盖排班的最大边际成本，但实际迭代中早期可能很不稳定，幅度跳动到几千上万也正常，这时子问题会疯狂生成列。第三，要考虑把对偶价格“平滑”一下再传给子问题。常见的稳定化手段是限幅：令 π_f = min(π_f, π_max)，或者做加权平均 π_f_new = απ_f_new + (1-α)π_f_old。Gurobi 本身有一种叫 dual simplex 的求解方法，在 RMP 中换基时对偶值跳跃很大，很多文献里讲的“对偶震荡”就是这个阶段出来的。对偶稳定化不是数学上必须的步骤，但工程上几乎总会遇到，越早加入越好。
4. 定价子问题：用对偶价格驱动候选排班生成
4.1 检验数计算与航班网络图的构造
定价子问题的目标是找一条新的合法排班，使得它加入 RMP 后能改善 LP 目标值。这条新排班的检验数公式是：
reduced cost = (排班成本 + rho) - Σ π_f（该排班覆盖的每个航班 f 的对偶价格）
如果 reduced cost 为负，说明这条列有进入基的潜力。把问题转到图上：节点是航班，每条排班路径由航班节点按合法衔接顺序组成。路径成本 = 路径上所有航班的“调整后成本”之和，其中节点成本设为原航班成本 + rho/len 的分摊（或者更简单，把 rho 加在路径总成本上，边成本设为 0），再减去对偶价格。
图里每个节点（航班）的成本为 c_f - π_f，其中 c_f 是航班自身变动成本，比如机组过夜住宿补贴等。边的成本设为 0，但只有合法衔接才有边：前置航班到达机场等于后置航班出发机场，且到达时刻 + 最小中转时间 ≤ 后置航班出发时刻。此外还要带上资源约束，比如总执勤时间不超过上限。需求是找一条从基地节点出发到基地节点结束的最小成本路径，路径总成本为负就产生新列。
这里有个新手常踩的坑：子问题不能直接用 Dijkstra 求最短路，因为节点成本可能为负（对偶价格可能大于航班成本）。我的做法是直接用 Gurobi 建一个小型整数规划来解子问题，航班量在几百级别时，这个 IP 规模很小，求解速度是毫秒级；等业务量上去再考虑换标号算法做带资源约束的最短路。
4.2 Python 代码：用 Gurobi 解定价子问题
下面的函数接收对偶价格、航班衔接关系、执勤时间上限，返回一条最小修正成本的排班路径。
import gurobipy as gp from gurobipy import GRB def solve_pricing(flight_nodes, arcs, dual_prices, flight_costs, max_duty_minutes=720, base="BASE"): """ 求解定价子问题：找一条从基地出发回到基地的负检验数排班路径 :param flight_nodes: 航班节点属性列表，每个元素是 dict，含 id、dep_airport、arr_airport、dep_time_min、arr_time_min、duty_minutes :param arcs: 合法衔接边列表，每对 (i, j) 表示航班 i 后可以接航班 j :param dual_prices: 航班对偶价格 dict，键为航班id :param flight_costs: 航班变动成本 dict :param max_duty_minutes: 最大执勤分钟数 :return: 新排班航班ID列表，或 None（无负检验数列） """ n = len(flight_nodes) m = gp.Model("Pricing") m.setParam("OutputFlag", 0) # 路径选择变量：x[i] = 1 表示航班 i 被选入当前排班 x = m.addVars(n, vtype=GRB.BINARY, name="x") # 衔接指示：y[i,j] = 1 表示排班中航班 i 之后接着飞 j y = m.addVars(arcs, vtype=GRB.BINARY, name="y") # 路径流守恒约束：起点和终点在基地，中间节点流守恒 # 每个被选中的航班要么被"进入"，要么是起点 # 用通用建模：所有航班节点的流入量 - 流出量 = -x[i]（起点）或 0（中间） # 这里简化为每个航班至多一个前序、至多一个后继，且选中的航班必须被连接 for i in range(n): in_arcs = [y[idx] for idx in arcs if idx[1] == i] out_arcs = [y[idx] for idx in arcs if idx[0] == i] m.addConstr(gp.quicksum(in_arcs) <= 1, name=f"in_{i}") m.addConstr(gp.quicksum(out_arcs) <= 1, name=f"out_{i}") # 选中的航班必须有至少一个前序或后继（不能是孤立点） # 起点航班允许只有后继没有前序；终点航班允许只有前序没有后继 for i in range(n): in_arcs = [y[idx] for idx in arcs if idx[1] == i] out_arcs = [y[idx] for idx in arcs if idx[0] == i] m.addConstr( gp.quicksum(in_arcs) + gp.quicksum(out_arcs) >= 2 * x[i], name=f"connect_{i}" ) # x[i] = 1 时必须有路径流量；x[i] = 0 时禁止流量 m.addConstr(gp.quicksum(in_arcs) + gp.quicksum(out_arcs) <= 2 * x[i], name=f"no_flow_{i}") # 执勤时间约束：选中航班的执勤分钟总和不能超过上限 m.addConstr( gp.quicksum(flight_nodes[i]["duty_minutes"] * x[i] for i in range(n)) <= max_duty_minutes, name="duty_limit" ) # 目标：最小化修正成本，即航班成本 - 对偶价格 + 排班惩罚按比例折算 # 因为 rho 是固定惩罚，在最短路里折算成每条排班成本常量 # 这里直接用每个航班的调整成本求和，rho 在外面统一加 m.setObjective( gp.quicksum((flight_costs[fid] - dual_prices[fid]) * x[i] for i, fid in enumerate([fn["id"] for fn in flight_nodes])), GRB.MINIMIZE ) m.optimize() if m.status != GRB.OPTIMAL: return None # 从解中提取航班路径 selected = [i for i in range(n) if x[i].X > 0.5] if not selected: return None # 按衔接边排序路径 path = [] arc_used = [(i, j) for idx in arcs if y[idx].X > 0.5] # 找到起点：没有前序且被选中的航班 predecessors = {j: i for i, j in arc_used} start = [i for i in selected if i not in predecessors.values()][0] path.append(start) while True: nxt = [j for i, j in arc_used if i == path[-1]] if not nxt: break path.append(nxt[0]) # 目标值 = 修正成本 + rho，在这里判断是否加入 reduced_cost = m.ObjVal + rho if reduced_cost >= -1e-6: return None return [flight_nodes[i]["id"] for i in path]这段定价代码的核心是一个路径选择 IP：x 变量选航班节点，y 变量选衔接边，流守恒通过“选中节点必须连接、最多一个前序一个后继”来实现。弧的集合 arcs 在传入前已经做过合法性过滤，也就是说只有时间衔接、机场匹配、机型一致的边才会进来，这比在模型里加时间窗约束更高效，因为弧的合法性检查在 Python 里做一次即可。
计算修正成本时要注意：排班惩罚 rho 在这个模型里没有建模进约束，而是最后统一加到目标值上判断是否为负。这样处理没问题，因为 rho 是常量，不会影响子问题的最优路径结构，只影响收敛判据。
这个实现的边界在于：没有处理基地节点显式建摸。实际业务里航线从基地出发回基地的约束，靠“第一个航班的出发机场=基地、最后一个航班的到达机场=基地”在外面过滤掉。这么做在航班规模几百条时足够；如果以后扩展到几千航班再考虑用资源扩展的标号算法，那才是这个问题的标准解法。
4.3 收敛判据与负数跳跃的权衡
主循环终止条件是定价子问题返回 None，也就是没有负检验数列。但浮点计算里不能把判据设成 reduced_cost < 0，要用容差。常见的做法是 reduced_cost < -1e-6 才加列，在 -1e-6 到 0 之间视为收敛。这个容差要和 Gurobi 的可行性容差 Parameter FeasibilityTol 配套。
另一个工程问题是列的数量不能无节制涨。早期迭代中，对偶价格跳动剧烈，一次定价可能返回多条负检验数列，如果全都加进 RMP，模型列数很快膨胀。我通常给每次定价加列设置上限，比如最多加 20 条，按检验数升序取最负的若干条。还有一种做法是在一次迭代里做多次不同的随机扰动，生成多样化列，这能有效减少总迭代次数，代价是每轮 RMP 求解时间变长。取舍标准是看 RMP 求解耗时占整体比重，Gurobi 求解 LP 很快，瓶颈通常在子问题的图构建上，所以多生成几条列通常划算。
5. 列生成避坑：收敛判据、启动列与高频翻车排查
5.1 主循环框架：RMP、定价、加列三件套
把第 3、4 章的代码串起来，一个完整的主循环大概长这样。
def column_generation(flight_nodes, arcs, initial_columns, col_costs, flight_costs, rho=100.0): # 构建 RMP m, col_vars = build_rmp( [fn["id"] for fn in flight_nodes], initial_columns, col_costs, rho ) columns = list(initial_columns) costs = list(col_costs) col_count = len(columns) for iteration in range(200): m.optimize() if m.status != GRB.OPTIMAL: print(f"迭代 {iteration}: RMP 求解失败，状态 {m.status}") break # 取对偶价格并做简单稳定化：限幅到 [-200, 200] dual = {} for fn in flight_nodes: c = m.getConstrByName(f"cover_{fn['id']}") raw_pi = c.Pi dual[fn['id']] = max(-200.0, min(200.0, raw_pi)) # 定价：找负检验数列 new_col = solve_pricing( flight_nodes, arcs, dual, flight_costs, max_duty_minutes=720 ) if new_col is None: print(f"迭代 {iteration}: 无负检验数列，LP 最优") break # 加列：更新 model 的列变量和覆盖约束系数 new_var = m.addVar( lb=0.0, ub=1.0, vtype=GRB.CONTINUOUS, obj=sum(flight_costs[f] for f in new_col) + rho, name=f"col_{col_count}" ) col_count += 1 columns.append(new_col) costs.append(sum(flight_costs[f] for f in new_col)) # 更新每个航班的覆盖约束系数 for fn in flight_nodes: if fn['id'] in new_col: c = m.getConstrByName(f"cover_{fn['id']}") m.chgCoeff(c, new_var, 1.0) m.update() print(f"迭代 {iteration}: 加入新列，航班数={len(new_col)}") return columns, costs主循环的要点有四个。第一，对偶价格限幅，我习惯把限制幅度设成 [-200, 200]，这个值取决于成本量纲，成本单位是千元就设成 -2000 也行，原则是不要限得太死，否则定价方向失真；第二，每次加完列后必须 m.update()，让 Gurobi 接受新变量；第三，要每轮判断 m.status，因为 Gurobi 的 LP 求解可能因为数值问题返回 INF 或 UNBOUNDED，这时不能继续；第四，迭代上限 200 是保险丝，正常收敛在 30-50 轮内，如果超过 200 还在加列，说明建模或定价代码里有缺陷，比如弧合法性判断出错。
收敛后拿到的解是 LP 松弛解，列变量不是整数。工程上这个 LP 下界很有价值：你可以拿它和下界的整数可行解对比，评估你的启发式方案离最优有多远。但注意不要直接把 LP 解当运营方案，因为会有大量排班取小数。
5.2 启动列：没有初始可行解就别谈对偶价格
列生成的第一步必须有一个可行的 RMP，否则对偶价格无法计算。初始列的构造有三种常见方案。
第一种是“一航班一列”，每个航班单独成列，成本就是它单飞的成本。这种方案简单，保证每个航班都被覆盖，但列之间完全独立，LP 对偶价格全部落在单航班上，初始对偶值偏大，定价子问题会非常激进。第二种是“贪心拼接”，按时间排序，把能够合法衔接的航班尽量串成链，每条链尽量拉长，直到值班时长上限。这种初始列成本低、覆盖密，对偶价格分布合理，是我用下来最均衡的方案。第三种是“历史排班复用”，如果有前一天的运营排班数据，直接拿历史方案做初始列，效果最好但有限制，航线变化大时不适用。
注意一个细节：build_rmp 里如果某个航班没有任何初始列覆盖会直接报错，这其实是个不错的防御机制。航空公司航线列表中偶尔会有红眼航班、短转场航班，贪心拼接时很容易漏掉，报错能逼着检查输入数据质量。
5.3 避坑：5 个高频翻车场景，现象、原因与解决
我把实际运行列生成时会反复遇到的坑整理成五条，按出现频率排序。
第一条翻车场景是 RMP 求解状态一直显示 INF 或 ITERATION_LIMIT。原因是覆盖约束用了 ≥ 但启动列没有覆盖全部航班，或者整数列在 LP 松弛里不满足覆盖。解决方法是先跑一个纯启发式：把所有航班按贪心拼接生成若干初始列，打印每个航班的覆盖次数，确认最小覆盖≥1，再进主循环。这个检查代码不超过 10 行，但能省掉一晚上的排错时间。
第二条是定价子问题返回的列全是单航班列。现象是迭代次数很多，但排班平均长度不涨，目标值下降极慢。原因是排班成本里 rho 设成 0，或者 max_duty_minutes 设得太宽松但实际弧过滤时把长链边给过滤掉了。检查方法：打印每条新列覆盖的航班数，如果大量是 1-2 个航班，基本可以断定是 arc 构建逻辑出错，比如最小中转时间设得太大或者机场匹配条件写反了。
第三条是 LP 松弛目标值随着迭代下降，但整数化后反而比简单启发式差。这不算 bug，而是对偶价格引导的 LP 最优解结构对 IP 不友好。实践中常见的原因是覆盖约束是 ≥，LP 松弛里大量冗余覆盖，整数化时这些冗余把解推偏。解决办法是最后一轮把覆盖约束改成 =1，或者加一个冗余惩罚系数，让 Gurobi 在整数解里自动消掉多余覆盖。
第四条是列数爆炸，迭代 50 轮后就加了 800 条列。根源通常是定价子问题每次只生成最负的一条列，导致对偶价格来回震荡，每次都补充极端列。解决思路是每次定价生成多条列（前 20 条最负的），同时加入“列管理”机制：定期清理 RMP 里检验数很大、很久没进基的列，因为 Gurobi 里删除变量的成本很低。
第五条是数值问题：Gurobi 报 “Numerical trouble” 或者对偶价格出现 NaN。原因多半是指标差太大：航班成本几万，对偶价格几千，检验数算出来是 1e-10 级别。解决方法是统一量纲，把成本单位从“元”换成“千元”或“万元”，再设置 ModelSense 和 obj 系数缩放。这一条看起来玄学，但碰到一次就知道值多少时间。
6. 从 LP 下界到真正可用的排班：整数化与参数调优
列生成跑到收敛后，拿到的 LP 下界是很好的参照系，但直接给运营排班还差一步：整数化。常见做法是在最后一轮 RMP 里把所有列变量改成 BINARY 或 INTEGER，重新让 Gurobi 求解。几百个列、几百个约束的整数规划对 Gurobi 来说不难，gap 通常在几分钟内压到 1% 以下。如果列数上万，那就得考虑所谓 branch-and-price，把分支和列生成嵌套起来。但现实项目里，多数场景“列生成 + 最后一轮整数化”已经够用，因为列生成产生的那批列已经覆盖了大部分良性候选方案。
整数化之后的验证环节容易被忽视，我一般做三层验证。第一层是硬约束自动校验：每条排班重新检查航段衔接、执勤时长、基地闭环，不通过就找 Gurobi 的 solution pool 里备选解；第二层是覆盖率检查：所有航班至少被一条排班覆盖，没有漏班；第三层是人工抽查，拿一周的排班表给资深签派看，他们经常能发现模型里没有体现的隐性规则，比如某些机场过站时间要额外加缓冲。这套流程走完，再谈参数调优才有意义。
参数调优里收益最大的是 Gurobi 的 MIPFocus 和 Threads。整数化阶段，把 MIPFocus 设为 1 或 3，前者聚焦找可行解，后者聚焦下界，根据当前 gap 情况切换。Threads 设成机器物理核数的一半或全部，Gurobi 在多核下对整数规划的加速比接近线性。定价子问题的求解线程也可以并行，多个子问题独立生成列互不干扰。
还有两个经验参数。一是对偶稳定化的限幅区间，这个不是越大越好，限得太宽会让对偶震荡，限得太窄会让定价方向钝化；我习惯先用宽区间跑一轮看检验数分布，再收紧到合理范围。二是启动列的贪心参数，比如最小中转时间设成 45 分钟还是 60 分钟，直接影响后续列生成的弧集大小。这两个参数对迭代轮数和整数解质量的影响，比任何求解器参数都更显著。
最后说一个我做项目时的习惯：每轮列生成结束，把 RMP 目标值、加列数、平均排班长度打印成日志，画成曲线看一眼。如果曲线下降平滑、后期趋于水平，基本可以放心；如果曲线反复震荡，说明对偶稳定化没到位或弧过滤逻辑有问题。这个习惯救过我很多次，因为模型的数学形式再漂亮，最终还是要落在可以复现、可以解释的工程日志上。踩过这些坑之后，我自己再做航班调度项目时，最优先保证的就是启动列质量和对偶稳定化，这两点做好，后续整数化其实是个很轻松的过程。希望这篇笔记能帮你少走几次弯路，把列生成从论文模型真正跑成业务系统里稳定的排班引擎。
本文还有配套的精品资源，点击获取
