PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm

Utkarsh Azad, Bikash K. Behera, Emad A. Ahmed, Prasanta K. Panigrahi, Ahmed Farouk

arXiv:2002.01351v2quant-ph

TL;DR

The paper studies how to use QAOA to solve the NP-hard Vehicle Routing Problem by encoding it as an Ising Hamiltonian and optimizing it with a quantum-classical procedure. Across the reported experiments, some runs found correct solutions while another reported solution was not optimal; the paper concludes that finite-p QAOA does not guarantee an optimum.

  • Problem

    The paper addresses solving the NP-hard Vehicle Routing Problem, a combinatorial optimization problem, using QAOA.

    Source: §I · p. 1

  • Method

    The authors encode VRP as an Ising cost Hamiltonian and use QAOA with classically supplied and optimized parameters based on measured final-state energy.

    Source: §I · p. 1, §IV · p. 4

  • Results

    For p≥12 and p≥24, respectively, the reported experiments found correct solutions with sufficient probability, while another reported solution was not optimal.

    Source: A. Experiment 1 · p. 5, C. Experiment 3 · p. 6, B. Experiment 2 · p. 6

  • Takeaways & Limitations

    The reported experiments show that QAOA can yield correct VRP solutions in some cases, but outcomes vary across the tested cases.

    Source: A. Experiment 1 · p. 5, B. Experiment 2 · p. 6, C. Experiment 3 · p. 6

    For finite p, QAOA is not guaranteed to produce the most optimal solution to the original combinatorial optimization problem.

    Source: §VI · p. 7

Abstract

from arXiv · show

In this paper, we describe the usage of the Quantum Approximate Optimization Algorithm (QAOA), which is a quantum-classical heuristic, to solve a combinatorial optimization and integer programming task known as Vehicle Routing Problem (VRP). We outline the Ising formulation for VRP and present a detailed procedure to solve VRP by minimizing its simulated Ising Hamiltonian using the IBM Qiskit platform. Here, we attempt to find solutions for the VRP problems: (4,2), (5,2), and (5,3), where each (n, k) represents a VRP problem with n locations and k vehicles. We find that the performance of QAOA is not just dependent upon the classical optimizer used, the number of steps p in which an adiabatic path is realized, or the way parameters are initialized, but also on the problem instance itself.

I. INTRODUCTION

Combinatorial optimization can become computationally intractable as problem size or constraints increase. The paper applies QAOA, a hybrid quantum-classical algorithm, to the NP-hard Vehicle Routing Problem.

I. INTRODUCTION

  • Problem size and added constraints can increase optimization hardness, with computational resources scaling exponentially and making problems intractable.The introduction motivates developing efficient tools for solving such problems with available computing power.Source: §I · p. 1
  • Current-generation NISQ processors are limited by qubit count, connectivity, qubit control, coherence time, error correction, and circuit depth.The passage presents QAOA as a quantum-classical hybrid variational algorithm for this setting.Source: §I · p. 1
  • The paper uses QAOA to solve VRP by mapping the NP-hard combinatorial optimization problem to minimization of an Ising Hamiltonian.The introduction describes this as using QAOA on near-term devices.Source: §I · p. 1

II. VEHICLE ROUTING PROBLEM

The Vehicle Routing Problem (VRP) assigns routes to k vehicles that collectively visit n−1 locations once and return to a common depot. This paper considers the basic version without added real-world constraints.

II. VEHICLE ROUTING PROBLEM

  • A VRP instance (n, k) has k vehicles and n−1 non-depot locations; every vehicle starts and ends at depot D, and each location is visited exactly once.The paper relates VRP to the Travelling Salesman Problem, extended to multiple salesmen serving locations collectively.Source: §II · p. 1
  • The optimal route set minimizes the total distance travelled by all k vehicles.Source: §II · p. 1
  • The paper focuses on basic VRP without additional constraints such as vehicle capacity or limited coverage-time.Source: §II · p. 1

III. ISING FORMULATION OF VRP

The paper encodes VRP as an Ising-Hamiltonian minimization problem. It starts from edge-decision variables and routing constraints, then converts the objective through a QUBO representation to spin variables.

III. ISING FORMULATION OF VRP

  • VRP is mapped to minimization of an instance-encoding Ising Hamiltonian, beginning with binary variables for possible directed edges.Each x_ij indicates whether an edge i→j with positive weight exists.Source: §III · p. 2
  • The formulation imposes node-visiting and depot constraints so each location is visited once and vehicles start and return to depot D.The energy functional H_VRP is written as the sum of five terms, H_A through H_E.Source: §III · p. 2
  • The penalty constant A is positive and depends on the problem instance.Source: §III · p. 2
  • The VRP objective is expressed as a quadratic unconstrained binary optimization (QUBO), with Q for edge interactions, g for node contributions, and c as a constant offset.The coefficients are obtained by expanding and regrouping the VRP energy expression.Source: §III · p. 2
  • The QUBO is rewritten using spin variables s_ij∈{−1,1} in place of binary x_ij, and similar terms are regrouped into the VRP Ising Hamiltonian.The Hamiltonian is represented with Pauli-Z operators for implementation on a quantum computer.Source: §III · p. 3

IV. QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

The section frames QAOA as a discretized alternative to following an adiabatic path, whose step size is constrained by the energy gap. It uses a parameterized quantum state and classical optimization of its parameters.

  • A small energy gap constrains the adiabatic step size and can make computation time rise exponentially, limiting AQC on hard instances.Source: §IV · p. 3
  • QAOA discretizes the adiabatic pathway into p steps, using parameters β and γ to construct a parameterized gate sequence.Source: §IV · p. 3
  • For instance (4,2) at p=12, the probability distribution identifies states 779 and 2125 as optimal.Source: Figure 2 · p. 4
  • A classical routine optimizes β and γ from measured final-state energy; at optimal parameters, the resulting state is the ground state of Hcost.Source: §IV · p. 4

V. SIMULATIONS AND RESULTS

The simulations encode VRP instances in qubits and use a mixer and cost Hamiltonian to evolve an initial state. A classical optimizer selects parameters from energy measurements, after which the final state is measured and represented as a bit string.

  • The simulations cover instances (4,2), (5,2), and (5,3), using N = n × (n−1) qubits to encode possible edges and squared Euclidean distances.Source: §V · p. 4
  • Each run starts in |+⟩^N, the mixer ground state prepared by applying Hadamard gates to qubits initialized in |0⟩.Source: §V · p. 4
  • The state evolves through p alternating mixer and cost unitary operations parameterized by β and γ.Source: §V · p. 4
  • The procedure measures the cost-Hamiltonian expectation, classically optimizes the parameters, then measures the optimized state and represents its index as a bit string encoding the flattened adjacency matrix.Source: §V · p. 4

A. Experiment 1

For instance (4,2), the authors report that COBYLA produced the correct solution with sufficient probability for p ≥ 12. The reported solution state has cost 124.871.

A. Experiment 1

  • Figure 3 shows the top 12 feasible solutions for instance (5,3) at p=24, with optimal states 69963 and 74014 highlighted in blue.Source: Figure 3 · p. 5
  • For p ≥ 12, COBYLA produced the correct (4,2) solution with sufficient probability; states 779 and 2125 were equiprobable solutions.Source: A. Experiment 1 · p. 5

B. Experiment 2

Experiment 2 tested QAOA on the (5, 2) VRP instance with several optimizers and p values; the reported QAOA state was not optimal.

B. Experiment 2

  • To encode the problem, the experiment used N = 5×4 = 20 qubits; COBYLA, NELDER MEAD, and L-BFGS-B were tried for p values from 6 to 40, and state 623144 used adjacency matrix A2.Source: B. Experiment 2 · p. 5
  • COBYLA, NELDER MEAD, and L-BFGS-B were tried for p values from 6 to 40.Source: B. Experiment 2 · p. 5
  • Figure 5’s QAOA state has cost 128.545; Figure 6 is identified as the optimal state, and the solution obtained in Figure 5 was not optimal.Source: Figure 5 · p. 6, B. Experiment 2 · p. 6

C. Experiment 3

For the (5, 3) instance, COBYLA produced the correct solution states with sufficient probability for p ≥24; both reported cases had cost 30.530.

C. Experiment 3

  • The solution state visualized as index 688424 is reported with cost 138.511.Its caption gives the state bit string as 10101000000100101000.Source: Figure 6 · p. 6
  • For p ≥24, COBYLA produced the correct solution with sufficient probability, with states 69963 and 74014 equiprobable.The probability distribution shown for p = 24 covers the top 12 feasible solutions.Source: C. Experiment 3 · p. 6
  • Both reported cases have cost 30.530, calculated as 12.138 + 5.300 + 7.200 + 2 × 2.626 + 2 × 0.320.Source: C. Experiment 3 · p. 6

VI. DISCUSSIONS

The discussion reports QAOA applied to VRP and cautions that finite-p solutions are not guaranteed to be optimal because the adiabatic path is approximated in p steps.

VI. DISCUSSIONS

  • The paper applies QAOA to the Vehicle Routing Problem.Source: §VI · p. 6
  • The visualized solution state indexed 69963 is reported with cost 30.530.The caption marks the depot with a yellow star.Source: Figure 7 · p. 7
  • For finite p, QAOA does not guarantee the most optimal solution because it approximates the adiabatic time-evolution path using p steps.Source: §VI · p. 7
Loading 2002.01351v2…