Using submodularity within column generation to solve the flight-to-gate assignment problem

In this paper, the authors 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, the authors 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. The authors 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 the authors' knowledge, this is the first use of submodularity property to efficiently solve pricing problems and improve the performance of column generation algorithm. The authors show that the dynamic programming algorithm is pseudo-polynomial when there are integer inputs. The authors also design and employ a rolling horizon method and block decomposition algorithm to solve large-sized instances. Finally, the authors perform extensive computational experiments to validate the performance of their approach.

• Record URL:
  https://doi.org/10.1016/j.trc.2021.103217
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S0968090X2100231X
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • © 2021 Elsevier Ltd. All rights reserved. Abstract reprinted with permission of Elsevier.
• Authors:
  • Li, Yijiang
  • Clarke, John-Paul
  • Dey, Santanu S
• Publication Date: 2021-8

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: 103217
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 129
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Aircraft gates; Approximation (Mathematics); Dynamic programming; Pricing; Slot allocation
• Subject Areas: Aviation; Operations and Traffic Management; Planning and Forecasting; Terminals and Facilities;

Filing Info

• Accession Number: 01782760
• Record Type: Publication
• Files: TRIS
• Created Date: Sep 24 2021 10:20AM