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.