# Designing container shipping network under changing demand and freight rates/ Konteineriu gabenimo tinklo projektavimas kintant paklausai ir kroviniu kainoms.

1. IntroductionWith the growth of the global economy, the container shipping industry is playing a more and more important role in international cargo transportation (Jarzemskiene and Jarzemskis 2009; Liu et al. 2009; Su and Wang 2009; Paulauskas and Bentzen 2008; Vasilis Vasiliauskas and Barysiene 2008; Jarzemskis and Vasilis Vasiliauskas 2007; Rohacs and Simongati 2007). to adapt to greater container cargo shipment demand, shipping companies are increasing capacity via new super-size container ships. Companies have also begun to pay special attention to optimizing container shipping network designs and operations in order to promote higher quality service. This paper looks at the issues of container shipping network structures and operations considering changing demand and freight rates in dealing with empty container repositioning, ship-slot allocating, ship sizing and container configuration.

The container shipping network design problem (CSNDP) involves selecting a group of calling ports from a set of candidate ports and determining the calling sequence. The objective is to make optimal decisions regarding the following issues: voyage itinerary, the scale of ship assets and containers to be deployed, allocating ship-slots at each calling port in a specified sequence, container quantities loaded at each route and maximizing ship-slot profits in a round-trip operation.

In most existing studies, the CSNDP is solved based on the assumption that cargo demand is given only as a set of constants by a demand matrix that represents either a set of stable values or a set of the average values of annual demand. This assumption arises from the belief that ship sizes can be determined by the given demand and that the costs of route shipping are fixed. It further assumes that freight rates are not directly affected by fluctuations in the real-world demand for a fixed ship capacity. However, this assumption does not reflect the reality of container shipping network design. In fact, cargo traffic demand and freight rates fluctuate periodically. In this case, the shipping network operations may result in large capacity over plus when demand is low and make a great loss on revenue when demand is high. For example, within a year, in Sino-Japan shipping line, the highest cargo demand and freight rates are often three times higher than the lowest ones. Therefore, how to move or lease empty containers in a timely and efficient manner, what size ships maximize revenues during peak seasons and minimize loss during off-seasons and how to determine container configurations to reduce the risk of excessive containers in off-seasons and guarantee enough available containers in peak-seasons are the problems to be solved. These questions have already become critical and fundamental issues of the CSNDP that should be influenced primarily by container cargo distribution among all ports in the trade area. Since it is essential to consider the impact of changing demand and changing freight rates, the CSNDP can be broken down into a series of sub problems, including the ship routing problem (SRP), calling sequencing problem (CSP), ship-slot allocating problem (SAP), ship-sizing problem (SSP) and container constituting problem (RCCP).

Based on the characteristics and attributes of the CSNDP, this study will propose an integrated model. The issues such as empty container repositioning, ship-slot allocating, ship sizing and container configuration are simultaneously considered based on a series of the matrices of demand for a year. The problem is formulated using the analytical method and the average revenue expected value technique by the Knapsack problem (KP), Salesman Travelling problem (STP) and Mixed Integer Nonlinear problem (MIP) basis. to solve the model, the bi-level genetic algorithm based method is proposed. Finally, numerical experiments are provided to illustrate the validity of the introduced model and algorithms.

The rest of this paper is organized as follows: In Section 2, a brief review of previous works is given. The descriptions of the problem are presented in Section 3. In section 4, the model for the CSNDP is developed. A bi-level genetic algorithm is designed in section 5. Numerical examples are used to test the performance of the worked out method in Section 6. Conclusions are given in Section 7.

2. Literature Review

A number of the existing research papers have focused on container shipping transportation. The larger part of them can be divided into two major categories covering ship routing and related operations.

On the issue of containership routing, the existing literature is rather limited. A comprehensive survey of vehicle routing problems can be found in Bodin et al. (1983), Laporte (1992) and Christiansen et al. (2004). Boffey et al. (1979) developed a heuristic optimization model and an interactive decision support system for scheduling container ships on the North Atlantic route. Rana and Vickson (1988 and 1991) tried to find the optimal sequence of calling ports for a fleet of ships operating on a trade route in order to maximize liner operation profit while also determining an optimal calling port sequence. They assumed that non-profitable ports should be rejected as calling ports on the route. They formulated the problem as a mixed integer nonlinear programming model and solved it by using Lagrangean relaxation techniques and the decomposing method. Perakis and Jaramillo (1991) and Jaramillo and Perakis (1991) designed a Linear Programming model for a routing strategy to minimize total operating and lay-out cost over a planning time horizon. They also studied the assignment of the existing fleet of container ships to a predetermined set of routes (sequence of calling ports) based on the realistic models of shipping operation costs. Cho and Perakis (1996) proposed optimal models for the fleet size and design of liner routes by taking into account future cargo demands both in real-life situations and future forecasts. The problem is formulated as Mixed Integer Linear Programming and solved by devising a flow-route incidence matrix in the models to examine a number of candidate ports for different ships. Fagerholt (1999) studied the problem of determining the optimal fleet and liner routes based on a weekly frequency formulated as a multi-trip vehicle routing problem solved by a partitioning approach. Bendall and Stent (2001) proposed a determination model for optimal fleet configuration while taking into account the fleet deployment plan applied in a hub-spoke container shipping network. Lam et al. (2007) used a simple shipping route with two ports and operation with two voyages (TPTV) and its extension with multiple ports and multiple voyages (MPMV) to demonstrate the effectiveness of an approximate dynamic programming approach in finding operational strategies for empty container allocation. Since temporal difference learning for average cost minimization is utilized in the above suggested approach, only two voyages may not be sufficient to represent complete shipping route system operation. Hsu and Hsieh (2007) formulated a two-objective model to determine optimal liner routing, ship size and sailing frequency for carriers and shippers by minimizing shipping costs and inventory costs simultaneously, based on a trade-off between the two costs. From the viewpoints of carriers and shippers, the proposed approach may be of practical value.

On the issue of shipping route operations, considerable research has been done focusing primarily on empty container repositioning. Gavish (1981) developed a system for making decisions regarding container fleet management. In his study, if empty containers were not relocated at the requested time, the system would assign the owned and leased containers to satisfy demand based on the marginal cost criterion. It should be further noted that the extra leased containers affected liner operation total cost without consideration for the inventory of the idle owned containers. Crainic et al. (1993) introduced dynamic and stochastic models for empty container relocation in a land distribution and transportation system. Similarly, to deal with the problem of leased and empty container relocation, the authors ignored difference between short-term leasing cost and long-term cost. This seems impractical and not in keeping with the practice of dealing with long-term leased containers as the owned ones. Cheung and Chen (1998) also considered the sea-borne empty container allocation problem. In their paper, the dynamic container allocation problem was formulated as a two-stage stochastic network model. The model assists liner operators in allocating empty containers and consequently in reducing leasing cost and inventory level at calling ports. However, their work failed to consider the duration of leasing time. Imai et al. (2009) studied the optimization problem of container shipping network design proposing an approach to solve empty container repositioning problems. In their paper, port calling sequence and empty container repositioning are considered simultaneously by designing the objective function with a penalty cost factor. Thus, the issue is integrated and formulated as a two-stage problem. The idea of adding penalty cost in the proposed model and using virtual points in designing network structure should be certainly valuable. Nevertheless, due to a lack of cargo traffic demand fluctuations and cargo flow distributions among ports in their experiments, there are evident flaws in ship-slot allocations among calling ports. More recently, Chang et al. (2008) studied a heuristic method to provide an optimal solution to reduce the cost of empty container interchange. Using the available data, they tested the effectiveness of computational time and solution quality. Di Francesco et al. (2009) developed a multi-scenario, multi-commodity, time-extended optimization model to deal with the empty container repositioning problem. Some uncertain model parameters that cannot be estimated through historical data are treated as the sets of a limited number of values according to the shipping company opinions. Bandeira et al. (2009) created a decision support system (DSS) to deal with full and empty container trans-shipment operations. The arrangement of repositioning empty containers can be determined by adjusting several parameters in the DSS model.

None of the above introduced studies has looked into the encountered problem and approach in this paper: namely container shipping network design and operation should be incorporated into a single, coordinated problem to be addressed by considering the revenue-loss risk control of ship sizing and container configuration based on periodic fluctuations in cargo demand and freight rates.

3 Problem Descriptions

In general, the optimization of the CSNDP should be completed by a series of decision-making processes that involve selecting appropriate calling ports from candidate ports in a trade area determining the reasonable order of calling sequence with the fixed regular frequency service and settling rational ship-slot allocation at each calling port with the suitable scale of the deployed assets that include ship size, container quantity and container configurations in the network. These decision-making processes depend upon the following influencing factors and are also called controllable factors mainly covering distances and cargo traffic demand together with freight rates among candidate ports in a trade area, the investment costs of ships and containers and company's policies regarding the shipping market and investment etc. Based on these controllable factors, the decisionmaking process ought to determine factors, including the optimal set of ports to be called, the optimal order of calling sequence, the optimal size of ships and the optimal series of ship-slot allocations on shipboard at each calling port. Since the ship size is unchangeable during a planning period and fluctuating demand produces a significant effect on ship size, it is more feasible to use a series of the matrices of demand in order of time to represent fluctuating demand rather than to use only a matrix of the average demand.

The container shipping network structures generally can be divided into two types of forms according to their operation characteristics. One is circular and another is pendulum, as shown in Fig. 1. From the viewpoint of topology, they can be essentially reduced to the circular route as a basic form because any pendulum type can be converted to a circular one by adding virtual nodes representing the ports in the backward direction and by constructing an adequate matrix for demand distributions. Shipping network operation is generally performed by a fleet of ships with a series of ship-slot allocations for calling ports. The fleet of ships travelling on the route ought to be split into two groups where one group travels in a clockwise direction while another travels at the same time in a counterclockwise direction. In this way, cargo traffic at any calling port is conveniently transported to its adjacent ports in different directions. For example, cargo traffic from Port 1 to Port 2 must be carried by one group of ships in a clockwise direction and cargo traffic from Port 1 to Port 9 can be carried by another group of ships in a counterclockwise direction, as shown in Fig. 2. The ships are only required to pick up the containers to be transported to other calling ports located in a half voyage travelling in the same direction as the ships.

[FIGURE 1 OMITTED]

In addition, due to the imbalanced directional cargo flows between some calling ports, there must be difference between the total cargo traffic originating from the port and the one arriving to it. Since load rejection is very unlikely in practice assuming that ship capacities have spare slots, liner shipping companies must decide whether to reposit empty containers or lease extra containers and store the idle owned containers at the specific ports. Since comparisons of the costs in a single voyage are not reasonable, comparing these average costs in a sufficient number of voyages under consideration is necessary. These elements must be represented in the formulation as the opportunity costs with mutual-substitution relation between them.

[FIGURE 2 OMITTED]

Thus, the model we will construct should include the above influencing factors and elements. The model with an objective of the average unit ship-slot profit maximization can be formulated by designing an average closed voyage trip in a circular route with the appropriate scales of ships and containers deployed. In ship routing, it is not necessary for ships to call at all ports in the trade area, for example, Ports 1, 2, 4, 5, 7 and 9 are selected but Ports 3, 7, and 8 are given up, as shown in Fig. 2. Other assumptions are as follows:

(a) As a key influencing factor, fluctuating cargo traffic demand among all ports is presented by a series of demand matrices in order of time and with relevant homogenous freight rates rather than by a matrix of the average demand in a planning horizon. The reason is mainly because the practical number of containers transported in the planning horizon should be limited by the accepted ship size once it is determined, as shown in Fig. 3.

(b) There must be an appropriate quantity of containers equipped at every calling port corresponding to the quantity handled at them, according to container shipping network design. Additional containers can be leased at any port but must ultimately be returned to the original port.

(c) The ships deployed in the network or route must be the same with capacities and cruising speeds.

(d) The ship's capacity must not be exceeded by a total number of containers loaded on shipboard at any route leg.

[FIGURE 3 OMITTED]

4. Model Formulations

As described above, the CSNDP consists of four sub-problems. The first one is choosing the best group of calling ports for the optimal network or route. The second is identifying the calling sequence of the chosen group of calling ports for an optimal arrangement of voyage itinerary. The third is optimizing ship-slot allocations at each calling port with a series of container quantities handled on each voyage at each calling port for the average unit ship-slot profit maximization. The last problem is determining rational container configurations deployed in the networks depending upon the above container quantities handled at each calling port. Since there are interrelations and interactions among these sub-problems, the CSNDP can be formulated as a mixed integer non-linear programming problem (MINP) at three stages, based respectively on the Knapsack Problem (KP), Salesman Travelling Problem (STP) along with the Operation Problem (OP) and Container Configuration Problem (CCP). The optimal model can be developed as follows:

Stage 1:

[KP] Maximize [summation over (k[member of V]) [[omega].sub.k] x [P.sup.k], (1)

Subject to [summation over (k[member of]V]) [[omega].sub.k] = 1, (2)

[[omega].sub.k] [member of] {0,1}, [for all]k [member of] V, (3)

where: V is a set of combinations of calling ports taken from a set of candidate ports N in the trade area; [[omega].sub.k] = 1 if the route constructed by a candidate combination of calling ports k is selected and 0 otherwise; [P.sup.k] is the values of the objective function under the candidate combination of calling ports k.

Stage 2:

Given a set of calling ports, an optimal calling sequence can be formulated by constructing the MINP with the STP and OP. In order to find decision variables as described, let [w.sub.ij] (i, j [member of] N,i [not equal to] j) be binary flow variables, [x.sub.ij], [y.sub.ij] (i, j [member of] N ,i [not equal to] j)--respectively full and empty ship-slot allocation variables at each calling port, u--the ship-size variable and [X.sub.ijg], [Y.sub.ijg](i, j [member of] N, g [member of] G) express respectively the real quantities of full and empty containers as auxiliary variables loaded in the scenario g(g [member of] G) of the series of cargo traffic demand [d.sub.ijg] (i, j [member of] N, g [member of] G). In consideration of the period fluctuations of cargo traffic among calling ports, the unit ship-slot profit an average voyage in a planning horizon is introduced which may be more reasonable and effective and can be represented by the expected revenue in a year with total G voyages. hus, if route operation by a single ship with capacity (u) is considered, [MINP] may be formulated by the unit ship-slot profit an average voyage in a year with total G voyages as follows: Maximize:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Subject to:

[summation over (j[member of]N)] [w.sub.ij] - [summation over (j[member of]N)][w.sub.ji] = 0, [for all]i [member of] N, (5)

[summation over (i[member of][phi])][summation over (j[member of][phi])] [w.sub.ij] [greater than or equal to] 1, [for all][phi] [subset] N, (6)

[w.sub.ij] [member of] {0,1}, [for all]i, j [member of] N, (7)

[z.sub.ij] [less than or equal to] [d.sub.ijg], [for all]i, j [member of] N, [for all]g [member of] G, (8)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (9)

[X.sub.ijg] = [d.sub.ijg], [for all][x.sub.ij] [greater than or equal to] [d.sub.ijg], i, j [member of] N, g [member of] G, (10)

[X.sub.ijg] = [x.sub.ij], [Y.sub.ijg] = [y.sub.ij], [for all][x.sub.ij] < [d.sub.ijg], i, j [member of] N, g [member of] G, (11)

[x.sub.ij], [y.sub.ij], [X.sub.ijg], [Y.sub.ijg] [member of] N [union] {0}, [for all]i, j [member of] N, [for all]g [member of G, (12)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (14)

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[C.sub.sh](u) = ([alpha] x [u.sup.2] + [beta] x u + [gamma])x (v + [epsilon] * n); (16)

[t.sub.ij] the time of ship's travel from port (i) to port (j); v the number of ships deployed in the route with the fixed cruising speed; N a set of calling ports for k [member of] V ; [phi] a non-empty subset of N; [C.sub.sp] (x) a shipping cost function of the selected arcs (i, j represented in a linear part of the scope; [C.sub.cn](x) the requested quantity of containers (including at ports and on the shipboard); [LS.sub.i] the number of leasing containers (TEU) at port (i); [ST.sub.i] the number of storing containers (TEU) at port (i); M the number of the route equal to the number of calling ports in the circular route form; [C.sup.f.sub.ij], [C.sup.e.sub.ij] the unit cost of handling full and empty containers (TEU) at a calling port; [R.sup.f.sub.ij], [R.sup.e.sub.ij] the unit revenue of transporting full and empty containers (TEU) from port (i)to port (j); [a.sub.ijm] = 1 if route-leg covering cargo traffic flows between port pairs (i, j) = 0 otherwise.

Functions (1)-(3) provide the method by which an optimal set of ports to be called in the route can be selected from the candidate ports in the trade area.

Constraint (5) ensures that each ship that arrives at a calling port must leave from it.

Constraint (6) guarantees that all the ports to be called must be connected via the constructed route in which there is no such sub-voyage that it does not visit all the ports selected in N.

Constraints (8)-(9) are constraints for full containers loaded at each calling port and ship's capacity on any route-leg, respectively.

Constraints (10)-(12) indicate the real quantity of containers loaded at each calling port and equal to real cargo traffic demand when the quantity of ship-slots allocated on shipboards is greater than real cargo traffic demand at it, whereas otherwise, the real quantity of containers loaded at the port only equals to the quantity of ship-slots allocated on shipboards.

Constraints (13) and (14) are leasing and storing container constraints.

Functions (15)-(16) represent the relationships between the assets of ships and containers deployed in the route and shipping operation cost with ship size, where [eta], [alpha], [beta], [gamma] respectively denote the weighted factors for the relative terms.

Objective function (4) is to maximize the unit shipslot profit of an average voyage which is an algebraic sum of the total revenue, repositioning cost, leasing and storage costs and assets operation costs divided by ship's capacity, where [sigma], [lambda], [mu], [epsilon] express the cost coefficients of the relative terms, respectively.

Stage 3:

The problem of container configuration is to determine and arrange the optimal configurations of containers with the owned container quantity, long-term leasing container quantity and short-term leasing container quantity deployed in the networks in order to minimize the total using container cost. If short-term leasing time be set to less than three months and long-term leasing time be more than three months, and let [Q.sup.O.sub.i], [Q.sup.L.sub.i] and [Q.sup.S.sub.i] respectively signify the quantity variables of the owned containers, long-term and short-term leasing containers deployed at calling port i, the total container cost, including using costs and the idling costs of containers can be formulated as follows:

Minimize

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)

Subject to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

[C.sup.O] [less than or equal to] [C.sup.L] [less than or equal to] [C.sup.S], (19)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (20)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (21)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (22)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (23)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (25)

Objective function (17) represents the total using cost of all containers during an average voyage where coefficients [C.sup.O], [C.sup.L] and [C.sup.S] respectively imply the unit using costs of the owned containers, long-term leasing containers and short-term leasing containers and where variables [[DELTA].sup.O], [[DELTA].sup.L] and [[DELTA].sup.S] signify the idle quantities of the owned containers, long-term leasing containers and short-term leasing containers deployed in the route, respectively. Homogenously, there are coefficients [C.sup.O.sub.I i], [C.sup.L.sub.I i] and [C.sup.S.sub.I i] respectively denoting the unit idle costs of the owned containers, long-term leasing containers and short-term leasing containers. Constraint (18) gives the limit requirement between the quantities handled and the quantities of all container configurations deployed at each calling port. Constraints (19) show requirements for general relations among [C.sup.O], [C.sup.L] and [C.sup.S]. Constraints (20)-(22) represent constraint requirements between the variables deployed and the quantities handled at each calling port. Equalities (23)-(25) represent the idle quantity of each part of container configurations at every calling port, respectively.

5. Design of Algorithms

To reflect the interrelation between the three stage models, a bi-level genetic algorithm (GA) is designed. The upper level genetic algorithm is used to searching for the ports to be called by ships and the lower level genetic algorithm is applied for searching an optimal port calling a sequence of ships. Based on the ports selected by the upper level, the lower level algorithm optimizes calling sequence and container configuration is obtained. Then, the outcome of the lower level is feedback to the upper level to calculate the objective function of the lower level algorithm. The process is shown in Fig.4.

[FIGURE 4 OMITTED]

(1) Representation of chromosomes

The chromosomes of the upper level algorithm are represented as binary bit strings. The length of a chromosome equals to the number of ports. In the figure depicting chromosomes, '0' denotes the port that is not selected and '1' indicates the selected port, e.g. chromosome '1-0-1-1-0-1-1' denotes that there are 7 ports from which ports 1, 3, 4, 6, 7 are selected.

The chromosomes of the lower level are all represented as character strings. Each chromosome denotes a stowage plan of outbound containers and each integer in the chromosome denotes an outbound container. For example, chromosome 4-1-7-5-2-6-3 denotes that containers 4, 1, 7, 5, 2, 6, 3 are loaded in position 1, 2, 3, 4, 5, 6, 7 of ship.

(2) Initialization

The initialization method of the upper level algorithm is based on selecting the number of ports to be called. The initialization method of the lower level algorithm is randomly selected calling sequence for the selected ports. [M.sub.1] and [M.sub.2] individuals are generated for the upper and lower levels.

(3) Calculation of the fitness value

Maximization is the problem of the paper, thus the larger is the objective function value the higher the fitness value must be. Therefore, the fitness function of the upper and lower levels can be defined as equations (26) and (27):

[F.sub.1](x) = [[omega].sub.k] x [P.sup.k]; (26)

[F.sub.2] (x) = [bar.P], (27)

where: [C.sub.M] is a constant to ensure F(x) [greater than or equal to] 0 and is determined by the problem scale.

(4) Reproduction

Reproduction is a process in which individual chromosomes are copied according to their scaled fitness function values. Chromosomes with a higher fitness value would be selected with higher probabilities. Selection probability can be expressed in the following way:

P([x.sub.i]) = F/([x.sub.i])/[M.summation over (i=1)] F([x.sub.i]) (28)

(5) Crossover operator

The process of crossover for upper and lower GA is as follows: selecting two parents, generating the point randomly and swapping the genes for two parents.

(6) Mutation

Mutation introduces random changes in the chromosomes by altering the value to a gene with user-specified probability [p.sub.m] called the mutation rate. The mutation method of the upper and lower levels generates two random numbers between 1 and the length of chromosomes first and exchanges the values of the gene at these two positions second.

(7) Stopping criterion

Having reached the pre-determined stopping generations, the algorithm stops.

6. Numerical Experiments

This section presents sample cases to demonstrate the application of the proposed formulation. The case experiments focus on container shipping network design in the trade area of Far East Asia. Since there are a number of relevant factors to be considered that have an impact on shipping network design, we implemented the case experiments according to some empirical knowledge about shipping operation and management in this trade area.

6.1. Parameter Settings

(1) Candidate ports in the trade area (10 ports): Dalian (DL), Tianjin (TJ), Qingdao (Qd), Shanghai (SH), Busan (BSN), Kaohsiung (KSH), KeeLung (KL), Kitakyushu (KTK), Osaka (OSK) and Tokyo (TKY).

(2) Planning horizon: one year.

(3) Weekly service frequency: once.

(4) The turnaround time of containers at each port: less than or equal to service interval.

(5) Storage cost at each port (i): $USD2/TEU-day.

(6) Short-term leasing cost at each port (i): $USD2/ TEU-day.

(7) Given ship cruising speed: 21 knots.

(8) Total handling and standby time at each port: 0.5 day/per port.

(9) Given cargo traffic demand in the matrix: from January to December.

(10) Fuel oil and diesel oil cost: $USD 320 /metric ton and $USD 560 /metric ton respectively.

The above parameters (5)-(8) are set to be average value. Due to a lack of detailed data on ship expense criteria at each port, we assume that they are the same for all ports under consideration. However, according to such assumptions, the reliability of the solution cannot be affected in the decision making process.

6.2. Demand Matrices

With the characteristics of periodic fluctuations, historic cargo traffic demand may be obtained through market surveys or provided by liner companies. The distributions of cargo traffic demand with relevant freight rates can be represented by a series of matrices consisting of weekly data based on bi-months in a year. In this case, the series of the matrices of fluctuating demands are displayed in the Tables 1-6.

6.3 Results of Experiments

Ship-size, as the main variable, should be represented by a relevant function, including shipping cost. Actually, it is very difficult to construct the precise relationship between ship-size and shipping cost with an exact function. Generally, the function should be presented by a quadratic approximation. Taking into consideration cargo traffic in the trade area of the case, the ship-size to be deployed may be located in the categories of 2,000 TEU to 7,000 TEU. In this section, the relationship between ship-size and shipping cost can be represented approximately by a linear function. The function consists of three sub models: one is associated with fuel oil and diesel oil consumption, the second is associated with ship leasing and the last one is associated with the cost of handling the ship at calling ports. By quoting relevant models and performing regression analysis based on the above cost data, we set up the following linear shipping cost function using TEU (twenty-foot equivalent unit) capacity as an independent variable:

[C.sub.sp] = 9.54 x u + 21,973.38.

The model is an algebraic sum of three sub-models: the fuel oil cost model is 1.64 x u + 5,440 per day, the diesel oil cost model is 0.2066 x u + 12,208 per day, the ship rental model is 6.54 x u + 1,422.52 (2005) per day and the cost of ship handling at calling ports is 1.95 x u + 3,453.36 (2005) per entry. Then, the proposed formulation is solved by Mat Lab based on the GA and results are shown as the following tables and figures.

The optimal set of calling ports with the optimal order of calling sequence based on weekly service frequency is as follows:

Qingdao [right arrow] Shanghai [right arrow] KeeLung [right arrow] Kaohsiung [right arrow] Busan [right arrow] Kitakyushu [right arrow] Qingdao.

Based on fluctuating demand, the optimal shipsize has an approximate capacity of 1,715 TEU with the maximal total profit of USD 102,578.5 and the maximal unit ship-slot profit of USD 60 per average voyage. Based on the average demand, the optimal ship-size has an approximate capacity of 2508 TEU with the maximal total profit of USD 42,509 and the maximal unit shipslot profit of USD 17 per average voyage. Their ship-slot allocations are shown in Tables 7 and 8.

When the range of fluctuating demand expands 10% and 30% respectively based on original fluctuating demand, the optimal ship sizes with other relevant values based on fluctuation and the average demand vary as shown in Tables 9-11.

The above tables reveal that the larger the range fluctuating demand expands, the better the optimal ship size with relevant values would be based on fluctuating demand; however, the ones based on the average demand would vary in reverse. Consequently, the proposed formulation based on fluctuating demand has distinct superiority in container shipping network design to the one based on classic average demand.

As the results of optimal shipping network design, the maximal container quantities handled at all calling ports are also solved to be 810 TEU at Qingdao, 955 TEU at Shanghai, 1,035 TEU at Keelung, 890 TEU at Kaohsiung, 1,180 TEU at Busan and 1,215 TEU at Kitakyushu, respectively. Based on the maximal quantities handled and ship-slot allocations at all calling ports, optimal container configurations at each calling port are obtained as shown in Table 12.

All determinant factors concerning container shipping network design have been obtained solving the proposed formulations. Results are shown in accordance with the real-world cases of container shipping route operations. They are therefore more practical and applicable than the ones based on classic average demand and generally utilized in the existing studies.

7. Conclusions

1. This study addressed the optimization problem of container shipping network design based on fluctuating demand along with freight rates. Through numerical experiments, we have reached the following conclusions. In considering the influence of fluctuating demand, the unit ship-slot profit of optimal service network operation in binary directions is the best in comparison with the ones based on the fixed average demand. As a result, the problem based on fluctuating demand along with freight rates results in optimizing the smallest ship-size and corresponding container configurations that do not only gain the best voyage profit but also largely reduce the costs of asset deployment.

2. The proposed approach is very useful for assessing shipping network operations from both strategic and tactical viewpoints. Furthermore, it is also extremely effective at employing unit ship-slot profit per average voyage to deal with the issue of comparison between repositioning and leasing empty containers and at optimizing ship-size to deal with revenue-loss control problems.

3. In fact, container shipping network structure and operation should be designed not only for fluctuating demand combined with freight rates determined by historical usage but also for the projections of future fluctuating demand. A combination of these two approaches may provide an interesting topic for future research.

doi: 10.3846/transport.2010.07

Received 13 August 2009; accepted 1 February 2010

References

Bandeira, D. L.; Becker, J. L.; Borenstein, D. 2009. A DSS for integrated distribution of empty and full containers, Decision Support Systems 47(4): 383-397. doi:10.1016/j.dss.2009.04.003

Bendall, H. B.; Stent, A. F. 2001. A scheduling model for a high speed containership service: A hub and spoke short-sea application, International Journal of Maritime Economics 3(3): 262-277. doi:10.1057/palgrave.ijme.9100018

Bodin, L.; Golden, B.; Assad, A.; Ball, M. 1983. Routing and scheduling of vehicles and crews: the state of the art, Computer and Operations Research 10(2): 63-211.

Boffey, T. B.; Edmond, E. D.; Hinxman, A. I.; Pursglove, C. J. 1979. Two approaches to scheduling container ships with an application to the North Atlantic route, Journal of the Operational Research Society 30(5): 413-425. doi:10.1057/jors.1979.101

Chang, H.; Jula, H.; Chassiakos, A.; Ioannou, P. 2008. A heuristic solution for the empty container substitution problem, Transportation Research Part E: Logistics and Transportation Review 44(2): 203-216. doi:10.1016/j.tre.2007.07.001

Cheung, R. K.; Chen, C. 1998. A two-stage stochastic network model and solution methods for the dynamic empty container allocation problem, Transportation Science 32(2): 142-162. doi:10.1287/trsc.32.2.142

Cho, S.-C.; Perakis, A. N. 1996. Optimal liner fleet routeing strategies, Maritime Policy and Management 23(3): 249259. doi:10.1080/03088839600000087

Crainic, T. G.; Gendreau, M.; Dejax, P. 1993. Dynamic and stochastic models for the allocation of empty containers, Operations Research 41(1):102-126. doi:10.1287/opre.41.1.102

Christiansen, M.; Fagerholt, K.; Ronen, D. 2004. Ship routing and scheduling: Status and perspectives, Transportation Science 38(1):1-18. doi:10.1287/trsc.1030.0036

Di Francesco, M.; Crainic, T. G.; Zuddas, P. 2009. The effect of multi-scenario policies on empty container repositioning, Transportation Research Part E: Logistics and Transportation Review 45(5): 758-770. doi:10.1016/j.tre.2009.03.001

Fagerholt, K. 1999. Optimal fleet design in a ship routing problem, International Transactions in Operational Research 6(5): 453-464. doi:10.1111/j.1475-3995.1999.tb00167.x

Gavish, B. 1981. A decision support system for managing the transportation needs of a large corporation, AIIE Transactions 13(1): 61-85. doi:10.1080/05695558108974537

Hsu, C.-I.; Hsieh, Y.-P. 2007. Routing, ship size, and sailing frequency decision-making for a maritime hub-and-spoke container network, Mathematical and Computer Modelling 45(7-8): 899-916. doi:10.1016/j.mcm.2006.08.012

Imai, A.; Shintani, K.; Papadimitriou, S. 2009. Multi-port vs. hub-and-spoke port calls by containerships, Transportation Research Part E: Logistics and Transportation Review 45(5): 740-757. doi:10.1016/j.tre.2009.01.002

Jaramillo, D. I.; Perakis, A. N. 1991. Fleet deployment optimization for liner shipping Part 2: Implementation and results, Maritime Policy and Management 18(4): 235-262. doi:10.1080/03088839100000028

Jarzemskiene, I.; Jarzemskis, V. 2009. Allotment booking in intermodal transport, Transport 24(1): 37-41. doi:10.3846/1648-4142.2009.24.37-41

Jarzemskis, A.; Vasilis Vasiliauskas, A. 2007. Research on dry port concept as intermodal node, Transport 22(3): 207-213.

Lam, S.-W.; Lee, L.-H.; Tang, L.-C. 2007. An approximate dynamic programming approach for the empty container allocation problem, Transportation Research Part C: Emerging Technologies 15(4): 265-277. doi:10.1016/j.trc.2007.04.005

Laporte, G. 1992. The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research 59(3): 345-358. doi:10.1016/0377-2217(92)90192-C

Liu, W.; Xu, H.; Zhao, X. 2009. Agile service oriented shipping companies in the container terminal, Transport 24(2): 143-153. doi:10.3846/1648-4142.2009.24.143-153

Paulauskas, V.; Bentzen, K. 2008. Sea motorways as a part of the logistics chain, Transport 23(3): 202-207. doi:10.3846/1648-4142.2008.23.202-207

Perakis, A. N.; Jaramillo, D. I. 1991. Fleet deployment optimization for liner shipping Part 1: Background, problem formulation and solution approaches, Maritime Policy and Management 18(3): 183-200. doi:10.1080/03088839100000022

Rana, K.; Vickson, R. G.1988. A model and solution algorithm for optimal routing of a time-chartered containership, Transportation Science 22(2): 83-95. doi:10.1287/trsc.22.2.83

Rana, K.; Vickson, R. G.1991. Routing container ships using Lagrangean relaxation and decomposition, Transportation Science 25(3): 201-214. doi:10.1287/trsc.25.3.201

Rohacs, J.; Simongati, G. 2007. The role of inland waterway navigation in a sustainable transport system, Transport 22(3): 148-153.

Su, T.-J.; Wang, P. 2009. Carrier's liability under international maritime conventions and the UNCITRAL draft convention on contracts for the international carriage of goods wholly or partly by sea, Transport 24(4): 345-351. doi:10.3846/1648-4142.2009.24.345-351

Tolli, A.; Laving, J. 2007. Container transport direct call--logistic solution to container transport via Estonia, Transport 22(4): 1A-1F

Vasilis Vasiliauskas, A.; Barysiene, J. 2008. An economic evaluation model of the logistic system based on container transportation, Transport 23(4): 311-315. doi:10.3846/1648-4142.2008.23.311-315

Chao Chen (1), Qingcheng Zeng (2)

(1,2) College of Transportation Management, Dalian Maritime University, 116026 Dalian, China

E-mails: (1) chenchaovip@126.com; (2) zqcheng2000@hotmail.com

Table 1. Weekly distributions of the average demand and freight rates in January and February (TEU/USD) [d.sub.ij6] [R.sup.f .sub.ij6] DL TJ QD SH DL 0/0 0/0 0/0 0/0 TJ 0/0 0/0 0/0 0/0 QD 0/0 0/0 0/0 0/0 SH 0/0 0/0 0/0 0/0 BSN 105/230 125/220 200/220 200/220 OSK 50/230 40/250 40/240 50/240 KTK 20/220 30/240 40/220 40/220 TKY 25/230 35/250 30/230 55/240 KL 233/370 350/380 320/360 420/340 KHS 260/390 240/380 300/380 400/340 [d.sub.ij6] [R.sup.f .sub.ij6] BSN OSK KTK TKY DL 230/250 220/250 200/250 220/230 TJ 240/270 230/260 220/260 250/240 QD 250/240 230/240 240/230 220/240 SH 280/260 220/250 280/230 250/250 BSN 0/0 250/270 300/250 300/270 OSK 60/260 0/0 0/0 0/0 KTK 150/250 0/0 0/0 0/0 TKY 40/260 0/0 0/0 0/0 KL 350/450 325/380 300/360 330/380 KHS 340/460 300/360 300/360 290/360 [d.sub.ij6] [R.sup.f .sub.ij6] KL KHS DL 250/430 200/440 TJ 270/450 250/430 QD 260/420 250/420 SH 260/380 250/400 BSN 350/330 300/350 OSK 170/350 190/380 KTK 160/300 150/300 TKY 145/350 125/380 KL 0/0 0/0 KHS 0/0 0/0 Table 2. Weekly distributions of the average demand and freight rates in March and April (TEU/USD) [d.sub.ij6] [R.sup.f .sub.ij6] DL TJ QD SH BSN DL 0/0 0/0 0/0 0/0 100/220 TJ 0/0 0/0 0/0 0/0 160/220 QD 0/0 0/0 0/0 0/0 160/210 SH 0/0 0/0 0/0 0/0 210/160 BSN 55/220 75/230 100/210 160/210 0/0 OSK 30/220 30/240 30/220 40/200 50/280 KTK 20/220 30/240 30/220 28/200 45/280 TKY 25/220 30/240 30/220 45/200 40/280 KL 260/280 250/280 240/270 360/240 300/400 KHS 220/280 210/280 200/270 300/240 300/400 [d.sub.ij6] [R.sup.f .sub.ij6] OSK KTK TKY KL KHS DL 200/230 180/220 200/210 200/300 200/300 TJ 200/230 200/220 220/240 220/320 220/330 QD 150/220 160/210 160/220 220/360 250/380 SH 200/160 260/160 250/160 260/340 240/350 BSN 230/240 210/240 220/240 250/380 250/400 OSK 0/0 0/0 0/0 100/320 120/320 KTK 0/0 0/0 0/0 110/350 100/350 TKY 0/0 0/0 0/0 115/350 100/350 KL 220/30 220/280 220/300 0/0 0/0 KHS 240/300 220/280 240/300 0/0 0/0 Table 3. Weekly distributions of the average demand and freight rates in May and June (TEU/USD) [d.sub.ij6] [R.sup.f. sub.ij6] DL TJ QD SH BSN DL 0/0 0/0 0/0 0/0 200/200 TJ 0/0 0/0 0/0 0/0 230/210 QD 0/0 0/0 0/0 0/0 180/180 SH 0/0 0/0 0/0 0/0 250/180 BSN 50/200 75/210 150/210 220/210 0/0 OSK 30/200 30/210 30/200 50/180 50/200 KTK 20/200 30/220 35/200 50/180 45/190 TKY 25/200 30/210 30/200 45/180 40/200 KL 200/280 200/280 250/270 380/240 340/380 KHS 200/280 160/280 210/270 340/240 320/380 [d.sub.ij6] [R.sup.f. sub.ij6] OSK KTK TKY KL KHS DL 200/210 240/200 240/220 220/280 240/280 TJ 240/210 210/210 220/220 230/300 230/310 QD 250/200 250/180 280/200 240/360 280/360 SH 280/200 300/180 280/200 280/340 260/340 BSN 220/210 200/180 200/210 200/350 200/360 OSK 0/0 0/0 0/0 100/300 100/300 KTK 0/0 0/0 0/0 110/320 100/320 TKY 0/0 0/0 0/0 100/320 90/320 KL 255/300 250/300 240/300 0/0 0/0 KHS 200/300 230/320 240/300 0/0 0/0 Table 4. Weekly distributions of the average demand and freight rates in July and August (TEU/USD) [d.sub.ij6] [R.sup.f .sub.ij6] DL TJ QD SH BSN DL 0/0 0/0 0/0 0/0 230/200 TJ 0/0 0/0 0/0 0/0 200/220 QD 0/0 0/0 0/0 0/0 210/210 SH 0/0 0/0 0/0 0/0 360/220 BSN 105/250 125/250 200/250 220/300 0/0 OSK 50/230 40/240 40/210 50/220 60/280 KTK 20/210 30/220 40/200 40/200 100/280 TKY 25/220 35/240 30/210 55/220 80/260 KL 280/320 250/330 300/300 410/280 400/520 KHS 260/310 240/320 300/300 400/280 380/500 [d.sub.ij6] [R.sup.f .sub.ij6] OSK KTK TKY KL KHS DL 230/370 390/300 360/320 280/500 270/480 TJ 260/390 300/310 360/320 270/480 300/490 QD 300/320 350/300 360/320 300/450 350/470 SH 390/320 400/300 400/320 350/430 340/450 BSN 280/380 330/280 350/380 350/400 300/400 OSK 0/0 0/0 0/0 210/350 190/380 KTK 0/0 0/0 0/0 200/300 180/300 TKY 0/0 0/0 0/0 190/350 185/380 KL 325/490 350/480 330/490 0/0 0/0 KHS 320/490 320/480 300/490 0/0 0/0 Table 5. Weekly distributions of the average demand and freight rates in September and October (TEU/USD) [d.sub.ij6] [R.sup.f .sub.ij6] DL TJ QD SH BSN DL 0/0 0/0 0/0 0/0 280/300 TJ 0/0 0/0 0/0 0/0 240/320 QD 0/0 0/0 0/0 0/0 280/320 SH 0/0 0/0 0/0 0/0 400/350 BSN 120/370 150/380 210/380 300/400 0/0 OSK 60/240 50/250 50/240 60/240 80/310 KTK 30/220 40/240 50/220 50/220 100/300 TKY 35/240 45/250 40/240 65/240 50/310 KL 250/430 300/450 350/420 510/420 500/680 KHS 280/430 300/450 320/420 500/420 500/680 [d.sub.ij6] [R.sup.f .sub.ij6] OSK KTK TKY KL KHS DL 280/500 400/490 400/540 360/520 320/540 TJ 260/500 440/500 450/550 390/540 400/540 QD 300/500 500/460 480/550 400/500 400/500 SH 560/480 550/460 560/540 450/460 400/480 BSN 550/540 500/350 480/560 450/460 400/480 OSK 0/0 0/0 0/0 200/400 210/400 KTK 0/0 0/0 0/0 200/360 200/370 TKY 0/0 0/0 0/0 165/400 145/400 KL 425/600 450/580 430/600 0/0 0/0 KHS 420/600 400/580 410/610 0/0 0/0 Table 6. Weekly distributions of the average demand and freight rates in November and December (TEU/USD) [d.sub.ij6] [R.sup.f .sub.ij6] DL TJ QD SH BSN DL 0/0 0/0 0/0 0/0 360/330 TJ 0/0 0/0 0/0 0/0 400/350 QD 0/0 0/0 0/0 0/0 380/380 SH 0/0 0/0 0/0 0/0 450/400 BSN 110/400 140/450 300/400 300/450 0/0 OSK 60/240 50/270 50/260 50/250 120/340 KTK 40/220 40/250 70/240 60/240 150/320 TKY 40/240 45/270 40/260 65/250 120/340 KL 480/470 450/480 440/500 600/500 600/700 KHS 360/470 440/480 400/500 550/500 580/700 [d.sub.ij6] [R.sup.f .sub.ij6] OSK KTK TKY KL KHS DL 530/600 560/600 560/650 450/620 370/610 TJ 560/650 580/650 560/650 500/650 500/620 QD 600/620 600/600 620/620 500/600 460/600 SH 660/620 670/600 650/620 540/550 500/550 BSN 480/470 600/450 500/470 500/500 420/550 OSK 0/0 0/0 0/0 190/420 210/440 KTK 0/0 0/0 0/0 210/400 250/420 TKY 0/0 0/0 0/0 190/420 225/440 KL 525/680 600/660 530/680 0/0 0/0 KHS 520/620 550/660 540/650 0/0 0/0 Table 7. Optimal ship-slot allocations at each calling port based on fluctuating demand QD SH KL [X.sub.ij], [Y.sub.ij] F E F E F E QD [right arrow] 5 500 -- -- SH [right arrow] 435 -- -- 105 350 KL [right arrow] -- -- 500 KHS [right arrow] 150 -- -- 500 80 BS [right arrow] 300 25 150 175 -- -- 455 KTK [right arrow] 70 190 60 495 100 -- -- 225 KHS BS KTK [X.sub.ij], [Y.sub.ij] F E F E F E QD [right arrow] 230 140 180 490 SH [right arrow] 450 200 150 410 KL [right arrow] 210 600 225 420 KHS [right arrow] 580 160 BS [right arrow] 530 175 KTK [right arrow] 180 550 QD [X.sub.ij], [X.sub.ij], [Y.sub.ij] F E [Y.sub.ij] QD [right arrow] -- -- [left arrow] QD SH [right arrow] -- -- [left arrow] SH KL [right arrow] -- -- [left arrow] KL KHS [right arrow] -- -- [left arrow] KHS 180 BS [right arrow] -- -- [left arrow] BS 405 KTK [right arrow] -- -- [left arrow] KTK Table 8. Optimal ship-slot allocations at each calling port based on the average demand QD SH KL [X.sub.ij], [Y.sub.ij] F E F E F E QD [right arrow] 320 320 -- -- SH [right arrow] 363 363 -- -- 83 83 KL [right arrow] -- -- 350 350 KHS [right arrow] 144 144 -- -- 415 415 BS [right arrow] 185 185 439 113 -- -- 197 197 KTK [right arrow] 43 43 41 787 82 82 -- -- KHS BS KTK [X.sub.ij], [Y.sub.ij] F E F E F E QD [right arrow] 162 162 166 166 335 335 SH [right arrow] 327 327 163 163 98 98 KL [right arrow] 338 415 415 181 181 312 312 KHS [right arrow] 403 403 111 111 BS [right arrow] 357 357 181 181 KTK [right arrow] 162 162 410 410 QD [X.sub.ij], [X.sub.ij], [Y.sub.ij] F E [Y.sub.ij] QD [right arrow] -- -- [left arrow] QD SH [right arrow] -- -- [left arrow] SH KL [right arrow] -- -- [left arrow] KL KHS [right arrow] -- -- [left arrow] KHS 144 144 BS [right arrow] -- -- [left arrow] BS 317 317 KTK [right arrow] -- -- [left arrow] KTK Table 9. Comparison between two different demand forms based on original fluctuation data Based on Based on fluctuating the average Original data demand demand Optimal ship-size 2-1,715 TEU 2-2,508TEU Maximal total profit per average voyage $USD 205,157 $USD 85,018 Maximal unit ship-slot profit per $USD 60/TEU $USD 17/TEU average voyage Table 10. Comparison between two different demand forms based on 10% expansion of original fluctuation data Based on Based on fluctuating the average +10% expansion of original data demand demand Optimal ship-size 2-1,826 TEU 2-2,508TEU Maximal total profit per average voyage $USD 282,079 $USD--340,881 Maximal unit ship-slot profit per $USD 77/TEU $USD--68/TEU average voyage Table 11. Comparison between two different demand forms based on 30% of original fluctuation data Based on Based on fluctuating the average +30% expansion of original data demand demand Optimal ship-size 2-1,978 TEU 2-2,508TEU Maximal total profit per average voyage $USD 494,358 $USD--498,917 Maximal unit ship-slot profit per $USD 125/TEU $USD--99/TEU average voyage Table 12. Container configurations deployed at each calling port based on fluctuating demand Calling ports Constitutions QD SH KL KHS BS KTK Owned quantity 340 365 480 390 565 425 Long-term quantity 235 300 253 239 236 384 Short-term quantity 235 290 302 261 379 406 Total quantity at port 810 955 1035 890 1180 1215

Printer friendly Cite/link Email Feedback | |

Author: | Chen, Chao; Zeng, Qingcheng |
---|---|

Publication: | Transport |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Mar 1, 2010 |

Words: | 8792 |

Previous Article: | A fuzzy model for an increase in locomotive traction force/Neraiskusis modelis lokomotyvu traukos jegai didinti. |

Next Article: | Finite element based adaptive neuro-fuzzy inference technique for parameter identification of multi-layered transportation structures/Besikeiciancios... |

Topics: |