Feasibility Study on Quantum Optimization of Aircraft Container Loading

点击翻译按钮获取中文摘要

Air cargo load planning today is often a manual task that has to be performed by experienced load planners. The air cargo business practice still involves a lot of pen-and-paper or spreadsheet-based planning and trial and error during the actual packaging and loading.This leads to high labour costs but often also to suboptimal results, as there is a constant pressure of time, and the problem complexity can be pretty high.Accordingly, in today's highly competitive air cargo market, optimizing the loading process can provide a significant advantage for airlines, first by increasing the productivity of its load planning staff and second, producing high-quality solutions tailored for each flight.The first objective of an air-cargo loading solution is to maximize the mass of goods loaded to make air freight more profitable. However, the arrangement of the containers affects the position of the aircraft's centre of gravity, which in turn impacts aircraft drag. The challenge is to balance the load so that the aircraft will fly more safely, fly faster, and use less fuel. In this feasibility study, we are concerned with the problem of optimizing the layout of containers within the cargo holds to take into account these conflicting objectives.Finding the optimal loading for a plane is challenging for classical algorithms, mainly because the solution must respect several flight constraints simultaneously. This problem can be viewed as an extension of the knapsack problem. This combinatorial optimization problem aims to select the optimal set of items subject to a budget constraint.The knapsack problem belongs to a class of "NP" problems, meaning "nondeterministic polynomial time." The name references how these problems force a computer to go through many steps to arrive at a solution. The number increases dramatically based on the size of the inputs---for example, the inventory of items to choose from when stuffing a particular knapsack. A computer must run through every possible combination to generate the single one with the most lucrative haul. Given an indefinite amount of time, a computer could use brute force to optimize large cases like this, but not on timescales that would be practical.Complicated scenarios meant to solve multiple variables are not achievable by a classical computing algorithm in a short time. This feasibility study explores how algorithms leveraging quantum computing may achieve this objective.