The manufacturing industry encounters numerous optimization problems, one of which is the optimization of storage location assignment (OSLA) problem in logistics. OSLA is a combinatorial optimization problem focused on improving the efficiency of picking operations in logistics centers. We explore quantum annealing (QA) as a potential solution to combinatorial optimization problems and investigate its applicability to the OSLA. The objective function for this optimization is the average travel distance of workers to their assigned destinations. However, this value is derived by solving the Traveling Salesman Problem for multiple orders, which is itself a combinatorial optimization problem. Therefore, it cannot be analytically represented in a quadratic unconstrained binary optimization form. To address this limitation, we employed black-box optimization with annealing (BBO-Annealing), which combines a surrogate model with an annealing algorithm, an approach that has recently gained attention in applied research involving QA. To evaluate the effectiveness of quantum computing, we compared results obtained using simulated annealing (SA) with those obtained using QA. Additionally, to assess the optimization performance of our proposed method, we compared it with a genetic algorithm (GA) that did not utilize a surrogate model of the objective function. QA demonstrated a higher probability of finding the optimal solution (33.3% vs 26.7% with SA). However, the optimization performance of GA surpassed that of the proposed method. Our analysis suggests that the relatively lower performance of our method was primarily attributable to the strong influence of constraints. The optimization performance can be improved by incorporating methods that consider the uncertainty of surrogate model predictions such as the lower confidence bound.
The manufacturing industry encounters numerous optimization problems, one of which is the optimization of storage location assignment (OSLA) problem in logistics. OSLA is a combinatorial optimization problem focused on improving the efficiency of picking operations in logistics centers. We explore quantum annealing (QA) as a potential solution to combinatorial optimization problems and investigate its applicability to the OSLA. The objective function for this optimization is the average travel distance of workers to their assigned destinations. However, this value is derived by solving the Traveling Salesman Problem for multiple orders, which is itself a combinatorial optimization problem. Therefore, it cannot be analytically represented in a quadratic unconstrained binary optimization form. To address this limitation, we employed black-box optimization with annealing (BBO-Annealing), which combines a surrogate model with an annealing algorithm, an approach that has recently gained attention in applied research involving QA. To evaluate the effectiveness of quantum computing, we compared results obtained using simulated annealing (SA) with those obtained using QA. Additionally, to assess the optimization performance of our proposed method, we compared it with a genetic algorithm (GA) that did not utilize a surrogate model of the objective function. QA demonstrated a higher probability of finding the optimal solution (33.3% vs 26.7% with SA). However, the optimization performance of GA surpassed that of the proposed method. Our analysis suggests that the relatively lower performance of our method was primarily attributable to the strong influence of constraints. The optimization performance can be improved by incorporating methods that consider the uncertainty of surrogate model predictions such as the lower confidence bound.
As global demand for logistics continues to grow, improving the efficiency of warehouse operations has become increasingly important. While many processes in logistics warehouses have been automated, the receiving area still relies heavily on manual work. Therefore, optimizing this area is essential. When optimizing operations in a logistics warehouse, various problems must be considered, such as layout design and worker assignment. Previous research has typically focused on these problems individually. However, because they are closely related, jointly optimizing them can further improve overall efficiency. In this study, we focus on the receiving area and conduct joint optimization of layout design and worker assignment. Specifically, we extend and apply a black-box optimization method called FMQA, which combines Factorization Machines (FM) with Quantum Annealing (QA). By using Factorization Machine regression, we build an objective function from simulator data. We then use Quantum Annealing to minimize it and improve the receiving area. A comparison with an actual warehouse environment, using the multi-agent simulator, shows that our approach can reduce mean package processing time by up to 22.1%. This result demonstrates the effectiveness of joint optimization of layout design and worker assignment.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.
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.
Abstract The warehouse layout problem (WLP), also known as warehouse slotting problem, aims to determine the assignment of products to storage locations while minimizing the total travel distance for picking operations. It is combinatorial in nature and well-known to be NP-hard. To obtain high-quality solutions to medium and large WLP instances efficiently remains a computational challenge, which has motivated our work on applying quantum optimization algorithms for this problem. We reformulate the classical quadratic assignment programming (QAP) model of the WLP to a quadratic unconstrained binary optimization (QUBO) model. Our QUBO model avoids adding slack variables and reduces additional overheads as in the typical QUBO reformulation approach, which facilitates the application of the D-Wave Leap Hybrid solver. Computational study is performed on a use case with 30 stock-keeping-units (SKUs) and 32 storage slots, for which the QUBO formulation has 960 binary decision variables. We show that the D-Wave Leap Hybrid solver finds better solution to the base scenario than the exact IBM CPLEX mixed-integer quadratic programming (MIQP) solver operating under a 60-second wall-clock limit, one-tenth of the 600-second budget allocated to CPLEX in this experimental design. A sensitivity analysis across 30 scenarios, generated by crossing five annual pick volume profiles with six co-picking matrix density levels (0.5 to 1.0), shows that the D-Wave hybrid solver outperforms CPLEX MIQP solver in 26 of 30 cases, with solution quality improvements of 0.4 to 12.1%. D-Wave’s advantage generally increases as the density of co-picking matrix decreases. These results demonstrate quantum utility for WLP and motivate further investigation of hybrid quantum-classical methods for combinatorial logistics optimization at industrial strength scales.
This paper explores the application of Quantum Annealing (QA) to the field of combinatorial optimization. The core idea is to leverage the principles of quantum mechanics, specifically quantum tunneling, to efficiently solve complex optimization problems. We present a framework for utilizing QA to tackle problems represented as quadratic unconstrained binary optimization (QUBO) models. The methodology focuses on mapping the problem's constraints and objective function into a form suitable for QA hardware. We discuss the challenges involved in this mapping process, including the limitations of current QA devices and the need for careful problem formulation. Furthermore, we analyze the potential advantages of QA over classical optimization techniques, particularly concerning the exploration of a wider solution space. The research highlights the promise of QACO as a viable approach for tackling computationally demanding combinatorial optimization tasks, offering a novel method to enhance optimization efficiency.
Airline companies struggle every day trying to schedule crew, flights and aircraft.Tail Assignment is the problem of allocating individual aircraft to a set of flights, while ensuring multiple constraints and aiming to minimise an objective function, such as operational costs.Given the enormous amount of possibilities and constraints involved, this problem has been a study case for the last decade.Many solutions have emerged using classical computing, but with limitations regarding performance.Quantum Annealing (QA) is a heuristic technique for finding global minimum energy levels over an energy landscape using quantum mechanics.Due to its characteristics, it has been proved to have a clear advantage in solving some complex optimisation problems, being a promising technique to apply in multiple fields.In this study, Tail Assignment Problem was set as a Quadratic Unconstrained Binary Optimisation (QUBO) model, using two different techniques, and was solved using a classical and two hybrid solvers.Tests were run based on extractions from real-world data, analysing the performance of the implementation in terms of time, scalability and quality (i.e., the lowest operational costs) of the obtained solutions.We concluded that using a library for modelling the problem as well as considering individual flights rather than pre-aggregating them in strings can be a bottleneck when it comes to its scalability.Furthermore, we found out that there was a higher probability of obtaining better solutions for this problem using one of the hybrid solvers when compared with the classical heuristic algorithms such as Simulated Annealing (SA).These findings can serve as foundations for further studies.