Network flow models for ECR in complex shipping networks
This section considers a shipping network consisting of multiple service routes. When multiple service routes are considered, it is possible and common that transhipments will occur. In other words, a container may be lifted off the vessel in one service route at a port and then lifted on a vessel in another service route at the same port. For example, large container ports such as Singapore, Hong Kong, and Rotterdam involve a large number of transhipments that exceed their 50% of the port throughput.
The following assumptions are made to facilitate the model formulation:
- (i) The weekly demands for any port-pair are constant.
- (ii) Shipment is splittable; i.e., it can be fulfilled partially in different routes.
With the above assumptions, a linear programming model can be formulated to deal with both laden container routing and empty container repositioning in a given shipping network. We present an origin—destination (O-D)-link- based model below. It should be noted that if assumption (ii) is removed, then the model will become a mixed-integer programming model instead of a linear programming model. We introduce the notation as follows (some notation is based on Lee and Song 2017):
Input parameters:
P: the set of ports in the shipping network;
R: the set of shipping routes in the shipping network;
Rp. the set of routes that call at port peP;
Nf: the number of port calls on the route reR;
I,: the set of port call indices on the route reR, i.e. I,:=
{1,2, ...,Nr};
p(ri): the port that corresponds to the ith port call on route r;
I, p. the set of port call indices corresponding to port p on the route
reR, i.e. I, p:= {iel, p{ri) = p};
od: an index to represent the O-D port-pair from port oeP to port
deP;
D0(j: the weekly demand from port oeP to port deP;
Cp, C‘p, C'p. the unit cost of loading, unloading, transhipping containers at port peP;
C„ : the unit cost of transporting laden containers on vessel on leg
i on route reR;
C^: the unit penalty cost for lost sales for the od demand;
Capr the vessel capacity on route reR;
Decision variables:
yL ri’ xod ri: t^e number of laden (empty) containers for od that are loaded on the ith port call on route r;
y'od ri’ xod ri: t^e number of laden (empty) containers for od that are unloaded on the /th port call on route r;
i'od ri’ xod ri' t^e number of laden (empty) containers for od that are carried on board on leg i (from the ith port call to the (i+l)th port call) on route r;
y0l/: the fulfilled demand for od port-pair.
xp: the number of empty containers to be repositioned out of port p.
xo(f. the number of empty containers to be repositioned from port о
to port d.
A few intermediate variables are introduced to simplify the narrative. Let у Ур, and y'p denote the total number of laden container loading operations (including export and transhipment), the total number of laden container unloading operations (including import and transhipment), and the number of laden container transhipment operations at port p, respectively. Similarly, let x*p, x“, and x'p denote the total number of empty container loading (including repositioning out from the port and the transhipment), the total number of empty container unloading (including repositioning into the port and the transhipment), and the number of empty container transhipment at port p.
The objective function is the total cost consisting of the following: (i) the laden and empty container loading (lifting-on) costs; (ii) the laden and empty container unloading (lifting-off) costs; (iii) the laden and empty container transhipment costs; (iv) the lost-sale penalty costs; (v) the laden container transportation costs on vessel; and (vi) the empty container transportation costs on vessel.
The laden container routing and empty container repositioning problem can be formulated as a linear programming model:
subject to
Constraint (4.13) represents that the fulfilled demands are no more than received customer demands. Equation (4.14) indicates that the fulfilled demands from port о to port d must be loaded onto a vessel at port o. Equation (4.15) indicates that the fulfilled demands from port о to port d must be unloaded from a vessel at port d. Equation (4.16) indicates that if some of the fulfilled demands (laden containers) from port о to port d are unloaded at a transhipment port, these containers must be loaded to a vessel at the same transhipment port. This is to ensure no laden containers will be strayed at transhipment ports. Equation (4.17) represents the update of laden containers on board when the vessel passes a port call. Equations (4.18)—(4.20) represent the total laden containers that are loaded, unloaded, and transhipped at port p.
Constraint (4.21) represents that the empty container repositioning is driven by the net laden container flows. The reason to use inequality instead of equation is to avoid negative number. Equation (4.22) represents that the empty containers repositioned out of a port must go to other ports. Equations (4.23)—(4.25) indicate that the empty containers originating from port о and designating to port d must be loaded at port o, be unloaded at port d, and not be strayed at any transhipment ports, respectively. Equation (4.26) represents the update of empty containers on board when the vessel passes a port call. Equations (4.27)—(4.29) represent the total empty containers that are loaded, unloaded, and transhipped at port p. Constraint (4.30) represents the vessel capacity constraints on each leg for each route. Constraints (4.31) and (4.32) represent the non-negative of the relevant decision variables.
The above model has advantages: (i) the laden and empty container flows from origin port to destination port are explicitly determined including which shipping services are used and which transhipment ports are used — this implies that the path of a laden or empty container in the shipping network can be identified; (ii) the loading (lifting-on), unloading (lifting-off), and transhipping operations are explicitly considered; and (iii) the model is a linear programming problem, which can be solved by commercial software tools for realistic sizes of the problems.
The disadvantages include the following: (i) the model is static, is deterministic, and does not involve the time dimension. The weekly demands for individual port-pairs are fixed. Therefore, demand seasonality requires further consideration; (ii) the transportation cost is calculated on a leg-by-leg basis. In practice, the freight rate is for a trip and not necessarily splittable oversea legs; (iii) the model assumes that the demand is splittable. In practice, some large shipment with multiple laden containers may not be allowed to transport separately; and (iv) some constraints such as vessel capacity may not be satisfied at the operational planning level due to the dynamic operations. The model cannot be applied to stochastic situation directly.
