The Heterogeneous Fleet Vehicle Routing Problem with Draft Limits

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.