A Branch-Price-Cut-And-Switch Approach for Optimizing Team Formation and Routing for Airport Baggage Handling Tasks with Stochastic Travel Times

在每个大型机场的核心，都隐藏着一个大多数旅客从未察觉到的复杂且高风险的物流挑战：将行李从航站楼运送到飞机上并返回的过程。这一过程依赖于地面勤务团队的组织、装备以及在停机坪上的精准调度。每架航班都有严格的装载或卸载时间窗口，错过这些期限可能会引发连锁反应式的延误、航空公司的经济处罚以及乘客的沮丧。由于地面人员并非可以互换的资源，这一难度进一步增加；他们拥有不同的技能水平，具备操作特定重型机械（如高载机或传送带）的资质。此外，停机坪本身是一个动态环境，不同停机位之间的行驶时间很少是可预测的，经常因穿越飞机的移动或局部拥堵而减慢。几十年来，规划者一直试图在速度需求与这些不确定性的现实之间寻找平衡，但往往依赖于无法解释现实运营中混乱本质的简化假设。

慕尼黑工业大学的研究人员开发了一种新方法来解决这个难题，超越了长期主导该领域的静态模型。他们不再假设行驶时间是固定的，也不再假设总是会出现最坏的情况，而是将地面车辆的移动视为具有已知概率的变量。他们创建了一种复杂的算法，能够同时决定哪些工人组成一个团队、他们为哪架飞机提供服务以及服务的先后顺序，同时考虑到延误的可能性。其创新的核心是一种被称为“分支-定价-切割-切换”（Branch-Price-Cut-and-Switch）的技术。这种技术允许计算机在寻找最优解的过程中动态地改变其策略。它首先从劳动力的一个宽泛、简化的视角出发以快速找到较好的选项，但如果它遇到了一个在数学上看起来合理但在现实中无法执行的方案——例如某种工人无需行驶时间即可在任务间“瞬间移动”的情景——它会立即切换到更详细、更严谨的模型来纠正错误。这种切换机制确保了最终的计划不仅是一个数学理想，更是一个可行的现实。

该团队利用来自某欧洲大型枢纽机场生成的数据对算法进行了测试，模拟了长达两小时的规划周期，期间每小时有三十架次航班起降。他们将这种新方法与现有方法进行了对比，发现其表现显著优于后者，能够解决更复杂的实例并达到最优解，缩小了最优解与计算机所获解之间的差距。至关重要的是，研究表明，显式地为不确定性进行规划比忽略不确定性能获得更好的结果。当算法被输入确定性数据（即假设行驶时间固定为平均值或最佳值）时，生成的计划在面对模拟的现实世界变动时，往往无法满足服务水平要求。相比之下，通过考虑随机性（或概率性）行驶时间而生成的计划始终能保持高水平的服务，确保航班能够以高度的可靠性按时装载。

其中最引人注精的发现之一是算法如何管理效率与安全之间的权衡。通过使用特定的统计阈值来确定预留多少劳动力以应对潜在延误，研究人员可以根据需要将系统调节得更加保守或更加激进。他们发现，采用适度的谨慎程度，而非假设最坏的交通状况，可以在保证延误控制在可接受范围内的同时，实现更高效的可用人员利用。这种方法有效地在进度表中建立了安全缓冲，而没有浪费资源。研究还强调，仅仅假设平均行驶时间是不够的；虽然这比假设最佳情况产生的结果要好，但仍会导致频繁违反服务标准。只有通过对所有可能的行驶时间及其概率进行建模，系统才能保证稳定的服务水平，从而防止那种让乘客在行李提取处等待或错过转机航班的不可预测延误。

这项工作的意义不仅限于停机坪。该算法证明，在复杂的、充满不确定性的环境中，无需诉诸猜测或导致资源闲置的过度保守规划，也能创建高效且稳健的调度方案。通过在不同的数学模型之间进行动态切换，并使用精确方法将可行解与仅具理论意义的解区分开来，研究人员为处理资源受限系统中的不确定性提供了蓝图。他们的结果表明，机场运营商可以通过拥抱环境的不可预测性，而非试图忽视它，来实现更高的准点率和更低的成本。研究结论指出，显式地考虑行驶时间的随机性质不仅是理论上的改进，更是现代机场运营的实际需求，它提供了一种在提高可用劳动力效率的同时，确保行李处理商获得稳定服务水平的方法。