A method for solving ship routing problems with 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 problem with time windows (m-PDPTW), and a multi-inventory model. This problem involves the design of a set of minimum cost routes for a fleet of heterogeneous ships servicing a set of production and consumption harbours with a single product (ammonia). The production and inventory information at each harbour, together with the ship capacities and the location of the harbours, determine the number of possible arrivals at each harbour during the planning period, 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 and use a Dantzig–Wolfe decomposition approach. Then the IPDPTW decomposes into a subproblem for each harbour and each ship. By synchronising the solutions from both types of subproblems, we get extra constraints in the master problem as compared to the master problem for the m-PDPTW discussed in the literature. The LP-relaxation of the master problem is solved by column generation, where the columns represent ship routes or harbour visit sequences. Finally, this iterative solution process is embedded in a branch-and-bound search to make the solution integer optimal. Our computational results indicate that the proposed method works for the real planning problem.