Modelling path flows for a combined ship routing and inventory management problem

We consider a combined time constrained ship routing and inventory management problem. A fleet of ships transports a single product between production and consumption harbours. The transporter has the responsibility for keeping the stock level within its limits at all actual harbours, and there should be no need to stop the production at any harbours due to missing transportation possibilities. The number of arrivals to each harbour and the quantities loaded and discharged at each arrival are determined by the continuous production rates at the harbours, the stock limits and the actual ships visiting the harbours. We use a path flow formulation for this planning problem, and generate paths for each ship including information about the geographical route, the load quantity and start time at each harbour arrival. In addition, we generate paths for each harbour including information about the number of arrivals to the harbour, the load quantity and start time at each harbour arrival. We emphasise the formulation of the path generation problems which are subproblems in the total planning problem. The generated paths appear as columns in a path flow problem which corresponds to a master problem. We use a column generation approach to solve the continuous problem. The solution is made integer optimal by branch-and-bound. Computational results indicate that a path flow formulation and an optimisation based solution approach work for real instances of the planning problem.