Decomposition of a Combined Inventory and Time Constrained Ship Routing Problem

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.