Combined cargo allocation and multi-ship routing and scheduling problem: application in the fertilizer industry

• Pietro Tiaraju Giavarina dos Santos ^[1] ; Denis Borenstein ^[1]
  1. [1] Universidade Federal do Rio Grande do Sul

     Universidade Federal do Rio Grande do Sul

     Brasil

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. 1, 2025, págs. 29-55
• Idioma: inglés
• DOI: 10.1007/s11750-024-00676-w
• Enlaces
  • Texto completo
• Resumen

  • This paper explores the complex logistics of ship routing and scheduling for fertilizer companies in Brazil, considering the challenges posed by a dynamic international trade landscape affected by factors such as the COVID-19 pandemic and geopolitical conflicts. It expands previous research by incorporating cargo allocation to the heterogeneous fleet in the cargo routing and scheduling problem, which is critical for the contemporary operating scenario. The primary objective is to minimize transportation costs by optimizing ship routes, schedules, and cargo allocation to compartments, while addressing specific operational constraints, such as the capacity of ships’ compartments, delivery delays, change of direction in a ship’s route on the Brazilian coast, segregated storage, and ship stability. Considering the complexity of the generated models for real-life problems, a Lagrangian-based solution method, incorporating a modified relax-and-fix matheuristics and several heuristics to improve the solution process of mixed-integer linear programming solvers, is developed. Experimentation with previous real-life instances reveals that the optimization method obtains implementable operational plans with transportation costs reduced by 47.66%, on average, compared to the amounts paid by companies for sea freight services. A case study demonstrates the applicability of the optimization approach as a decision-support tool for real-life planning.

• Referencias bibliográficas
  • Accioli C, Monteiro S (2011) Brazil: world’s breadbasket. Braz Econ 3(11):14–21
  • Agra A, Christiansen M, Delgado A, Simonetti L (2014) Hybrid heuristics for a short sea inventory routing problem. Eur J Oper Res 236(3):924–935
  • Al-Khayyal F, Hwang SJ (2007) Inventory constrained maritime routing and scheduling for multicommodity liquid bulk, part I: applications and...
  • Arnesen MJ, Gjestvang M, Wang X, Fagerholt K, Thun K, Rakke JG (2017) A traveling salesman problem with pickups and deliveries, time windows...
  • Barbucha D, Filipowicz W (1997) Segregated storage problems in maritime transportation. IFAC Proc Vol 30(8):557–561
  • Caprara A, Fischetti M, Toth P (1999) A heuristic method for the set covering problem. Oper Res 47(5):730– 743
  • Christiansen M (1999) Decomposition of a combined inventory and time constrained ship routing problem. Transp Sci 33(1):3–16
  • Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228(3):467–483
  • Coelho LC, Laporte G (2014) Improved solutions for inventory-routing problems through valid inequalities and input ordering. Int J Prod Econ...
  • dos Santos PTG, Borenstein D (2022) Multi-objective optimization of the maritime cargo routing and scheduling problem. Int Trans Oper Res....
  • dos Santos PTG, Kretschmann E, Borenstein D, Guedes PC (2020) Cargo routing and scheduling problem in deep-sea transportation: case study...
  • Evans JR, Tsubakitani S (1993) Solving the segregated storage problem with Benders’ partitioning. J Oper Res Soc 44(2):175–184
  • Fagerholt K (2001) Ship scheduling with soft time windows: an optimisation based approach. Eur J Oper Res 131(3):559–571
  • Fagerholt K, Christiansen M (2000a) A combined ship scheduling and allocation problem. J Oper Res Soc 51(7):834–842
  • Fagerholt K, Christiansen M (2000b) A travelling salesman problem with allocation, time window and precedence constraints—an application to...
  • Fagerholt K, Ronen D (2013) Bulk ship routing and scheduling: solving practical problems may provide better results. Maritime Policy Manage...
  • Fischetti M, Lodi A (2008) Repairing MIP infeasibility through local branching. Comput Oper Res 35(5):1436–1445
  • Fisher ML (1981) The Lagrangian relaxation method for solving integer programming problems. Manage Sci 27(1):1–18
  • Held M, Karp RM (1971) The traveling-salesman problem and minimum spanning trees: part II. Math Program 1(1):6–25
  • Hvattum LM, Fagerholt K, Armentano VA (2009) Tank allocation problems in maritime bulk shipping. Comput Oper Res 36(11):3051–3060
  • Jetlund AS, Karimi I (2004) Improving the logistics of multi-compartment chemical tankers. Comput Chem Eng 28(8):1267–1283
  • Kobayashi K, Kubo M (2010) Optimization of oil tanker schedules by decomposition, column generation, and time-space network techniques. Jpn...
  • Korsvik JE, Fagerholt K (2010) A tabu search heuristic for ship routing and scheduling with flexible cargo quantities. J Heurist 16(2):117–137
  • Korsvik JE, Fagerholt K, Laporte G (2011) A large neighbourhood search heuristic for ship routing and scheduling with split loads. Comput...
  • Ladage A, Baatar D, Krishnamoorthy M, Mahajan A (2021) A revised formulation, library and heuristic for a chemical tanker scheduling problem....
  • Malaguti E, Martello S, Santini A (2018) The traveling salesman problem with pickups, deliveries, and draft limits. Omega 74:50–58
  • Neo KH, Oh HC, Karimi I (2006) Routing and cargo allocation planning of a parcel tanker. Comput Aided Chem Eng 21:1985–1990
  • Ostermeier M, Henke T, Hübner A, Wäscher G (2021) Multi-compartment vehicle routing problems: stateof-the-art, modeling framework and future...
  • Ronen D (1983) Cargo ships routing and scheduling: survey of models and problems. Eur J Oper Res 12(2):119–126
  • Ronen D (1993) Ship scheduling: the last decade. Eur J Oper Res 71(3):325–333
  • Rothberg E (2007) An evolutionary algorithm for polishing mixed integer programming solutions. Inf J Comput 19(4):534–541
  • Shen Q, Chu F, Chen H (2011) A Lagrangian relaxation approach for a multi-mode inventory routing problem with transshipment in crude oil transportation....
  • Uggen KT, Fodstad M, Nørstebø VS (2013) Using and extending fix-and-relax to solve maritime inventory routing problems. TOP 21(2):355–377
  • Vilhelmsen C, Lusby RM, Larsen J (2017) Tramp ship routing and scheduling with voyage separation requirements. OR Spectrum 39(4):913–943
  • Wang X, Arnesen MJ, Fagerholt K, Gjestvang M, Thun K (2018) A two-phase heuristic for an in-port ship routing problem with tank allocation....
  • Yamashita D, da Silva BJV, Morabito R, Ribas PC (2019) A multi-start heuristic for the ship routing and scheduling of an oil company. Comput...