提升列生成法效率：加速乘务调度问题求解策略

本文主要探讨了"加速列生成法求解乘务调度问题"的研究。列生成法作为一种在解决乘务调度问题中广泛应用的数学规划技术，其基本原理是通过构建和优化一系列线性约束条件（列）来逼近问题的全局最优解。然而，传统的列生成方法在处理大规模问题时，其收敛速度往往较慢，这限制了其在实际应用中的效率。 针对这一挑战，研究人员提出了三种关键的加速策略来改善列生成算法的性能： 1. 周期性移除受限主问题变量：在列生成的迭代过程中，定期剔除部分"较差"的变量，这有助于减少每次迭代时主问题的规模，从而加快搜索过程。这种方法通过对问题结构的动态调整，减轻了计算负担。 2. 强标号消除准则和子问题求解策略：文章提出了一种基于乘务问题特性设计的强标号消除规则，这是一种更为智能的选择列加入和剔除的方法。通过这种方法，可以针对性地处理问题中的关键部分，避免无效的计算，从而提升子问题求解的效率。 3. 利用已有解信息的班次池策略：在处理整数解时，作者提出了一种策略，即构建一个班次池，存储先前求解得到的部分解决方案。这种策略允许算法在后续搜索中复用已知的整数解，减少了重复计算的时间，显著缩短了整数解的求解时间。 通过在实际公共交通系统的10组案例上测试这些加速策略，研究结果表明，这些改进措施对于大规模的乘务调度问题具有显著的加速效果。它们不仅提高了列生成算法的求解速度，而且适用于复杂的实际场景，使得解决这类问题变得更加可行和高效。 本文的核心贡献在于针对乘务调度问题的特点，开发了一系列有效的加速策略，这些策略通过优化列生成算法的迭代过程、增强子问题求解的效率以及利用已有解信息，显著提高了算法在大规模问题上的性能。这对于优化人力资源管理和提高公共交通服务的调度效率具有重要的理论价值和实践意义。