Single string planning problem arising in liner shipping industries: A heuristic approach

We propose an efficient heuristic approach for solving instances of the Single String Planning Problem (SSPP) arising in the liner shipping industry. In the SSPP a Liner Service Provider (LSP) only revises one of its many operational strings, and it is assumed that the other strings are unchangeable. A string is a service route composed of a sequence of port calls-a call is a visit to a port followed by loading/unloading operations made by a vessel. In a string the vessel's round trip terminates at the same port that it started from, and the port calls follow a published itinerary. The SSPP is regularly encountered by all LSPs, and a major part of their seasonal network planning process is devoted to repeatedly solving SSPP for different regions using experts' knowledge. Despite the practical importance of the problem, very little has been written about it in the literature. A revision is carried out in the form of a controlled re-sequencing, insertion and elimination of ports from along the current string, given a set of ports limited to those that exist on the string and a set of potential ones. The outcome determines the required capacity, service level (frequency), call sequence, etc., corresponding to the LSP's seasonal strategy. Exact decomposition methods are limited and can solve only very small size instances-small in terms of the number of ports, vessel classes, vessel number and commodities. In contrast, the proposed heuristic method is an efficient approach for obtaining high quality and practical solutions to real-size instances in significantly less computational time.