Journal is indexed in following databases:
- SCOPUS
- Web of Science Core Collection - Journal Citation Reports
- EBSCOhost
- Directory of Open Access Journals
- TRID Database - Transportation Research Board
- Index Copernicus Journals Master List
- BazTech
- Google Scholar
2024 Journal Impact Factor - 0.6
2024 CiteScore - 1.9
ISSN 2083-6473
ISSN 2083-6481 (electronic version)
Editor-in-Chief
Associate Editor
Prof. Tomasz Neumann
Published by
TransNav, Faculty of Navigation
Gdynia Maritime University
3, John Paul II Avenue
81-345 Gdynia, POLAND
e-mail transnav@umg.edu.pl
Benchmarking the Maritime Inventory Routing Problem on a Quantum Annealing-Hybrid System
1 Fraunhofer Center for Maritime Logistics and Services (CML), Hamburg, Germany
2 eleQtron GmbH, Siegen, Germany
2 eleQtron GmbH, Siegen, Germany
ABSTRACT: 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.
KEYWORDS: Maritime Transport, Optimization, Benchmarking, Inventory Routing, Quantum Computing, Operations Research, Mixed Integer Programming (MIP), Heuristic Methods
REFERENCES
dwave-system documentation, 2021.
Hamburg soll an die spitze im quantencomputing. https://www.hamburg.de/bwi/medien/16613674/ 2022-10-25-bwi-quantencomputing/, 2022. Accessed: 2023-11-01.
MIRPLIB a library of maritime inventory routing problems. https://mirplib.scl.gatech.edu/ instances, 2023. Accessed: 2023-11-01.
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. - doi:10.1016/j.ejor.2013.06.042
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. - doi:10.1287/trsc.2017.0814
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. - doi:10.1007/s10479-015-2088-x
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. - doi:10.1016/j.ejor.2021.04.027
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. - doi:10.1016/j.cor.2009.11.009
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. - doi:10.1111/itor.12998
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. - doi:10.1038/nphys1157
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. - doi:10.1016/j.ijpe.2018.07.014
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. - doi:10.1016/j.ejor.2010.08.023
Leandro C. Coelho, Jean-Francois Cordeau, and Gilbert Laporte. Thirty years of inventory routing. Transportation Science, 48(1):1–19, 2014. - doi:10.1287/trsc.2013.0472
IBM ILOG Cplex. V12. 1: User’s manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
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. - doi:10.1287/inte.1060.0276
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. - doi:10.1016/j.cie.2016.04.002
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. - doi:10.1016/j.cor.2020.105051
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. - doi:10.1111/itor.13313
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. - doi:10.3389/fict.2019.00013
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. - doi:10.1109/TQE.2020.3033139
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. - doi:10.1109/TQE.2021.3049230
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. - doi:10.1088/1361-6633/ab85b8
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. - doi:10.1109/ACCESS.2022.3218908
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. - doi:10.1007/978-3-030-14082-3_13
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. - doi:10.1016/j.ejor.2022.08.006
Mingyu Li and Peter Schu¨tz. Planning annual lng deliveries with transshipment. Energies, 13(6):1490, 2020. - doi:10.3390/en13061490
Catherine McGeoch and Pau Farr´e. The d-wave advantage system: An overview. D-Wave Systems Inc., Burnaby, BC, Canada, Tech. Rep, 2020.
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. - doi:10.1016/j.cor.2019.05.031
M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
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. - doi:10.1007/978-3-319-61801-2_3
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. - doi:10.1287/trsc.2014.0542
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. - doi:10.1287/ijoc.2014.0601
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. - doi:10.1016/j.ejor.2013.12.013
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.
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. - doi:10.1177/03611981221138565
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. - doi:10.1016/j.ejor.2019.03.015
Jin-Hwa Song and Kevin C. Furman. A maritime inventory routing problem: Practical approach. Computers & Operations Research, 40(3):657–665, 2013. Transport Scheduling. - doi:10.1016/j.cor.2010.10.031
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.
United Nations Conference on Trade and Development (UNCTAD). Review of maritime transport 2022.
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. - doi:10.1016/j.martra.2022.100074
Citation note:
Szal O., Rubbert S., Rizvanolli A.: Benchmarking the Maritime Inventory Routing Problem on a Quantum Annealing-Hybrid System. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, Vol. 19, No. 1, doi:10.12716/1001.19.01.14, pp. 113-122, 2025
Other publications of authors:
File downloaded 61 times
