Shipping service route design

The shipping service route design aims to select ports to serve and determine the sequence of the port of calls (i.e. port rotation) to form a closed-loop round trip. Some ports may be called more than once in a round trip, which are called butterfly ports. A service route design is a combinatorial optimisation problem. For example, let us consider a seven-port service route in which five of these ports may be called twice on a single round-trip. This gives rise to a total of 12 portcalls and nearly 12! ~ 10^H different port rotations. It is computationally difficult to evaluate all these port rotations. Flowever, by making use of the characteristics of the empirical shipping service routes, it is possible to narrow down the candidates of port rotations substantially, even to a manageable size.

Definition 5.1

A directed simple cycle is defined as a graph in which all nodes are connected forming a single closed loop with all edges being oriented in the same direction.

For example, Figure 5.3 illustrates a shipping service route with two directed simple cycles, in which vessels are sailing from port 1 to port 2, port 3, port 4, port 5, port 6, port 7 and back to port 1 as a round-trip consecutively.

Figure 5.3 A shipping service route with two directed simple cycles.

Figure 5.4 An Asia/Europe Express with three directed simple cycles.

Empirical data showed that from the topological perspective almost all shipping service routes can be regarded as a combination of several directed simple cycles, in which any two-neighbouring directed simple cycles are joined by only one common port, i.e. the butterfly port. A real example is given in Figure 5.4, which is an Asia/Europe Express operated by COSCO shipping with the port rotation: Qingdao (QIN)—Kwangyang (KWY)-Busan (BUS)—Kaohsiung (KAO)—Yantian (YTN)—Singapore (SIN)—Hamburg (HAM)—Rotterdam (ROT)—Felixstowe (FEL)—Singapore (SIN)—Kaohsiung (KAO)—Qingdao (QIN). Topologically, this service route consists of three directed simple cycles with KAO and SIN being two butterfly ports.

Based on the empirical data from Containerisation International in 2008 (see Table 5.4), among 154 deep-sea service routes on three major trade lanes (trans-Pacific, Asia—Europe, and trans-Atlantic trade) deploying 1,092 container ships, 45% of them have only one directed simple cycle, 20% have two directed simple cycles, and 16% have three directed simple cycles. The maximum number of directed simple cycles in a service route is 9, in which 12 ships are deployed. The last column in Table 5.4 gives the average ship capacity overall services in the same category. It can be observed that all service routes can be classified into one of the nine categories in Table 5.4, which confirms that shipping service routes can indeed be characterised by

Table 5.4 Classification of deep-sea service routes in three major trade lanes (based on Song and Dong 2013)

the number of the directed simple cycles, and each port in a service route is called either once or twice in a round trip. More importantly, the majority of service routes have very few directed simple cycles. In total, 81% of the service routes have 1—3 directed simple cycles. This observation implies that the problem of designing a service route can be greatly simplified by limiting the number of directed simple cycles when generating the port rotation and route structure.

In addition, the knowledge of the port geographic locations is also very useful in designing the port rotation and route structure. For example, if a shipping service needs to connect two continents separated by an ocean (e.g. trans-Pacific or trans-Atlantic service routes), it is practical for the ship to visit each continent only once on a single round-trip. This implies that we can split the ports into two subsets according to their geographic locations, which will significantly reduce the complexity of port rotation generation. In addition, if there are no customer demands between the ports within the same continents, then it is straightforward to determine the size of the ships to deploy for a deep-sea service route connecting two continents, i.e. by taking the maximum of the total demands from one continent to the other. This would simplify the ship fleet deployment subproblem since we only need to determine the number of ships. However, if the deep-sea service route visits three continents, it becomes more complicated to determine the ship size. Nevertheless, it is noted that among 154 service routes in Table 5.4, only 26 service routes visit three or more continents.

Based on the observation of the practical service routes, a deep-sea service route can be regarded as a port rotation consisting of two-directional port call sequences including two end ports, termed head-end port and tail- end port. The sequence of portcalls on the way from the head-end port to the tail-end port is often termed as the outbound trip, while the sequence of portcalls on the way back from the tail-end port to the head-end port is termed as an inbound trip (Shintani et al. 2007). In practice, if the two ports are called in both outbound and inbound trips, their port call sequences should be in reverse order. This can be explained by the fact that if a port-pair is serviced twice in the same direction in a single round-trip, the ship utilisation will be reduced whereas the voyage time will increase unnecessarily. Therefore, the following assumptions with respect to a service route structure are reasonable.

Assumption 5.1

The route structure of a deep-sea service route should satisfy:

• (i) there is a head-end port on the rightmost (or leftmost) side and a tail-end port on the opposite side, and a round-trip voyage consists of an outbound trip and an inbound trip;
• (ii) the head-end port and the tail-end port are called only once in a round trip, and any other ports in the service route may be called twice in a round trip (as butterfly ports), but will not be called more than once in the same direction trip;
• (iii) if two ports are called in both outbound and inbound directions, their port call sequences are in reverse order;
• (iv) the shipping service route can be categorised according to the number of directed simple cycles, or the number of butterfly ports, in the route structure.