《Computers & Operations Research》：Revisiting local search for Curriculum-Based Course Timetabling
编辑推荐：
课程大纲制式排课（Curriculum-Based Course Timetabling，CB-CTT）是教育排课领域一个成熟的基准问题，拥有大量真实与合成数据集。尽管该问题在算法开发上已有悠久历史，但在时间限制下设计能够跨多样数据集有效工作的搜索方法仍然具有
课程大纲制式排课（Curriculum-Based Course Timetabling，CB-CTT）是教育排课领域一个成熟的基准问题，拥有大量真实与合成数据集。尽管该问题在算法开发上已有悠久历史，但在时间限制下设计能够跨多样数据集有效工作的搜索方法仍然具有挑战性。研究人员聚焦于局部搜索，在对文献中报道的所有邻域结构进行透彻分析后，提出了一种改进的模拟退火（Simulated Annealing，SA）算法，该算法由经典LectureMove邻域的扩展版本LectureKick驱动，能够在保持可行性的同时实现灵活的讲座重定位。该邻域进一步丰富了若干采样偏置，专门用于处理CB-CTT的软约束，而SA的整体行为由嵌入冷却进度中的截断机制调节。该方法涉及众多参数，包括SA进度与邻域偏置参数，这些参数在大型人工数据集上被严格调优。最终算法随后在可用基准上评估，包括“标准”ITC 2007 comp数据集，并采用原始竞赛超时条件。结果表明，该研究提出的方法明显优于所有先前提出的局部搜索方法，并与CB-CTT总体报告的最佳方法具有竞争力，同时在多个实例上有所改进。
研究背景方面，课程大纲制式排课（CB-CTT）自2003年由Di Gaspero和Schaerf提出、并在ITC 2007第三赛道标准化以来，一直是大学排课的核心基准。该问题要求将各课程的讲座分配至周内的时段（period）与房间（room），满足硬约束（RoomOccupancy、Conflicts、Availabilities）的同时，最小化软约束（RoomCapacity、RoomStability、MinWorkingDays、IsolatedLectures）违例的加权和（权重分别为1、1、5、2）。现有文献中局部搜索自ITC 2007冠军Müller方案起多沿多邻域循环框架发展，而精确与混合方法在大计算预算下不断刷新最优；但在原竞赛时间限制内，局部搜索类方法整体弱于memetic或ALNS等框架，且文献中邻域贡献缺乏在统一框架下的受控评估。为此，研究人员在《Computers 》期刊论文中重新审视CB-CTT局部搜索，目标是用单一扩展邻域配合偏置采样与改进SA，在ITC 2007时限内达到乃至超越已有局部搜索并媲美最优整体方法。
关键技术方法上，研究人员采用三阶段初始解构造（随机分配加两轮仅含ML与SL邻域的Hill Climbing，分别消Conflicts与降软约束代价）；主搜索以LectureKick（LK）为唯一邻域——将LectureMove中“冲突讲座回填原槽”放宽为“冲突讲座可踢至任意空闲槽?period,room?”；在邻域采样中引入面向四项软约束的偏置（如优先选能减IsolatedLectures或补MinWorkingDays的讲座/目标槽）；SA冷却进度嵌入cut-off机制控制温度截断；全部SA与偏置参数在Lopes-Smith-Miles式人工生成集上严格调优，后在ITC 2007 comp及De Coster等真实集上以原竞赛时限评估。
研究结果部分，按论文主体小节浓缩如下。
问题定义小节重申ITC 2007的UD2模型：实体含天、timeslot、period?day,timeslot?、course、teacher、room、curriculum；硬约束三项，软约束四项及固定权重，目标为软违例加权和最小。
解方法小节给出搜索空间为讲座数长度的槽向量；初始解先随机填槽保Availabilities与非占房，再用ML+SL的Hill Climbing两阶段获可行并粗优；主循环以LK为邻域、软约束代价为能量、带cut-off的SA接受准则，偏置采样在选讲座l1、目标槽s2、踢出讲座l2去向s3三处介入。
实验评估小节显示：在comp的21例上，该方法在原始ITC 2007时限内平均软分显著低于Bellio等SA与Kampke等LK-only框架，多个先前未达优的实例获更优；与Abdullah-Turabieh memetic及Kiefer等ALNS相比总体持平并在部分实例占优；在De Coster真实集与调优用人工集上同样保持局部搜索最优。
讨论与结论翻译浓缩：研究人员指出，LectureMove经LK放宽后在统一SA中配合软约束偏置与cut-off，能以纯局部搜索形式在原竞赛时限逼平需嵌精确求解器的混合框架；系统筛查证明多数复杂邻域相对LK无增益，参数严格调优比多邻域堆叠更关键；该工作为CB-CTT提供可复现的强局部搜索基线（代码见iolab-uniud/cb-ctt），并析出一组高难实例作补充基准。结论是，对CB-CTT此类受时限约束的排课基准，精心设计的单邻域偏置SA可超越历史局部搜索并竞争总体最优，无需借力大预算精确法。
