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

• Autorzy: Szal Oliver , Rubbert Sebastian , Rizvanolli Anisa

Identyfikatory

DOI

10.12716/1001.19.01.14

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

maritime transport; optimization; benchmarking; inventory routing; quantum computing; operations research; mixed integer programming; MIP; heuristic methods

• Wydawca: Faculty of Navigation, Gdynia Maritime University
• Czasopismo: TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
• Rocznik: 2025
• Tom: Vol. 19 No. 1
• Strony: 113--122
• Opis fizyczny: Bibliogr. 41 poz., rys., tab.

Twórcy

autor

Szal Oliver

• Fraunhofer CML, Hamburg, Germany

autor

Rubbert Sebastian

• eleQtron GmbH, Siegen, Germany

autor

Rizvanolli Anisa

• Fraunhofer CML, Hamburg, Germany

Bibliografia

• [1] dwave-system documentation, 2021.
• [2] Hamburg soll an die spitze im quantencomputing. https://www.hamburg.de/bwi/medien/16613674/ 2022-10-25-bwi-quantencomputing/, 2022. Accessed: 2023-11-01.
• [3] MIRPLIB a library of maritime inventory routing problems. https://mirplib.scl.gatech.edu/ instances, 2023. Accessed: 2023-11-01.
• [4] Amira Abbas et al. Quantum Optimization: Potential, Challenges, and the Path Forward. 12 2023. [5] Agostinho Agra, Marielle Christiansen, Alexandrino Delgado, and Luidi Simonetti. Hybrid heuristics for a short sea inventory routing problem. European Journal of Operational Research, 236(3):924–935, 2014. Vehicle Routing and Distribution Logistics.
• [6] Agostinho Agra, Marielle Christiansen, Lars Magnus Hvattum, and Filipe Rodrigues. Robust optimization for a maritime inventory routing problem. Transportation Science, 52(3):509–525, 2018.
• [7] Agostinho Agra, Marielle Christiansen, Kristine S Ivarsøy, Ida Elise Solhaug, and Asgeir Tomasgard. Combined ship routing and inventory management in the salmon farming industry. Annals of operations research, 253:799–823, 2017.
• [8] Agostinho Agra, Marielle Christiansen, and Laurence Wolsey. Improved models for a single vehicle continuous-time inventory routing problem with pickups and deliveries. European Journal of Operational Research, 297(1):164–179, 2022.
• [9] Henrik Andersson, Arild Hoff, Marielle Christiansen, Geir Hasle, and Arne Løkketangen. Industrial aspects and literature survey: Combined inventory management and routing. Computers & Operations Research, 37(9):1515–1536, 2010.
• [10] Mohamed Ben Ahmed, Onyemaechi Linda Okoronkwo, Edwin Chimezie Okoronkwo, and Lars Magnus Hvattum. Long-term effects of short planning horizons for inventory routing problems. International Transactions in Operational Research, 29(5):2995–3030, 2022.
• [11] Hans J Briegel, David E Browne, Wolfgang Dur, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5(1):19–26, 2009.
• [12] Jaeyoung Cho, Gino J Lim, Seon Jin Kim, and Taofeek Biobaku. Liquefied natural gas inventory routing problem under uncertain weather conditions. International Journal of Production Economics, 204:18–29, 2018.
• [13] Marielle Christiansen, Kjetil Fagerholt, Truls Flatberg, Øyvind Haugen, Oddvar Kloster, and Erik H. Lund. Maritime inventory routing with multiple products: A case study from the cement industry. European Journal of Operational Research, 208(1):86–94, 2011.
• [14] Leandro C. Coelho, Jean-Francois Cordeau, and Gilbert Laporte. Thirty years of inventory routing. Transportation Science, 48(1):1–19, 2014.
• [15] IBM ILOG Cplex. V12. 1: User’s manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
• [16] Stephane Dauzere-Peres, Atle Nordli, Asmund Olstad, Kjetil Haugen, Ulrich Koester, Myrstad Per Olav, Geir Teistklub, and Alf Reistad. Omya hustadmarmor optimizes its supply chain for delivering calcium carbonate slurry to european paper manufacturers. Interfaces, 37(1):39–51, 2007.
• [17] Arijit De, Vamsee Krishna Reddy Mamanduru, Angappa Gunasekaran, Nachiappan Subramanian, and Manoj Kumar Tiwari. Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization. Computers & Industrial Engineering, 96:201–215, 2016.
• [18] Line Eide, Gro Cesilie Hahjem Ardal, Nataliia Evsikova, Lars Magnus Hvattum, and Sebastian Urrutia. Load-dependent speed optimization in maritime inventory routing. Computers & Operations Research, 123:105051, 2020.
• [19] Kjetil Fagerholt, Lars Magnus Hvattum, Dimitri J. Papageorgiou, and Sebastian Urrutia. Maritime inventory routing: recent trends and future directions. International Transactions in Operational Re- search, 30(6):3013–3056, 2023.
• [20] Sebastian Feld, Christoph Roch, Thomas Gabor, Christian Seidel, Florian Neukart, Isabella Galter, Wolfgang Mauerer, and Claudia Linnhoff-Popien. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT, 6:13, 2019.
• [21] Claudio Gambella and Andrea Simonetto. Multiblock admm heuristics for mixed-binary optimization on classical and quantum computers. IEEE Transactions on Quantum Engineering, 1:1–22, 2020.
• [22] Stuart Harwood, Claudio Gambella, Dimitar Trenev, Andrea Simonetto, David Bernal, and Donny Greenberg. Formulating and solving routing problems on quantum computers. IEEE Transactions on Quantum Engineering, 2:1–17, 2021.
• [23] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. Perspectives of quantum annealing: methods and implementations. Reports on Progress in Physics, 83(5):054401, May 2020.
• [24] Sovanmonynuth Heng, Dongmin Kim, Taekyung Kim, and Youngsun Han. How to solve combinatorial optimization problems using real quantum machines: A recent survey. IEEE Access, 10:120106–120121, 2022.
• [25] Hirotaka Irie, Goragot Wongpaisarnsin, Masayoshi Terabe, Akira Miki, and Shinichirou Taguchi. Quan- tum annealing of vehicle routing problem with time, state and capacity. In Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1, pages 145–156. Springer, 2019.
• [26] Jana Ksciuk, Stefan Kuhlemann, Kevin Tierney, and Achim Koberstein. Uncertainty in maritime ship routing and scheduling: a literature review. European Journal of Operational Research, 308(2):499–524, 2023.
• [27] Mingyu Li and Peter Schu¨tz. Planning annual lng deliveries with transshipment. Energies, 13(6):1490, 2020.
• [28] Catherine McGeoch and Pau Farr´e. The d-wave advantage system: An overview. D-Wave Systems Inc., Burnaby, BC, Canada, Tech. Rep, 2020.
• [29]Lluis-Miquel Munguia, Shabbir Ahmed, David A. Bader, George L. Nemhauser, Yufen Shao, and Dimitri J. Papageorgiou. Tailoring parallel alternating criteria search for domain specific mips: Application to maritime inventory routing. Computers & Operations Research, 111:21–34, 2019.
• [30] M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
• [31] Dimitri J Papageorgiou, Myun-Seok Cheon, Stuart Harwood, Francisco Trespalacios, and George L Nemhauser. Recent progress using matheuristics for strategic maritime inventory routing. Modeling, computing and data handling methodologies for maritime transportation, pages 59–94, 2018.
• [32] Dimitri J. Papageorgiou, Myun-Seok Cheon, George Nemhauser, and Joel Sokol. Approximate dynamic programming for a class of long-horizon maritime inventory routing problems. Transportation Science, 49(4):870–885, 2015.
• [33] Dimitri J. Papageorgiou, Ahmet B. Keha, George L. Nemhauser, and Joel Sokol. Two-stage decom- position algorithms for single product maritime inventory routing. INFORMS Journal on Computing, 26(4):825–847, 2014.
• [34] Dimitri J. Papageorgiou, George L. Nemhauser, Joel Sokol, Myun-Seok Cheon, and Ahmet B. Keha. Mirplib – a library of maritime inventory routing problem instances: Survey, core model, and benchmark results. European Journal of Operational Research, 235(2):350–366, 2014. Maritime Logistics.
• [35] Niklas Pirnay, Vincent Ulitzsch, Frederik Wilde, Jens Eisert, and Jean-Pierre Seifert. An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems. 12 2022.
• [36] F Radan, SMT Fatemi Ghomi, SMJ Mirzapour Al-e hashem, and Moeen Sammak Jalali. Maritime inventory routing problem considering weather conditions and tide at ports. Transportation Research Record, 2677(5):934–950, 2023.
• [37] Filipe Rodrigues, Agostinho Agra, Marielle Christiansen, Lars Magnus Hvattum, and Cristina Requejo. Comparing techniques for modelling uncertainty in a maritime inventory routing problem. European Journal of Operational Research, 277(3):831–845, 2019.
• [38] Jin-Hwa Song and Kevin C. Furman. A maritime inventory routing problem: Practical approach. Computers & Operations Research, 40(3):657–665, 2013. Transport Scheduling.
• [39] Byron Tasseff, Tameem Albash, Zachary Morrell, Marc Vuffray, Andrey Y. Lokhov, Sidhant Misra, and Carleton Coffrin. On the emerging potential of quantum annealing hardware for combinatorial optimization. 2022.
• [40] United Nations Conference on Trade and Development (UNCTAD). Review of maritime transport 2022.
• [41] Amir Zojaji, Kiarash Soltaniani, Lars Magnus Hvattum, and Sebastia´n Urrutia. Cyclic solutions to a maritime inventory routing problem. Maritime Transport Research, 3:100074, 2022.

Uwagi

1. Pełne imiona podano na stronie internetowej czasopisma w "Author Index."

2. Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).