Groupe d’études et de recherche en analyse des décisions

G-2000-68

A Model and Column Generation Algorithm for the Aircraft Loading Problem

, et

In this paper, we study the aircraft loading problem (ALP) which consists of transporting a series of items between two different points by aircraft at a minimum cost. The problem is formulated as an integer nonlinear multi-commodity network flow model with resource constraints. It is solved by using a column generation approach embedded within a branch-and-bound framework. Lower bounds are provided via a Dantzig-Wolfe decomposition scheme and branching decisions are taken on aggregated flow variables. The algorithm has been tested on real instance and on randomly generated problems. The results show that this approach can solve the ALP to optimality within a reasonable amount of time.

, 22 pages