Abstract
This paper introduces a new problem to the OR community that combines traditional tramp shipping with a vendor managed inventory (VMI) service. Such a service may replace the more traditional contract of affreightment (COA) which for decades has been the standard agreement between a tramp shipping company and a charterer. We present a new mathematical formulation describing the routing and scheduling problem faced by a tramp shipping company that offers a VMI service to its customers. The problem is formulated as an arc-flow model, and is then reformulated as a path-flow model which is solved using a hybrid approach that combines branch-and-price with a priori path-generation. To solve larger, and more realistic, instances we present a heuristic path-generation algorithm. Computational experiments show that the heuristic approach is much faster than the exact method, with insignificant reductions in solution quality. Further, we investigate the economic impact of introducing a VMI service, by comparing the results obtained with the new model with results obtained by solving the traditional routing and scheduling problem faced by tramp shipping companies using COA. The computational results show that it is possible to substantially increase supply chain profit and efficiency by replacing the traditional COAs with VMI services.