Benchmarking the Maritime Inventory Routing Problem on a Quantum Annealing-Hybrid System

The maritime inventory routing problem (MIRP) is an optimization task aimed to increase the efficiency of the distribution of bulk products by sea. It combines the routing of a fleet of heterogeneous vessels between capacitated supplying and demanding ports with the inventory handling at the involved facilities. We consider a well-studied and general MILP-model variant and introduce modelling adaptations to reduce end-of-horizon effects. The primary goal is to investigate the capabilities and limitations of current large-scale quantum-based optimization platforms as a new solution method for MIRPs. We thus benchmark the computational performance of D-Wave’s quantum-classical hybrid solver on our model by comparing it to results obtained with CPLEX as a classical state-of-the-art solution method. The test instances cover a range of different parameter scales, ranging from 2 to 4 ports, fleet size of 2 to 7 vessels and up to 45 discrete time periods. The benchmark results show that the hybrid system fails to find solutions in the same time as CPLEX for about half the problem instances. In particular, it struggles to explore tight solution spaces of larger instances. The hybrid solutions that were found vary in quality, averaging to about 65% to 75% of the classically computed objective values. For improved results we believe that the problem formulation needs to be changed to a regime better suited for the hybrid solver, e.g. by incorporating quadratic terms.