在异质车辆路由问题上应用量子近似优化
David Fitzek1,2, Toheed Ghandriz3,4, Leo Laine3,4
1Department of Microtechnology and Nanoscience, Chalmers University of Technology, 412 96, Gothenburg, Sweden. davidfi@chalmers.se.
Scientific reports
|October 25, 2024
概括
本研究探讨了量子计算用于异质车辆路由问题 (HVRP). 研究人员使用量子近似优化算法 (QAOA) 找出近似解决方案,展示了量子方法应对复杂物流挑战的潜力.
科学领域:
- 量子计算是一种量子计算.
- 运营研究 运营研究
- 组合优化的优化.
背景情况:
- 量子计算为解决复杂的组合问题提供了新的启发式.
- 小规模和中等规模的量子设备可以在实际问题尺寸上测试这些启发式.
- 不同质的车辆路由问题 (HVRP) 是物流中的一个关键的组合挑战.
研究的目的:
- 研究量子计算的应用,以找到HVRP的近似解决方案.
- 使用量子近似优化算法 (QAOA) 进行HVRP.
- 分析量子算法的可扩展性和性能,以优化物流.
主要方法:
- 制定了一个将HVRP映射到一个伊辛哈密尔顿.
- 在使用最多21个量子比特的问题实例上模拟了QAOA.
- 在QAOA框架内比较了各种经典优化器的性能.
主要成果:
- 对于HVRP映射所需的量子比特的数量与客户的数量成正方形.
- 证明了使用QAOA用于大致HVRP解决方案的可行性.
- 在HVRP的QAOA中确定了经典优化器性能和运行时间之间的权衡.
结论:
- 量子计算,特别是QAOA,显示出解决异质车辆路由问题的前景.
- 这种量子方法的量子比特要求与问题大小 (客户数量) 相对应.
- 需要进一步的研究来优化物流应用中QAOA的经典优化器.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
42
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
42
Distributed Loads: Problem Solving
627
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
627
Maxwell-Boltzmann Distribution: Problem Solving
1.4K
Individual molecules in a gas move in random directions, but a gas containing numerous molecules has a predictable distribution of molecular speeds, which is known as the Maxwell-Boltzmann distribution, f(v).
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
1.4K
Ampere-Maxwell's Law: Problem-Solving
553
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
553
Statically Indeterminate Problem Solving
365
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
365
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.0K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.0K


