A method for solving ship routing problemswith inventory constraints

We present an optimisation-based solution approach for a real ship planning problem,which is a combination of a variant of the multi-vehicle pickup and delivery problemwith time windows (m-PDPTW), and a multi-inventory model. This problem involves thedesign of a set of minimum cost routes for a fleet of heterogeneous ships servicing a set ofproduction and consumption harbours with a single product (ammonia). The production andinventory information at each harbour, together with the ship capacities and the location ofthe harbours, determine the number of possible arrivals at each harbour during the planningperiod, the time windows for start of service and the load quantity intervals at each arrival.We call this problem the inventory pickup and delivery problem with time windows -IPDPTW. In the mathematical programming model, we duplicate some of the variables anduse a Dantzig - Wolfe decomposition approach. Then the IPDPTW decomposes into a sub-problemfor each harbour and each ship. By synchronising the solutions from both types ofsubproblems, we get extra constraints in the master problem as compared to the masterproblem for the m-PDPTW discussed in the literature. The LP-relaxation of the masterproblem is solved by column generation, where the columns represent ship routes or harbourvisit sequences. Finally, this iterative solution process is embedded in a branch-and-boundsearch to make the solution integer optimal. Our computational results indicate that theproposed method works for the real planning problem. Copyright Kluwer Academic Publishers 1998