IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v20y2023i1d10.1007_s10287-023-00478-8.html
   My bibliography  Save this article

An ALNS-based matheuristic algorithm for a multi-product many-to-many maritime inventory routing problem

Author

Listed:
  • Nooshin Heidari

    (University of Bergen)

  • Ahmad Hemmati

    (University of Bergen)

Abstract

In this paper, we propose an adaptive large neighborhood search-based matheuristic algorithm to solve a multi-product many-to-many maritime inventory routing problem. The problem addresses a short sea inventory routing problem that aims to find the best route and distribution plan for multiple products with a heterogeneous fleet of vessels through a network including several producers and customers. Each port can be visited a given number of times during the planning horizon, and the stock level for each product should lie within the predefined bound limits. The problem was introduced by Hemmati et al. (Eur J Oper Res 252:775–788, 2016). They developed a mixed integer programming formulation and proposed a matheuristic algorithm to solve the problem. Although their proposed algorithm worked well in terms of running time, it suffers from disregarding a part of the solution space. In this study, we propose a new matheuristic algorithm to find better solutions by exploring the entire solution space for the same problem. In our solution methodology, we split the variables into routing and non-routing variables. Then in an iterative process, we determine the values of the routing variables with an adaptive large neighborhood search algorithm, and we pass them as input to a penalized model which is a relaxed and modified version of the mathematical model introduced in Hemmati et al. (2016). The information from solving the penalized model, including the values of the non-routing variables, is then passed to the adaptive large neighborhood search algorithm for the next iteration. Several problem-dependent operators are defined. The operators use the information they get from the penalized model and focus on decreasing the penalty values. Computational results show up to 26% improvement in the quality of the solutions for the group of instances with a large feasible solution space. We get the optimal value for the remaining instances matched with the reported results.

Suggested Citation

  • Nooshin Heidari & Ahmad Hemmati, 2023. "An ALNS-based matheuristic algorithm for a multi-product many-to-many maritime inventory routing problem," Computational Management Science, Springer, vol. 20(1), pages 1-23, December.
    • Handle: RePEc:spr:comgts:v:20:y:2023:i:1:d:10.1007_s10287-023-00478-8
    DOI: 10.1007/s10287-023-00478-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-023-00478-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10287-023-00478-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gustavo Souto dos Santos Diz & Fabrício Oliveira & Silvio Hamacher, 2017. "Improving maritime inventory routing: application to a Brazilian petroleum case," Maritime Policy & Management, Taylor & Francis Journals, vol. 44(1), pages 42-61, January.
    2. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    3. Agra, Agostinho & Christiansen, Marielle & Delgado, Alexandrino & Simonetti, Luidi, 2014. "Hybrid heuristics for a short sea inventory routing problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 924-935.
    4. AGRA, Agostinho & ANDERSSON, Henrik & CHRISTIANSEN, Marielle & WOLSEY, Laurence A., 2013. "A maritime inventory routing problem: discrete time formulations and valid inequalities," LIDAM Reprints CORE 2584, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Al-Khayyal, Faiz & Hwang, Seung-June, 2007. "Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part I: Applications and model," European Journal of Operational Research, Elsevier, vol. 176(1), pages 106-130, January.
    6. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    7. Christiansen, Marielle & Fagerholt, Kjetil & Flatberg, Truls & Haugen, Øyvind & Kloster, Oddvar & Lund, Erik H., 2011. "Maritime inventory routing with multiple products: A case study from the cement industry," European Journal of Operational Research, Elsevier, vol. 208(1), pages 86-94, January.
    8. Zixuan Yu & Ping Zhang & Yang Yu & Wei Sun & Min Huang, 2020. "An Adaptive Large Neighborhood Search for the Larger-Scale Instances of Green Vehicle Routing Problem with Time Windows," Complexity, Hindawi, vol. 2020, pages 1-14, October.
    9. Faramroze G. Engineer & Kevin C. Furman & George L. Nemhauser & Martin W. P. Savelsbergh & Jin-Hwa Song, 2012. "A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing," Operations Research, INFORMS, vol. 60(1), pages 106-122, February.
    10. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    11. Marielle Christiansen, 1999. "Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem," Transportation Science, INFORMS, vol. 33(1), pages 3-16, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hemmati, Ahmad & Hvattum, Lars Magnus & Christiansen, Marielle & Laporte, Gilbert, 2016. "An iterative two-phase hybrid matheuristic for a multi-product short sea inventory-routing problem," European Journal of Operational Research, Elsevier, vol. 252(3), pages 775-788.
    2. Xu, Dongyang & Li, Kunpeng & Zou, Xuxia & Liu, Ling, 2017. "An unpaired pickup and delivery vehicle routing problem with multi-visit," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 218-247.
    3. Agra, Agostinho & Christiansen, Marielle & Wolsey, Laurence, 2022. "Improved models for a single vehicle continuous-time inventory routing problem with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 297(1), pages 164-179.
    4. Agostinho Agra & Marielle Christiansen & Kristine S. Ivarsøy & Ida Elise Solhaug & Asgeir Tomasgard, 2017. "Combined ship routing and inventory management in the salmon farming industry," Annals of Operations Research, Springer, vol. 253(2), pages 799-823, June.
    5. Mutlu, Fatih & Msakni, Mohamed K. & Yildiz, Hakan & Sönmez, Erkut & Pokharel, Shaligram, 2016. "A comprehensive annual delivery program for upstream liquefied natural gas supply chain," European Journal of Operational Research, Elsevier, vol. 250(1), pages 120-130.
    6. Agra, Agostinho & Christiansen, Marielle & Delgado, Alexandrino & Simonetti, Luidi, 2014. "Hybrid heuristics for a short sea inventory routing problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 924-935.
    7. Leandro C. Coelho & Jean-François Cordeau & Gilbert Laporte, 2014. "Thirty Years of Inventory Routing," Transportation Science, INFORMS, vol. 48(1), pages 1-19, February.
    8. Chen, Qingfeng & Li, Kunpeng & Liu, Zhixue, 2014. "Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 218-235.
    9. Papageorgiou, Dimitri J. & Nemhauser, George L. & Sokol, Joel & Cheon, Myun-Seok & Keha, Ahmet B., 2014. "MIRPLib – A library of maritime inventory routing problem instances: Survey, core model, and benchmark results," European Journal of Operational Research, Elsevier, vol. 235(2), pages 350-366.
    10. Gustavo Souto dos Santos Diz & Silvio Hamacher & Fabricio Oliveira, 2019. "A robust optimization model for the maritime inventory routing problem," Flexible Services and Manufacturing Journal, Springer, vol. 31(3), pages 675-701, September.
    11. Mingyu Li & Peter Schütz, 2020. "Planning Annual LNG Deliveries with Transshipment," Energies, MDPI, vol. 13(6), pages 1-24, March.
    12. Kirschstein, Thomas, 2018. "Rail transportation planning in the chemical industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 142-160.
    13. Archetti, Claudia & Christiansen, Marielle & Grazia Speranza, M., 2018. "Inventory routing with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 268(1), pages 314-324.
    14. Fokkema, Jan Eise & Land, Martin J. & Coelho, Leandro C. & Wortmann, Hans & Huitema, George B., 2020. "A continuous-time supply-driven inventory-constrained routing problem," Omega, Elsevier, vol. 92(C).
    15. Jørgen Bjaarstad Nikolaisen & Sofie Smith Vågen & Peter Schütz, 2023. "Solving a maritime inventory routing problem under uncertainty using optimization and simulation," Computational Management Science, Springer, vol. 20(1), pages 1-27, December.
    16. Jørgen Glomvik Rakke & Henrik Andersson & Marielle Christiansen & Guy Desaulniers, 2015. "A New Formulation Based on Customer Delivery Patterns for a Maritime Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(2), pages 384-401, May.
    17. Stålhane, Magnus & Andersson, Henrik & Christiansen, Marielle & Fagerholt, Kjetil, 2014. "Vendor managed inventory in tramp shipping," Omega, Elsevier, vol. 47(C), pages 60-72.
    18. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    19. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    20. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:comgts:v:20:y:2023:i:1:d:10.1007_s10287-023-00478-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.