ExxonMobil & IBM Explore Quantum Algorithms to Solve Routing Formulations
By Stuart Harwood, Claudio Gambella, Dimitar Trenev, and Andrea Simonetto
About 90 percent¹ of world trade relies on maritime shipping, every year moving goods with a total value of $14 trillion², with more than 50,000³ merchant ships delivering everything from food to natural gas to widgets. Logistically speaking, this isn’t the “traveling salesperson problem.” It’s a problem with thousands of companies moving every kind of good imaginable around the globe, on ships that can carry as many as 200,000 containers¹, each.
In an industry with such large and complex logistical challenges, route optimization problems are challenging to solve with classical computing technologies and often rely on heuristics and simplifications. As a result, we wanted to see whether quantum computers could transform how we solve such complex optimization problems and provide more accurate solutions in less computational time. The first step to realizing that goal, however, is for researchers like us to investigate how recent advances in quantum algorithms for mathematical programming could be used to model the industry’s routing problems on current and near-term quantum devices.
To figure out the “how,” our research teams at IBM and ExxonMobil collaborated to model maritime inventory routing problems on quantum devices and develop practical approaches for their solution. In our recently published IEEE Transactions on Quantum Engineering paper, “Formulating and Solving Routing Problems on Quantum Computers,” we analyzed the strengths and trade-offs of different mathematical formulations for vehicle (and inventory) routing from a quantum computing perspective. Our research enables us to offer strategies for modeling maritime routing on quantum devices to explore complex business-relevant problems such as routing problems.
Solving routing problems with time constraints
Quantum variational algorithms are already being studied for optimization problems in finance and chemistry. ExxonMobil sought to understand the extent to which maritime routing problems could also be addressed using existing quantum variational algorithms, and to determine which strategies are needed to account for complex real-world constraints, including capacity limitations and time windows, which dictate the arrival and departure of shipments.
We started with Mixed Integer Programming (MIP) and Quadratic Unconstrained Binary Optimization (QUBO) techniques that lie at the heart of many important decision problems in routing and logistics, including maritime inventory routing. The mathematical formulations represent the routing decisions to take as:
- routes traveled,
- feasible movements between customer/port locations,
- order in which each customer/port location is visited in a vehicle route.
The arrival time in each location can be modelled with continuous decision variables, typically bounded in time windows dictated by the actual use case. MIP and QUBOs have often been solved with quantum variational algorithms compatible with the size and modelling limitations of today’s quantum devices.
Different quantum strategies for different mathematical formulations
We investigated which characteristics of a vehicle routing problem influence the difficulty in sampling feasible and optimal solutions with variational approaches for QUBO and MIP formulations. In this context, “optimal” means finding a routing schedule that minimizes the distance travelled by the vehicles.
We performed our experiments on a simulated quantum device, available through the Qiskit QasmSimulator backend. We used the Qiskit Optimization module, available since July, to represent the mathematical formulations, to invoke the Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA) and Alternating Direction Method of Multiplier (ADMM) solvers, and extract the solution from the quantum computations.
We found that the best QUBO solver depends on the number of samples taken from the optimized circuit. The VQE algorithm and QAOA represent two extremes of the trade-off between having a flexible circuit — called an ansatz — that can represent the optimal solution, and having a small enough number of parameters to facilitate the convergence of the classical optimizer to a high-quality solution.
In our tests, with a large enough number of samples, the QAOA/COBYLA (“Constrained Optimization by Linear Approximations,” a numerical optimization) solver had the highest probability of sampling an optimal configuration. Meanwhile, when the number of samples was limited, using VQE yielded a larger success probability.
The adoption of the approach (included in the Qiskit optimization module) in a non-convex setting reveals that a certain degree of inexactness in solving QUBOs is tolerable. This is a promising feature to handle the inherent noise affecting the quantum algorithms on real devices.
From ships to vehicles
We have also shown how to turn a maritime inventory routing problem into a vehicle routing problem with time constraints. In particular, we have leveraged the efforts in classical optimization on the representation of each port into a series of nodes with a fixed demand level and time constraint.
The routing problems that the mathematical formulations are considering can also pertain to vehicles different from ships, such as those used in transportation and logistics applications including goods delivery, ride-sharing services and urban waste management. The metrics adopted to characterize the formulations and solutions obtained are of high value for practitioners interested in appreciating the current capabilities offered by optimization algorithms on quantum gate-based devices.
Our paper describes the mathematical formulations and solution algorithms adopted in detail, so they can be reproduced by researchers and practitioners thanks to the Qiskit Optimization module. The instances used are documented as well, and their use is not restricted in any way. Further research could investigate the robustness or the limitations of the proposed approaches against the noise inherent to computation on the real hardware.
Finally, the solution framework described has a certain flexibility, as it is agnostic of the actual QUBO solver. It could therefore use the ongoing research on quantum optimization algorithms and incorporate future advances in quantum solvers.
As a result of our joint research, ExxonMobil now has a greater understanding of the modelling possibilities, quantum solvers available, and potential alternatives for routing problems in any industry.
S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. E. Bernal Neira and D. Greenberg, “Formulating and Solving Routing Problems on Quantum Computers,” in IEEE Transactions on Quantum Engineering, doi: 10.1109/TQE.2021.3049230.
References
- “Maritime Industry Foundation” Shipping Facts | Maritime Industry Knowledge Center, www.maritimeinfo.org/en/Why-Maritime/Shipping-Facts.
- “Shipping and world trade: driving prosperity” | International Chamber of Shipping, www.ics-shipping.org/shipping-fact/shipping-and-world-trade-driving-prosperity/.
- “Number of ships in the world merchant fleet as of January 1, 2019, by type” | Statista, www.statista.com/statistics/264024/number-of-merchant-ships-worldwide-by-type/.
