The vessel swap-body routing problem.

Abstract

This paper introduces the Vessel Swap-Body Routing problem (VSBR), a generalization of the pickup and delivery problem with time windows, which considers freight distribution between ports located

throughout an inland waterway network. Subject to time windows and precedence constraints, each customer request is associated with a number of containers and must be served via a single body. Bodies

are capacitated components that cannot move independently and must therefore be towed by a vessel. Bodies can be transferred between vessels at customer locations or transfer points in order to reduce

overall costs. Vessels and bodies can end their routes at any location, meaning they do not need to return to a depot. Moreover, every vessel-body combination is permitted, which greatly expands the size

of the solution search space. Although body transfers constitute a fundamental component of this realworld problem, the flexibility such transfers engender poses a huge logistical challenge to the human

planners tasked with efficiently scheduling vessel routes. In this paper we model the VSBR as an optimization problem and introduce complementary approaches for solving it. We propose a mixed integer

programming formulation and a heuristic approach with tailored neighborhoods for body transfers. To

help stimulate further research, a set of instances is introduced based on real-world data and benchmarks are made publicly available.