(Image: Getty)

ExxonMobil & IBM Explore Quantum Algorithms to Solve Routing Formulations

By Stuart Harwood, ExxonMobil, Claudio Gambella, IBM Quantum, Dimitar Trenev, ExxonMobil, and Andrea Simonetto, IBM Quantum

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.

  • feasible movements between customer/port locations,
  • order in which each customer/port location is visited in a vehicle route.

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.

From ships to vehicles

(Image: IBM)

References

  1. “Maritime Industry Foundation” Shipping Facts | Maritime Industry Knowledge Center, www.maritimeinfo.org/en/Why-Maritime/Shipping-Facts.
  2. “Shipping and world trade: driving prosperity” | International Chamber of Shipping, www.ics-shipping.org/shipping-fact/shipping-and-world-trade-driving-prosperity/.
  3. “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/.

This is the official Medium account of IBM Research. It’s managed by IBM Research’s Chief Writer Katia Moskvitch, & follows the IBM Social Computing Guidelines.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store