Related Experiment Video
Updated: Jun 9, 2025
05:30
Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit
Published on: September 8, 2023
490
Applying quantum approximate optimization to the heterogeneous vehicle routing problem.
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
Summary
This study explores quantum computing for the heterogeneous vehicle routing problem (HVRP). Researchers used the quantum approximate optimization algorithm (QAOA) to find approximate solutions, showing potential for quantum approaches to complex logistics challenges.
Area of Science:
- Quantum Computing
- Operations Research
- Combinatorial Optimization
Background:
- Quantum computing presents novel heuristics for solving complex combinatorial problems.
- Small- and intermediate-scale quantum devices enable testing these heuristics on practical problem sizes.
- The heterogeneous vehicle routing problem (HVRP) is a key combinatorial challenge in logistics.
Purpose of the Study:
- Investigate the application of quantum computing to find approximate solutions for the HVRP.
- Utilize the quantum approximate optimization algorithm (QAOA) for HVRP.
- Analyze the scalability and performance of quantum algorithms for logistics optimization.
Main Methods:
- Formulated a mapping of the HVRP to an Ising Hamiltonian.
- Simulated the QAOA on problem instances using up to 21 qubits.
- Compared the performance of various classical optimizers within the QAOA framework.
Main Results:
- The number of qubits required for the HVRP mapping scales quadratically with the number of customers.
- Demonstrated the feasibility of using QAOA for approximate HVRP solutions.
- Identified a trade-off between classical optimizer performance and runtime in QAOA for HVRP.
Conclusions:
- Quantum computing, specifically QAOA, shows promise for addressing the heterogeneous vehicle routing problem.
- The qubit requirements for this quantum approach scale quadratically with problem size (number of customers).
- Further research is needed to optimize classical optimizers for QAOA in logistics applications.
Related Concept Videos
01:29Mechanistic 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
01:21Distributed 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
01:20Maxwell-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
01:17Ampere-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
01:16Statically 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
01:34Woodward–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