Feasibility Study on Quantum Optimization of Aircraft Container Loading

飞机集装箱装载量子优化可行性研究

• 批准号: 10073838
• 金额: $ 34.59万
• 依托单位: UNISYS LIMITED
• 依托单位国家: 英国
• 项目类别: Feasibility Studies
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=10073838
• 关键词: Feasibility; Study; Quantum; Optimization; Aircraft

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.

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