Hub-and-spoke network design and fleet deployment for string planning of liner shipping

All shipping liner companies divide their service regions into several rotations (strings) in order to operate their container vessels. A string is the ordered set of ports at which a container vessel will call. Each port is usually called at no more than twice along one string, although a single port may be called at several times on different strings. The size of string dictates the number of vessels required to offer a given frequency of service. In order to better use their shipping capacity, groups of Liner Service Providers sometimes make a short term agreement to merge some of their service routes (in a certain region) into one main ocean going rotation and p feeder rotations. In order to minimize the weighted sum of transit time, and fixed deployment costs, this paper proposes a mixed integer linear programming model of the network design, and an allocation of proper capacity size and frequency setting for every rotation. Given that none of the existing general-purpose MIP solvers is able to solve even very small problem instances in a reasonable time, we propose a Lagrangian decomposition approach which uses a heuristic procedure and is capable of obtaining practical and high quality solutions in reasonable times. The model will be applied on a real example, and we shall present some of the results obtained by our model which show how it facilitates a better use of assets and a significant reduction in the use of fuel, therefore allowing a more environmentally friendly service.