# Integrated Optimization of Port Rotation Direction and Fleet Deployment for Container Liner Shipping Routes

Authors: Jingxu Chen; Yiran Wang; Xinlian Yu; Zhiyuan Liu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

This paper provides an integrated planning methodology for the optimization of port rotation direction and fleet deployment for container liner shipping routes with consideration of demand uncertainty. We first consider a special case that demand is deterministic. A multicommodity flow network model is developed via minimizing the total network-wide cost. Its decisions are the selection of port rotation direction and fleet deployment and container routings in the shipping network. Afterward, we address the generic case that uncertain demand is considered, which is represented by potentially realizable demand scenarios. We develop a minimax regret model to procure the least maximum regret across all the demand scenarios. The proposed models are applied to an Asia-Europe-Oceania liner shipping network with 46 ports and 12 ship routes. Results could provide the liner company with a comprehensive decision tool to simultaneously determine port rotation direction and fleet deployment when tackling uncertain demand.


---

## Body

## 1. Introduction

Container transportation is a significant component of international transportation, which is vital to the sustainable development of international trade and global economy [1–8], among many others. In 2017, annual containerized trade volume was estimated at 1.83 billion tons [9]. Containers are transported by container liner shipping companies over their shipping networks. A shipping network operated by a particular liner company involves a number of weekly serviced ship routes. Each route is a sequence of port visits (port rotation) composing a directed loop in ways that ships visit the first port again after visiting the last one. A notable trait of shipping network is its prohibitively high operating cost. Hence, the liner company entails determining a set of efficient decisions so as to reduce the total operating cost. The decisions span the strategic, tactical, and operational stages, such as network design/alteration, fleet deployment, speed optimization, and schedule design [10].Among these decisions, network design/alteration and fleet deployment are two important decisions at the strategic planning level. Network alteration is a special case of network design, which strives to retrofit the existing network via minor alterations (the essential difference between network alteration and network design is that network design aims at obtaining a newly designed network with minimized network-wide cost (the result may be quite different from the existing network) while network alteration attempts to enhance an existing network where the network should not deviate too much from the existing one). The alteration of port rotation direction of existing ship routes is one manner of network alteration. Fleet deployment determines which type of ship to deploy on each ship route. The liner company can benefit from economies of scale by deploying ships with large capacity. Yet, larger ships signify higher chartering and voyage costs which may be not appropriate if demand is insufficient. At the same time, future demand is not available to be predicted accurately, which is reliant on several influencing factors [11].Uncertainty in demand complicates the analysis of the impact of port rotation direction and fleet deployment on the shipping network operation. Table1 shows a simple network containing a sole ship route. The route visits three ports with either clockwise or counterclockwise direction. There are four types of ships whose capacities are 2000 twenty-foot equivalent units (TEU), 5000 TEU, 8000 TEU, and 10000 TEU, respectively. Under three demand scenarios, the maximum number of containers transported by the ship route itself is quite different when selecting different port rotation directions and ship types. For instance, in scenario II, if clockwise direction and 2000-TEU ship type are chosen, the maximum number of containers for each O-D pair is 1000 TEU/week. In this case, the liner company needs to purchase ship slots from other companies in order to fulfill the remaining demand. If the company selects counterclockwise direction and 5000-TEU ships, all the demand of three O-D pairs can be transported by its own ship route. In addition, the transit time and associated inventory cost of containers from origin to destination may also be various, which will cause an effect on competitiveness and market share. Therefore, the problem of determining port rotation direction and fleet deployment is not trivial especially when uncertain demand is taken into account. This study investigates the integrated optimization problem with respect to these two strategic decisions for container liner shipping routes.Table 1
Impact of port rotation direction and ship capacity.
Ship capacity (TEU)2000500080001000020005000800010000Scenario I (q = 2000)q110002000200020002000200020002000q210000000000Scenario II (q = 5000)q110002500400050002000500050005000q240002500100003000000Scenario III (q = 9000)q110002500400050002000500080009000q280006500500040007000400010000Note:q1 represents the number of containers transported by this route service for each of three O-D pairs (TEU/week); q2 represents the number of containers transported by slot-purchasing for each of three O-D pairs (TEU/week).


### 1.1. Literature Review

For a liner company, the design of container liner shipping service at the strategic stage mainly subsumes network design/alteration and fleet deployment. For decades, a number of previous studies have been conducted on network design (e.g., [6, 8, 12–17]). Liner shipping network design problem is defined as follows: given a set of ports and a group of origin-destination demand pairs, network design determines the fixed cyclic itinerary of ship routes (i.e., which ports each route service should visit and in what order) such that the network-wide cost is minimized. For instance, Agarwal and Ergun [18] developed a space-time network model for liner shipping network design with cargo routing. Yet, their model did not consider transshipment costs. Meng and Wang [19] proposed a network design model incorporating hub-and-spoke structure and multiple port-calling operations. Brouer et al. [20] proved the liner shipping network design problem to be strongly NP-hard and contributed a seminal benchmark suite for global network design based on the data from the largest liner shipping company in the world (i.e., Maersk Line). In additional, some countries prohibit foreign carriers to ship cargo between two ports within the country as well as other limitations so as to protect the national trade business. Zheng et al. [21] developed a hub-and-spoke network design model considering the effect of cabotage rules. Regarding various model formulations and solution methods, we refer the readers to Brouer et al. [20]; Tran and Haasis [5] and Christiansen et al. [2] for a comprehensive review of liner shipping network design.In reality, for an existing shipping network, the liner company can hardly reshuffle its network overnight. As a compromise, network alteration aims to improve the existing network through making minor alterations [22]. Current, studies associated with network alteration are limited, which can be divided into two patterns: (i) the disassembly and reassembly of routes with the homogeneous type of ship and (ii) the alteration of port rotation directions [23]. For example, Chen et al. [23] proposed a mixed-integer programming model to obtain the optimal port rotation directions of ship routes in a given shipping network.There are numerous studies that have been dedicated to the optimization of fleet deployment. Relevant studies can be separated into two categories. The first category assumes that container shipment demand is known with complete certainty. For instance, Gelareh and Meng [24] developed a mixed integer nonlinear programming model for a short-turn fleet deployment problem, in which the optimal vessel speeds for different vessel types on different routes were considered. Liu et al. [25] proposed two models associated with fleet deployment and container flow management. Results show that the joint optimization model outperforms the sequential model in terms of improving ship capacity utilization. The second category relaxes the deterministic demand assumption and addresses the fleet deployment problem with uncertain demand. For instance, Meng and Wang [26] proposed a space-time network approach to address the practical ship fleet problem under the background of week-dependent demand. In the model of Ng [27], dependencies between shipment demands on different routes were incorporated. Some other studies investigated the fleet deployment problem in conjunction with other decisions, such as network design, frequency setting, and speed optimization (e.g., [28–33]). Readers are referred to Ng [34] for the exposition of a class of fleet deployment models.Uncertain demand can be expressed in numerous avenues. A viable way is to generate a set of potentially realizable demand scenarios based on historical demand data [35]. The liner company needs to make decisions in advance that will perform adequately under any likely to occur scenario. In other words, uncertain demand is incorporated via making it part of the decision making reasoning. Therefore, the impact of port rotation direction and fleet deployment on the shipping network operation gets more complex in the presence of uncertain demand. Numerous previous studies focus on liner shipping network design and fleet deployment, while studies of network alteration are limited. The alteration of port rotation directions is one pattern of network alteration. The mutual effect of two strategic decisions (port rotation direction and fleet deployment) gives rise to apparent influence as preliminarily described in Table 1. Nevertheless, to the authors’ knowledge, formulations that thoroughly discuss the integrated optimization of port rotation direction and fleet deployment have not been presented in the literature. This study aims to remedy the above gap in which uncertain demand is taken into account as well.


### 1.2. Objective and Contribution

The primary objective and contribution of this study is to propose two network-level models for the integrated optimization of port rotation direction and fleet deployment. In our formulations, the first model deals with the special case that demand is assumed to be deterministic. We develop a multicommodity flow network model. The objective is to minimize the total network-wide cost, which is made up of loading and discharge cost, transshipment cost, inventory cost, slot-purchasing cost, and deployment cost. The decision variables subsume the port rotation direction, fleet deployment, and container routings of all O-D pairs. The second model addresses the generic case that deterministic demand assumption is relaxed and uncertain demand is taken into account. We develop a minimax regret model, whose objective is to procure the least maximum regret across all the potentially realizable demand scenarios. The proposed two models are applied to an Asia-Europe-Oceania container liner shipping network with 46 ports and 12 ship routes.The remainder of this paper is organized as follows. Section2 describes the problem and formulates two network-level models. A numerical example is presented in Section 3. Finally, conclusions are provided in Section 4.


## 1.1. Literature Review

For a liner company, the design of container liner shipping service at the strategic stage mainly subsumes network design/alteration and fleet deployment. For decades, a number of previous studies have been conducted on network design (e.g., [6, 8, 12–17]). Liner shipping network design problem is defined as follows: given a set of ports and a group of origin-destination demand pairs, network design determines the fixed cyclic itinerary of ship routes (i.e., which ports each route service should visit and in what order) such that the network-wide cost is minimized. For instance, Agarwal and Ergun [18] developed a space-time network model for liner shipping network design with cargo routing. Yet, their model did not consider transshipment costs. Meng and Wang [19] proposed a network design model incorporating hub-and-spoke structure and multiple port-calling operations. Brouer et al. [20] proved the liner shipping network design problem to be strongly NP-hard and contributed a seminal benchmark suite for global network design based on the data from the largest liner shipping company in the world (i.e., Maersk Line). In additional, some countries prohibit foreign carriers to ship cargo between two ports within the country as well as other limitations so as to protect the national trade business. Zheng et al. [21] developed a hub-and-spoke network design model considering the effect of cabotage rules. Regarding various model formulations and solution methods, we refer the readers to Brouer et al. [20]; Tran and Haasis [5] and Christiansen et al. [2] for a comprehensive review of liner shipping network design.In reality, for an existing shipping network, the liner company can hardly reshuffle its network overnight. As a compromise, network alteration aims to improve the existing network through making minor alterations [22]. Current, studies associated with network alteration are limited, which can be divided into two patterns: (i) the disassembly and reassembly of routes with the homogeneous type of ship and (ii) the alteration of port rotation directions [23]. For example, Chen et al. [23] proposed a mixed-integer programming model to obtain the optimal port rotation directions of ship routes in a given shipping network.There are numerous studies that have been dedicated to the optimization of fleet deployment. Relevant studies can be separated into two categories. The first category assumes that container shipment demand is known with complete certainty. For instance, Gelareh and Meng [24] developed a mixed integer nonlinear programming model for a short-turn fleet deployment problem, in which the optimal vessel speeds for different vessel types on different routes were considered. Liu et al. [25] proposed two models associated with fleet deployment and container flow management. Results show that the joint optimization model outperforms the sequential model in terms of improving ship capacity utilization. The second category relaxes the deterministic demand assumption and addresses the fleet deployment problem with uncertain demand. For instance, Meng and Wang [26] proposed a space-time network approach to address the practical ship fleet problem under the background of week-dependent demand. In the model of Ng [27], dependencies between shipment demands on different routes were incorporated. Some other studies investigated the fleet deployment problem in conjunction with other decisions, such as network design, frequency setting, and speed optimization (e.g., [28–33]). Readers are referred to Ng [34] for the exposition of a class of fleet deployment models.Uncertain demand can be expressed in numerous avenues. A viable way is to generate a set of potentially realizable demand scenarios based on historical demand data [35]. The liner company needs to make decisions in advance that will perform adequately under any likely to occur scenario. In other words, uncertain demand is incorporated via making it part of the decision making reasoning. Therefore, the impact of port rotation direction and fleet deployment on the shipping network operation gets more complex in the presence of uncertain demand. Numerous previous studies focus on liner shipping network design and fleet deployment, while studies of network alteration are limited. The alteration of port rotation directions is one pattern of network alteration. The mutual effect of two strategic decisions (port rotation direction and fleet deployment) gives rise to apparent influence as preliminarily described in Table 1. Nevertheless, to the authors’ knowledge, formulations that thoroughly discuss the integrated optimization of port rotation direction and fleet deployment have not been presented in the literature. This study aims to remedy the above gap in which uncertain demand is taken into account as well.


## 1.2. Objective and Contribution

The primary objective and contribution of this study is to propose two network-level models for the integrated optimization of port rotation direction and fleet deployment. In our formulations, the first model deals with the special case that demand is assumed to be deterministic. We develop a multicommodity flow network model. The objective is to minimize the total network-wide cost, which is made up of loading and discharge cost, transshipment cost, inventory cost, slot-purchasing cost, and deployment cost. The decision variables subsume the port rotation direction, fleet deployment, and container routings of all O-D pairs. The second model addresses the generic case that deterministic demand assumption is relaxed and uncertain demand is taken into account. We develop a minimax regret model, whose objective is to procure the least maximum regret across all the potentially realizable demand scenarios. The proposed two models are applied to an Asia-Europe-Oceania container liner shipping network with 46 ports and 12 ship routes.The remainder of this paper is organized as follows. Section2 describes the problem and formulates two network-level models. A numerical example is presented in Section 3. Finally, conclusions are provided in Section 4.


## 2. Problem Statement and Model Development

Consider a liner company which operates a number of ship routes, denoted by the setR. Each ship route r∈R maintains weekly service frequency. The company regularly serves a group of ports denoted by the set P. Let pri denote the port corresponding to the ith port of call on route r. The port rotation of ship route r composes a directed loop, which is expressed as(1)pr1⟶pr2⟶⋅⋅⋅⟶prNr⟶pr1,where Nr denotes the number of ports of call on ship route r. Define Ir:=1,2,…,Nr and pr,Nr+1:=pr1. The voyage from port of call i to port of call i+1 is called leg i, and leg Nr is the voyage from port of call Nr to the first port of call. Figure 1 presents an illustrative liner service network, which contains three ship routes denoted by R=1,2,3 and seven ports denoted by P=HK,JK,SG,XM,CB,CN,CC. Route 1 has three legs, route 2 has five legs, and route 3 has three legs.Figure 1
A liner shipping network with three ship routes [31].Definexr1r∈R as a binary decision variable which equals 1 if the port rotation direction of ship route r is reversed and 0 otherwise. Let V be the set of ship types. Ships of the same type in each route r∈R are assumed to be homogeneous in their capacity, deployment cost, and other ship-specific characteristics. Let Ev (TEU) denote the capacity of ship type v∈V. The deployment cost of ship route r∈R per week is Crv if ship type v∈V is selected. We define xrv2 (r∈R, v∈V) as a binary decision variable which equals 1 if ships of type v are deployed on route r and 0 otherwise. Let vector x:=xr1,xrv2|r∈R,v∈V be the integrating decisions on port rotation direction and fleet deployment.Represent byW the set of O-D pairs, W=P×P. Based on historical demand data, the liner shipping company is available to generate a set of potentially realizable demand scenarios (denoted by Θ). Uncertain demand is represented by these generated demand scenarios. Under scenario ω∈Θ, the demand for O-D pair o,d∈W is designated by qωod (TEU). Decision x needs to be made before it is known which scenario is realized.Letc^p and c˜p (USD/TEU) denote the container loading cost and discharge cost charged by port p∈P, respectively. If there is no direct service between some origins and destinations, containers can be transshipped, and the transshipment cost at port p∈P is denoted by c¯p (USD/TEU). An additional time yields due to transshipment operations at port p, which is called the connection time, denoted by tp (h). In this study, we make the simplifying assumption that the connection time tp at each port p∈P is a fixed number. We let tri denote the transit time of containers on leg i of route ri∈Ir,r∈R. The inventory cost rate associated with the transit time of containers is denoted by α (USD/TEU/h).Furthermore, if the liner shipping company cannot transport all the containers by its own ships, it may purchase ship slots from other shipping companies. Letgod (USD/TEU) denote the cost for purchasing one slot for O-D pair o,d∈W. We do not consider empty containers for simplicity [36–38]. At the same time, we let Tod denote the transit time of containers of O-D pair o,d transported by the purchased slots for formulating the inventory cost.


### 2.1. Model with Deterministic Demand

We first formulate a special model that the actual scenario realizationω∈Θ is assumed to be already known. Then, the problem is to obtain the integrating decision x that minimizes the total network-wide cost when demand is deterministic.


#### 2.1.1. Multicommodity Flow Network Representation

In this study, the shipping network is converted into a multicommodity flow (MCF) network, which is an extension of Wang and Meng [22]. Let G=N,A represent the MCF network, where N is the set of nodes and A is the set of arcs in the network. In general, the definition of MCF network has two main steps. The first step is to define the topological structure (containing nodes and arcs) that can reflect the transport of container operations in this study. There are three categories of nodes, including source node, sink node and portcall node. There are six categories of arcs, including source arc, sink arc, original voyage arc, reversed voyage arc, transshipment arc, and slot-purchasing arc. The second step is to define the attributes of arcs (i.e., cost and capacity) as described in Table 2. Two steps are specifically described as follows.Table 2
Cost and capacity of arcs in the MCF network.
Type of arcCostCm,n (USD/TEU)CapacityEm,n (TEU)Arcm,n∈ASource arcAsrcc^p∞m=npsrc,n=i,pri=p,p∈P,i∈Ir,r∈RSink arcAsinkc¯p∞m=i,n=npsink,pri=p,p∈P,i∈Ir,r∈ROriginal voyage arcAvoy0αtrm∑v∈VEv1−xr1xrv2m=i,n=i+1,i∈Ir\Nr,r∈Rm=i,n=1,n=Nr,r∈RReversed voyage arcAvoy1αtrn∑v∈VEvxr1xrv2m=i,n=i−1,i∈Ir\1,r∈Rm=i,n=Nr,i=1,r∈RTransshipment arcAtranc¯p+αtp∞m=i,n=i′,pri=pr′i′=p,p∈P,i∈Ir,i′∈Ir′,r,r′∈R,Slot-purchasing arcAslotgod+αTod∞m=nosrc,n=ndsink,o,d∈WSetN is composed of three categories of nodes. First, for each port p∈P, construct one source node (denoted by npsrc) and one sink node (denoted by npsink). Let Nsrc and Nsink denote the set of newly constructed source nodes and sink nodes, respectively. The third category of nodes is termed as calls at a port. For each ship route r∈R, construct one portcall node for each port of call i∈Ir, and all these nodes constitute the set Ncall.Arcs in setA are directed, which can be grouped into six categories: (i)
Source arc setAsrc: construct an arc from npsrc to each of nodes in Ncall that represents calls at port p∈P, and all the newly constructed source arcs form the set Asrc.(ii)
Sink arc setAsink: construct an arc from each of nodes in Ncall that represents calls at port p∈P to npsink, and all the newly constructed sink arcs form the set Asink;(iii)
Original voyage arc setAvoy0: construct a voyage arc for each voyage leg with original direction, and all the original voyage arcs form the set Avoy0.(iv)
Reversed voyage arc setAvoy1: construct a voyage arc for each voyage leg with reversed direction, and all the reversed voyage arcs form the set Avoy1.(v)
Transshipment arc setAtran: if port p∈P is visited more than once, construct two opposite-direction arcs between any two nodes in Ncall that correspond to port p. All the transshipment arcs form the set Atran.(vi)
Slot-purchasing arc setAslot: for each O-D pair o,d∈W, construct an arc from nosrc to ndsink, and all the slot-purchasing arcs form the set AslotThe liner shipping network, set out in Figure1, is taken as the example. Suppose that there is a single O-D pair, W=JK,CB. Figure 2 exhibits the associated MCF network representation of this network. First, construct a source node (representing Jakarta) and a sink node (representing Colombo). The setting of the source/sink nodes enables that the containers of each O-D pair always have a unique origin and destination. Each port of call on three ship routes is indexed by a portcall node. Note that one physical port may correspond to more than one portcall node, such as Colombo which is visited twice per week.Figure 2
An illustrative O-D pair in the MCF network.Second, construct source arcs from the source node to all the portcall nodes that represents port Jakarta (arc 1). Construct sink arcs from portcall nodes that signify port Colombo to the sink node (arc 34 and 35). Add original voyage arcs corresponding to all the legs in the network, for example, arc 2, 3, and 4 of ship route 1. Add reversed voyage arcs to represent the voyage of ships on the legs with reversed direction, for example, arc 5, 6, and 7 of ship route 1. Construct transshipment arcs on behalf of the container transshipment operations. For instance, arc 28 means the transshipment at Singapore from the ship visiting Singapore as the third port of call on ship route 1, to the other ship visiting Singapore as the third port of call on ship route 2. Construct a slot-purchasing arc linking the source node to the sink node (arc 36).The cost and capacity pertinent to each category of arcs in setA is summarized in Table 2. At the same time, the set of O-D pairs in the MCF network can be represented by W⌢=nosrc,ndsink|o,d∈W⊂Nsrc×Nsink. Under scenario ω∈Θ, the demand of O-D pair nosrc,ndsink in set W⌢ is expressed as q⌢ωnosrc,ndsink=qωod. For two arbitrary nodes n,n′∈N, define q⌢ωn,n′=0 if n,n′∉W⌢.


#### 2.1.2. Model Formulation of MCF Network

To obtain the network-wide cost, we entail determining the optimal container routings of all O-D pairs in the MCF network. To this end, we definefmno,ω as a continuous decision variable signifying the number of containers (TEU) that originate from port o∈Nsrc and flow on arc m,n∈A under demand scenario ω∈Θ. The MCF network model with deterministic demand is formulated as follows:(2)MCF−ωZω=minx,fmno,ω∑m,n∈Acmn∑o∈Nsrcfmno,ω+∑r∈R∑v∈VCrvxrv2,subject to(3)∑m,n∈Afmno,ω−∑n,m∈Afnmo,ω=q⌢ωon,n≠o,−∑d∈Nsinkq⌢ωod,n=o,n∈N,o∈Nsrc,(4)∑o∈Nsrcfmno,ω≤∑v∈VEv1−xr1xrv2,m,n∈Avoy0,r∈R,(5)∑o∈Nsrcfmno,ω≤∑v∈VEvxr1xrv2,m,n∈Avoy1,r∈R,(6)∑v∈Vxrv2=1,r∈R,(7)xr1∈0,1,r∈R,(8)xrv2∈0,1,v∈V,r∈R,(9)fmno,ω≥0,m,n∈A,o∈Nsrc.The objective function, equation (2), minimizes the total network-wide cost under scenario ω∈Θ: the first term is the total cost on all the arcs in set A containing loading and discharge cost, transshipment cost, inventory cost, and slot-purchasing cost (cmn denotes the cost of arc mn as depicted in Table 2), and the second term is the deployment cost of ship routes. Equation (3) is the container flow conservation equation. Equations (4) and (5) enforce the ship capacity constraint on original voyage arcs and reversed voyage arcs, respectively. Equation (6) imposes that exactly one type of ship is deployed on each ship route. Equations (7) and (8) indicate that xr1 and xrv2 are binary variables. Equation (9) is the nonnegativity constraint.Equations (4) and (5) contain nonlinear terms xr1xrv2. Based on equation (6), these two equations can be linearized as follows:(10)∑o∈Nsrcfmno,ω≤Ev,max1−xr1,m,n∈Avoy0,r∈R,(11)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy0,r∈R,(12)∑o∈Nsrcfmno,ω≤Ev,maxxr1,m,n∈Avoy1,v∈V,r∈R,(13)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy1,r∈R,where Ev,max denotes the maximum capacity of all ship types in set V, i.e. maxv∈VEv.As a result, modelMCF−ω is reformulated to a mixed-integer linear programming (MILP) model, which can be solved by off-the-shelf MILP solvers.


### 2.2. Model with Uncertain Demand

In practice, demand is usually uncertain, which can be reflected by a set of potentially realizable demand scenarios as stated. Considering this practical circumstance, it is important to grasp the performance of decisionx across all the demand scenarios. A minimax regret model with uncertain demand (represented via scenario set Θ) is proposed next.Under scenarioω∈Θ, Zω is the optimal objective value of model MCF−ω in equation (2). Let xω denote the corresponding optimal port rotation direction and fleet deployment solution to model MCF−ω. Furthermore, we let Zx,ω be the generalized network-wide cost under scenario ω∈Θ for a given decision x. Then, maxω∈ΘZx,ω−Zω is called the maximum absolute regret that exhibits the worst-case deviation from optimality, for the given decision x over all scenarios in set Θ.The minimax regret model is to procure the optimal decisionx with the least maximum regret:(14)MMR−Θminx,fmno,ωmaxω∈ΘZx,ω−Zω.For each scenarioω∈Θ, the value of Zω can be achieved through solving model MCF−ω. We intend to linearize the objective function equation (14) by introducing an auxiliary continuous variable (denoted by M). The minimax regret model MMR−Θ is reformulated as an equivalent MILP model:(15)MMR−Θ2minx,fmno,ωM,subject to(16)M≥∑m,n∈Acmn∑o∈Nsrcfmno,ω+∑r∈R∑v∈VCrvxrv2−Zω,ω∈Θ,(17)∑m,n∈Afmno,ω−∑n,m∈Afnmo,ω=q⌢ωon,n≠o,−∑d∈Nsinkq⌢ωod,n=o,n∈N,o∈Nsrc,ω∈Θ,(18)∑o∈Nsrcfmno,ω≤Ev,max1−xr1,m,n∈Avoy0,r∈R,ω∈Θ,(19)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy0,r∈R,ω∈Θ,(20)∑o∈Nsrcfmno,ω≤Ev,maxxr1,m,n∈Avoy1,v∈V,r∈R,ω∈Θ,(21)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy1,r∈R,ω∈Θ,(22)∑v∈Vxrv2=1,r∈R,(23)xr1∈0,1,r∈R,(24)xrv2∈0,1,v∈V,r∈R,(25)fmno,ω≥0,m,n∈A,o∈Nsrc,ω∈Θ.Equation (16) ensures that auxiliary variable M is not less than the maximum value of Zx,ω−Zω for all scenarios in set Θ, which is equivalent to the nonlinear expression in equations (14), and (17) guarantees conservation of flow in each scenario. Equations (18)–(21) are linearized expressions of ship capacity constraint. Equation (22) indicates that each ship route only employs a single ship type. Equations (23) and (24) present that xr1 and xrv2 are binary variables. Equation (25) signifies that continuous variables fmno,ω are nonnegative.


## 2.1. Model with Deterministic Demand

We first formulate a special model that the actual scenario realizationω∈Θ is assumed to be already known. Then, the problem is to obtain the integrating decision x that minimizes the total network-wide cost when demand is deterministic.


### 2.1.1. Multicommodity Flow Network Representation

In this study, the shipping network is converted into a multicommodity flow (MCF) network, which is an extension of Wang and Meng [22]. Let G=N,A represent the MCF network, where N is the set of nodes and A is the set of arcs in the network. In general, the definition of MCF network has two main steps. The first step is to define the topological structure (containing nodes and arcs) that can reflect the transport of container operations in this study. There are three categories of nodes, including source node, sink node and portcall node. There are six categories of arcs, including source arc, sink arc, original voyage arc, reversed voyage arc, transshipment arc, and slot-purchasing arc. The second step is to define the attributes of arcs (i.e., cost and capacity) as described in Table 2. Two steps are specifically described as follows.Table 2
Cost and capacity of arcs in the MCF network.
Type of arcCostCm,n (USD/TEU)CapacityEm,n (TEU)Arcm,n∈ASource arcAsrcc^p∞m=npsrc,n=i,pri=p,p∈P,i∈Ir,r∈RSink arcAsinkc¯p∞m=i,n=npsink,pri=p,p∈P,i∈Ir,r∈ROriginal voyage arcAvoy0αtrm∑v∈VEv1−xr1xrv2m=i,n=i+1,i∈Ir\Nr,r∈Rm=i,n=1,n=Nr,r∈RReversed voyage arcAvoy1αtrn∑v∈VEvxr1xrv2m=i,n=i−1,i∈Ir\1,r∈Rm=i,n=Nr,i=1,r∈RTransshipment arcAtranc¯p+αtp∞m=i,n=i′,pri=pr′i′=p,p∈P,i∈Ir,i′∈Ir′,r,r′∈R,Slot-purchasing arcAslotgod+αTod∞m=nosrc,n=ndsink,o,d∈WSetN is composed of three categories of nodes. First, for each port p∈P, construct one source node (denoted by npsrc) and one sink node (denoted by npsink). Let Nsrc and Nsink denote the set of newly constructed source nodes and sink nodes, respectively. The third category of nodes is termed as calls at a port. For each ship route r∈R, construct one portcall node for each port of call i∈Ir, and all these nodes constitute the set Ncall.Arcs in setA are directed, which can be grouped into six categories: (i)
Source arc setAsrc: construct an arc from npsrc to each of nodes in Ncall that represents calls at port p∈P, and all the newly constructed source arcs form the set Asrc.(ii)
Sink arc setAsink: construct an arc from each of nodes in Ncall that represents calls at port p∈P to npsink, and all the newly constructed sink arcs form the set Asink;(iii)
Original voyage arc setAvoy0: construct a voyage arc for each voyage leg with original direction, and all the original voyage arcs form the set Avoy0.(iv)
Reversed voyage arc setAvoy1: construct a voyage arc for each voyage leg with reversed direction, and all the reversed voyage arcs form the set Avoy1.(v)
Transshipment arc setAtran: if port p∈P is visited more than once, construct two opposite-direction arcs between any two nodes in Ncall that correspond to port p. All the transshipment arcs form the set Atran.(vi)
Slot-purchasing arc setAslot: for each O-D pair o,d∈W, construct an arc from nosrc to ndsink, and all the slot-purchasing arcs form the set AslotThe liner shipping network, set out in Figure1, is taken as the example. Suppose that there is a single O-D pair, W=JK,CB. Figure 2 exhibits the associated MCF network representation of this network. First, construct a source node (representing Jakarta) and a sink node (representing Colombo). The setting of the source/sink nodes enables that the containers of each O-D pair always have a unique origin and destination. Each port of call on three ship routes is indexed by a portcall node. Note that one physical port may correspond to more than one portcall node, such as Colombo which is visited twice per week.Figure 2
An illustrative O-D pair in the MCF network.Second, construct source arcs from the source node to all the portcall nodes that represents port Jakarta (arc 1). Construct sink arcs from portcall nodes that signify port Colombo to the sink node (arc 34 and 35). Add original voyage arcs corresponding to all the legs in the network, for example, arc 2, 3, and 4 of ship route 1. Add reversed voyage arcs to represent the voyage of ships on the legs with reversed direction, for example, arc 5, 6, and 7 of ship route 1. Construct transshipment arcs on behalf of the container transshipment operations. For instance, arc 28 means the transshipment at Singapore from the ship visiting Singapore as the third port of call on ship route 1, to the other ship visiting Singapore as the third port of call on ship route 2. Construct a slot-purchasing arc linking the source node to the sink node (arc 36).The cost and capacity pertinent to each category of arcs in setA is summarized in Table 2. At the same time, the set of O-D pairs in the MCF network can be represented by W⌢=nosrc,ndsink|o,d∈W⊂Nsrc×Nsink. Under scenario ω∈Θ, the demand of O-D pair nosrc,ndsink in set W⌢ is expressed as q⌢ωnosrc,ndsink=qωod. For two arbitrary nodes n,n′∈N, define q⌢ωn,n′=0 if n,n′∉W⌢.


### 2.1.2. Model Formulation of MCF Network

To obtain the network-wide cost, we entail determining the optimal container routings of all O-D pairs in the MCF network. To this end, we definefmno,ω as a continuous decision variable signifying the number of containers (TEU) that originate from port o∈Nsrc and flow on arc m,n∈A under demand scenario ω∈Θ. The MCF network model with deterministic demand is formulated as follows:(2)MCF−ωZω=minx,fmno,ω∑m,n∈Acmn∑o∈Nsrcfmno,ω+∑r∈R∑v∈VCrvxrv2,subject to(3)∑m,n∈Afmno,ω−∑n,m∈Afnmo,ω=q⌢ωon,n≠o,−∑d∈Nsinkq⌢ωod,n=o,n∈N,o∈Nsrc,(4)∑o∈Nsrcfmno,ω≤∑v∈VEv1−xr1xrv2,m,n∈Avoy0,r∈R,(5)∑o∈Nsrcfmno,ω≤∑v∈VEvxr1xrv2,m,n∈Avoy1,r∈R,(6)∑v∈Vxrv2=1,r∈R,(7)xr1∈0,1,r∈R,(8)xrv2∈0,1,v∈V,r∈R,(9)fmno,ω≥0,m,n∈A,o∈Nsrc.The objective function, equation (2), minimizes the total network-wide cost under scenario ω∈Θ: the first term is the total cost on all the arcs in set A containing loading and discharge cost, transshipment cost, inventory cost, and slot-purchasing cost (cmn denotes the cost of arc mn as depicted in Table 2), and the second term is the deployment cost of ship routes. Equation (3) is the container flow conservation equation. Equations (4) and (5) enforce the ship capacity constraint on original voyage arcs and reversed voyage arcs, respectively. Equation (6) imposes that exactly one type of ship is deployed on each ship route. Equations (7) and (8) indicate that xr1 and xrv2 are binary variables. Equation (9) is the nonnegativity constraint.Equations (4) and (5) contain nonlinear terms xr1xrv2. Based on equation (6), these two equations can be linearized as follows:(10)∑o∈Nsrcfmno,ω≤Ev,max1−xr1,m,n∈Avoy0,r∈R,(11)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy0,r∈R,(12)∑o∈Nsrcfmno,ω≤Ev,maxxr1,m,n∈Avoy1,v∈V,r∈R,(13)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy1,r∈R,where Ev,max denotes the maximum capacity of all ship types in set V, i.e. maxv∈VEv.As a result, modelMCF−ω is reformulated to a mixed-integer linear programming (MILP) model, which can be solved by off-the-shelf MILP solvers.


## 2.1.1. Multicommodity Flow Network Representation

In this study, the shipping network is converted into a multicommodity flow (MCF) network, which is an extension of Wang and Meng [22]. Let G=N,A represent the MCF network, where N is the set of nodes and A is the set of arcs in the network. In general, the definition of MCF network has two main steps. The first step is to define the topological structure (containing nodes and arcs) that can reflect the transport of container operations in this study. There are three categories of nodes, including source node, sink node and portcall node. There are six categories of arcs, including source arc, sink arc, original voyage arc, reversed voyage arc, transshipment arc, and slot-purchasing arc. The second step is to define the attributes of arcs (i.e., cost and capacity) as described in Table 2. Two steps are specifically described as follows.Table 2
Cost and capacity of arcs in the MCF network.
Type of arcCostCm,n (USD/TEU)CapacityEm,n (TEU)Arcm,n∈ASource arcAsrcc^p∞m=npsrc,n=i,pri=p,p∈P,i∈Ir,r∈RSink arcAsinkc¯p∞m=i,n=npsink,pri=p,p∈P,i∈Ir,r∈ROriginal voyage arcAvoy0αtrm∑v∈VEv1−xr1xrv2m=i,n=i+1,i∈Ir\Nr,r∈Rm=i,n=1,n=Nr,r∈RReversed voyage arcAvoy1αtrn∑v∈VEvxr1xrv2m=i,n=i−1,i∈Ir\1,r∈Rm=i,n=Nr,i=1,r∈RTransshipment arcAtranc¯p+αtp∞m=i,n=i′,pri=pr′i′=p,p∈P,i∈Ir,i′∈Ir′,r,r′∈R,Slot-purchasing arcAslotgod+αTod∞m=nosrc,n=ndsink,o,d∈WSetN is composed of three categories of nodes. First, for each port p∈P, construct one source node (denoted by npsrc) and one sink node (denoted by npsink). Let Nsrc and Nsink denote the set of newly constructed source nodes and sink nodes, respectively. The third category of nodes is termed as calls at a port. For each ship route r∈R, construct one portcall node for each port of call i∈Ir, and all these nodes constitute the set Ncall.Arcs in setA are directed, which can be grouped into six categories: (i)
Source arc setAsrc: construct an arc from npsrc to each of nodes in Ncall that represents calls at port p∈P, and all the newly constructed source arcs form the set Asrc.(ii)
Sink arc setAsink: construct an arc from each of nodes in Ncall that represents calls at port p∈P to npsink, and all the newly constructed sink arcs form the set Asink;(iii)
Original voyage arc setAvoy0: construct a voyage arc for each voyage leg with original direction, and all the original voyage arcs form the set Avoy0.(iv)
Reversed voyage arc setAvoy1: construct a voyage arc for each voyage leg with reversed direction, and all the reversed voyage arcs form the set Avoy1.(v)
Transshipment arc setAtran: if port p∈P is visited more than once, construct two opposite-direction arcs between any two nodes in Ncall that correspond to port p. All the transshipment arcs form the set Atran.(vi)
Slot-purchasing arc setAslot: for each O-D pair o,d∈W, construct an arc from nosrc to ndsink, and all the slot-purchasing arcs form the set AslotThe liner shipping network, set out in Figure1, is taken as the example. Suppose that there is a single O-D pair, W=JK,CB. Figure 2 exhibits the associated MCF network representation of this network. First, construct a source node (representing Jakarta) and a sink node (representing Colombo). The setting of the source/sink nodes enables that the containers of each O-D pair always have a unique origin and destination. Each port of call on three ship routes is indexed by a portcall node. Note that one physical port may correspond to more than one portcall node, such as Colombo which is visited twice per week.Figure 2
An illustrative O-D pair in the MCF network.Second, construct source arcs from the source node to all the portcall nodes that represents port Jakarta (arc 1). Construct sink arcs from portcall nodes that signify port Colombo to the sink node (arc 34 and 35). Add original voyage arcs corresponding to all the legs in the network, for example, arc 2, 3, and 4 of ship route 1. Add reversed voyage arcs to represent the voyage of ships on the legs with reversed direction, for example, arc 5, 6, and 7 of ship route 1. Construct transshipment arcs on behalf of the container transshipment operations. For instance, arc 28 means the transshipment at Singapore from the ship visiting Singapore as the third port of call on ship route 1, to the other ship visiting Singapore as the third port of call on ship route 2. Construct a slot-purchasing arc linking the source node to the sink node (arc 36).The cost and capacity pertinent to each category of arcs in setA is summarized in Table 2. At the same time, the set of O-D pairs in the MCF network can be represented by W⌢=nosrc,ndsink|o,d∈W⊂Nsrc×Nsink. Under scenario ω∈Θ, the demand of O-D pair nosrc,ndsink in set W⌢ is expressed as q⌢ωnosrc,ndsink=qωod. For two arbitrary nodes n,n′∈N, define q⌢ωn,n′=0 if n,n′∉W⌢.


## 2.1.2. Model Formulation of MCF Network

To obtain the network-wide cost, we entail determining the optimal container routings of all O-D pairs in the MCF network. To this end, we definefmno,ω as a continuous decision variable signifying the number of containers (TEU) that originate from port o∈Nsrc and flow on arc m,n∈A under demand scenario ω∈Θ. The MCF network model with deterministic demand is formulated as follows:(2)MCF−ωZω=minx,fmno,ω∑m,n∈Acmn∑o∈Nsrcfmno,ω+∑r∈R∑v∈VCrvxrv2,subject to(3)∑m,n∈Afmno,ω−∑n,m∈Afnmo,ω=q⌢ωon,n≠o,−∑d∈Nsinkq⌢ωod,n=o,n∈N,o∈Nsrc,(4)∑o∈Nsrcfmno,ω≤∑v∈VEv1−xr1xrv2,m,n∈Avoy0,r∈R,(5)∑o∈Nsrcfmno,ω≤∑v∈VEvxr1xrv2,m,n∈Avoy1,r∈R,(6)∑v∈Vxrv2=1,r∈R,(7)xr1∈0,1,r∈R,(8)xrv2∈0,1,v∈V,r∈R,(9)fmno,ω≥0,m,n∈A,o∈Nsrc.The objective function, equation (2), minimizes the total network-wide cost under scenario ω∈Θ: the first term is the total cost on all the arcs in set A containing loading and discharge cost, transshipment cost, inventory cost, and slot-purchasing cost (cmn denotes the cost of arc mn as depicted in Table 2), and the second term is the deployment cost of ship routes. Equation (3) is the container flow conservation equation. Equations (4) and (5) enforce the ship capacity constraint on original voyage arcs and reversed voyage arcs, respectively. Equation (6) imposes that exactly one type of ship is deployed on each ship route. Equations (7) and (8) indicate that xr1 and xrv2 are binary variables. Equation (9) is the nonnegativity constraint.Equations (4) and (5) contain nonlinear terms xr1xrv2. Based on equation (6), these two equations can be linearized as follows:(10)∑o∈Nsrcfmno,ω≤Ev,max1−xr1,m,n∈Avoy0,r∈R,(11)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy0,r∈R,(12)∑o∈Nsrcfmno,ω≤Ev,maxxr1,m,n∈Avoy1,v∈V,r∈R,(13)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy1,r∈R,where Ev,max denotes the maximum capacity of all ship types in set V, i.e. maxv∈VEv.As a result, modelMCF−ω is reformulated to a mixed-integer linear programming (MILP) model, which can be solved by off-the-shelf MILP solvers.


## 2.2. Model with Uncertain Demand

In practice, demand is usually uncertain, which can be reflected by a set of potentially realizable demand scenarios as stated. Considering this practical circumstance, it is important to grasp the performance of decisionx across all the demand scenarios. A minimax regret model with uncertain demand (represented via scenario set Θ) is proposed next.Under scenarioω∈Θ, Zω is the optimal objective value of model MCF−ω in equation (2). Let xω denote the corresponding optimal port rotation direction and fleet deployment solution to model MCF−ω. Furthermore, we let Zx,ω be the generalized network-wide cost under scenario ω∈Θ for a given decision x. Then, maxω∈ΘZx,ω−Zω is called the maximum absolute regret that exhibits the worst-case deviation from optimality, for the given decision x over all scenarios in set Θ.The minimax regret model is to procure the optimal decisionx with the least maximum regret:(14)MMR−Θminx,fmno,ωmaxω∈ΘZx,ω−Zω.For each scenarioω∈Θ, the value of Zω can be achieved through solving model MCF−ω. We intend to linearize the objective function equation (14) by introducing an auxiliary continuous variable (denoted by M). The minimax regret model MMR−Θ is reformulated as an equivalent MILP model:(15)MMR−Θ2minx,fmno,ωM,subject to(16)M≥∑m,n∈Acmn∑o∈Nsrcfmno,ω+∑r∈R∑v∈VCrvxrv2−Zω,ω∈Θ,(17)∑m,n∈Afmno,ω−∑n,m∈Afnmo,ω=q⌢ωon,n≠o,−∑d∈Nsinkq⌢ωod,n=o,n∈N,o∈Nsrc,ω∈Θ,(18)∑o∈Nsrcfmno,ω≤Ev,max1−xr1,m,n∈Avoy0,r∈R,ω∈Θ,(19)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy0,r∈R,ω∈Θ,(20)∑o∈Nsrcfmno,ω≤Ev,maxxr1,m,n∈Avoy1,v∈V,r∈R,ω∈Θ,(21)∑o∈Nsrcfmno,ω≤∑v∈VEvxrv2,m,n∈Avoy1,r∈R,ω∈Θ,(22)∑v∈Vxrv2=1,r∈R,(23)xr1∈0,1,r∈R,(24)xrv2∈0,1,v∈V,r∈R,(25)fmno,ω≥0,m,n∈A,o∈Nsrc,ω∈Θ.Equation (16) ensures that auxiliary variable M is not less than the maximum value of Zx,ω−Zω for all scenarios in set Θ, which is equivalent to the nonlinear expression in equations (14), and (17) guarantees conservation of flow in each scenario. Equations (18)–(21) are linearized expressions of ship capacity constraint. Equation (22) indicates that each ship route only employs a single ship type. Equations (23) and (24) present that xr1 and xrv2 are binary variables. Equation (25) signifies that continuous variables fmno,ω are nonnegative.


## 3. Numerical Example

The proposed two models in Section2 are applied to an Asia-Europe-Oceania shipping network of a global liner shipping company. This network consists of 46 ports, as shown in Figure 3. Twelve ship routes are operated in the network, and the port rotation of each ship route is described in Table 3. Three types of ships are considered: 3000 TEU, 5000 TEU, and 10000 TEU. Their corresponding deployment costs are $76,900, $115,400, and $173,100 per week, respectively.Figure 3
Ports of the shipping network (source: [22]).Table 3
Port rotation of twelve ship routes.
IDPorts of call1Tokyo⟶Nagoya⟶Kobe⟶Kwangyang⟶Xingang⟶Shanghai⟶Yantian⟶Ho Chi Minh2Kaohsiung⟶ Hong Kong⟶Shanghai⟶Qingdao⟶Xingang⟶Dalian⟶Busan⟶Tokyo3Sydney⟶Xiamen⟶Shanghai⟶Dalian⟶Busan⟶Kobe⟶Yokohama4Kaohsiung⟶Hong Kong⟶Ningbo⟶Qingdao⟶Brisbane⟶Sydney⟶Melbourne5Fremantle⟶Sydney⟶Melbourne⟶Adelaide⟶Fremantle⟶Singapore6Jakarta⟶Ho Chi Minh⟶Laem Chabang⟶Singapore⟶Chittagong⟶Chennai⟶Colombo7Colombo⟶Cochin⟶Nhava Sheva⟶Karachi⟶Jebel Ali⟶Salalah8Singapore⟶Port Klang⟶Manila⟶Busan⟶Shanghai⟶Xiamen⟶Chiwan⟶Hong Kong9Salalah⟶Sokhna⟶Aqabah⟶Jeddah⟶Singapore10Southampton⟶Thamesport⟶Hamburg⟶Bremerhaven⟶Rotterdam⟶Antwerp⟶Zeebrugge⟶Le Havre11Antwerp⟶Rotterdam⟶Hamburg⟶Thamesport⟶Port Klang⟶Yantian⟶Ningbo⟶Shanghai⟶Dalian12Singapore⟶Rotterdam⟶Bremerhaven⟶Hamburg⟶Antwerp⟶Jebel Ali⟶Singapore⟶Hong Kong⟶ Ningbo⟶Busan⟶ManilaThe parameter values used are summarized as follows: the container loading costc^p, discharge cost c˜p, and the transshipment cost c¯p are $100, $100, and $150 per TEU, the unit inventory cost rate is α = 0.2 USD/TEU/h, and the connection time is tp = 3.5 days (84 h) for all the ports. The slot-purchasing cost god and the transit time Tod are assumed to be(26)god≔1000+0.2×distance between the two portsn mile,∀o,d∈W,Tod≔7×24+distance between the two portsn mile/15knots,∀o,d∈W.Both modelMCF−ω and model MMR−Θ2 can be efficiently solved using CPLEX of version 12.8 with default settings, running on a desktop with Intel Core Quad CPU Q9550 @ 2.83 GHz and 8.00 G RAM.There are 652 O-D pairs with container shipment demand in the network. Three demand scenarios are generated based on the historical container slot booking data of three months in one quarter. Specifically, the data is ordered from smallest to largest according to the weekly demand of all the O-D pairs. In this study, we partition the data into three quantiles of (nearly) equal sizes, which are denoted by low-demand quantile, medium-demand quantile, and high-demand quantile, respectively. For each of three quantiles, the mean of demand of the O-D pairs is viewed as the corresponding demand scenario.First, modelMCF−ω is solved for each demand scenario. Table 4 describes the optimal computational results of three demand scenarios. Results show that both the optimized port rotation direction and fleet deployment of twelve routes are significantly different under different demand scenarios. For example, in scenario I, the number of ship routes with reversed port rotation direction is 6 and ten routes are suggested to employ 3000-TEU ship type. Yet, in scenario II, there are only three ship routes that are recommended to reverse their port rotation direction (i.e., route 4, 10, and 11). Meantime, ship route 9 needs to utilize 10000-TEU ship type so as to satisfy all the O-D pairs in scenario II. Note that the slot purchasing cost equals 0 for three demand scenarios. It indicates that the liner company prefers to transporting all the demand by its own ship routes (even if deploying ships with larger capacity) rather than purchasing slots from other companies due to relatively high slot-purchasing cost per TEU.Table 4
Optimal results of modelMCF−ω for each demand scenario.
Optimal ResultsDemand scenarioScenario IScenario IIScenario IIITotal demand (TEU)220542704033028Total cost ($ millions/week)15.0518.0821.61Load/discharge cost4.415.416.61Inventory cost2.593.163.92Transshipment cost3.594.385.37Deployment cost4.465.135.71Slot-purchasing cost000Port rotation directionOriginal direction Count route ID6 2, 6, 7, 8, 9, 129 1, 2, 3, 4, 5,6, 7, 8, 9, 127 1, 2, 5, 6,7, 8, 12Reversed direction Count  route ID6 1, 3, 4, 5, 10, 113 4, 10, 115 3, 4, 9, 10, 11Fleet deployment3000-TEU ship Count route ID10 1, 2, 3, 4, 5, 6,7, 10, 11, 129 1, 2, 3, 4, 5,6, 7, 10, 126 1, 2, 3, 4, 5,75000-TEU ship Count route ID2 8, 92 8, 115 6, 8, 10, 11,1210000-TEU ship Count  route ID01 91 9Then, modelMMR−Θ2 is solved to obtain the optimal network when three demand scenarios are simultaneously considered (see Table 5). The optimal decisions on port rotation direction and fleet deployment of twelve routes are not identical to either of three demand scenarios. Five routes are chosen to reverse their port rotation direction (i.e., route 1, 3, 4, 10, and 11). The number of ship routes that select 3000-TEU ship type, 5000-TEU ship type and 10000-TEU ship type are 7, 4 and 1, respectively.Table 5
The optimal network of modelMMR−Θ2.
IDShip typePorts of call13000TEUTokyo⟶Ho Chi Minh⟶Yantian⟶Shanghai⟶Xingang⟶Kwangyang⟶Kobe⟶Nagoya23000TEUKaohsiung⟶Hong Kong⟶Shanghai⟶Qingdao⟶Xingang⟶Dalian⟶Busan⟶Tokyo33000TEUSydney⟶Yokohama⟶Kobe⟶Busan⟶Dalian⟶Shanghai⟶Xiamen43000TEUKaohsiung⟶Hong Kong⟶Ningbo⟶Qingdao⟶Brisbane⟶Sydney⟶Melbourne53000TEUFremantle⟶Sydney⟶Melbourne⟶Adelaide⟶Fremantle⟶Singapore63000TEUJakarta⟶Ho Chi Minh⟶Laem Chabang⟶Singapore⟶Chittagong⟶Chennai⟶Colombo73000TEUColombo⟶Cochin⟶Nhava Sheva⟶Karachi⟶Jebel Ali⟶Salalah85000TEUSingapore⟶Port Klang⟶Manila⟶Busan⟶Shanghai⟶Xiamen⟶Chiwan⟶Hong Kong910000TEUSalalah⟶Sokhna⟶Aqabah⟶Jeddah⟶Singapore105000TEUSouthampton⟶Le Havre⟶Zeebrugge⟶Antwerp⟶Rotterdam⟶Bremerhaven⟶Hamburg⟶Thamesport115000TEUAntwerp⟶Dalian⟶Shanghai⟶Ningbo⟶Yantian⟶Port Klang⟶Thamesport⟶Hamburg⟶Rotterdam125000TEUSingapore⟶Rotterdam⟶Bremerhaven⟶Hamburg⟶Antwerp⟶Jebel Ali⟶Singapore⟶Hong Kong⟶Ningbo⟶Busan⟶ManilaTable6 further compares the results of absolute regret pertinent to four various decisions x. The first three columns denotes the optimal x of model MCF−ω for each demand scenario in Table 4. The last column denotes the optimal decision x of model MMR−Θ2 in Table 5. The last row presents the maximum regret across all three demand scenarios. Though xI, xII, and xIII is the optimal port rotation direction and fleet deployment decisions for the corresponding single demand scenario, their performance gets worse when any of the other two various scenarios occurs. For example, when xI is applied to demand scenario III, the absolute regret attains $ 10.53 million per week since about 6.4% demand needs to be transported through purchasing slots from other liner companies. Therefore, the issue of demand uncertainty cannot be neglected. Model MMR−Θ2 procures that the least maximum regret across all three scenarios is $1.13 million per week. Furthermore, results in Table 6 show that the maximum regret of xI (regarding the optimal decision of low-demand scenario) is apparently higher than the results of xII and xIII (regarding the optimal decisions of medium-demand scenario and high-demand scenario, respectively). It indicates that deploying ships with relatively larger capacity seems to be a better choice for the liner company. Otherwise, purchasing slots from other liner companies will results in a significant increase of operating cost when confronting abruptly high demand.Table 6
Results of absolute regret (unit: $ million/week).
xIxIIxIIIxΘDemand scenario I—0.701.251.13Demand scenario II2.10—0.470.37Demand scenario III10.532.92—0.09Maximum regret10.532.921.251.13In addition, we analyze the leg-based ship capacity utilization, which is termed as the number of containers on one leg divided by the associated route capacity. Figure4 depicts the fluctuation of ship capacity utilization of 12 routes under three demand scenarios. Results exhibit that route 6 is the busiest ship route that the ship capacity utilization of the majority of its legs exceeds 50%. On the contrary, route 2 has the lowest leg-based ship capacity utilization, whose average value is only around 9.5%. Regarding the particularly low-utilized route (like route 2), ship capacity is less likely to be fully used even in the event of confronting abruptly high demand. In such case, the associated remaining ship slots can be open to other companies in advance in a relatively low slot-purchasing cost. If ship capacity utilization of some routes is always in a low condition, these routes can be considered canceled or access to some adjacent ports in order to attract more demand.Figure 4
Ship capacity utilization of twelve ship routes.


## 4. Conclusions

This paper focused on the optimization of port rotation direction and fleet deployment for container liner shipping routes. When demand is assumed to be deterministic, a multicommodity flow network model was formulated. The objective aimed to minimize the total network-wide cost, which consists of loading and discharge cost, transshipment cost, inventory cost, slot-purchasing cost, and deployment cost. Later, we relaxed deterministic demand assumption and accounted for uncertain demand which is represented by a set of potentially realizable demand scenarios. A minimax regret model was developed, with the objective of least maximum regret across all the demand scenarios. Finally, a case study of an Asia-Europe-Oceania container liner shipping network with 46 ports and 12 ship routes was conducted based on CPLEX solver. The computational results indicate that the practical implication of the proposed models is beneficial to reduce the operating cost especially when uncertain demand is considered.Admittedly, our proposed models come with some limitations. The further improvements and future research directions are as follows: (i) in this study, the minimax regret model is used to handle uncertain demand. Other methods such as stochastic programming model and robust optimization model can be systematically compared to explore the effect of demand uncertainty; (ii) more practical circumstances of the liner shipping business can be incorporated into the model formulation, such as berth resource allocation in container terminal, which influences the arrival and departure time of ships. The authors recommend that future studies could focus on these issues.



---

*Source: 3592460-2021-12-07.xml*