Column Generation for Outbound Baggage Handling at Airports

Abstract : The planning of outbound baggage handling at international airports is challenging. Outgoing flights have to be assigned and scheduled to handling facilities at which the outgoing baggage is loaded into containers. To avoid disruptions of the system the objective is to minimize workload peaks over the entire system. The resource demand of the jobs, which have to be scheduled, is depending on the arrival process of the baggage. In this paper we present a time-indexed mathematical programming formulation for planning the outbound baggage. We propose an innovative decomposition procedure in combination with a column generation scheme to solve practical problem instances. The decomposition significantly reduces the symmetry effect in the time-indexed formulation and also speeds up the computational time of the corresponding Dantzig-Wolfe formulation. To further improve our column generation algorithm we propose state-of-the-art acceleration techniques for the primal problem and pricing problem. Computational results based on real data from a major European Airport show that the proposed procedure reduces the maximal workloads by more than 60% in comparison to the current assignment procedure used.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01614391
Contributor : Christian Artigues <>
Submitted on : Tuesday, October 10, 2017 - 6:27:49 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Thursday, January 11, 2018 - 1:52:35 PM

File

FreyKolischArtigues.pdf
Files produced by the author(s)

Identifiers

Citation

Markus Frey, Rainer Kolisch, Christian Artigues. Column Generation for Outbound Baggage Handling at Airports. Transportation Science, INFORMS, 2017, 35p. ⟨10.1287/trsc.2017.0739⟩. ⟨hal-01614391⟩

Share

Metrics

Record views

188

Files downloads

1025