Analyzing complex service structures in liner shipping network design

One of the most important strategic decisions of a liner shipping company is the design of a set of cyclic routes, services, for container vessels to provide transport for goods from origins to destinations. This problem is called the liner shipping network design problem (LSNDP). The cyclic nature of the services as well as the possibility of transshipping cargoes between services makes the problem difficult to solve for large instances. Therefore, it is common to make assumptions regarding the structure of the services. We analyze the effect of different structures ranging from simple ones visiting a port once in a service, to butterfly services where one port can be visited twice in a service and a more general structure where every port in a service can be visited more than once. To perform these analyses, we have developed a new mathematical model for the LSNDP where there are no limitations on the number of visits to each port. The model is solved by a branch-and-price method, where we for the sake of computational time have reduced the number of visits per port on a service to a maximum of two. The computational study shows that complex service structures can create more cost-efficient networks and that the objective value can be improved by allowing general service structures even for small sized instances.