  Quantum computing offers new heuristics for combinatorial problems. With
small- and intermediate-scale quantum devices becoming available, it is
possible to implement and test these heuristics on small-size problems. A
candidate for such combinatorial problems is the heterogeneous vehicle routing
problem (HVRP): the problem of finding the optimal set of routes, given a
heterogeneous fleet of vehicles with varying loading capacities, to deliver
goods to a given set of customers. In this work, we investigate the potential
use of a quantum computer to find approximate solutions to the HVRP using the
quantum approximate optimization algorithm (QAOA). For this purpose we
formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the
algorithm on problem instances of up to 21 qubits. We find that the number of
qubits needed for this mapping scales quadratically with the number of
customers. We compare the performance of different classical optimizers in the
QAOA for varying problem size of the HVRP, finding a trade-off between
optimizer performance and runtime.
