An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping

• We study a problem that combines tramp shipping with a VMI service.
• We use a novel method to convert inventories into cargoes with time windows.
• An iterative heuristic combining cargo generation and an ALNS heuristic is presented to solve the problem.
• The factors that influence the benefits obtainable through VMI are analyzed.

In this paper a vendor managed inventory (VMI) service in tramp shipping is considered. VMI takes advantage of introducing flexibility in delivery time and cargo quantities by transferring inventory management and ordering responsibilities to the vendor which in this case is a shipping company. A two-phase heuristic is proposed to determine routes and schedules for the shipping company. The heuristic first converts inventories into cargoes, thus turning the problem into a classic ship routing and scheduling problem. It then uses adaptive large neighborhood search to solve the resulting cargo routing and scheduling problem. The heuristic iteratively changes the cargoes generated to handle the customer’s inventories, based on the information obtained from an initial solution. Computational results are presented, discussed and compared with exact solutions on large realistic instances. The results reveal the potential savings from converting traditional contracts of affreightment to an integrated VMI service. The factors that influence the benefits obtainable through VMI are also analyzed.