《Decision Analytics Journal》：A generic analytics-driven constructive search heuristic for feasibility in cross-domain timetabling
编辑推荐：
排课问题是复杂的组合优化挑战，出现在包括教育机构、体育联赛和医疗设施在内的多个领域。尽管具有基本特征，但大多数解决方案方法是领域特定的，在应用于不同排课变体时需要大量重新设计。研究人员提出一个统一的基于迭代局部搜索（Iterated Local Search,
排课问题是复杂的组合优化挑战，出现在包括教育机构、体育联赛和医疗设施在内的多个领域。尽管具有基本特征，但大多数解决方案方法是领域特定的，在应用于不同排课变体时需要大量重新设计。研究人员提出一个统一的基于迭代局部搜索（Iterated Local Search, ILS）的构造性搜索框架，扩展了之前应用于高度约束体育排课的ILS启发式。研究人员证明，通过仅调整领域特定的邻域算子以适应问题的结构拓扑，核心ILS搜索算法可以在保持相同高层搜索机制、冲突解决策略和参数值的同时，求解多种排课问题。为了验证这种跨领域泛化性，研究人员在两个根本不同的基准数据集上评估所提出的框架：多伦多考试排课基准（Toronto examination timetabling benchmark）和国际排课竞赛2019（International Timetabling Competition 2019, ITC 2019）课程排课基准。实验结果表明该框架性能一致，在两个领域的所有实例中均实现了100%的可行性率。这一性能与专门为这些问题设计的特殊算法相当。这项工作促进了通用排课方法论的发展，为跨变体的约束满足提供了理论见解，并为不同排课场景提供了多功能工具。
排课问题（Timetabling problems）是复杂的组合优化挑战，在多个领域广泛存在，包括教育机构、体育联赛和医疗设施。尽管这些共享基本特征，但大多数现有方法都是领域特定的，在应用于不同排课变体时需要大量重新设计。为了开发真正通用的方法，研究人员基于先前在高度约束体育排课中验证的迭代局部搜索（Iterated Local Search, ILS）启发式，将其扩展为一个统一的ILS基构造性搜索框架。研究人员假设，仅通过调整领域特定的邻域算子以适应问题的结构拓扑，核心算法就能在保持相同高层搜索机制、冲突解决策略和参数值的前提下，解决多样化的排课问题。为验证跨领域泛化性，研究在两个根本不同的基准数据集上评估框架：多伦多考试排课基准（Toronto examination timetabling benchmark，包含13个来自加拿大、美国等教育机构的真实数据集）和国际排课竞赛2019（ITC 2019）课程排课基准（包含30个来自普渡大学、马萨里克大学、AGH科技大学等机构的复杂实例）。实验结果表明，该框架在所有实例上均实现100%的可行性率，且性能与专门为这些问题设计的算法相当。论文发表在《Decision Analytics Journal》，标志着通用排课方法论的重要进展，为跨变体的约束满足提供理论见解，并为不同排课场景提供多功能工具。
**主要关键技术方法（不超过250字）**
研究核心为迭代局部搜索（ILS）框架，交替进行扰动阶段和局部搜索阶段。扰动阶段随机选择未排事件，并通过自适应概率参数（probabilityRandomTimeSlot）平衡选择最少冲突时隙或随机时隙，以逃离局部最优。局部搜索阶段尝试将所有未排事件排入最少冲突时隙（最多允许一个冲突），并采用洗牌策略（Shuffling）重排已排事件以创造新机会。洗牌阶段使用三种邻域算子：Move算子（移动单个事件）、Swap算子（交换两个事件）和Kempe Chain算子（移动冲突事件链）。对于Toronto考试排课（无容量约束），启用所有算子；对于ITC 2019课程排课（高度约束），主要使用Move算子以避免级联冲突。样本队列来源明确来自多伦多考试排课基准和ITC 2019课程排课基准（包括Early、Middle、Late三个类别共30个实例）。
**研究结果**
- **4.2 Toronto examination timetabling benchmark**
- *4.2.1 Benchmark characteristics*：描述13个数据集的规模特征（如CAR91有681场考试、56,242个选课记录，PUR93有2,419场考试、120,681个选课记录），约束仅为无冲突分配（冲突自由约束）。
- *4.2.2 Experimental results*：框架在所有13个数据集上实现100%可行性率（10次运行均成功）。小型实例（如EAR83）平均执行时间<1秒，大型实例（如PUR93）平均约24小时，但所有实例均稳定找到可行解。
- *4.2.3 Search behavior analysis*：通过搜索过程图（Fig. 4）展示算法行为：初始阶段快速减少未排事件，随后进入振荡阶段（未排事件数在1-5之间波动），表明有效逃离局部最优；随问题规模增大，振荡阶段变长（如CAR91需>1400次迭代）。
- *4.2.4 Comparison with state-of-the-art*：与2012-2022年间27项研究覆盖模式比较，多数研究选择性报告结果（如PUR93仅37%研究包含），而框架完全覆盖所有13个实例，且100%可行，证明其稳健性。
- **4.3 ITC 2019 course timetabling benchmark**
- *4.3.1 Benchmark characteristics*：描述30个实例的复杂特性，包括大规模（最多8,813门课、38,437名学生）、19种分布约束（如SameRoom、NotOverlap等）以及多层资源限制（预定时隙和房间列表）。
- *4.3.2 Experimental results*：框架在所有30个实例上实现100%可行性率（10次运行均成功）。多数实例在1小时内完成（如tg-spr18平均167.6秒），仅两个大型实例（agh-fal17和pu-proj-fal19）平均需3.3小时和8.1小时。
- *4.3.3 Search behavior analysis*：搜索过程图（Fig. 5）显示更陡峭的下降模式，扰动阶段偶发向上尖峰（如迭代40附近），随后局部搜索快速解决冲突；由于主要使用Move算子，级联冲突减少，使得大规模实例（如pu-d9-fal19）在较少迭代内实现可行。
- *4.3.4 Comparison with state-of-the-art*：与8项先前研究比较，框架与5项最优化方法并列（全部30个实例可行），但框架是唯一通用方法（无需领域特定优化），且具有100%的每实例运行可行性率（其他研究未报告此指标），凸显可靠性优势。
**讨论与结论**
讨论部分指出，框架的跨领域泛化性归因于几个关键因素：交替的扰动与局部搜索阶段天然平衡探索与利用；自适应参数动态调整策略；洗牌机制通过战略重排创造机会。框架最小化领域特定元素，仅冲突解决机制和邻域算子需要调整。实践意义在于为排课从业者提供通用工具，理论发现表明不同排课变体共享基本结构属性，可通过共同算法原则有效解决。局限性方面，当前研究仅关注可行性（硬约束），未优化软约束；未来应扩展至其他领域如学校排课和护士排班，以及非排课问题（如带时间窗的车辆路径问题）以进一步验证。
研究结论部分翻译：本文形式化并评估了一个用于求解跨领域复杂排课问题的通用构造性搜索框架。基于迭代局部搜索（ILS），该框架保持相同核心结构和不变参数设置，仅需最小限度的领域特定邻域算子调整。通过在两个根本不同的基准数据集（多伦多考试排课基准和ITC 2019课程排课基准）上进行综合实验，框架在所有实例上实现了100%的可行性率，性能与专门为这些领域设计的算法相当。这些结果扩展了先前在ITC 2021体育排课基准上的发现（相同的搜索结构也在45个实例上实现了完全可行）。这一跨领域性能（涵盖三个不同排课变体）值得关注，因为传统上排课算法高度领域特定，在应用于不同问题类型时通常需要大量重新设计。成功地将单一总框架以最小调整应用于多样化的排课领域，促进了排课通用方法论的发展。这表明尽管排课变体之间存在明显差异，但它们共享可通过共同算法原则有效解决的基本结构属性。该见解不仅有助于排课中约束满足的理论理解，还通过为不同情境提供通用工具带来实践效益。未来研究将聚焦于将该框架扩展到其他排课领域（如学校排课和护士排班），并探索其应用于完全不同类别的组合优化问题，以进一步验证其通用性。
