论文标题
行李带分配问题
The Baggage Belt Assignment Problem
论文作者
论文摘要
我们考虑将航班分配到机场的行李收回区域中的行李带的问题。该问题由哥本哈根机场的现实申请起源。目的是构建一个健壮的时间表,将乘客和航空公司的偏好考虑在内。我们考虑许多业务和公平限制,避免交通拥堵并确保良好的乘客流动。解决方案的鲁棒性是通过将交货时间与乘客预期到达时间相匹配的,并通过在同一皮带上安排的两个航班之间添加缓冲时间来实现。我们将这个问题表示为行李带分配问题(BBAP)。我们首先为问题提供了通用整数线性编程(ILP)公式。然后,我们提出了一种基于列生成解决的ILP模型的重新印象的分支机构(B&P)算法。我们的方法依靠有效的动态编程算法来处理定价问题。我们在哥本哈根机场的一系列现实数据以及受实际数据启发的一组实例上测试了所提出的算法。我们的B&P计划优于一个商业求解器,该商业求解器在该问题的ILP公式上发起,并且有效地在有限的计算时间内提供了高质量的解决方案,从而使其在中型和大型机场的日常运营中有可能使用。
We consider the problem of assigning flights to baggage belts in the baggage reclaim area of an airport. The problem is originated by a real-life application in Copenhagen airport. The objective is to construct a robust schedule taking passenger and airline preferences into account. We consider a number of business and fairness constraints, avoiding congestions, and ensuring a good passenger flow. Robustness of the solutions is achieved by matching the delivery time with the expected arrival time of passengers, and by adding buffer time between two flights scheduled on the same belt. We denote this problem as the Baggage Belt Assignment Problem (BBAP). We first derive a general Integer Linear Programming (ILP) formulation for the problem. Then, we propose a Branch-and-Price (B&P) algorithm based on a reformulation of the ILP model tackled by Column Generation. Our approach relies on an effective dynamic programming algorithm for handling the pricing problems. We tested the proposed algorithm on a set of real-life data from Copenhagen airport as well as on a set of instances inspired by the real data. Our B&P scheme outperforms a commercial solver launched on the ILP formulation of the problem and is effective in delivering high quality solutions in limited computational times, making it possible its use in daily operations in medium-sized and large airports.