Vehicle routing applications are ubiquitous in the field of pick-up and delivery service. We focus on the vehicle routing problem with balanced pick-up called VRPBP which originates from the package pick-up service. The aim of the problem is not only to efficiently explore the shortest travel route but also to balance loads between depots and vehicles. These problems can be regarded as optimization problems, and recent developments in Ising machines, including quantum annealing machines, bring us a new opportunity to solve complex real-world optimization problems. In this paper, a two-phase method and a three-phase method using Ising machines are proposed for solving the VRPBP. As the applicability of current Ising machines is limited due to the small size of Ising spins and connectivities, we partition the complex problem into two or three sub-problems, and the key elements of each sub-problem are mapped onto quadratic unconstrained binary optimization (QUBO) models to fit in the structure of the Ising machines. We first compared the performances of the Ising machine on the standard TSP and CVRP datasets with a conventional state-of-the-art solver and three conventional methods. Then, we evaluated the performances of the proposed methods compared with five conventional method for solving the VRPBP. The results confirm the effectiveness of the two proposed methods in solving vehicle-routing-related optimization problems.
Vehicle routing applications are ubiquitous in the field of pick-up and delivery service. We focus on the vehicle routing problem with balanced pick-up called VRPBP which originates from the package pick-up service. The aim of the problem is not only to efficiently explore the shortest travel route but also to balance loads between depots and vehicles. These problems can be regarded as optimization problems, and recent developments in Ising machines, including quantum annealing machines, bring us a new opportunity to solve complex real-world optimization problems. In this paper, a two-phase method and a three-phase method using Ising machines are proposed for solving the VRPBP. As the applicability of current Ising machines is limited due to the small size of Ising spins and connectivities, we partition the complex problem into two or three sub-problems, and the key elements of each sub-problem are mapped onto quadratic unconstrained binary optimization (QUBO) models to fit in the structure of the Ising machines. We first compared the performances of the Ising machine on the standard TSP and CVRP datasets with a conventional state-of-the-art solver and three conventional methods. Then, we evaluated the performances of the proposed methods compared with five conventional method for solving the VRPBP. The results confirm the effectiveness of the two proposed methods in solving vehicle-routing-related optimization problems.
Vehicle routing problems (VRPs) can be solved as optimization problems. Practical applications of the VRPs are involved in various areas including manufacturing, supply chain, and tourism. Conventional approaches using von Neumann computers obtain good approximate solutions to the optimization problems, but conventional approaches show disadvantages of computation costs in large-scale or complex problems due to the combinatorial explosion. Oppositely, Ising machines or quantum annealing machines are non-von Neumann computers that are designed to solve complex optimization problems. In this paper, we propose an Ising-machine based approach for the vehicle routing problem with balanced pick-up (VRPBP). The development of the VRPBP is motivated by postal items pick-up services in the real-world. Our approach includes various features of VRP variants. We propose a 2-phase approach to solve the VRPBP and key elements in each phase are mapped onto quadratic unconstrained binary optimization (QUBO) forms. Specifically, the first phase belongs to the clustering phase which is an extension to the knapsack problem with additional distance and load balancing concerns. The second phase is mapped to the traveling salesman problem. Experimental results of our approach are evaluated in terms of solution quality and computation time compared with conventional approaches.
The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.
The Vehicle Routing Problem (VRP) is an extension of the Travelling Salesperson Problem (TSP). A VRP determines the delivery sequence where multiple vehicles are available, delivery should be made to multiple points, and each point should be visited once. However, road conditions change depending on the time of day, and the time required to travel between two points changes accordingly. Unless these changes are considered, a calculated minimum cost is not realized in actual logistics. Aiming to apply the Time-Dependent Vehicle Routing Problem with Time Windows (TDVRPTW), which is a VRP extension that counts changes in the time required to travel between two points depending on the time of day, to Ising machines including quantum annealers, this paper proposes an effective formulation to realize TDVRPTW, composed of several objective functions and constraints. Further, this paper compares and evaluates the results obtained by a physical Ising machine and confirms the validity of the formulation, thus verifying the applicability of the TDVRPTW to quantum computing.
Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone has still been unable to demonstrate this capability except for small-sized problems. Hybrid approaches, where QC and classical computing work together, have shown the most potential for solving real-world-scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new Hybrid Quantum-classical Tabu Search (HQTS) algorithm to solve the Capacitated Vehicle Routing Problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the Traveling Salesman Problem (TSP) for each route as a Quadratic Unconstrained Binary Optimization (QUBO) and solves it using D-Wave’s Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. Across different starting solution methods, including quantum-based and classical heuristics, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap relative to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
Quantum annealing (QA) is a quantum computing algorithm that works on the principle of Adiabatic Quantum Computation (AQC), and it has shown significant computational advantages in solving combinatorial optimization problems such as vehicle routing problems (VRP) when compared to classical algorithms. This paper presents a QA approach for solving a variant VRP known as multi-depot capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization problem with real-world applications in the fields of transportation, logistics, and supply chain management. We consider heterogeneous depots and vehicles with different capacities. Given a set of heterogeneous depots, the number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a set of spatially distributed customer locations, the MDCVRP attempts to identify routes of various vehicles satisfying the capacity constraints such as that all the customers are served. We model MDCVRP as a quadratic unconstrained binary optimization (QUBO) problem, which minimizes the overall distance traveled by all the vehicles across all depots given the capacity constraints. Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer requests. We discuss the problem complexity and a solution approach to solving MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.
The multi-day travel planning assists users with realistic travel itineraries by searching for the optimal travel routes through a set of candidate hotels and point-of-interests (POIs). The multi-day travel planning problem (MTPP) can be solved as an optimization problem. Although conventional methods using von Neumann computers obtain good approximate solutions to the optimization problems, large computation costs are required to solve large-scale or complex problems due to the combinatorial explosion. On the other hand, Ising machines or quantum annealing machines are non-von Neumann computers, and those machines are developed to deal with complex optimization problems. In this paper, we propose an Ising-machine-based method for the MTPP. Practical factors of the MTPP include the POI satisfaction, travel expenses, and time limits. Those factors are mapped onto quadratic unconstrained binary optimization (QUBO) forms. We evaluate the proposed method using two real-world datasets including Sapporo and Tokyo, Japan. Experimental results show that the MTPP can be effectively solved using Ising machines compared with the conventional methods in terms of the solution quality and the execution time. To the best of our knowledge, this study is the first solution of the MTPP using Ising machines.