# The Optimized Transport Scheme of Empty and Heavy Containers with Novel Genetic Algorithm

Authors: Lianwei Qu; Kang Chen; Bao Hongli; Jingshu Ma; Wan Tao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

To design the transport scheme of empty and heavy containers reasonably, a model with objective maximizing the route benefits is proposed. The model considered two factors: (1) the fluctuation of cargo transport demand and the switching of different voyages; (2) the optimal transport scheme of empty and heavy containers in slack and brisk seasons and the handover process of these two seasons. In order to solve this model, a novel GA is developed. With this model and algorithm, the optimal transport scheme of empty and heavy containers is put forward, and the optimization allocation of resources can be realized. The case study about China-Europe route proves that this model can improve the liner company's benefits effectively.


---

## Body

## 1. Introduction

Currently, there are many studies about optimization scheme of empty and heavy containers. Some studies [1–3] developed an optimization method studying the transporting scheme of empty containers based on simulation and two-stage random network model, and the model took short-term container leasing into consideration. Reference [4] studied the transporting plan of empty containers from a new perspective, which determined the number of empty containers to be transported by using inventory management theory and Markov process theory. With the constantly rising proportion of heavy containers to be transported, scholars paid more attention to the heavy container optimization problem among ports. Chen and Zeng [4] attempted to deal with the programming problem of empty and heavy containers simultaneously by utilizing decision supporting system. When studying container route optimization, they did an in-depth analysis about the optimization transporting problem of empty and heavy containers. Concerning the cyclical fluctuations of cargo demand, this paper proposed an optimization model of empty and heavy containers. However, this model does not consider two problems: the first one is the effect of network change has on transporting scheme of empty and heavy containers; the second one is the adjustment problem of different empty and heavy containers. Therefore, in this paper, we established an integer programming model aiming at maximizing the total voyage profits. Considering the variation of transport demand and alteration of routes, the optimal transporting scheme of empty and heavy containers is proposed. Finally taking the data of China-Europe route as research data, the practicality of model is tested.Before 2009 most researchers only fixed their attention on the slot allocation for empty containers, often called empty container relocation problem as we know. For example, Crainic et al. [2] raised two dynamic deterministic formulations to deal with the single and multicommodity cases; for empty container relocation they also put forward an ordinary model. Cheung and Chen [3] adopted a two-stage stochastic network model to optimize the empty container relocation problem and ascertained the minimum quantity of leased containers. Imai and Rivera [5] analyzed the accurate number of container fleet size and the relocation of the empty containers by utilizing simulation model. Li et al. [6] disposed the problem of empty container relocation by offering a new method. They applied methods of inventory management and Markov processes to analyze the quantity of empty containers conveyed among ports and compute the floor level and maximum quantity of the empty containers stored in ports. Feng and Chang [7] used a two-stage model considering both inventory management and the nature of the shipping network to deal with the empty container relocation problem. These studies above-cited are based on some assumption that the shipping routes are given and all transport demands are ought to be served. The latter assumption means that from one port to another, the number of full containers is fixed, so is the quantity of slot allocation for full containers.Lindstrom Bandeira et al. [1] wanted to use a decision support system to optimize the slot allocation both for full and empty containers simultaneously. But the system cannot serve all transport demand. Lu et al. [8] also optimized slot allocation for full and empty containers by using a new integer programming model. In this paper, we assume that shipping lines could give up some transport demand to obtain maximum profit.


## 2. Problem Description

### 2.1. The Transporting Process of Empty and Heavy Containers

The transporting process of containers includes two parts: the transporting process at sea and the circulation at ports.


#### 2.1.1. The Transport Process at Sea

The liner transport process at sea is relatively simple. Liner companies accomplish container transport by sailing among ports. During this process, route structure has a big influence on transport plan of empty and heavy containers. As shown in Figure1, shipping companies should consider the import/export demand of port 3 under the route structure of route (a), which is unnecessary in route (b). Apart from the direct influence route structure has on transport demand, its another influence is it limits the transport capacity of empty and heavy containers. For the case in route (a), shipping company should consider whether the total number of empty and heavy containers exceed the maximum vessel capacity. There are three segments on route (a), and each segment is loaded with containers between different ports. On segment 1, the total number of empty and heavy containers transported from port 3 to port 1 should not exceed the ship’s transport capacity.The diagram of segments.
(a)
(b)


#### 2.1.2. The Container Circulation at Port

The container circulation process at port includes transport cargoes, stock empty containers, empty heavy containers, and return empty containers. For instance, take port 2 in Figure2 as example. As shown in Figure 2, port 2 will import empty and heavy containers from port 1 and port 3. According to the attribution of containers, these containers should be divided into three categories: (1) empty containers owned by liner company, (2) heavy containers owned by liner company, and (3) short-term leasing heavy container. The circulation process of these three containers is different. After unloaded, the empty containers owned by liner companies will either be stored in container yard at port, or be loaded with cargoes and transported to the port of discharge. The heavy containers will be delivered to consignees after being unloaded from a ship. After being emptied and returned, heavy containers will either be stored at container yard, or shipped to the ports where empty containers are needed. Different from the two above mentioned containers, after unloading the short-term leasing containers, these containers will be returned to the port of discharge due to the relatively high leasing costs.Figure 2
The circulation of containers at port.It can be learned that from the container circulation process, shipping company should formulate a series of interactional plans, as shown below: the transport plan of empty & heavy container owned by liner company, transport plan of short-term leasing heavy containers among ports, and stock capacity of empty containers at each port. These schemes are not only influenced by determined factors like route structure, freight rate, handling costs at port, stockpiling costs, but cyclical fluctuation of transport demand.


### 2.2. Cyclical Fluctuation of Transport Demand

The fluctuation of transport demand among different ports has the following two characteristics:(1) the fluctuation of transport demand is obviously seasonal, which can be divided into the slack season with less transport demand and brisk season with more demand; and (2) there are slight fluctuations during both slack and brisk seasons, and the overall demand is relatively stable.According to those characteristics, we use the following method to deal with fluctuations of transport demand. One year is divided into four phases: slack season, the transition phase from slack season to brisk season, brisk season, and the transition phase from brisk season to slack season. In slack season and brisk season, the transport plan of heavy containers is not changed, while the transport scheme of empty containers can be adjusted anytime. In the other two transition phases, to accomplish the transition process between slack season and brisk season, both the transport scheme of empty and heavy containers can be adjusted. It should be noted that the transition here not only includes the transport scheme of different empty and heavy containers, but the transition of empty container stockpiling plan.


## 2.1. The Transporting Process of Empty and Heavy Containers

The transporting process of containers includes two parts: the transporting process at sea and the circulation at ports.


### 2.1.1. The Transport Process at Sea

The liner transport process at sea is relatively simple. Liner companies accomplish container transport by sailing among ports. During this process, route structure has a big influence on transport plan of empty and heavy containers. As shown in Figure1, shipping companies should consider the import/export demand of port 3 under the route structure of route (a), which is unnecessary in route (b). Apart from the direct influence route structure has on transport demand, its another influence is it limits the transport capacity of empty and heavy containers. For the case in route (a), shipping company should consider whether the total number of empty and heavy containers exceed the maximum vessel capacity. There are three segments on route (a), and each segment is loaded with containers between different ports. On segment 1, the total number of empty and heavy containers transported from port 3 to port 1 should not exceed the ship’s transport capacity.The diagram of segments.
(a)
(b)


### 2.1.2. The Container Circulation at Port

The container circulation process at port includes transport cargoes, stock empty containers, empty heavy containers, and return empty containers. For instance, take port 2 in Figure2 as example. As shown in Figure 2, port 2 will import empty and heavy containers from port 1 and port 3. According to the attribution of containers, these containers should be divided into three categories: (1) empty containers owned by liner company, (2) heavy containers owned by liner company, and (3) short-term leasing heavy container. The circulation process of these three containers is different. After unloaded, the empty containers owned by liner companies will either be stored in container yard at port, or be loaded with cargoes and transported to the port of discharge. The heavy containers will be delivered to consignees after being unloaded from a ship. After being emptied and returned, heavy containers will either be stored at container yard, or shipped to the ports where empty containers are needed. Different from the two above mentioned containers, after unloading the short-term leasing containers, these containers will be returned to the port of discharge due to the relatively high leasing costs.Figure 2
The circulation of containers at port.It can be learned that from the container circulation process, shipping company should formulate a series of interactional plans, as shown below: the transport plan of empty & heavy container owned by liner company, transport plan of short-term leasing heavy containers among ports, and stock capacity of empty containers at each port. These schemes are not only influenced by determined factors like route structure, freight rate, handling costs at port, stockpiling costs, but cyclical fluctuation of transport demand.


## 2.1.1. The Transport Process at Sea

The liner transport process at sea is relatively simple. Liner companies accomplish container transport by sailing among ports. During this process, route structure has a big influence on transport plan of empty and heavy containers. As shown in Figure1, shipping companies should consider the import/export demand of port 3 under the route structure of route (a), which is unnecessary in route (b). Apart from the direct influence route structure has on transport demand, its another influence is it limits the transport capacity of empty and heavy containers. For the case in route (a), shipping company should consider whether the total number of empty and heavy containers exceed the maximum vessel capacity. There are three segments on route (a), and each segment is loaded with containers between different ports. On segment 1, the total number of empty and heavy containers transported from port 3 to port 1 should not exceed the ship’s transport capacity.The diagram of segments.
(a)
(b)


## 2.1.2. The Container Circulation at Port

The container circulation process at port includes transport cargoes, stock empty containers, empty heavy containers, and return empty containers. For instance, take port 2 in Figure2 as example. As shown in Figure 2, port 2 will import empty and heavy containers from port 1 and port 3. According to the attribution of containers, these containers should be divided into three categories: (1) empty containers owned by liner company, (2) heavy containers owned by liner company, and (3) short-term leasing heavy container. The circulation process of these three containers is different. After unloaded, the empty containers owned by liner companies will either be stored in container yard at port, or be loaded with cargoes and transported to the port of discharge. The heavy containers will be delivered to consignees after being unloaded from a ship. After being emptied and returned, heavy containers will either be stored at container yard, or shipped to the ports where empty containers are needed. Different from the two above mentioned containers, after unloading the short-term leasing containers, these containers will be returned to the port of discharge due to the relatively high leasing costs.Figure 2
The circulation of containers at port.It can be learned that from the container circulation process, shipping company should formulate a series of interactional plans, as shown below: the transport plan of empty & heavy container owned by liner company, transport plan of short-term leasing heavy containers among ports, and stock capacity of empty containers at each port. These schemes are not only influenced by determined factors like route structure, freight rate, handling costs at port, stockpiling costs, but cyclical fluctuation of transport demand.


## 2.2. Cyclical Fluctuation of Transport Demand

The fluctuation of transport demand among different ports has the following two characteristics:(1) the fluctuation of transport demand is obviously seasonal, which can be divided into the slack season with less transport demand and brisk season with more demand; and (2) there are slight fluctuations during both slack and brisk seasons, and the overall demand is relatively stable.According to those characteristics, we use the following method to deal with fluctuations of transport demand. One year is divided into four phases: slack season, the transition phase from slack season to brisk season, brisk season, and the transition phase from brisk season to slack season. In slack season and brisk season, the transport plan of heavy containers is not changed, while the transport scheme of empty containers can be adjusted anytime. In the other two transition phases, to accomplish the transition process between slack season and brisk season, both the transport scheme of empty and heavy containers can be adjusted. It should be noted that the transition here not only includes the transport scheme of different empty and heavy containers, but the transition of empty container stockpiling plan.


## 3. The Optimization Model of Empty and Heavy Containers

### 3.1. Model Hypotheses

This model is established according to the following assumptions:(1) the density of liner schedule is on weekly basis and only container of 20 ft is considered; (2) shipping companies only adjust route structure once a time in a year; (3) every port can lease enough empty containers and have enough space to stock them, if they want; (4) to simplify calculation, the decision variables are not set as integer, besides, K in the model means the total working weeks within a year (52 weeks); (5) in nontransition phases, the number of heavy containers transported does not change; (6) it is assumed that 1-N1 week is set as slack season, N1+1-N2 is set as the transition phase of slack season and brisk season, N2+1-N3 is set as brisk season, and N3+1-N4 is set as the transition phase between brisk season and slack season.


### 3.2. Model Establishment

Based on the above analyses, a linear integer programming model is established. The specific formulation of model is shown as follows:(1)MaxZ=∑k∈K{∑i∈P∑j∈P[(Rijk-CFijk)×oxijk+(Rijk-CRijk)×rxijk-CEijk×oyijk]∑j∈P}-∑k∈K∑i∈PCSik×syiy,S.t(2)∑∀(i,j)∈SEG1(oxijk+rxijk+oyijk)≤U1,∀k∈K,(3)∑∀(i,j)∈SEG2(oxijk+rxijk+oyijk)⩽U2,∀k∈K,(4)oxijk+rxijk≤Dijk,∀k∈K,∀i,j∈P,(5)syik=∑j(oxjik-1+oyjik-1)+syik-1-∑j(oxijk+oyijk),∀k∈K,j∈P,(6)oxjik=oxjiN,∀k∈[1,N1],∀i,j∈P,(7)oxjik=oxjikN3,∀k∈[N2,N3],∀i,j∈P,(8)oxji1=oxjiN4,∀i,j∈P,(9)oyji1=oyjiN4,∀i,j∈P,(10)∑j(oxijk+oyijk)+syik-∑j(oxjik+oyjik)≥0,∀i∈P.


### 3.3. Model Explanation

The model aims at maximizing the total profitsZ of voyage, its decision variables are as follows: oxijk—the number of heavy containers which are owned by liner companies transported from port i to port j; oyijk—the number of empty containers which are owned by liner companies transported from port i to port j; rxijk—the number of heavy containers which are leased in short-term by liner companies from port i to port j; syik—the number of empty containers stocked in port i of week k.Equation (1) is the objective function, where i and j represent port, P is the set of all ports in all voyages, K is the total working week within a year, Rijk means the freight rate from port i to port j at week k, CFijk and CEijk represents from port i to port j, the total handling costs generated by one heavy container and empty container, respectively, CRijk represents the total costs of short-term container leasing costs and handling cost from port i to port j, and CSik is the stock cost of one TEU in port i. Equations (2) and (3) ensure that in the case with different route structures, the containers loaded on ship do not exceed shipping capacity on each segment, where SEG1 and SEG2 are, respectively, the segment set of route structure 1 and 2. Equation (4) means the heavy containers transported are not bigger than actual transport demand, where Dijk is the transport demand from port i to port j at week k. Equation (5) means the change of stockpile at ports. Equations (6)–(9) assure that in slack season and brisk season, the number of heavy container transported between ports is constant. The model is liner programming model, which can be solved by using classic algorithm.


## 3.1. Model Hypotheses

This model is established according to the following assumptions:(1) the density of liner schedule is on weekly basis and only container of 20 ft is considered; (2) shipping companies only adjust route structure once a time in a year; (3) every port can lease enough empty containers and have enough space to stock them, if they want; (4) to simplify calculation, the decision variables are not set as integer, besides, K in the model means the total working weeks within a year (52 weeks); (5) in nontransition phases, the number of heavy containers transported does not change; (6) it is assumed that 1-N1 week is set as slack season, N1+1-N2 is set as the transition phase of slack season and brisk season, N2+1-N3 is set as brisk season, and N3+1-N4 is set as the transition phase between brisk season and slack season.


## 3.2. Model Establishment

Based on the above analyses, a linear integer programming model is established. The specific formulation of model is shown as follows:(1)MaxZ=∑k∈K{∑i∈P∑j∈P[(Rijk-CFijk)×oxijk+(Rijk-CRijk)×rxijk-CEijk×oyijk]∑j∈P}-∑k∈K∑i∈PCSik×syiy,S.t(2)∑∀(i,j)∈SEG1(oxijk+rxijk+oyijk)≤U1,∀k∈K,(3)∑∀(i,j)∈SEG2(oxijk+rxijk+oyijk)⩽U2,∀k∈K,(4)oxijk+rxijk≤Dijk,∀k∈K,∀i,j∈P,(5)syik=∑j(oxjik-1+oyjik-1)+syik-1-∑j(oxijk+oyijk),∀k∈K,j∈P,(6)oxjik=oxjiN,∀k∈[1,N1],∀i,j∈P,(7)oxjik=oxjikN3,∀k∈[N2,N3],∀i,j∈P,(8)oxji1=oxjiN4,∀i,j∈P,(9)oyji1=oyjiN4,∀i,j∈P,(10)∑j(oxijk+oyijk)+syik-∑j(oxjik+oyjik)≥0,∀i∈P.


## 3.3. Model Explanation

The model aims at maximizing the total profitsZ of voyage, its decision variables are as follows: oxijk—the number of heavy containers which are owned by liner companies transported from port i to port j; oyijk—the number of empty containers which are owned by liner companies transported from port i to port j; rxijk—the number of heavy containers which are leased in short-term by liner companies from port i to port j; syik—the number of empty containers stocked in port i of week k.Equation (1) is the objective function, where i and j represent port, P is the set of all ports in all voyages, K is the total working week within a year, Rijk means the freight rate from port i to port j at week k, CFijk and CEijk represents from port i to port j, the total handling costs generated by one heavy container and empty container, respectively, CRijk represents the total costs of short-term container leasing costs and handling cost from port i to port j, and CSik is the stock cost of one TEU in port i. Equations (2) and (3) ensure that in the case with different route structures, the containers loaded on ship do not exceed shipping capacity on each segment, where SEG1 and SEG2 are, respectively, the segment set of route structure 1 and 2. Equation (4) means the heavy containers transported are not bigger than actual transport demand, where Dijk is the transport demand from port i to port j at week k. Equation (5) means the change of stockpile at ports. Equations (6)–(9) assure that in slack season and brisk season, the number of heavy container transported between ports is constant. The model is liner programming model, which can be solved by using classic algorithm.


## 4. Solution of the Model

Because the integer programming model considers some additional constraints such as transport of heavy and empty containers, short-term container lease, and stock capacity of ports, it is hard to be solved. Genetic algorithms (GA) have been applied to a very wide range of practical problems, for example, transit dispatching [9, 10], route network optimization [11], and route headway design [12]. To find an approximate solution, we design a novel GA, named NGA hereafter. The running steps are as follows.Step 1 (Initialization).
Setn=0, and then generate an initial population Pn={popv|v=1,…,λ} where popv={oxijk,oyijk}; λ is the population size.Step 2 (Calculation of the Fitness Value).
Computing the fitness value of individualv as fitv with  (1).Step 3 (Convergence Judgment).
Checking whether the gap between the maximum fitness and the average fitness in current generation is less than the preinstalled thresholdμ, if yes, go to Step 4; otherwise, terminate the calculation.Step 4 (Implementation of Selection, Crossover, and Mutation Operations).
Letn=n+1 and do selection, crossover, and mutation operations to get a new generation of individuals Pn. Then return to Step 1.


## 5. Case Study

In this paper, we take the China-Europe voyage as our study object. During slack season, the Asia - Europe voyage is Qingdao-Hong Kong-Le Havre-Felix Stowe-Hamburger-Qingdao; during brisk season, the voyage is Dalian (DL)-Qingdao (QD)- Shanghai (SH)-Hong Kong (HK)-Le Havre-Felix Stowe-Hamburger-Dalian. The total amount of containers from Asia to Europe in slack season is about 10500 TEU. The freight in slack season is set as the average Maersk and COSCO’s freight rate promulgated between March and April. During brisk season, the transport demand is 50% higher than brisk season, and the freight rate is 100% higher. The stockpile cost of this liner company is 1 USD/TEU at ports in Europe, and 0.5 USD/TEU at ports in Asia.For calculation, we set the maximum calculating iterations as 200, the crossover probability as 0.92 and the mutation probability as 0.01. We will terminate the calculation when the gap between the maximum fitness and the average one is less than 0.002.After calculation, the result of model is obtained: the fluctuation of empty and heavy container’s transport demand at each port is shown in Figures3 and 4. It can be learned from Figure 3 that the transport scheme of heavy containers remains stable in majority of time. This result is in accordance with the hypotheses proposed in model.Figure 3
Heavy containers fluctuation of Asia ports.Figure 4
Empty container fluctuation of each port.To stabilize the transport plan of heavy containers, transport scheme of empty containers should be adjusted constantly, and that is the reason why the number of empty container from the first week to the twenty-sixth week of each port changes regularly. The effects of cyclical fluctuation of transport demand and route adjustment have on the allocation of empty containers are shown in Figure5. It can be seen that during slack season (from the 1th week to the 13th week), the amount of empty containers stocked in Asia ports and Europe ports fluctuates around 6000 TEU and 3000 TEU; while during the handover phase of slack season and brisk season (from the 4th week to the 26th week), the number of containers stocked at Europe port declines, and the empty containers stocked at Asia ports gradually increase. The reason why this outcome is generated is liner companies should store enough empty containers for the upcoming brisk season in Asia ports. In brisk season (from 27th week to 39th week), the number of empty containers in both Asia and Europe ports is 0. In this case, all the empty containers owned by liner company have been fully utilized, and meanwhile, the use efficiency is improved greatly.Figure 5
Empty container fluctuation of Asia and Europe ports.


## 6. Conclusion

In this paper, a model with objective maximizing total voyage profits is proposed. In this model, cyclical fluctuation of voyage, alteration of routes and the handover of transition scheme are taken into consideration. The case study verified the practicability of this model.



---

*Source: 434125-2013-02-04.xml*