Long-haul liner service route design with ship deployment and empty container repositioning

•Model liner service route design with ship deployment and empty repositioning.•Propose a novel notion of service route topological structure.•Establish the relationship between container flows and route topological structure.•Propose a three-stage solution method that is practically more applicable.

This paper proposes a single liner long-haul service route design problem including route structure design, ship deployment and empty container repositioning. The objective of this problem is to minimise the total cost incurred from a liner long-haul service route, including ship related costs, fuel consumption costs, port related costs, laden containers and empty container inventory-in-transition costs. We propose a three-stage optimisation method to tackle the problem. We introduce the notions of topological structure and ship load factors, which lead to a classification of shipping route structures and the relationships between the container flow pattern and the route structure. This greatly simplifies the route structure design decisions at the first stage and enables us to develop an efficient heuristic algorithm to reposition empty containers at the second stage. The ship deployment problem concerning the number of ships and their capacity and sailing speeds is considered at the third stage. The model takes advantage of the characteristics of the existing route structures and can solve the service route design problems effectively from the practical perspective. In addition, the established relationships between the load factors and the route structure provide useful insights into ship utilisation and route structure choice. Case studies are presented to show efficiency and applicability of the proposed research methodology.