Feasibility Study on Quantum Optimization of Aircraft Container Loading

今天的航空货物装载计划通常是一项手工任务，必须由经验丰富的装载计划人员执行。在实际包装和装载过程中，航空货运业务实践仍然涉及大量基于纸笔或电子表格的计划和试错。这将导致较高的劳动力成本，但也经常导致次优结果，因为存在恒定的时间压力，并且问题的复杂性可能相当高。因此，在当今竞争激烈的航空货运市场中，优化装载过程可以为航空公司提供显著的优势，首先可以提高其装载计划人员的生产力，其次可以为每个航班提供高质量的解决方案。空运货物装载解决方案的第一个目标是使装载货物的质量最大化，以使空运更有利可图。然而，集装箱的布置会影响飞机重心的位置，进而影响飞机的阻力。挑战在于平衡负载，使飞机飞得更安全，飞得更快，用更少的燃料。在本可行性研究中，我们关注的是考虑到这些相互冲突的目标，优化货舱内集装箱布局的问题。寻找飞机的最佳载荷对于经典算法来说是一个挑战，主要是因为解决方案必须同时考虑多个飞行约束。这个问题可以看作是背包问题的扩展。这种组合优化问题的目的是在预算约束下选择最优的项目集。背包问题属于一类“NP”问题，意思是“不确定多项式时间”。这个名字指的是这些问题迫使计算机经历许多步骤才能得到解决方案。这个数字会根据输入的大小而急剧增加——例如，在填充特定背包时要选择的物品清单。一台计算机必须遍历每一种可能的组合，以产生最有利可图的组合。给定不确定的时间，计算机可以使用蛮力来优化像这样的大型案例，但在实际的时间尺度上并不可行。需要求解多个变量的复杂场景，是传统计算算法无法在短时间内实现的。本可行性研究探讨了利用量子计算的算法如何实现这一目标。

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.