Quantum Computing (QC) has proven to be a promising technology in several business applications. Notably, this technology is worth studying on problems whose complexity demands an overwhelming amount of solving time. Additionally, due to Moore’s law, the increase in computing capability is starting to be limited. Alternative algorithms for solving complex problems must be evaluated. Quantum Annealing (QA) is a meta-heuristic quantum algorithm designed for solving combinatorial optimization problems. A well-known combinatorial optimization problem many companies face nowadays is distribution logistics. A fleet of vehicles picks up or delivers goods optimally from one depot to various customer locations. Truck-specific capacity and schedule constraints must be fulfilled. This problem is known as the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), classified as an NP-hard problem. Throughout this work, CVRPTW was adapted to solve a Siemens AG operational process, expecting to find a real-time QA solution response required for potential industrial applicability. Furthermore, the modeling approach is based on a binary programming formulation of the CVRPTW in a time-expanded network. A time-expanded network allows discretizing time by expanding the location nodes with time dependencies, enabling the utilization of indicator decision variables. This work introduces a performance comparison of an adjusted CVRPTW on a four-month simulation task solved via an exact optimization algorithm (CBC) and QA, respectively. D-Wave’s quantum annealer Advantage 6.1 (5,640 qubits) with the CBC solver as a baseline was employed. Both solvers were run remotely. The four-month simulation was split into pieces of three days, run sequentially. Each of these three-day instances included a different number of nodes. QA handled up to 12 nodes instances, plus two exceptions that could not be solved with seven and nine nodes. It was found that the transformations of the initial problem into an eligible QA intake hinder the solving time advantages of this algorithm, such as parameter tuning and quantum embedding for each instance. Therefore, a real-world application of the CVRPTW via QA is not yet recommended. However, QA outperformed the CBC, by an order of about two of magnitude, in finding the optimal solution once all parameters and transformations were completed; demonstrating the potential of this technology in the nearer future.     «

Quantum Computing (QC) has proven to be a promising technology in several business applications. Notably, this technology is worth studying on problems whose complexity demands an overwhelming amount of solving time. Additionally, due to Moore’s law, the increase in computing capability is starting to be limited. Alternative algorithms for solving complex problems must be evaluated. Quantum Annealing (QA) is a meta-heuristic quantum algorithm designed for solving combinatorial optimization...     »

Quantum Computing (QC) hat sich als eine vielversprechende Technologie für verschiedene Anwendungen erwiesen. Insbesondere ist diese Technologie für Probleme interessant, deren Komplexität eine überwältigende Menge an Lösungszeit erfordert. Darüber hinaus ist die Zunahme der Rechenleistung aufgrund des Mooreschen Gesetzes allmählich begrenzt. Alternative Algorithmen für das Lösen komplexer Probleme müssen daher evaluiert werden. Quantum Annealing (QA) ist ein metaheuristischer Quantenalgorithmus, der zur Lösung von kombinatorischen Optimierungsproblemen genutzt wird. Ein bekanntes kombinatorisches Optimierungsproblem, mit dem viele Unternehmen heutzutage konfrontiert sind, ist die Distributionslogistik. Eine Flotte von Fahrzeugen holt oder liefert Waren optimal von einem Depot zu verschiedenen Kundenstandorten. Fahrzeugspezifische Kapazitäts- und Terminbeschränkungen müssen dabei erfüllt werden. Dieses Problem ist bekannt als das Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), das als NP-hartes Problem eingestuft wird. Im Rahmen dieser Arbeit wurde das CVRPTW zur Lösung eines Problems der Siemens AG angewendet, in der Erwartung, eine Echtzeit-QA-Lösung zu finden, die für eine potentielle industrielle Anwendbarkeit erforderlich ist. Außerdem basiert der Modellierungsansatz auf einer binären Programmierformulierung des CVRPTW in einem zeitlich erweiterten Netzwerk. Ein zeitlich erweitertes Netzwerk ermöglicht die Diskretisierung der Zeit durch die Erweiterung der Standortknoten mit zeitlichen Abhängigkeiten, was die Verwendung von Indikator-Entscheidungsvariablen ermöglicht. In dieser Arbeit wird ein Leistungsvergleich eines angepassten CVRPTW an einer viermonatigen Simulationsaufgabe durchgeführt, die mit einem exakten Optimierungsalgorithmus (CBC) und QA gelöst wurde. D-Wave's Quantenglühanlage Advantage 6.1 (5.640 Qubits) wurde mit dem CBC Solver als Basislösung verwendet. Beide Solver wurden aus der Ferne ausgeführt. Die viermonatige Simulation wurde in Teile von drei Tagen aufgeteilt, die nacheinander ausgeführt wurden. Jede dieser dreitägigen Instanzen umfasste eine unterschiedliche Anzahl von Knoten. QA bewältigte Instanzen mit bis zu 12 Knoten, mit zwei Ausnahmen, die mit sieben und neun Knoten nicht gelöst werden konnten. Es wurde festgestellt, dass die Umwandlung des Ausgangsproblems in eine geeignete QA-Instanz, sowie die Parameterabstimmung und die Quanteneinbettung für jede Instanz, die Lösungszeitvorteile dieses Algorithmus beeinflusst. Daher ist eine reale Anwendung des CVRPTW über QA noch nicht empfohlen. QA übertraf jedoch den CBC um eine Größenordnung in Bezug auf die Geschwindigkeit der optimalen Lösungsfindung, sobald alle Parameter und Transformationen abgeschlossen waren, was das Potenzial dieser Technologie für die nähere Zukunft verdeutlicht.     «

Quantum Computing (QC) hat sich als eine vielversprechende Technologie für verschiedene Anwendungen erwiesen. Insbesondere ist diese Technologie für Probleme interessant, deren Komplexität eine überwältigende Menge an Lösungszeit erfordert. Darüber hinaus ist die Zunahme der Rechenleistung aufgrund des Mooreschen Gesetzes allmählich begrenzt. Alternative Algorithmen für das Lösen komplexer Probleme müssen daher evaluiert werden. Quantum Annealing (QA) ist ein metaheuristischer Quanten...     »