Over the past two decades, international maritime transport has been characterized by the advent of ever larger ships. This phenomenon is known as naval gigantism. If, on the one hand, naval gigantism allows to reduce transport costs by exploiting the economies of scale achievable by large ships, on the other hand, it implies a series of operational issues. Indeed, due to their large draft, such giant vessels are not allowed to enter small ports when fully or near-fully loaded, and in some cases, they cannot enter such small ports at all. In fact, their draft can strongly vary depending on the load on board. This implies restrictions for vessels in accessing ports, which impact not only at the strategical level on the fleet sizing problem, but also at the tactical/operational level, on the sequence of port visits among each route. In fact, given a set of ports that a ship has to visit, determining the optimal sequence of visits becomes a very challenging issue, as the sequence that gives the shortest travel distance (i.e., the smallest travel cost) may prove infeasible due to draft limit restrictions for accessing ports. Furthermore, the same sequence of ports, which may be infeasible for a large ship, may become viable if operated by a smaller ship. On the other hand, due to the economy of scale, travel costs per load unit are generally much lower for large ships than for small ones. Therefore, the draft restrictions also affect the fleet sizing problem. In this paper, we introduce the Heterogeneous Fleet Vehicle Routing Problem with Draft Limits (HF-VRP-DL). We propose a mixed integer programming formulation and several valid inequalities to strengthen it. Since the mathematical model is able to handle only small-sized instances, to address larger instances we propose a Large Neighborhood Search matheuristic (LNS) and an Iterated Local Search matheuristic (ILS). Computational tests carried out show excellent performances of the proposed approach. Further analysis is provided on the impact of the instance layout on the computation time required to solve the problem to optimality.

The Heterogeneous Fleet Vehicle Routing Problem with Draft Limits

Paolo Fadda;Simona Mancini
;
Patrizia Serra;Gianfranco Fancello
2023

Abstract

Over the past two decades, international maritime transport has been characterized by the advent of ever larger ships. This phenomenon is known as naval gigantism. If, on the one hand, naval gigantism allows to reduce transport costs by exploiting the economies of scale achievable by large ships, on the other hand, it implies a series of operational issues. Indeed, due to their large draft, such giant vessels are not allowed to enter small ports when fully or near-fully loaded, and in some cases, they cannot enter such small ports at all. In fact, their draft can strongly vary depending on the load on board. This implies restrictions for vessels in accessing ports, which impact not only at the strategical level on the fleet sizing problem, but also at the tactical/operational level, on the sequence of port visits among each route. In fact, given a set of ports that a ship has to visit, determining the optimal sequence of visits becomes a very challenging issue, as the sequence that gives the shortest travel distance (i.e., the smallest travel cost) may prove infeasible due to draft limit restrictions for accessing ports. Furthermore, the same sequence of ports, which may be infeasible for a large ship, may become viable if operated by a smaller ship. On the other hand, due to the economy of scale, travel costs per load unit are generally much lower for large ships than for small ones. Therefore, the draft restrictions also affect the fleet sizing problem. In this paper, we introduce the Heterogeneous Fleet Vehicle Routing Problem with Draft Limits (HF-VRP-DL). We propose a mixed integer programming formulation and several valid inequalities to strengthen it. Since the mathematical model is able to handle only small-sized instances, to address larger instances we propose a Large Neighborhood Search matheuristic (LNS) and an Iterated Local Search matheuristic (ILS). Computational tests carried out show excellent performances of the proposed approach. Further analysis is provided on the impact of the instance layout on the computation time required to solve the problem to optimality.
Routing; Heterogeneous fleet; Draft limits; Large Neighborhood Search; Matheuristic; Maritime transportation
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0305054822002544-main.pdf

Solo gestori archivio

Descrizione: articolo online
Tipologia: versione editoriale
Dimensione 2.04 MB
Formato Adobe PDF
2.04 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
VRP_draft_limits_accepted version.pdf

embargo fino al 05/10/2025

Descrizione: articolo completo
Tipologia: versione post-print
Dimensione 530.06 kB
Formato Adobe PDF
530.06 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/345220
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact