An optimization model for container inventory management

Abstract

This paper formulates the empty container repositioning (ECR) problem, which is one of the most important issues in the container shipping industry, by running a model to generate the service route of feeder shipping in a dynamic environment. The objective is to reduce the disequilibrium of laden and empty containers. This paper first provides a literature review with the emphasis on the shipping scheduling and modelling of ECR. Second, a network model has been designed to find the optimum size of ship servicing a particular region. A simply ECR policy is tested to demonstrate an essential impact on the profit of a container transport system. With the aid of this heuristic shipping model, ECR is integrated with the tramp ship routing problem under dynamic condition.

1 Introduction

Maritime transport is the backbone of international trading (United Nations 2014, 2015). Nowadays, over 80% of merchandise trade in the world by volume delivered on the sea (Yip et al. 2011). Containers take an important role for reducing damages and leading to higher productivity during handling phases (Vojdani et al. 2013). Since 1990, container trade, which is counted in terms of twenty-foot equivalent units (TEUs), is estimated to have a drastic increase 5 times. The industry is still expanding by the increase of infrastructure and the trading demand (Yip and Wong 2015; Liu et al. 2013).

Due to the expansion of maritime trading, the growths of both ship size and fleet size have been also synchronized with it. The paper concentrates on solving the empty container problem by fleet size optimizing modelling. In the past decades, the models are mainly built to solve three important causes of empty containers, which are trade imbalance, dynamic operation, and uncertainties. Previous studies that have been done for dealing with this problem are mainly by network flow modelling and state-feedback control modelling (Song and Dong 2015). However, some new difficulties are needed to be faced. As the increase in the ship size with the same freight demand, the ship schedules may be changed with fewer service frequencies (Tran and Haasis 2015a, b). There will be accumulation of serviced empty containers. Fleet expansion is also a serious cause of empty containers as the expansion of freight demand cannot be confirmed (Hutchins 2015).

The main objective of managing the whole fleet of containers is to ensure that sufficient numbers of empty containers of various types, properly maintained, at the right time and in the right place to fulfil the customer demand with demand uncertainties and adverse weather in the container delivery system. In the related literature, previous studies mostly focus on generating the routes and schedules to optimize the performance. To sum up, the network model in the literature of this discipline has been designed to find the optimum size of container fleet or optimum size of ship servicing a particular region.

The paper is structured as follows. Section 2 is Literature Review about the trend of shipping industry, empty container repositioning and shipping fleet planning. Section 3 is Program description and model formulation. Section 4 is the computation result. Section 5 includes some conclusions and evaluation.

2 Literature review

2.1 Trend of shipping industry

The development of the shipping industry can be also responded by the size of container ship fleet and container capacity. The size of container ship fleet around the whole world has a drastic increase since the 1990s. The carrying capacity has a great increase by a factor of 6 where the number of Twenty-foot Equivalent Units (TEUs) has been increased from 3.17 million in 1990 to 18.9 million in 2014. A stable growth is generally provided by top 20 container ship lines (CSLs). Their total share of carrying capacities increases from 39% to around 75%. One of CSLs, MSC advanced about 90 times for fleet capacity, and this expansion is brought by the growth of ship size. The maximum ship size was 4300 TEUs in 1988, up to 7100 TEUs in 1996, up to 15,000 TEUs in 2006, and is 18,000 TEUs now (Tran and Haasis 2015a, b). Another CSL, Orient Overseas Container Line (OOCL) has already signed a $951.6 million contract for shipbuilding with Samsung Heavy Industries for constructing six mega ships of 20,000 TEUs (Progressive Digital Media Transportation News 2015).

There are several relationships between volume of seaborne trade, container freight index, world fleet capacity, ship broken up age, new delivery and order of container ships have been suggested (Stopford 2009). Finally, a hypothesis that freight rate is partially proportional to fleet size has been suggested. On the other hand, as the freight rate decreases if more shipping capacity is in operation and no change in seaborne trade volume (Xu et al. 2011). As the seaborne trade volume is affected by many factors such as trade agreement and exchange rate, so the trade volume cannot be forecasted easily.

2.2 Empty container repositioning

The ECR problem is critical for perfectly meeting the customer demand by arranging the empty containers from surplus ports to deficit ports. It does not only consist of environmental impact, but also the environmental impact as it can reduce the unnecessary transfer of empty containers. There are six causes of ECR problem (Song and Dong 2015):

• Trade imbalance;

• Dynamic operation;

• Uncertainties by unpredicted elements;

• Different types of container;

• Lack of visibility; and

• Companies’ operation practices.

The fundamental cause of ECR problem is trade imbalance which the trade in one direction is more than that in the opposite direction. There are three main trade routes listed by United Nation (UN) publications: Trans-Pacific (North America-Asia), Trans-Atlantic (Europe-North America) and Europe-Asia routes. For example, in 2012 the Euro-Asia trade container flow from Europe to Asia was about 6.3 million TEUs and for the opposite side it was about 13.7 million TEUs (Song and Dong 2011). As a consequence, the shipping companies should reposition about 7.3 million TEUs of empty containers from Europe to Asia. The trade between Europe-Asia and Trans-Pacific is totally imbalanced and it means that there are more goods transferred from Asia to Europe than that of the opposite direction. The difference between two routes can be briefly known as the number of empty containers which are needed to be transferred from surplus ports to deficit ports.

The second cause of ECR problem is dynamic operation, which is a normal characteristic of any transportation system. It can be understood as the supply and demand of empty containers. The whole container operation covers different ports in different places by some planned routes with fixed schedules and the service frequency ranges from several days to several months. On the supply side, the operation requires time to discharge the laden containers to empty containers in the designated port or nearby. However, the supply of laden containers in each port changes over time. On the demand side, it is mostly related to the trade demand as it changes over time for many reasons, such as seasonal products like festivals goods and agriculture products (Wolff et al. 2012). Although some operation planning can be done to reschedule due to the variation of demand and supply, the demand and supply of containers must have a proportion of mismatch. The expansion of ship size leads the problems to be more serious as the turnaround time of ships must be reduced. The expanded capacity by the ship size expansion cannot totally meet the change of demand of the trade demand or vice versa (Tran and Haasis 2015a, b).

The third cause of ECR problem is Uncertainty, is also the other normal characteristic of any transportation system. There are several unpredictable elements that affect the container shipping system. They include breakdown of equipment, unavailability of resource, port congestion, turn down of port and even sudden change of trade demand by political and environment issues. These issues may increase the transport time of containers or even change the parking ports of the ship or the whole schedule of ships. Not just those serious elements, even weather conditions and traffic congestion may increase the transport time. The uncertainties cannot be predicted easily, and this cause cannot be solved easily.

There are several types and sizes of containers, and they have different dimensions and designs for specific uses. The shortage of any one particular type of containers can also cause an ECR problem. For example, in some major agriculture exporting countries such as Thailand and Vietnam, reefer containers have a higher imbalance than dry containers. Different containers have different mass density. A twenty-foot container normally has a higher volumetric mass density than that of 40-foot container. Moreover, a portion of empty containers on board is necessary to maintain the balance of vessels.

Lack of visibility in the multimodal transport system is another cause of excess empty containers. Some of the containers are delivered by truck or rail, but some other containers are at the small inland terminals or storages of consignee and consigner. Some of the fleets can be traced containers’ location and status in real-time. Accordingly, the whole fleet can be managed effectively.

Companies’ operation practice is the last main cause of ECR problem. The shipping companies must concern more on laden containers than empty containers. The ship capacity constraint is a factor affecting the performance of ECR. On the other hand, the supply of empty containers depends on the supply of laden containers. Unnecessary transfer of empty containers exists if there is an inaccurate forecasting of empty containers or even the whole fleet forecasting.

To resolve the ECR problem, five requirements need to be addressed:

• Determine the optimum ship size and container fleet;

• Decide on a split between leased and owned containers;

• Ensure containers are maintained properly to meet regulatory requirements and scrapped and sold at the end of their useful life;

• Reposition empty containers from ‘surplus’ terminals to ‘demand’ terminals to ensure that forecasting booking can be solved; and

• Keep tracking the status and the movement of all containers to ensure proper management of assets under the system control.

The ECR problem cannot be completely eliminated but can be diminished. Among all of the mentioned six causes, the trade balance is the key cause. Also, the dynamic operation is very important and needs more concern as the increase of ship size has boosted the ECR problem. After introducing the causes, the solution for this problem has been introduced.

Determining the optimum ship size and container fleet is to avoid unnecessary containers to be kept in the fleet. It requires a long-term plan because the servicing duration of a container is about 15 years. Fleet management and ECR should be considered together to optimize the performance of the whole shipping system by avoiding lack of containers or too many empty containers. As the situations of liner shipping and tramp shipping are different, a particular model should be built to analyze each particular case.

After determining the number of containers needed, the next step for achieving the objective is to make a choice of proving containers by buying them from specialist manufacturers or leasing them from container owners (Institute of Chartered Shipbrokers 2015). Container leasing is common and the ownership of owned containers is about 50–60% of the world container fleet. There are two types of container leasing: Master leasing and term leasing. The master lease can be understood as a service arrangement as the customer can use the containers unless the lease expires. The leasing company is in charged in the full management, which include repositioning, storage and maintenance. The idea of master leasing is to lease to other parties one the original company produce over numbers of containers and avoid ECR. Term leasing has a fixed term period, ranging from a single trip to 8 years. The lessee should take the role in the management of containers which it opposite to the master leasing. Also, a model can be built to get the optimum lease spit (Dong and Song 2012a, b).

The containers should be used, maintained and laid off with specified regulations, which have been discussed and understood by all stakeholders. Also, the containers should be kept tracking the status and the movements as Container Safety Convention (CSC) set up standards from safety of using containers for freight transport by sea (Institute of Chartered Shipbrokers 2015).

Studies about ECR may be divided into three groups by their research contexts. The first group tackles on empty container repositioning problem in seaborne shipping networks; the second group tackles on intermodal or inland transportation network problems; whereas the third group tackles specific ECR such as ship fleet management and container fleet management.

Many studies have been done on empty containers repositioning (Song and Dong 2011, 2012; Olivo et al. 2012; Song and Dong 2013). However, it has just been built under the normal condition. The uncertainty and vulnerability, which may result in an increase of the difference between the demand and supply of empty containers, have not been included in the mathematical model. The disruption can affect both the port and the vessels performance (Di Francesco et al. 2013). The impact can make them fully or partially non-functional (Zhang et al. 2009). A dynamic model is needed to be built to resolve the empty containers problem which is generated by different kinds of uncertainties. Alternatively, a network model can be designed to find the optimum size of container fleet or the optimum size of ship servicing a particular region or type of ship route (Dong and Song 2012a, b). This kind of model can assist the company in the business plan of the coming years as the life time of a container normally is about 15 years.

2.3 Ship fleet management

Ship fleet management is a multi-dimensional and multi-modal topic and several system and software have been set up and offered in the market (PRWEB 2013; Investment Weekly News 2014; DNV, GL 2016). The objective of it is to aid the in optimizing fleet size in container shipping. It can be analyzed by various attributes which includes market size, market share, fleet vehicle types, and shipping route (Meng and Wang 2012a; Meng et al. 2012b; Varelas 2013). After those attributes have been analyzed, a forecasting demand of goods, containers and other transport modes can be estimated and an optimum fleet of containers can be determined.

However, the ship fleet management in this approach is static. The market size is iterative with the ship size. Thus, a new tool is needed to analyse the relationship between the ship size and market size. By the uncertainties of both demand and supply of container delivery, a good modelling for optimizing the size of a container ship or fleet is important to find out the best approach in purchasing new containers and ships. There are different kinds of operation mode in the shipping market, which can broadly be divided into liner shipping and tramp shipping. Liner shipping routes are fixed, but tramp ones are not. Tramp shipping is going to be analysed in the following part.

3 Problem formulation

3.1 Notations

The following notations are adopted in the following mathematical model.

Sets:

$N_0$ :

Set of ports including starting location;

N :

Set of ports;

V :

Set of ships;

T :

Set of periods;

Indices:

i, j:

Indices of nodes;

t :

Index of time;

Parameters:

$l_{it}$ :

Laden container inventory level at port i when the ship arrives at the first port in period t;

$e_{it}$ :

Empty container inventory level at port i when the ship arrives at the first port in period t;

$l_{i0}$ :

Initial laden container inventory level at port i;

$e_{i0}$ :

Initial empty container inventory level at port i;

$d_{it}^l$ :

Laden container demand at port i during period t;

$d_{it}^e$ :

Empty container demand at port i during period t;

$l_{it}^a$ :

Number of laden containers arriving at port i during period t;

$e_{it}^a$ :

Number of empty containers arriving at port i during period t;

I :

Freight income of delivering a laden container;

$S_i^l$ :

Stacking cost of laden container at port i;

$S_i^e$ :

Stacking cost of empty container at port i;

$L_i^l$ :

Lifting cost of laden container at port i;

$L_i^e$ :

Lifting cost of empty container at port i;

$V_{ij}$ :

Stacking cost of empty container from port i to port j;

Q :

Ratio of voyage cost to travelling time between ports;

k :

Capacity of the operating ship;

M :

Very large positive constant;

$\varepsilon$ :

Very small positive constant;

$T_{ij}$ :

Travel time from port i to port j;

D :

Duration for a period;

$D^{Tot}$ :

Total Duration;

L :

Time needed for a container loading from a port onto a ship;

U :

Time needed for a container unloading from a ship to a port;

$T_t^{Tr}$ :

Travelling time of the route for period t;

$T_t^{LU}$ :

Loading time and unloading time of the route for period t;

$T_t^O$ :

Exceeded time of the route for period t compared with the time limit.

Decision variables

$x_{ijt}$ :

1 if directly travels from port i to port j during period t; 0 otherwise;

$x_{ijt,t+1}$ :

1 if directly travels from port i in period t and arrives at port j in period $t+1$; 0 otherwise;

$l_{ijt}^{Tr}$ :

Number of laden containers carried when it travels directly from port i to port j during period t;

$e_{ijt}^{Tr}$ :

Number of empty containers carried by when it travels directly from port i to port j during period t;

$l_{ijt,t+1}^{Tr}$ :

Number of laden containers carried by when it travels directly from port i in period t to port j in period $t+1$;

$e_{ijt,t+1}^{Tr}$ :

Number of empty containers carried by when it travels directly from port i in period t to port j in period $t+1$;

$\phi _{{it}}$ :

Auxiliary variable associated with port i in period t used for the sub-tour elimination constraint;

$l_{jt}^L$ :

Number of laden containers picked up at port j during period t;

$e_{jt}^L$ :

Number of empty containers picked up at port j during period t;

$l_{jt,t+1}^L$ :

Number of laden containers picked up at the first port j visited in period $t+1$ based on the route assigned in period t;

$e_{jt,t+1}^L$ :

Number of empty containers picked up at the first port j visited in period $t+1$ based on the route assigned in period t;

$l_{jt}^U$ :

Number of laden containers discharged at port j during period t;

$e_{jt}^U$ :

Number of empty containers discharged at port j during period t;

$l_{jt,t+1}^U$ :

Number of laden containers discharged at the first port j visited in period $t+1$ based on the route assigned in period t;

$e_{jt,t+1}^U$ :

Number of empty containers discharged at the first port j visited in period $t+1$ based on the route assigned in period t.

3.2 Formulation

$$\begin{aligned} \max Z=&\sum _{j\in N} \left( I\times \left( {l_{jt,t+1}^L +l_{jt}^L } \right) -L_j^l \times \left( {l_{jt,t+1}^L +l_{jt}^L +l_{jt,t+1}^{UL} +l_{jt}^{UL} } \right) \right. \nonumber \\&-L_j^e \times \left. \left( {e_{jt,t+1}^L +e_{jt}^L +e_{jt,t+1}^{UL} +e_{jt}^{UL} } \right) \right) \nonumber \\&-\sum _{i\in N} {\left( {S_i^l l_{_{i(t+1)} }^ +S_i^e e_{{i(t+1)}}} \right) } -\sum _{i\in N} {\sum _{j\in N_0 \backslash \{i\}} {V_{ij} \left( {x_{ijt} +x_{ijt,t+1}} \right) } },\quad \hbox {for}\ t=1,2,...,T \end{aligned}$$

(1)

subject to

$$\begin{aligned}&l_{jt}^L -l_{jt}^U =\mathop \sum \limits _{i\in N_0 } l_{ijt}^{Tr} -\mathop \sum \limits _{k\in N_0 } l_{jkt}^{Tr} \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(2)

$$\begin{aligned}&l_{jt,t+1}^L -l_{jt,t+1}^U =\mathop \sum \limits _{i\in N_0 } l_{ijt,t+1}^{Tr} -\mathop \sum \limits _{k\in N_0 } l_{ij(t+1)}^{Tr} \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(3)

$$\begin{aligned}&e_{jt}^L -e_{jt}^U =\mathop \sum \limits _{i\in N_0 } e_{ijt}^{Tr} -\mathop \sum \limits _{k\in N_0 } e_{jkt}^{Tr} \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(4)

$$\begin{aligned}&e_{jt,t+1}^L -e_{jt,t+1}^U =\mathop \sum \limits _{i\in N_0 } e_{ijt,t+1}^T -\mathop \sum \limits _{k\in N_0 } e_{ij(t+1)}^T \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(5)

$$\begin{aligned}&l_{j1} =l_{j0} \quad \forall j\in N_0 \end{aligned}$$

(6)

$$\begin{aligned}&l_{jt} =l_{j(t-1)} +l_{j(t-1)}^a -d_{j(t-1)}^l \nonumber \\&\quad +\left( {l_{j(t-1)}^U +l_{j(t-1),t}^U -l_{j(t-1)}^L -l_{j(t-1),t}^L } \right) \quad \forall j\in N_0 ,t=2,...,|T| \end{aligned}$$

(7)

$$\begin{aligned}&e_{j1}=e_{j0}\quad \forall j\in N_0 \end{aligned}$$

(8)

$$\begin{aligned}&e_{jt}=e_{j(t-1)}+e_{j(t-1)}^a -d_{j(t-1)}^e \nonumber \\&\quad +\,\left( {e_{j(t-1)}^U +e_{j(t-1),t}^U -e_{j(t-1)}^L -e_{j(t-1),t}^L } \right) \quad \forall j\in N_0 ,t=2,\ldots ,|T| \end{aligned}$$

(9)

$$\begin{aligned}&T_t^{LU} =\mathop \sum \limits _{i\in N_0 } \mathop \sum \limits _{j\in N_0 \backslash \{i\}} \left[ x_{ijt} \left( {\left( {l_{jt}^L +e_{jt}^L } \right) L+\left( {l_{jt}^U +e_{jt}^U } \right) U} \right) \right. \nonumber \\&\left. \quad +\,x_{ijt,t+1}\left( {\left( {l_{jt,t+1}^L +e_{jt,t+1}^L } \right) L+\left( {l_{jt,t+1}^U +e_{jt,t+1}^U } \right) U} \right) \right] \quad \forall t\in T \end{aligned}$$

(10)

$$\begin{aligned}&T_t^{Tr} =\mathop \sum \limits _{i\in N_0 } \mathop \sum \limits _{j\in N_0 \backslash \{i\}} \left( {x_{ijt} T_{ij} +x_{ijt,t+1}T_{ij} } \right) \quad \forall t\in T \end{aligned}$$

(11)

$$\begin{aligned}&T_1^{Tr} +T_1^{LU} -T_1^O =D \end{aligned}$$

(12)

$$\begin{aligned}&T_t^{Tr} +T_t^{LU} -T_t^O +T_{t-1}^O =D \quad \forall t=2,...,|T| \end{aligned}$$

(13)

$$\begin{aligned}&T_t^O \le D \quad \forall t\in T \end{aligned}$$

(14)

$$\begin{aligned}&l_{ijt}^{Tr} +e_{ijt}^{Tr} \le kx_{ijt} \quad \forall i,j\in N_0 ,i\ne j,t\in T \end{aligned}$$

(15)

$$\begin{aligned}&l_{ijt,t+1}^{Tr} +e_{ijt,t+1}^{Tr} \le kx_{ijt,t+1}\quad \forall i,j\in N_0 ,i\ne j,t\in T \end{aligned}$$

(16)

$$\begin{aligned}&\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{ijt} =\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{jit} \quad \forall i\in N_0 ,t\in T \end{aligned}$$

(17)

$$\begin{aligned}&\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{ijt,t+1}=\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{jit,t+1}\quad \forall i\in N_0 ,t\in T \end{aligned}$$

(18)

$$\begin{aligned}&\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{ijt} \le 1 \quad \forall i\in N_0 ,t\in T \end{aligned}$$

(19)

$$\begin{aligned}&\mathop \sum \limits _{j\in N_0 \backslash \{i\}} x_{ijt,t+1}\le 1 \quad \forall i\in N_0 ,t\in T \end{aligned}$$

(20)

$$\begin{aligned}&\mathop \sum \limits _{i\in N_0 \backslash \{j\}} x_{ijt} \le 1 \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(21)

$$\begin{aligned}&\mathop \sum \limits _{i\in N_0 \backslash \{j\}} x_{ijt,t+1}\le 1 \quad \forall j\in N_0 ,t\in T \end{aligned}$$

(22)

$$\begin{aligned}&x_{ijt} ,x_{ijt,t+1}\in \left\{ {0,1} \right\} \quad \forall i,j\in N,t\in T \end{aligned}$$

(23)

$$\begin{aligned}&l_{ijt}^L ,l_{ijt,t+1}^L ,l_{ijt}^{Tr} ,l_{ijt,t+1}^{Tr} ,l_{ijt}^U ,l_{ijt,t+1}^U ,e_{ijt}^L ,e_{ijt,t+1}^L ,e_{ijt}^{Tr} ,e_{ijt,t+1}^{Tr} ,e_{ijt}^U ,\nonumber \\&e_{ijt,t+1}^U \ge 0 \quad \forall i,j\in N\hbox {,}t\in T \end{aligned}$$

(24)

$$\begin{aligned}&T_T^O \ge 0 \quad \forall v\in V,t\in T \end{aligned}$$

(25)

$$\begin{aligned}&x_{iit} =0 \quad \forall i\in N\hbox {,}t\in T \end{aligned}$$

(26)

$$\begin{aligned}&l_{iit}^{Tr} =0 \quad \forall i\in N\hbox {,}t\in T \end{aligned}$$

(27)

$$\begin{aligned}&e_{iit}^{Tr} =0 \quad \forall i\in N\hbox {,}t\in T \end{aligned}$$

(28)

$$\begin{aligned}&\varphi _{jt} =\varphi _{it} +1-M\left( {1-x_{ijt}} \right) \quad \forall i\in N_0 ,j\in N\backslash \{i\},t\in T \end{aligned}$$

(29)

$$\begin{aligned}&\varphi _{jt} =\varphi _{it} +1-M\left( {1-x_{ijt,t+1}} \right) \quad \forall i\in N_0 ,j\in N\backslash \{i\},t\in T \end{aligned}$$

(30)

$$\begin{aligned}&\varphi _{it} \ge 0 \quad \forall i\in N_0 \hbox {,}t\in T \end{aligned}$$

(31)

$$\begin{aligned}&D={D^{Tot}}/T \end{aligned}$$

(32)

$$\begin{aligned}&V_{ij}=Q_\times T_{ij}\quad \forall i,j\in N_0 ,i\ne j \end{aligned}$$

(33)

3.3 Equations explanation

Equation (1) is the objective function of the problem, which is the net profit and consists of four components. The first part is the income of delivering laden containers. The second part is the lifting cost for loading and unloading the laden and empty containers. The third part is the stacking cost of laden and empty containers at each port. The last part is the voyage cost during a period and between two periods, respectively.

Constraints (2) and (3) define that the loading activities of laden containers at each port during a period and between two periods, respectively. Constraints (4) and (5) define that the loading activities of laden containers at each port during a period and between two periods, respectively. Constraints (6) and (7) determine the inventory level of laden containers in all periods. Constraints (8) and (9) determine the inventory level of empty containers in all periods. Constraints (10) and (11) calculate the loading time and travel time of a ship, respectively, based on the route assigned in a period. Constraints (12) to (14) set the bounds for the loading time and travelling time, which can be named servicing time. The service time of a ship in a period is greater than or equal to the total time for one period and does not exceed the time for two periods. Equations (15)–(16) state that the total number of laden and empty containers on board cannot be greater than the ship capacity. Constraints (17) and (18) are the flow conservation constraints. Constraints (19)–(22) limit each node can be visited at most once in each period. Constraint (23) states the routing decision variables to be binary. Constraint (24) states the flow of containers, loading and unloading quantities to be non-negative. Constraint (25) guarantees the exceeded time to be non-negative. Constraint (26) ensures no inter-ship activity within the same port in period t. Constraints (27) and (28) ensure the container flow within the same port in period t. Constraints (29) and (30) are the sub-tour elimination constraints. Constraint (31) ensures that the auxiliary variables to be non-negative. Constraint (32) states the total duration dividing by period. Constraint (33) states the relationship between voyage cost and travelling time between ports.

3.4 Assumptions

There are multiple solutions for maximizing Z, the accumulated net profit of the whole ship and container system. If the number of laden containers and empty containers loading and unloading can be chosen, the number of solutions will drastically increase. There is only either increase or decrease in the inventory level in when arriving each port. Also, the final number of laden and empty containers of each node after repositioning must tend to a same reference level independently, which can also be called an equilibrium (or balanced) point. The numbers of laden and empty containers requiring service have been fixed. This assumption can prevent the solution are not worse comparing to the simple and general cases. Therefore, a feasible solution or optimal loading and unloading command in each port can be easier to be developed. Laden container has a higher priory to be transported than empty containers. Also, the destination of laden containers is pre-fixed but empty containers are not. Several features take place after implementing the following seven assumptions:

• 1. Only either loading or unloading activity will take place at a port throughout the whole servicing operation.

• 2. The numbers of laden and empty containers of each port tend to reach an equilibrium (or balanced) point after loading or unloading process.

• 3. When the time limit is reached and the ship is on the way to the next port, the ship must move the next port first.

• 4. As there is a total duration which is the sum of time of periods, there must be a remainder when the total duration is divided by the number of periods. And, the remainder is added to the last period.

• 5. The forecast of demand of laden and empty containers are assumed to be accurate.

• 6. Laden containers have a higher priory to be transported than empty containers.

• 7. The destinations of empty containers have not been specified.

4 Solution methodology

In Sect. 3, program formulations have been set up and can be used to solve the problems. To optimize the performance, heuristics method is good to sort out the best solution within a large amount of possible solutions. Artificial Bee Colony (ABC) algorithm is applied to find heuristic solutions.

4.1 Artificial bee colony algorithm

In ABC Algorithm, a food source (solution) has fitness. The “bees” are going to find out a food source with a food source as fit as possible. There are three key steps or types of “bee” in the whole algorithm: employed bees, onlooker bees and scout bees (Karaboga 2005b).

The value, or say the quality, of a food source depends on two factors, which are user dissatisfaction and travelling time. For the sake of simplicity, a single quality is used to represent a food source. Employed bees are associated with a particular food source which they are recently exploiting. They grab the information of the particular source and share the information with the probability of profit. Onlooker bees are waiting in the nest and establishing food sources by receiving the information shared by employed bees. Scout bees are searching the whole search area for new food sources randomly.

The part of the colony consists of “employees” and the other part consists of “onlookers”. For every food source, there is only one employed bee. The employed bees whose food source has been exhausted by the bees will convert to be a scout. The full main idea can be stated below:

• Send the scout bees to random initial food sources

• REPEAT

  • Send the employed bees to the food sources and check their fitness

  • Calculate the probability of the sources whether the sources are preferred by onlooker bees

• Send the onlooker bees to the food sources and check their fitness

  • Stop the exploitation step of the sources which has been exhausted by the bees

  • Send the scout bees to the search area for searching for new food sources

• Memorize the best food source

• UNTIL (meeting specific requirements)

Based on the basic idea of ABC, the steps of ABC algorithm are summarized as follows:

• 1. Generate a set of solutions randomly as initial food sources $w_{i}, i = 1,{\ldots },\pi$. Assign each employed bee to a food source

• 2. Evaluate the fitness $f(x_{i})$ of each of the randomized food sources $w_{i}, i = 1,{\ldots },\pi$

• 3. Set a counter, $z = 0$ and limitation of food sources (solution), $w_{1}= w_{2 }= {\ldots } = w_{\pi }= 0$

• 4. REPEAT

  • a. Employed Bee Phase

    • i. For each food source $x_{i}$, enforce a neighbourhood operator, $x_{i}\rightarrow x^{*}$

    • ii. If $f(x_{i}) < f(x^{*}),$ substitute $x_{i}$ by $x_{i}^{*}$ and $l_{1}= 0$. Otherwise, $w_{1}= w_{1}+ 1$

  • b. Onlooker Bee Phase

    • i. For each food source $\hbox {x}_{i}$, undergo the fitness based roulette wheel selection method.

    • ii. For each food source $\hbox {x}_{i}$, enforce a neighbourhood operator, $x_{i}\rightarrow x^{\#}$

    • iii. If $f(x_{i}) < f(x^{\#})$, $\hbox {x}_{i}$ is substituted by $\hbox {x}^{\#}$ and $l_{i} = 0$. Otherwise $w_{1}= w_{1}+ 1$

  • c. Scout Bee Phase

    • i. For each food source $x_{i}$, $w_{i} = \hbox {Limit}$, $x_{i}$ is substituted by a randomly generated food source

    • ii $z=z + 1$

• 5. UNTIL (Reaching Operation Cycle)

After figuring out the idea of ABC, the solution representation and neighbourhood operators have to be introduced to make the container inventory management problem fit it to the ABC algorithm.

4.2 Solution representation

In order to apply the ABC, identifying the food source, solution, is a must for the bees throughout the whole algorithm. z(x) is set up as the cost function of the whole delivery process.

First, the solution is represented in the form of a vector with a length of ($\hbox {number of nodes} + \hbox {number of vehicles} + 1$). A sequence should start and end with 0, which denote the starting point, to simulate the port will travel from starting to visit the ports. Consider a network with 8 ports in the first period (Fig. 1).

Fig. 1

Solution representation

The 0 in the middle means the jobs splitting between two vehicles. The ship passes through

$$\begin{aligned} 0\rightarrow 5\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 7 \rightarrow 1\rightarrow 6\rightarrow 8. \end{aligned}$$

Then, an initial solution is generated by putting the ports into the solution vector accordingly. Then the sequence will be shuffled several times. The number of shuffle equals to the half of the number of ports. A total of $\tau$ solutions are generated during initialization. Then, a neighbourhood operator is used to find out new solution $X^{\#}$ from the current solution $X_{i}$. A neighbourhood operator will be further explained in the next part.

4.3 Neighbourhood operators

A neighbourhood operator is used to find out new solution $X^{\#}$ from the current solution $X_{i}$. A neighbourhood operator will be chosen from the pre-selected neighbourhood operators and applied for one time. Except the first period, the port after 0 is avoided to be moved as it is the last port of the previous period. The shaded position is under operation.

Three neighbourhood operators are chosen to put in my program for random selection:

• Random swaps

The operator randomly chooses two positions, i and j with $i\ne j$ and exchanges the positions (Fig. 2).

Fig. 2

Example of random swap

• Reversing a subsequence

The operator randomly chooses a subsequence and reverses it (Fig. 3).

Fig. 3

Example of reversing a subsequence

• Random swaps of reversed subsequence.

The operator randomly chooses two sub-sequences and swaps them. Then each of the swapped subsequence has a chance to be reversed with a 50% probability. The length of sequence has been limited to 3 (Fig. 4).

Fig. 4

Example of random swaps of reversed subsequence

4.4 Fitness evaluation

In every period, each onlooker chooses a food source randomly. In order to drive the choosing process towards a better solution, roulette-wheel selection method is implemented for randomly choosing a solution by setting the fitness value of each bee is inversely proportional to the cost function value. The probability of choosing the solution $X_{i}$ is then stated as:

$$\begin{aligned} p\left( {X_i } \right) =\frac{z\left( {X_i } \right) }{\mathop \sum \nolimits _{j=1}^\tau z\left( {X_j } \right) },i=1,2,\ldots ,\tau \end{aligned}$$

5 Numerical experiment

For parameter setting, the bee colony size was set to be 50, and the numbers of employed bees and onlooker bees were equal to half of the bee colony size (i.e., 25 for each), which can help on reducing parameters when conducting the program including the algorithm (Karaboga and Basturk 2007). 25 employed bees represent that 25 particular routes are recently exploited and 25 onlooker bees represent that 25 routes are established by receiving information from “employed bees”.

5.1 Numerical settings

The experiments is working on the instances for the number of ports which is similar to the network size experimented by others before. They are equally separated. The ship capacity is restricted as 10,000 TEU (i.e. $k=10{,}000$) first. Both loading and unloading times are fixed as 60 min for 100 TEU (i.e. $L=U = 60\,\hbox {min}$), in which 100 TEU is the minimum unit of loading or unloading. The speed of vehicles is 0.8 km per hour. The duration of the whole running process is 10 days (i.e. $D^{Tot}=T\ \times \ D = 10\,\hbox {days}$). And, the whole duration has been divided into 10 periods, and each period is one day. The number of ports are set to be 60 (i.e. $N = 60$). Freight income of delivering a laden container is $100,000 (i.e. $I = 100,000$). The range of stacking cost of placing an empty container at ports is from $1000 to $10,000 (i.e. $C_{i} = [1000, 10,000]$), while the stacking cost at each port is randomly set. The cost of lifting a laden container is $2000 and that of lifting an empty container is $2000. Furthermore, the voyage cost is $1000 per mile and the speed of the ship is 0.8 kilometre per minute (i.e. $V_{ij} = 1000\ \times \ T_{ij} /0.8$). Moreover, the limit for starting scout bee phase is 500/3 times of number of ports (i.e. $w_{i} = 500\hbox {N}/3$), which has been tested in a similar problem of Shui and Szeto (2015) who studied in public bike repositioning (Shui and Szeto 2015). All experiments were performed on a computer equipped with Windows 10, an Intel(R) Core(TM)2 Quad CPU Q9550 @ 2.83GHz 2.83 GHz, and a 8.00GB of RAM, and the program was coded by using Dev-C++ 4.9.9.2.

We have tested some ranges of parameters (e.g. cost of lifting, voyage cost, ship speed), while the numerical setting reflects the recent industrial situation. As the results should not be interesting academically, we do not report them here.

5.2 Special models

Two special models have been designed to validate the experiment result, and they are Dijkstra’s shortest path algorithm and Simplex method. A computation experiment and a Dijkstra’s shortest path algorithm (Gass and Fu 2013) with calculation in are both done to compare the accuracy of model and access the possibility of performing experiments that are more complex. For comparing the result easier, the dynamic model has been modified to a static model:

The ship capacity is enlarged to 18,000 TEU (i.e. $k = 18{,}000$) first. The duration of the whole running process is reduced to 1 day with 1 period (i.e. $D^{Tot}=T\ \times \ D = 1\,\hbox {days}$). 20 numerical runs have been done for each test. The number of ports are set to be 10 (i.e. $\hbox {N} = 10$). The range of distance between ports is from 3 to 58 miles (i.e. $sci = [3, 58]$) and the number of running cycles is fixed at 10,000. Furthermore, the voyage cost is $1000 per mile and the speed of the ship is 0.8 kilometre per minute (i.e. $V_{ij} = 1000\ \times \ T_{ij} /1$). Only Port 6 consists of containers required to transfer and the stacking costs of Port 7 are the least. In addition, the distance from the starting point “0” to Port 6 and distance between Port 6 and Port 7 are the least comparing to other decisions. Thus, he optimized route by Dijkstra’s Shortest path algorithm is $0 \rightarrow 6 \rightarrow 7$. The starting situation is shown in Table 1:

Table 1 Summary of initial situation of ports

The results of 20 runs are shown in Table 2:

Table 2 Summary of results of benchmark model

The computation experiment results of 20 runs are the same with minor difference in running time, 3.623 s in average with a range from 3.522 to 3.741 s. We also obtained the same objective value by Dijkstra’s shortest path algorithm with objective value (Tables 3, 4):

Table 3 Summary of container delivery

Table 4 Summary of manual calculation

The Simplex method was coded in EXCEL and ran on a computer with same setting. Due to the limitation of the Simplex method, we consider a problem of two destinations, and we split the Simplex programming into two iterations. The Simplex method gives the same result ($\$1937-\$70=\$1867$) as our heuristic model but takes more than 120 s to return a solution. For a more complex problem, the Simplex method will not be able to return a solution within reasonable time limit. The two iterations of Simplex calculations are shown in Table 5.

Table 5 Simplex method

The same optimized solution can be obtained by Dijkstra’s shortest path algorithm with objective value calculation and integer programming by the Simplex method. Furthermore, Shui and Szeto (2015) used ABC to tackle public bike repositioning successfully (Shui and Szeto 2015). After validation, the model is conducted in the following computation experiments.

5.3 Measuring method

There are two parameters for measuring the performance of modelling: (1) Objective value of the first period, and (2) Accumulated objective value of the whole duration. The objective value of the first period is used to measure the performance of the ECR model. The accumulated objective value is used to observe the impact of the container repositioning. 20 numerical runs have been done for each test as 5 pre-tests has been done and the standard deviation of objective value of the first period are not more than 3.

We have further conducted two sets of computational experiments. The first set of experiments attempted to solve our problem by applying a simple genetic method to the integer programming formulation of ECR problem Eqs. (1)–(33) directly, while the second set of experiments tested the performance of heuristic method with ABC algorithm. The results are summarised in Fig. 5. The simple genetic method sources the new iteration by testing the similar solutions.

Fig. 5

Performance of models with and without ABC algorithm

In order to compare the performance of the model with ABC and without ABC algorithm, the values of first period profit are recorded at every 5000 test iterations. The model with ABC algorithm is able to achieve a higher profit than the model without ABC algorithm throughout the whole experiment or 0.19% higher after 40,000 test iterations. In terms of average computational time, the models with and without ABC algorithm takes 95.517 and 95.523 s, respectively. The model with ABC algorithm is also faster than that without. Experimental results indicate that the ABC algorithm obtains more optimal solutions (higher profit) and more quickly on the ECR problem.

5.4 Operator test

Fig. 6

Operator test

The objective value of the first period is used as the parameter to compare the performance of operators and combined version, as shown in Fig. 6. A test has been done for every 5000 iterations. The Combined Operators version perform a better performance starting from 30,000 iterations. And, the running time of four cases of each run with 50,000 iterations is shown in Table 6.

Table 6 Running time of operators

Switch has a shorter running time than that of Combined Operators. But, Combined Operators show a better result with an acceptable loading time. Thus, Combined Operators have been chosen to perform the following experiments.

5.5 Convergence test

The objective value of the first period is used as the parameter to measure the performance of the model and to find out the convergence point. Figure 7 shows that by increasing the number of iterations, the accumulated net profit increases with the decreasing rate and converges after the iteration of 40,000. Therefore, we can conclude that 50,000 iterations can be used as the basic parameter to undertake the following experiments.

Fig. 7

Convergence test

Fig. 8

Ship size test

5.6 Ship size test

The accumulated objective value of the whole duration is used to observe the performance change of by increasing the ship size, the accumulated net profit increases with varying growth rates in Fig. 8. Therefore, generally speaking, using bigger ships can reduce the problems of empty containers, as the marginal transport cost of empty containers is reduced and the scale economy is achieved with bigger ships. However, the accumulated net profits are nearly fixed when the ship size increases sharply from 50,000 to 130,000 TEU and from 160,000 to 180,000 TEU. Between two sharp increasing regions, there is a stable region where only 1.35% increment is taken place in this region. The relatively constant values of accumulated net profits over certain ship size indicate that the increase of ship size only sometimes enhances the efficient repositioning of empty containers or reduces the stacking of empty containers.

It is interesting to observe that the improvement of net profits is continuous for a range of ship size. Then, at certain ship sizes (from 130,000 to 160,000 TEU), less rate of improvements are observed. When the ship size increases, the shipping network is radically evaluated to next optimal arrangement. On the other hand, it reflects that the structural change of routing network in the system is not always realized with small changes of ship size. This simulation finding reflects the real observation in the shipping industry that the ship size does not increase steadily but radically.

5.7 Initial mix of laden and empty containers

Several scenarios, with different initial mix of laden and empty containers, have been set up to compare the performance of empty containers repositioning (ECR) policy. The ECR policy means the active shifting of empty containers. In the presence of ECR policy, empty containers will be transferred to next port if the ship capacity is available and the stacking cost of next port is lower. In other words, in the absence of ECR policy, empty containers will stay at where they occur. Empty containers will become laden containers, when cargo arrives. The results of improvement are summarised in Table 7.

Table 7 Summary of results for different initial mix of laden and empty containers

In general, the accumulated net profit increases with fewer empty containers in the system. Our simply ECR policy leads to the maximum improvement when the initial ratio of empty containers at 80% and the great reduction in loss when the initial ratio of empty containers at 85 %. With experimental results obtained show two major characteristics. First, ECR provides a significant impact in all scenarios which mean more than 7.5% improvement. Second, the improvement is more significant when the initial ratio of empty containers is more than 75%.

6 Conclusions

In this paper, we have studied the empty container repositioning (ECR) problem and examine the problem with container inventory management under dynamic condition. We aim at specifying the ratio of empty containers and laden containers to achieve empty container equilibrium (or balance) among ports for handling containers. The problem is formulated into an ECR model by implementing artificial bee colony algorithm. Experimental results indicate that good solutions are efficiently generated by this solution approach, and it should prove useful for container inventory management. A simple ECR policy can significantly reduce the empty container imbalance and smooth the container transport process in tramp shipping system. We have demonstrated the usefulness of the container inventory management. The method and models used as adjustable for more complex container inventory problems and other shipping systems, where further factors should be considered. Also, the time horizon can be extended to tackle liner ship fleet planning, maritime fleet size and renewal problem and strategic fleet renewal problem in shipping.