Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.
Metaheuristic approaches to solving combinatorial optimization problems have many attractions. They sidestep the issue of combinatorial explosion; they return good results; they are often conceptually simple and straight forward to implement. There are also shortcomings. Optimal solutions are not guaranteed; choosing the metaheuristic which best fits a problem is a matter of experimentation; and conceptual differences between metaheuristics make absolute comparisons of performance difficult. There is also the difficulty of configuration of the algorithm - the process of identifying precise values for the parameters which control the optimization process. Quantum annealing is a metaheuristic which is the quantum counterpart of the well known classical Simulated Annealing algorithm for combinatorial optimization problems. This research investigates the application of quantum annealing to the Vehicle Routing Problem, a difficult problem of practical significance within industries such as logistics and workforce scheduling. The work devises spin encoding schemes for routing and scheduling problem domains, enabling an effective quantum annealing algorithm which locates new solutions to widely used benchmarks. The performance of the metaheuristic is further improved by the development of an enhanced tuning approach using fitness clouds as behaviour models. The algorithm is shown to be further enhanced by taking advantage of multiprocessor environments, using threading techniques to parallelize the optimization workload. The work also shows quantum annealing applied successfully in an industrial setting to generate solutions to complex scheduling problems, results which created extra savings over an incumbent optimization technique. Components of the intellectual property rendered in this latter effort went on to secure a patent-protected status.
In this paper we propose a new strategy for solving the Capacitated Vehicle Routing Problem using a quantum annealing algorithm. The Capacitated Vehicle Routing Problem is a variant of the Vehicle Routing Problem being characterized by capacitated vehicles which contain goods up to a certain maximum capacity. Quantum annealing is a metaheuristic that uses quantum tunneling in the annealing process. We discuss devising a spin encoding scheme for solving the Capacitated Vehicle Routing Problem with a quantum annealing algorithm and an empirical approach for tuning parameters. We study the effectiveness of quantum annealing in comparison with best known solutions for a range of benchmark instances.
This study investigates the application of quantum annealing in solving logistics and scheduling problems, areas traditionally challenged by combinatorial complexity. Using a case study approach, quantum annealing was applied to optimize delivery routing and job-shop scheduling problems. The methodology incorporated D-Wave's quantum processing unit (QPU), and performance was benchmarked against classical simulated annealing. Results indicate a significant improvement in computational efficiency and solution optimality, particularly for mid-sized problem instances. The research identifies key parameters influencing performance and provides insights into hybrid quantum-classical integration. These findings contribute to the growing field of quantum computing applications in operations research. Keywords: Quantum annealing, logistics optimization, scheduling algorithms, quantum computing, operations research
Quantum Annealing was previously applied to the vehicle routing problem and the results were promising. For all benchmark instances in the study, optimal results were obtained. However, 100% success rate was not achieved in every case, and tuning the control parameters for larger instances proved cumbersome. This work addresses these remaining difficulties. An empirical approach is taken wherein measurements of run-time behaviour are exploited to transform existing good values of control parameters so that they can be used successfully for other problem instances. The course of this work shows a method which simplifies hand-tuning so that the heuristic performs successfully when applied to larger instances, and also demonstrates a tuning method which establishes control parameter values for instances which belong in broadly defined groupings. In addition, new best known solutions for large-scale instances, and initial results for the distance-constrained variant of the vehicle routing problem are presented.
In the current competitive industrial environment, the study of NP-hard issues is becoming more and more significant. In logistics, the Vehicle Routing Problem (VRP) is one of the popular challenges, especially in cold chain logistics, which requires the management of perishable goods. This problem involves identifying the optimal paths for vehicles responsible for transporting goods to different locations. Due to its combinatorial nature and the complexity of finding optimal solutions, it is identified as an NP-hard problem that requires an unreasonable time frame to solve. Recently, quantum computing has proven to be a promising approach for addressing some of the complex challenges. Among quantum methodologies, quantum annealing (QA) has demonstrated the potential to accelerate computation times in solving optimization problems. By leveraging the principles of quantum tunneling and superposition, QA can explore solution spaces more efficiently. Therefore, this study explores the application of QA to address VRP in cold chain logistics, aiming to develop solutions that minimize travel distances during deliveries. The case study demonstrates that QA can achieve, on average, at least 85% of optimal performance while providing approximately 95% faster run times compared to classical genetic algorithms (GA). This contributes to greater efficiency in cold chain logistics operations.
This paper explores the application of quantum annealing to solve combinatorial optimization problems. The core idea centers around mapping these problems onto a quantum annealing platform and utilizing the quantum effects to find optimal or near-optimal solutions. Specifically, we investigate the potential of improved parameter tuning and algorithmic modifications to enhance the effectiveness of quantum annealing for problems such as the Traveling Salesperson Problem (TSP) and the Knapsack Problem. While quantum annealing has shown promise, its practical performance remains limited, and this work aims to address this limitation through targeted algorithmic and parameter optimization. The central focus is on demonstrating a method for translating a classical combinatorial problem into a suitable form for quantum annealing, followed by a strategic approach to controlling the annealing process to guide the system toward a desired solution. The efficacy of this approach is evaluated conceptually, with a focus on outlining the necessary steps and considerations for successful implementation.
Large-scale logistic networks present a formidable challenge to traditional optimization techniques. The sheer number of variables and constraints involved—including vehicle routing, shipment scheduling, warehouse operations, and inventory management—often leads to computational bottlenecks, hindering efficient network design and operation. This paper investigates the application of quantum-inspired optimization algorithms to address these challenges. Specifically, we explore the potential of algorithms mimicking quantum phenomena, such as quantum annealing and quantum walks, to efficiently solve complex routing and scheduling problems within large logistic networks. Our approach leverages the inherent parallelism and ability of these algorithms to navigate complex solution spaces, offering a promising alternative to classical methods. We demonstrate the feasibility and potential benefits of this strategy through a theoretical framework and illustrative examples, highlighting the advantages of quantum-inspired optimization for improving the performance of large-scale logistic networks.