Refine
Document Type
Language
- English (3)
Has Fulltext
- no (3)
Is part of the Bibliography
- no (3)
Keywords
- Benchmarks (1)
- Industry application (1)
- QUTAC (1)
- Quantum computing (1)
- Reference problems (1)
Institute
Begutachtungsstatus
- peer-reviewed (3)
A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
(2019)
he Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implementation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.
Quantum computing promises to overcome computational limitations with better and faster solutions for optimization, simulation, and machine learning problems. Europe and Germany are in the process of successfully establishing research and funding programs with the objective to dvance the technology’s ecosystem and industrialization, thereby ensuring digital sovereignty, security, and competitiveness. Such an ecosystem comprises hardware/software solution providers, system integrators, and users from research institutions, start-ups, and industry. The vision of the Quantum Technology and Application Consortium (QUTAC) is to establish and advance the quantum computing ecosystem, supporting the ambitious goals of the German government and various research programs. QUTAC is comprised of ten members representing different industries, in particular automotive manufacturing, chemical and pharmaceutical production, insurance, and technology. In this paper, we survey the current state of quantum computing in these sectors as well as the aerospace industry and identify the contributions of QUTAC to the ecosystem. We propose an application-centric approach for the industrialization of the technology based on proven business impact. This paper identifies 24 different use cases. By formalizing high-value use cases into well-described reference problems and benchmarks, we will guide technological progress and eventually commercialization. Our results will be beneficial to all ecosystem participants, including suppliers, system integrators, software developers, users, policymakers, funding program managers, and investors.