Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem

TLDR

Ship routing and scheduling has been understudied compared to vehicle routing, yet it could yield large benefits, as exemplified by a fleet transporting ammonia between production and consumption harbors. The study presents a real ship planning problem that combines inventory management with routing under time windows, and describes its underlying mathematical model. The model determines loading and discharging quantities based on harbor production rates, stock levels, and ship visits, and is decomposed via Dantzig–Wolfe into routing and inventory subproblems that are solved with branch‑and‑bound after model adjustments. Computational results indicate that the proposed method works for the real planning problem.

Abstract

In contrast to vehicle routing problems, little work has been done in ship routing and scheduling, although large benefits may be expected from improving this scheduling process. We will present a real ship planning problem, which is a combined inventory management problem and a routing problem with time windows. A fleet of ships transports a single product (ammonia) between production and consumption harbors. The quantities loaded and discharged are determined by the production rates of the harbors, possible stock levels, and the actual ship visiting the harbor. We describe the real problem and the underlying mathematical model. To decompose this model, we discuss some model adjustments. Then, the problem can be solved by a Dantzig–Wolfe decomposition approach including both ship routing subproblems and inventory management subproblems. The overall problem is solved by branch-and-bound. Our computational results indicate that the proposed method works for the real planning problem.