Formation and Routing of Worker Teams for Airport Ground Handling Operations: A Branch-and-Price-and-Check Approach
研究机场地勤中行李装卸团队的组建与路径规划问题，提出分支定价检查算法，在真实数据上验证其能优化任务完成时间，优于现行调度策略。
We address workforce optimization for ground handling operations at the airport, focusing on baggage loading and unloading. Teams of skilled workers have to be formed and routed across the apron to unload the baggage from the aircraft after a landing and to load it before takeoff. Such tasks must be performed within time windows and require a team of workers with different skill levels. The goal is to find a feasible plan that minimizes the sum of the tasks completion times. We formalize a variation of the workforce scheduling and routing problem, integrating team formation, hierarchical skills with downgrading, multiple trips, and different execution modes. We propose a solution approach based on branch-and-price-and-check and test it on real-world instances from a major European hub airport. We propose a model based on the Dantzig–Wolfe decomposition. In the pricing problem, we generate tours of teams as shortest paths with constrained resources in a network. In the master problem, we select an optimal set of tours that do not exceed the workforce availability. Our experiments show that the proposed algorithm can produce optimal solutions for small- and medium-sized instances and good or optimal solutions for large instances. The results also show that our approach outperforms the current airport dispatching policy. Funding: G. Dall’Olio was funded by the Deutsche Forschungsgemeinschaft [Grant Advanced Optimization in a Networked Economy Graduiertenkolleg 2201, Project 277991500]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0110 .