A Hybrid Quantum-assisted Column Generation Algorithm for the Fleet Conversion Problem

• URL: http://arxiv.org/abs/2309.08267v3
• Date: Tue, 12 Mar 2024 09:10:39 GMT
• Title: A Hybrid Quantum-assisted Column Generation Algorithm for the Fleet Conversion Problem
• Authors: Yagnik Chatterjee, Zaid Allybokus, Marko J. Ran\v{c}i\'c, Eric Bourreau
• Abstract summary: Fleet Conversion aims to reduce the carbon emissions and cost of operating a fleet of vehicles for a given set of tours. We show how quantum and classical solvers can be used together to approach an industrial-sized use-case.
• Score: 0.7373617024876725
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of Fleet Conversion aims to reduce the carbon emissions and cost of operating a fleet of vehicles for a given set of tours. It can be modelled as a column generation scheme with the Maximum Weighted Independent Set (MWIS) problem as the slave. Quantum variational algorithms have gained significant interest in the past several years. Recently, a method to represent Quadratic Unconstrained Binary Optimization (QUBO) problems using logarithmically fewer qubits was proposed. Here we use this method to solve the MWIS Slaves and demonstrate how quantum and classical solvers can be used together to approach an industrial-sized use-case (up to 64 tours).

Related papers

• QUEST: QUantum-Enhanced Shared Transportation [0.3749861135832073]
  We present textbfQUEST (Quantum-Enhanced Shared Transportation)<n>We formulate the pairing of windbreakers and windsurfers as a mixed-integer quadratic problem (MIQP)<n>We verify the solution classically via the Hungarian Algorithm, a Gurobi-based solver, and brute-force enumeration of binary vectors.<n>Our quantum implementation successfully recovers the optimal assignment identified by the classical methods.
  arXiv  Detail & Related papers  (2025-05-12T21:19:19Z)
• Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation [1.474723404975345]
  This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) It integrates the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz) Experimental results on small-scale CVRP instances show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach.
  arXiv  Detail & Related papers  (2025-03-21T11:09:48Z)
• Qubit-Efficient Quantum Annealing for Stochastic Unit Commitment [4.2251752131402585]
  Unit Commitment (SUC) has been proposed to manage the uncertainties driven by the integration of renewable energy sources. This paper introduces the Powell-Hestenes-Rockafellar Augmented Lagrangian Multiplier (PHR-ALM) method to eliminate the need for slack variables. To further reduce the qubit overhead, quantum ADMM is applied to break large-scale SUC into smaller blocks and enables a sequential solution.
  arXiv  Detail & Related papers  (2025-02-21T20:15:40Z)
• Quantum Algorithms for Drone Mission Planning [0.0]
  Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives. Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers. We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
  arXiv  Detail & Related papers  (2024-09-27T10:58:25Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Light Cone Cancellation for Variational Quantum Eigensolver Ansatz [3.1347083354427707]
  Variational Quantum Algorithms (VQAs) represent a class of algorithms that utilize a hybrid approach. In this study, we apply a method known as Light Cone Cancellation (LCC) to optimize variational circuits. We show that LCC yields higher approximation ratios than those cases without LCC.
  arXiv  Detail & Related papers  (2024-04-30T12:31:03Z)
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
  We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. We benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints.
  arXiv  Detail & Related papers  (2023-10-04T12:14:56Z)
• Wasserstein Quantum Monte Carlo: A Novel Approach for Solving the Quantum Many-Body Schr\"odinger Equation [56.9919517199927]
  "Wasserstein Quantum Monte Carlo" (WQMC) uses the gradient flow induced by the Wasserstein metric, rather than Fisher-Rao metric, and corresponds to transporting the probability mass, rather than teleporting it. We demonstrate empirically that the dynamics of WQMC results in faster convergence to the ground state of molecular systems.
  arXiv  Detail & Related papers  (2023-07-06T17:54:08Z)
• Formulation of the Electric Vehicle Charging and Routing Problem for a Hybrid Quantum-Classical Search Space Reduction Heuristic [0.0]
  We show how to exploit multilevel carriers of quantum information -- qudits -- for the construction of constrained quantum optimization algorithms. We propose a hybrid classical quantum strategy that allows us to sample constrained solutions while greatly reducing the search space of the problem.
  arXiv  Detail & Related papers  (2023-06-07T13:16:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing [0.5161531917413706]
  This paper introduces QUBO and HOBO representations for rescheduling problems of railway traffic management. We consider the conditions of minimal headway between trains, minimal stay on stations, track occupation, and rolling stock circulation.
  arXiv  Detail & Related papers  (2021-07-07T14:07:07Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.