Implementation of a Hybrid Classical-Quantum Annealing Algorithm For Logistic Network Design
Preprint
Abstract
The logistic network design is an abstract optimization problem which, under the assumption of minimal cost, seeks the optimal configuration of infrastructures and facilities of the supply chain based on customer demand. Key economic decisions are taken about the location, number, and size of manufacturing facilities and warehouses base on the optimal solution to this problem. Therefore, improvements in the methods to address this question, which is known to be in the NP-hard complexity class, would have relevant financial consequences. Here, we implement in the D-Wave quantum annealer a hybrid classical-quantum annealing algorithm. The cost function with constraints is translated to a spin Hamiltonian, whose ground state encodes the searched result. As a benchmark, we measure the accuracy of result for a set of paradigmatic problems against the optimal published solutions (the error is on average below $1\%$), and the performance is compared against the classical algorithm, showing a remarkable reduction in the number of iterations. This work shows that, even still far from useful quantum supremacy, state-of-the-art quantum annealers may codify and solve relevant supply-chain problems.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Quantum computing for finance: Overview and prospectsReviews in Physics, 2019
- Reverse engineering protocols for controlling spin dynamicsScientific Reports, 2017
- Quantum annealing with manufactured spinsNature, 2011
- Solving the uncapacitated facility location problem using tabu searchComputers & Operations Research, 2006
- Hybrid genetic algorithm for multi-time period production/distribution planningComputers & Industrial Engineering, 2005
- Computing the Initial Temperature of Simulated AnnealingComputational Optimization and Applications, 2004
- Neighborhood search heuristics for the uncapacitated facility location problemEuropean Journal of Operational Research, 2003
- A simulated annealing methodology to distribution network design and managementEuropean Journal of Operational Research, 2003
- Adiabatic Theorem without a Gap ConditionCommunications in Mathematical Physics, 1999
- Quantum annealing: A new method for minimizing multidimensional functionsChemical Physics Letters, 1994