列生成算法在公交调度问题中的应用示例 题目描述 考虑一个公交调度问题：某公交公司需要为一组公交线路安排车辆，目标是使用最少的车辆数来满足全天的乘客需求。每条线路有多个可行的发车间隔方案（如每5分钟、10分钟或15分钟一班），每个方案对应不同的运营成本和服务水平。问题转化为选择最优的发车间隔组合，使得总车辆数最小，同时满足每个时段的乘客需求约束。由于可行方案数量庞大（组合爆炸），直接枚举不可行，需采用列生成算法进行求解。 解题过程 问题建模为线性规划 主问题（Master Problem, MP） ： 设公交线路集合为 \( I \)，时段集合为 \( T \)。每条线路 \( i \in I \) 有多个候选发车间隔方案 \( j \in J_ i \)，每个方案 \( j \) 对应一个二元决策变量 \( x_ {ij} \)（取1表示选择该方案）。 目标函数：最小化总车辆数 \( \min \sum_ {i,j} c_ {ij} x_ {ij} \)，其中 \( c_ {ij} \) 是方案 \( j \) 对线路 \( i \) 所需的车辆数。 约束：每个时段 \( t \in T \) 的乘客需求必须被满足，即 \( \sum_ {i,j} a_ {ijt} x_ {ij} \geq d_ t \)，其中 \( a_ {ijt} \) 是方案 \( j \) 在线路 \( i \) 时段 \( t \) 提供的运力，\( d_ t \) 是时段 \( t \) 的总需求。 附加约束：每条线路必须且仅选择一个方案，即 \( \sum_ j x_ {ij} = 1, \forall i \in I \)。 难点 ：方案集合 \( J_ i \) 可能极大（例如所有可能的发车间隔组合），直接求解MP计算量过大。 列生成算法框架 限制主问题（Restricted Master Problem, RMP） ： 初始时仅包含少量可行方案（如每条线路一个默认方案），求解RMP得到当前最优解和对偶变量值。 子问题（Pricing Problem） ： 利用对偶变量为每条线路 \( i \) 生成新的改进方案（即列）。子问题目标是最小化 检验数 \( \bar{c} {ij} = c {ij} - \sum_ {t} \pi_ t a_ {ijt} - \mu_ i \)，其中 \( \pi_ t \) 是需求约束的对偶变量，\( \mu_ i \) 是线路约束的对偶变量。若存在 \( \bar{c}_ {ij} < 0 \) 的方案，则将其加入RMP。 迭代 ：重复求解RMP和子问题，直到无负检验数列生成，此时RMP的解即为MP的最优解。 子问题的具体求解 对每条线路 \( i \)，子问题是寻找一个发车间隔方案 \( j \)，使检验数最小化。 发车间隔方案可建模为时间轴上的发车时刻序列。例如，将一天划分为若干分钟间隔，决策变量为是否在某个分钟发车。 目标函数：\( \min \left( c_ {ij} - \sum_ {t} \pi_ t a_ {ijt} \right) \)，其中 \( c_ {ij} \) 由发车次数决定（每辆车可覆盖多趟发车），\( a_ {ijt} \) 由时段 \( t \) 内的发车次数和车辆容量计算。 约束：发车间隔需满足最小和最大间隔要求（如不得小于3分钟），且发车次数需覆盖高峰需求。 求解方法：可将子问题转化为最短路径问题（如通过时间网络图建模发车决策），用动态规划求解。 算法终止与结果 当所有子问题的最优检验数均非负时，算法终止。 最终RMP的解给出每条线路选择的发车间隔方案，以及总车辆数。若变量为分数（松弛问题），可结合分支定界法得到整数解。 关键点总结 列生成通过分解主问题与子问题，避免枚举所有方案。 子问题的设计需高效生成可行发车间隔方案，并准确计算其对资源（车辆）和需求覆盖的贡献。 实际应用中需处理整数性约束（如通过分支定价），但线性松弛版本通常提供紧的下界。