论文标题
在列生成中使用suppodulinity解决航班分配问题
Using Submodularity within Column Generation to Solve the Flight-to-Gate Assignment Problem
论文作者
论文摘要
在本文中，我们提供了一种基于列的生成方法来解决机场飞往门口的分配问题，其目标是通过将每个计划的每次飞行分配给兼容的门来最大程度地减少到达延迟的地面部分。具体而言，我们为主问题使用集合覆盖公式，并分解定价问题，以便每个门是为了降低成本降低的分配模式而解决的独立定价问题的基础。我们基于基础集合和动态编程算法的近似算法的组合来解决独立的定价问题。据我们所知，这是首次使用supdodulinity属性来有效解决定价问题并改善列生成算法的性能。我们表明，当有整数输入时，动态编程算法是伪级别的。我们还设计并采用了滚动的地平线方法和块分解算法来求解大型实例。最后，我们执行广泛的计算实验来验证方法的性能。
In this paper, we provide a column generation-based approach for solving the airport flight-to-gate assignment problem, where the goal is to minimize the on-ground portion of arrival delays by optimally assigning each scheduled flight to a compatible gate. Specifically, we use a set covering formulation for the master problem and decompose the pricing problem such that each gate is the basis for an independent pricing problem to be solved for assignment patterns with negative reduced costs. We use a combination of an approximation algorithm based on the submodularity of the underlying set and dynamic programming algorithms to solve the independent pricing problems. To the best of our knowledge, this is the first use of submodularity property to efficiently solve pricing problems and improve the performance of column generation algorithm. We show that the dynamic programming algorithm is pseudo-polynomial when there are integer inputs. We also design and employ a rolling horizon method and block decomposition algorithm to solve large-sized instances. Finally, we perform extensive computational experiments to validate the performance of our approach.
