Liner Shipping Cargo Allocation with Repositioning of Empty Containers

This paper is concerned with the cargo allocation problem considering empty repositioning of containers for a liner shipping company. The aim is to maximize the profit of transported cargo in a network, subject to the cost and availability of empty containers. The formulation is a multi-commodity flow problem with additional inter-balancing constraints to control repositioning of empty containers. In a study of the cost efficiency of the global container-shipping network, Song et al. (2005) estimate that empty repositioning cost constitutes 27% of the total world fleet running cost. An arc-flow formulation is decomposed using the Dantzig-Wolfe principle to a path-flow formulation. A linear relaxation is solved with a delayed column generation algorithm. A feasible integer solution is found by rounding the fractional solution and adjusting flow balance constraints with leased containers. Computational results are reported for seven instances based on real-life shipping networks. Solving the relaxed linear path-flow model with a column generation algorithm outperforms solving the relaxed linear arc-flow model with the CPLEX barrier solver even for very small instances. The proposed algorithm is able to solve instances with 234 ports, 16,278 demands over 9 time periods in 34 min. The integer solutions found by rounding down are computed in less than 5 s and the gap is within 0.01% from the upper bound of the linear relaxation. The solved instances are quite large compared to those tested in the reviewed literature.