这篇文档属于类型a，即报告了一项原创研究的学术论文。以下是基于文档内容的学术报告：
主要作者及研究机构
本文的主要作者为Paula Fermín Cueto、Sergio García和Miguel F. Anjos，均来自英国爱丁堡大学（University of Edinburgh）的数学学院和麦克斯韦数学科学研究所（Maxwell Institute for Mathematical Sciences）。该研究发表于期刊《Computers & Operations Research》2025年第177卷，文章编号为106972。
学术背景
本研究的主要科学领域是运筹学与优化算法，特别是机场时隙分配问题（Airport Slot Allocation Problem, ASAP）。随着全球航空业的快速发展，繁忙机场的需求往往超过其基础设施的容量，因此需要一种高效的时隙分配机制来最大化现有资源的使用。机场时隙分配问题是一种资源受限的项目调度问题（Resource Constrained Project Scheduling Problem, RCPSP），其目标是在满足机场容量限制和其他操作约束的前提下，最小化分配时隙与请求时隙之间的差异。尽管已有许多研究提出了复杂的模型和快速启发式算法，但精确方法的研究较少，尽管它们具有提供更高质量解决方案的潜力。本文旨在提出一种高效的列生成与行生成算法（Column-and-Row Generation Algorithm），以解决单机场时隙分配问题，并设计了一种针对该问题的预处理方案，能够在短时间内识别出比商业求解器更多的冗余约束和变量。
研究流程
本研究主要包括以下几个步骤：
问题建模
研究首先建立了一个基本的时隙分配模型，该模型包括以下要素：最小化总时隙位移和拒绝时隙的数量、终端和/或跑道容量约束、以及最小周转时间约束。模型采用时间索引的整数规划（Integer Programming）形式，并引入了新的二元变量𝑦𝑖，用于表示是否拒绝某个时隙请求。
预处理方案
针对时隙分配问题的结构，研究提出了一种高效的预处理方案，能够在短时间内识别并移除大量的冗余约束和变量。该方案包括变量固定（Variable Fixing）、冗余容量约束识别（Redundant Capacity Constraints）和冗余周转约束识别（Redundant Turnaround Constraints）等步骤。通过预处理，模型的规模显著减小，从而提高了求解效率。
列生成与行生成算法（CARACAL）
研究提出了一种名为CARACAL的算法，该算法结合了列生成和行生成技术，以动态增加问题规模，直到获得完整的可行解。算法的核心思想是从一个简化的初始模型开始，逐步引入新的变量和约束，直到找到最优解。CARACAL算法的设计灵感来源于ZEBRA算法，后者用于解决大规模p-中值问题（p-Median Problem）。
实验验证
研究通过一系列实验验证了CARACAL算法的性能。实验分为两部分：首先，使用合成的实例进行测试，以评估算法在不同规模和复杂度下的表现；其次，使用来自英国7个机场的实际数据进行测试，以验证算法在实际应用中的有效性。实验结果表明，CARACAL算法在求解速度和解的质量上均优于现有的精确方法。
主要结果
1. 预处理效果
预处理方案能够在短时间内识别并移除大量的冗余约束和变量，显著减少了模型的规模。实验数据显示，预处理方案比商业求解器多移除了10%的变量和41%的约束，且处理速度快了13.3倍。
CARACAL算法的性能
在合成实例的测试中，CARACAL算法在53%的实例中求解时间少于10秒，在79%的实例中求解时间少于1分钟。与基线方法相比，CARACAL算法的平均求解速度快了83倍。在实际数据的测试中，CARACAL算法同样表现出色，能够快速找到最优或接近最优的解决方案。
模型扩展
研究还展示了CARACAL算法在处理时隙分配问题变体时的灵活性，包括优先级组（Priority Groups）、最大周转时间约束（Maximum Turnaround Constraints）、历史超额（Historic Overages）和季节分段（Season Segmentation）等扩展。实验结果表明，CARACAL算法在处理这些复杂问题时仍能保持高效。
结论
本研究提出了一种高效的列生成与行生成算法（CARACAL），用于解决单机场时隙分配问题。通过引入预处理方案和动态增加问题规模的策略，CARACAL算法在求解速度和解的质量上均优于现有的精确方法。该研究不仅为机场时隙分配问题提供了新的解决方案，还为其他资源受限的调度问题提供了有价值的参考。
研究亮点
1. 高效的预处理方案：能够在短时间内识别并移除大量的冗余约束和变量，显著提高了求解效率。
2. CARACAL算法：结合了列生成和行生成技术，能够动态增加问题规模，直到找到最优解。
3. 实际应用验证：通过使用英国7个机场的实际数据进行测试，验证了算法在实际应用中的有效性。
4. 模型扩展性：展示了CARACAL算法在处理复杂时隙分配问题变体时的灵活性。
其他有价值的内容
研究还公开了合成数据生成器的代码和生成的数据集，为其他研究人员提供了宝贵的资源，便于进行基准测试和进一步研究。
这篇报告详细介绍了研究的背景、方法、实验和结果，并强调了其科学价值和实际应用意义。