Column generation heuristics for ship routing and scheduling problems in crude oil transportation with split deliveries

•We present a column generation heuristics for crude oil transportation.•The problem is formulated as a multi-item split pickup ship routing problem with finite capacity to minimize the total costs.•An efficient heuristic algorithm with column generation is developed to find a good solution with practical constraints.•Computational studies demonstrate the effectiveness of the proposed algorithm for a real data.

We propose a column generation based heuristic algorithm to solve a ship routing and scheduling problem for crude oil transportation with split deliveries. The problem is to find an optimal assignment and sequence and loading volume of demand simultaneously in order to minimize the total distance satisfying the capacity of tankers. The problem can be considered as a multi-product heterogeneous fleet split pickup ship routing problem with finite capacity and loading constraints. An efficient heuristic algorithm based on the column generation method is developed to generate a feasible solution taking into account of practical constraints. The performance of the proposed method is compared with the branch and bound algorithm and that of human operators. Computational results demonstrate the effectiveness of the proposed algorithm for a real case.