Shipping service network design
This section addresses the shipping network design problem from the organisational management perspective. Firstly, the concept of liner shipping service and the complexity of the shipping network design problem are discussed. Secondly, the issues of service route design are explained with the emphasis on how to reduce the number of route structures (port rotations) by using the characteristics of empirical shipping service routes. Thirdly, a two-stage planning model is presented to tackle the single service route design problem including port rotation generation, ship deployment, empty container repositioning, and ship speed optimisation.
Hierarchical structure and complexity of network design
In the liner shipping industry, a shipping network consists of a number of liner services. Each service forms a round trip with a fixed sequence of the port of calls and a fixed frequency. In the current shipping practice, liner service frequency is on a weekly basis. A set of similar type of vessels will be deployed in the same service route. The voyage time of a round trip is given by the number of deployed vessels multiplied by seven to maintain the weekly frequency. The shipping network design aims to optimise the shipping services in terms of the structure of routes, port selection, port rotation (sequence), frequency of routes, and the assignment of ships to routes. The purpose is to maximise the net profit or minimise the total cost to meet the forecasted customer demands.
Broadly, management decisions on the shipping network design may include: how many liner service routes should be opened; how a service route should be structured in terms of port rotation and schedule; which frequency the service route should be; which type of ships and how many ships should be deployed in a service route; how the timetable of the ships should be scheduled; how the planned sailing speed should be designed; how the container fleet including empty container repositioning should be managed; and how the customer demands should be assigned over the service network. In this view, the shipping service network design includes a number of subproblems which may be tackled in a hierarchical structure as shown in Figure 5.2.
It should be noted that the subproblems in Figure 5.2 may be treated individually or jointly. Shipping service routes may be created from the given set
Figure 5.2 Hierarchical shipping network design.
of ports and optimised in a combinatorial optimisation way or selected from a pre-specified set of candidate service routes that are assumed to be designed in advance based on industrial experience.
In the liner shipping industry, customer demand can be defined as a requirement to transport a shipment (that may consist of a number of laden containers) from a specified origin to a specified destination with the arrival time information and the delivery time window. As a shipping network includes multiple interconnected service routes, it is common that some shipments may be transhipped at transhipment ports. The cost and profitability of the shipping service network will depend on the paths chosen to transport the shipments and the vessels deployed on service routes.
It has been proved that the problem of designing a liner shipping network is NP-hard as it can be reduced to a Knapsack problem (Agarwal and Ergun 2008a). Later on, Brouer et al. (2014) further proved that the liner shipping network design problem is strongly NP-hard by reducing it to a travelling salesman problem. Even if the service network design problem is narrowed down to select the best subset of candidate service routes from a pre-specified set of service routes to meet the given customer demands, Brouer et al. (2014) showed that this problem is also strongly NP-hard, as it can be reduced to a set-covering problem (e.g. choose the cheapest set of service routes to cover all ports). In addition, ship fleet deployment and cargo routing are often implied within shipping network design problem, their computational complexity should be discussed. We have the following results.
The complexity of the liner shipping network design problem can be described as follows: (i) the problem of designing a service network for liner shipping is strongly NP-hard; (ii) the problem of designing a liner shipping network from a set of pre-specified service routes is also strongly NP-hard; (iii) deploying a fleet of vessels over a given set of service routes is NP-hard; and (iv) shipment routing in a given shipping network is NP-hard if shipments are not allowed to splittable.
Proof: assertions (i) and (ii) are implied in Brouer et al. (2014). For assertion (iii), we reduce the problem to the Knapsack problem. Suppose given a set of service routes N, a fleet of vessels W with the same type, and each service requires w, vessels to maintain weekly frequency and generate profit q. We assume that these service routes are disjoint. Then, the selection of a subset service route subject to the vessel fleet W to maximise the total profit is equivalent to the 0—1 Knapsack problem. For assertion (iv), we can similarly reduce the problem to the Knapsack problem. Suppose given a set of service routes N, with each route having a common leg, all shipments have to be carried across this leg. The total capacity of the leg is denoted by M. Each shipment has a volume иу and revenue c,. The selection of the shipments to maximise the total revenue subject to service capacity is equivalent to the 0—1 Knapsack problem. This completes the proof.