Tighter MIP Models for Barge Container Ship Routing

This paper addresses the problem of optimal planning of a line for a barge container shipping company. Given estimated weekly splittable demands between pairs of ports and bounds for the turnaround time, our goal is to determine the subset of ports to be called and the amount of containers to be shipped between each pair of ports, so as to maximize the profit of the shipping company. In order to save possible leasing or storage costs of empty containers at the respective ports, our approach takes into account the repositioning of empty containers. In our setting we determine a single route following the outbound-inbound principle (i.e., the predefined ordering of ports is given, together with the starting and the ending port). We first propose two new MIP formulations that are tailored for barge container ship routing in the inland waterway transport. We then demonstrate that the models can be extended to general maritime shipping given the outbound-inbound principle. On the publicly available set of benchmark instances for barge container routing, our models significantly outperform the existing approaches from the literature. We also propose some variants of the problem that are of interest for practitioners in the domain, including optimization of the turnaround time, allowing multiple round-trips, and dealing with unsplittable demands. Numerical experiments are provided to compare the computational performance of the models and the impact of both empty container repositioning and unsplittable demands on the total profit.



View Tighter MIP Models for Barge Container Ship Routing