A major operational planning problem in the air cargo industry is how to arrange cargo
in an aircraft to fly safely and profitably. Therefore, a challenging planning puzzle has to
be solved for each flight. Besides its complexity, the planning is mostly done manually
today, which is a time consuming process with uncertain solution quality. The literature
on loading problems in an air cargo context is scarce and the term is used ambiguously for
different subproblems like selecting containers, packing items into containers, or loading
containers into aircraft. All of the presented models only focus on certain aspects of what
is in practice a larger planning problem. Additionally, some practical aspects have not
been covered in the literature.
In this work, we provide a comprehensive overview of the air cargo load planning problem
as seen in the operational practice of our industrial partner. We formalize its requirements
and the objectives of the respective stakeholders. Furthermore, we develop and
evaluate suitable solution approaches. Therefore, we decompose the problem into four
steps: aircraft configuration, build-up scheduling, air cargo palletization, and weight and
balance. We solve these steps by employing mainly mixed-integer linear programming.
Two subproblems are further decomposed by adding a rolling horizon planning approach
and a Logic-based Benders Decomposition (LBBD). The actual three-dimensional packing
problem is solved as a constraint program in the subproblem of the LBBD.
We evaluated our approaches on instances containing 513 real and synthetic flights. The
numerical results show that the developed approaches are suitable to automatically generate
load plans for cargo flights. Compared to load plans from practice, we could achieve
a 20 percent higher packing density and significantly reduce the handling effort in the air
cargo terminal. The achieved costs of additional fuel burn due to aircraft imbalances and
reloading operations at stop-over airports are almost negligible. The required runtimes
range between 13 and 38 minutes per flight on standard hardware, which is acceptable
for non-interactive planning.
Cargo airlines can significantly profit from employing the developed approaches in their
operational practice. More and especially the profitable last-minute cargo can be transported.
Furthermore, the costs of load planning, handling effort, and aircraft operations
can be significantly reduced.