The Baggage Belt Assignment Problem

David Pisinger*, Rosario Scatamacchia

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

1 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number100041
JournalEURO Journal of Transportation and Logistics
Number of pages16
ISSN2192-4376
DOIs
Publication statusAccepted/In press - 2021

Keywords

  • Combinatorial optimization
  • Baggage belt assignment problem
  • Inbound baggage handling
  • Branch and price
  • Knapsack problem

Fingerprint

Dive into the research topics of 'The Baggage Belt Assignment Problem'. Together they form a unique fingerprint.

Cite this