Empty Container Repositioning

Abstract

Empty container repositioning (ECR) is one of the most important issues in the liner shipping industry. Not only does it have an economic effect on the stakeholders in the container transport chain, but it also has an environmental and sustainability impact on the society since the reduction of empty container movements will reduce fuel consumption, and reduce congestion and emissions. This chapter first analyzes the main reasons that cause empty container repositioning. Secondly, we provide a literature review with the emphasis on modeling the ECR problem from the network scope, e.g. modeling ECR in seaborne transportation network, modeling ECR in inland or intermodal transportation network, and treating ECR as a sub-problem or a constraint under other decision-making problems. Thirdly, we discuss the solutions to the ECR problems from the logistics channel scope perspective, which are categorized into four groups including organizational solutions, intra-channel solutions, inter-channel solutions, and technological innovations. Fourthly, we discuss the solutions to the ECR problems from the modeling technique perspective, which includes two broad research streams: network flow models and inventory control-based models. We then present two specific models representing the above two research streams, which aim to tackle the ECR problems in stochastic dynamic environments considering both laden and empty container management.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Container ships carry an estimated 52 % of global seaborne trade in terms of value (UN 2013). Container shipping has experienced a rapid development in the last two decades. According to the data from Containerization International (ci-online.co.uk) and United Nations (UN 2008, 2012, 2013), the container traffic has increased from 84.6 million TEUs (20-foot equivalent unit) in 1990 to 485 million TEUs in 2007 (before the global economic crisis in 2008), to 602 million TEUs in 2012. The annual growth rate was about 10.8 % in the period from 1990 to 2007, and about 9.3 % in the period from 1990 to 2012. The above growth rates were well above the average world trade growth rate around 6 %, and also showed the continuous growth despite the global economic crisis in 2008. There are several factors that have contributed to the rapid growth of container traffic in the world. Firstly, in the last two decades more and more goods have been containerized, not only the majority of manufactured goods, but also commodities such as coffee and refrigerated cargos (e.g. fruit, meat, fish). Secondly, the size of the containerships has increased dramatically from about 5000 TEUs in 1990s (Post-Panamax vessels) to 18,000 TEUs in 2013 (Maersk’s triple-E series, where the Triple-E stands for energy efficiency, economies of scale and environmental improvements). One major shipping line in China, CSCL, placed orders for even larger container ships in 2013, which are scheduled to carry 18,400 TEU and to be delivered in 2014. The deployment of the mega-vessels has reshaped the container shipping networks, e.g. from direct service network to hub-and-spoke systems in many cases, which requires more double-handling (i.e. transshipment) at the hub ports. For example, the share of transshipments in total port throughput has grown from 10 % in 1980 to 27 % in 2007 (UN 2008). Transshipment plays a particularly important role in hub ports such as Singapore, Hong Kong, Busan and Rotterdam. For instance, in Hong Kong port, transshipment cargo movements took up 57 % of port cargo throughput in 2011 (Hong Kong Census and Statistics Department 2012). Thirdly, the world trade becomes more imbalanced and empty container movements have accounted for a significant percentage of port traffic. The last point, empty container repositioning (ECR), is the main topic of this chapter.

The trade imbalance of container shipping and the economic impact of empty container management have been well documented in the literature. In the Europe-Asia and Trans-Pacific trade routes, European ports and American ports have been experiencing a high surplus of empty containers, while Asian ports are facing severe shortages. Drewry Shipping Consultant estimated that about 20 % of all ocean container movements have involved repositioning of empty boxes since 1998 (Mongelluzzo 2004; Drewry 2006). According to the data in the annual reports published by United Nations Conference on Trade and Development (UN 2005, 2008, 2011, 2012, 2013), the container trade volume from Asia to Europe was between twice and three times of the volume in the opposite direction in the last decade. In other words, at least half of the boxes moving westward to Europe were sent back empty. The percentage of empty container movements in inland networks could be higher since empty containers are often stored at ports or depots, which are away from the demand locations. Various reports have shown that the share of empty containers in hinterland transport ranges from 40 to 50 % of all containers transported (e.g. Crainic et al. 1993a; Konings 2005; Braekers et al. 2011).

A number of cost components could be incurred in relation to empty containers including handling and transshipping at the terminals/ports/depots, storage and maintenance at empty warehouses, chassis location for drayage, inland transportation by rail or truck, and seaborne repositioning by vessels. Various sources have provided estimations of the overall cost of empty container repositioning. For example, it was reported that the cost of container management inefficiencies in year 2001 reached almost US$ 17 billion (Boile 2006; Theofanis and Boile 2009). Drewry Consultant stated that empty container repositioning costs have reached US$ 20 billion yearly (Veestra 2005). Based on the data for 2002, Song et al. (2005) simulated the global maritime container shipping business and reported that the cost of repositioning empties was just under US$15 billion, which was about 27 % of the total world fleet running cost. It was estimated that shipping companies spent about US$ 110 billion per year in managing their container fleets (e.g. purchase, maintenance, repairs), of which US$ 16 billion (or 15 %) for repositioning empty containers (Rodrigue et al. 2013). It is estimated by the UN (UN 2011) that the cost of seaborne empty container repositioning was about $ 20 billion in 2009. If the cost of landside transportation of empty container repositioning is considered, the total cost would reach $ 30.1 billion and account for 19 % of global industry income in 2009. Although the reported figures of the total cost associated with empty container repositioning in the above sources were slightly different, they lead to the same conclusion, i.e. the cost is huge and has become a burden to the container shipping industry. In particular, the profitability of shipping lines is highly dependent on whether, or not, the empty repositioning cost is redeemable. For example, it was reported that a shipping company after implementing an empty container logistics optimization system has saved cost US$ 81 million in year 2010 (Epstein et al. 2012).

The container transport chain can be broadly described as follows (Fig. 6.1). Consignors (shippers) are regarded as the customers who require empty containers to transport their cargoes. Shipping companies are usually responsible for providing the required empty containers to their customers. Empty containers may be stored in an inland depot or a sea port. After consolidating the cargoes into the containers at the customers’ premise (or a depot or port), the laden containers will be transported to the depot or ports waiting for vessels. These laden containers are then lifted on a vessel in the booked shipping service. There may involve a couple of other shipping services for transshipment at sea ports before the laden containers finally reach the port of destination. Then the laden containers will be discharged from the vessel and transported to the consignees (cargo receivers) or a depot for unpacking. After unpacking, the empty container can either be moved/stored in an inland depot or a port for survey and reuse in the future, or be repositioned to other ports in the shipping networks to meet customer demands there. It can be observed that the container transport chain actually involves two supply chains: the forward supply chain of laden container flows, and the backward supply chain of empty container flows. A unique characteristic of container transport chains is that both laden and empty containers have to be moved and stored in the same shipping network using the same resources (e.g. vessels, trucks, trains, and facilities), which implies that these two supply chains are interwoven and difficult to separate. It should be noted that one important difference between laden container flows and empty container flows is that the former is driven externally by the customer demands whereas the latter is driven by the laden container flows and determined internally by the shipping companies themselves.

Fig. 6.1

The container transport chain. (Note: solid-lines indicate laden container flows and dashed-lines indicate empty container flows)

In a broad sense, the stakeholders in the container transport chain include shipping lines (including feeder operators), terminal operators, port authorities, depot operators, freight forwarders, inland transport operators (rail operators, road hauliers, barge operators), shippers or customers (consignors and consignees), container leasing companies, and others (e.g. associations, residents). In terms of empty container repositioning, the focal player is the shipping lines (ocean carriers), who usually bear the costs of repositioning empty containers and are responsible to transport both laden and empty containers at sea (port-to-port service) or even at inland as well (door-to-door service). It is therefore necessary to explain a bit more about shipping lines’ business operations. A shipping line usually operates a number of shipping service routes, which form an inter-connected shipping service network. A shipping service route refers to a fixed sequence of ports, in which a fleet of container vessels is deployed to provide regular service (normally weekly service). These vessels make round-trips (voyages) along the service route repeatedly. A port may be called at more than once in a single round-trip. The shipping lines normally publish their service routes and schedules on the Internet several months before the actual voyages.

The empty container repositioning (ECR) problem concerns arranging the storage and movements of empty containers in the shipping networks in order to better position the movable resources to better satisfy customer demands. Effectively and efficiently repositioning empty containers has been a very important problem in shipping industry. It does not only have significant economic effect, but also an environmental and sustainability impact since the reduction of empty container movements would reduce the emissions along the container transport chain.

The rest of the chapter is organized as follows. In the next section, we discuss the main reasons that cause the empty container repositioning. In Sect. 6.3, we explain the empty container repositioning problem and provide a literature review with the emphasis on ECR models from the network scope, e.g. modeling ECR in seaborne transportation network, modeling ECR in inland or intermodal transportation network, and treating ECR as a sub-problem or a constraint under other decision-making problems. In Sect. 6.4, we discuss the solutions to the ECR problems from the logistics channel scope perspective. More specifically, the ECR problems could be tackled internally within an organization, externally in the vertical logistics channel, externally in the horizontal channels (i.e. collaboration with other shipping companies), and through technological innovations. In Sect. 6.5, we discuss the solutions to the ECR problems from the modeling technique perspective focusing on two main research streams based on recent studies. We present two specific models that represent the above two research streams. The models aim to tackle the ECR problem in stochastic dynamic environments considering both laden and empty container movements simultaneously. Finally, conclusions are drawn in Sect. 6.6.

2 Causes of ECR Problems

Empty container repositioning has been an on-going issue since the beginning of containerization. But it has become more prominent in the recent decades due to the rapid growth of container shipping business and the regional difference in economic development. This section will discuss the critical factors that cause empty container movements, which include the trade imbalance, dynamic operations, uncertainties, size and type of equipment, lack of visibility and collaboration within the transport chain, and transport companies’ operational and strategic practices (Song and Carter 2009).

The fundamental reason for empty container repositioning is the trade imbalance, i.e. the trade in one direction is more than that in the other direction. The trans-Pacific and Europe-Asia routes are prominently imbalanced. Due to the China’s economic boom in the last three decades, there is ever-increasing container traffic demand out of China, although the importing volume to China is also increasing. The United Nation publishes an annual review of maritime transport, which lists the estimated container flows on three major trade routes: Europe-Asia, Trans-Pacific (North America-Asia), and Trans-Atlantic (Europe-North America) routes. For example, the annual container trade demands for the years from 2007 to 2012 are summarized in Table 6.1.

Table 6.1 Containerized trade demands in three major shipping routes in million TEUs. (UN 2011, 2012, 2013)

It can be seen from Table 6.1 that the trade demands in the Europe-Asia and the Trans-Pacific routes were severely imbalanced. The volume in one direction was more than double of that in the opposite direction. This indicates the scale of empty container movements in the global context since the empty containers have to be moved from surplus areas to deficit areas.

The majority of the existing literature on empty container repositioning has explicitly emphasized the importance of considering trade demand imbalance in empty container allocation/repositioning. For example, Crainic et al. (1993a) indicated that empty containers are often repositioned between depots in order to overcome regional imbalances. They proposed the concept of container flow balancing in the context of inland transportation network between depots, customers and ports. Cheung and Chen (1998) stated that most international trades in liner shipping industry are imbalanced in terms of the numbers of import and export containers due to the different economic needs in different regions. They focused on seaborne shipping network and proposed a single-commodity two-stage stochastic network model, in which the first stage is deterministic and aims to balance the empty container flows (including leasing empty containers) according to exogenous information of empty container supply and demand. Olivo et al. (2005) claimed that empty container movements would not exist in a perfect world as there would always be cargos to fill every container when and where it was emptied, but pointed out that in reality commercial traffic never seems to be in balance either in volume or value. They presented an integer programming model to balance container movements between ports and depots with multiple transport modes. Feng and Chang (2008) stated that the phenomenon of import-export imbalance is unavoidable in world trade and this results empty container problem in liner shipping industry. They studied the container balancing issue in an intra-Asia shipping network. Song and Carter (2009) considered the container balancing problem in three major trade lanes (Trans-Pacific, Trans-Atlantic, Europe-Asia) at the aggregated level, and analyzed four strategies that shipping companies could adopt to balance container flows depending on whether companies are sharing empty containers or coordinating empty containers among routes. Song and Dong (2011a) contrasted two types of container flow balancing policies, a point-to-point balancing policy, and a coordinated balancing policy. The policies were applied to a range shipping service routes with different topological structures to investigate their sensitivity to route structure and to the trade demand pattern.

The dynamic operation is the natural characteristic of any transport system since it covers different geographical locations and often requires transit time in weeks or months to access them. The impact of dynamic operations on empty container management may be understood from the perspective of the supply and demand of empty containers. The main supply source of empty containers is at the destinations of laden containers where they are discharged and unpacked and become empty containers for reuse, in particular at those import-oriented regions such as Europe and America. Note that the geographic locations of laden containers change over time in the shipping networks, the supply of empty containers therefore changes over time and space. On the demand side, the requirements of empty containers are driven by the trade demands, which also change over time for various reasons, e.g. seasonal products like agriculture produces, special festivals such as Christmas and Chinese New Year. These demand changes, although they may be predictable to a large degree, result in a dynamic impact on the container transport chain. The demands for empty containers and the arrivals of laden containers to be reused cannot match due to the time and space constraints and the volume difference. As a result, empty containers have either to be accumulated in advance to meet these expected increases in demand, or to be repositioned to the areas where empty containers are needed more urgently. The implication is that even if the overall laden container flows between two regions are balanced in long-term, the dynamic operations of the transportation system could be in favor of repositioning empty containers to order to improve container utilization. The impact of seasonality on the flow of empty containers has been confirmed by the empirical research in the Baltic Sea Region (Wolff et al. 2011).

Most of the existing literature on empty container repositioning has taken into account the dynamic operation explicitly or implicitly. Essentially, all studies that tackle the empty container repositioning problem at the operational planning level consider the dynamic nature of the environment explicitly. Examples of such studies (focusing on dynamic but deterministic situations) include: Shen and Khoong (1995); Lai et al. (1995); Olivo et al. (2005); Erera et al. (2005); Feng and Chang (2008); Erera et al. (2009); Di Francesco et al. (2009); Bandeira et al. (2009); and Song and Dong (2012).

The uncertainty is another key characteristic in container shipping, which represents the unpredictable elements that affect the container transport system. Uncertainty may occur during the operations in the container transport chain or during the interfaces with external environment. The former includes equipment breakdown, resource unavailability, port congestion, labor strikes (i.e. industrial action), bad weather (Notteboom 2006; Vernimmen et al. 2007). The latter includes random customer demands for empty containers and the instability of the political and economic environment (e.g. the financial crisis in 2008). The impact of uncertainty on empty container management may be explained as follows. For example, industrial action at a port may result in containers piled at the port and/or force container vessels to change their schedule. Weather conditions and traffic congestion may increase the transport time. As a result, these types of uncertainties cause either laden containers not to be delivered to customers on time, or empty containers not to be repositioned timely so as to meet the demands. Therefore, the movements of containers deviate from the plan and often incur extra container movements and costs. On the other hand, customer demand uncertainty probably has a more fundamental impact on container shipping operations. It is often the case that when shippers book the container in advance, often the day of pick-up is unpredictable. At present, liners tend to set up long-term contracts with big shippers, e.g. Maersk line with Argos. However, normally only the total volume within a period (e.g. a year) is specified in the contract whereas the detailed pick-up times of the shipments are unknown. Moreover, in the highly competitive shipping market, shippers have more choices and become more demanding. Therefore, it is extremely difficult for shipping lines to forecast the demands accurately. To accommodate the uncertainty in demands, shipping lines have to invest spare capacity, build up safety stocks, and reposition empties more efficiently. It has been illustrated that even in an overall balanced trade route, if the trade demands are uncertain, efficient empty repositioning could reduce the total cost significantly (Song 2007b).

Crainic et al. (1993a) is probably the first paper that addressed the empty container repositioning problem under stochastic/uncertain situations. Since then, a large number of studies have emerged in this line, for examples, Cheung and Chen 1998; Li et al. 2004, 2007; Lam et al. 2007; Song 2007a; Song and Dong 2008; Dong and Song 2009; Chou et al. 2010; Song and Dong 2011a; Yun et al. 2011; Epstein et al. 2012; Di Francesco et al. 2013.

Container size and type also affect the empty container repositioning. There are several different types of container that vary in their dimensions as well as the cargos they are designed to carry. The shortage of empty containers could happen because the size or types of available empty containers do not match customer requirements. Some regions such as Thailand may have a higher imbalance of reefer containers than dry containers. Even for dry containers, it has different grades including food grade, general purpose, and flexible grade. In shipping practice, normally 20-foot container is used for accommodating cargos with high volumetric mass density, while 40-foot one is used for cargoes with low volumetric mass density. Moreover, a full 40-foot container should not be 1.5 times heavier than a full 20-foot one in general. It has been observed that although some trade routes may not have significant trade imbalances, the need to transport empty containers may still be quite significant. One reason is that most types of cargo require, or it is more convenient to use, a specific type of containers (Branch 2000). Wolff et al. (2011) mentioned that the imbalance of container equipment could result from the fact that different goods types demanding for different equipment distinguished by dimension (e.g. TEU, FEU, high cube, pallet wide) and the specific application possibilities (e.g. reefers, tankers). Monios and Wilmsmeier (2013) analyzed highly disaggregated empirical data on container type movements and identified the container type diversification at UK ports, e.g. the use of high-cube and 45 ft pallet-wide maritime containers.

Rather limited literature has explicitly considered the size and type of containers when dealing with the empty container repositioning problem. Chang et al. (2008) allowed container substitution between different types in order to reduce the cost of empty container interchange under the street-turn and depot-direct schemes (i.e. empty containers can be directly distributed among customers without necessarily passing through container terminals). They considered a relatively compact transportation network, i.e. the Los Angeles/Long Beach port area. Wang (2013), which formulated a mixed-integer linear programming model for shipping network design and fleet deployment that took into account multi-type containers and empty container repositioning.

The lack of visibility of containers in the transport chain associated with the lack of collaboration between channel members in the supply chain is another reason to cause inefficiency in empty container management. International Asset Systems (IAS) used the term, blind spot, to describe the situation when containers are moving via rail or truck, or while they are in inland terminals or at shipper/consigner premises (Song and Carter 2009). Blind spots in the transport chain may prevent shipping lines from tracking each container’s location and status in real-time, thereby challenging liners’ efforts to improve container utilization. In other words, without having timely and accurate information of container status and location, shipping lines are unable to manage their container fleet in the most effective way.

In the last decade, with the development of information and communication technology, auto-ID systems (e.g. barcodes, optical character recognition (OCR), radio frequency identification (RFID)) started being applied to maritime containers. For example, Savi Technology and Hutchison Port Holdings (HPH) formed a partnership in 2005 to use active RFID technology to track ocean shipping containers. It was reported 40 terminals worldwide were outfitted with Savi readers placed on cranes that load and unload ships, and at gates to track the movement of containers. The data were uploaded to a database hosted by Savi Networks (Roberti 2005). The main objective is to secure container terminals (using electronic seals) and meanwhile to add business value (providing information to shippers). Nevertheless, the Savi Networks was shut down in November 2010 according to WorldCargo news online. A few research papers have reported the application of auto-ID technologies to track and secure containers in container yards and terminals at ports (e.g. Lirn and Chiu 2009; Chao and Lin 2010; Rizzo et al. 2011; Acciaro and Serra 2013); however, there were little discussion on such technologies in relation to empty container repositioning.

Transport companies’ strategies and operational practices actually determine empty container movements. Unlike the laden container movements that are largely determined by the shippers’ requirements, empty container repositioning is an endogenous activity determined by shipping companies. Inappropriate or inefficient practices would lead to unnecessary empty container movements. It is not unusual that empty containers may be re-repositioned due to the vessel capacity constraints and the priority of laden container movements. Some shipping lines form an alliance in which they may share vessel slots. Willingness to exchange or share resources with other carriers can provide more opportunities for container reuse and reducing empty repositioning. Transport companies’ strategies and operational practices, on the one hand, affect the actual movements of empty containers; on the other hand, act as the potential tools that the empty container repositioning problem could be tackled appropriately. This is the area that has attracted much attention in the last decade and extensive research has been carried out, which will be discussed in more detail in the next section.

Among all of the above factors, the trade imbalance is the root cause and accounts for the largest share for requiring empty container repositioning. This indicates that it is impossible to eliminate empty container movements completely in the real world. However, it has been recognized and demonstrated that through the development of innovative strategies and effective empty container repositioning policies, the costs and impacts associated with empty container repositioning can be reduced significantly. For example, Epstein et al. (2012) reported a cost saving of US$ 81 million for a shipping company after implementing the empty container logistics optimization system.

3 ECR Problems and Relevant Literature

Empty container repositioning problem aims to reposition empty containers efficiently and effectively in order to minimize the relevant costs while meeting customer demands for empty containers. This section will provide a literature review with the emphasis on modeling the ECR problems from the transport network scope.

An earlier literature review on empty container transportation was given in Dejax and Crainic (1987). They noted that “in spite of some very interesting problems with important practical applications, work in empty container allocation has still not integrated the latest methodologies created for the other modes (e.g. rail and truck) and has not yet generated any truly innovative modeling approach”. However, since 1990s, particularly in the last decade, numerous studies have been carried out in the area of empty container repositioning. Our literature will concentrate on those from 1990s.

A natural way to classify the empty container repositioning problems is based on the research scope of the underlying container transport networks. For example, the relevant literature may be classified into three groups according to the research context associated with the transport modes. The first group addresses empty container repositioning in seaborne shipping networks; the second group focuses on inland or intermodal transportation networks; whereas the third group tackles the empty repositioning problem as a sub-problem or a constraint under other decision-making problems.

In the first group, some studies consider a single shipping service route or a service network with specific route structure. For example, Lai et al. (1995) used a simulation model and some heuristic search methods to find cost-effective ways to reposition empty containers from Middle East ports to Far East ports in a Europe-Asia service route. Du and Hall (1997) proposed a threshold control policy to allocate empty equipment in a hub-and-spoke transport network. Li et al. (2004) and Song and Zhang (2010) established the optimality of the threshold-type inventory-based control policy in a single port subject to uncertain demands. Song (2007a), Lam et al. (2007) and Shi and Xu (2011) investigated the optimal empty container repositioning policies in two-port systems. Song and Dong (2008) developed threshold-type policies to reposition empties in cyclic service routes with uncertain demands. Li et al. (2007) and Zhang et al. (2014) extended the threshold control policy to multiple port systems. Feng and Chang (2008) presented a two-stage linear programming model for an intra-Asia shipping service route. Dong and Song (2009) employed the simulation-based optimization method and an inventory control based policy to deal with the joint optimization problem of container fleet sizing and empty container repositioning, in which the movements of both laden and empty containers and the constraints of vessel capacities are explicitly modeled. Chou et al. (2010) considered the empty container allocation problem in a single service route. A two-stage model is formulated. At stage one, a fuzzy backorder quantity inventory decision making model is proposed to determine the optimal quantity of empty container at a port; at stage two, an optimization mathematical programming network model is proposed to determine the optimal number of empty containers to be allocated between ports. Song and Dong (2011a) presented flow balancing-based empty repositioning policies in shipping service routes with typical topological structures. One advantage of focusing a specific structure of the service route is to provide opportunities to design optimal or near-optimal repositioning policies in stochastic situations. However, specific structure or a single service route simplifies the routing decisions and excludes the transshipment operations, which is an important phenomenon in container shipping operations.

On the other hand, some studies consider more general shipping networks. For example, Shen and Khoong (1995) optimized the flow of empty containers in a network with multiple ports over a planning horizon, in which vessels are not explicitly modeled. Cheung and Chen (1998) proposed a two-stage stochastic network model to allocate empty containers over a shipping network. They considered the random residual capacity for containers on the ships. Cheang and Lim (2005) developed a decision support system using a minimum cost flow model to distributing empty containers over a shipping network dynamically. The above three papers did not explicitly consider the topological structure of service routes and the regularity of vessel schedules. Erera et al. (2009) developed a robust optimization framework for dynamic empty repositioning problems modeled using time-space networks. They established the feasibility conditions of a repositioning plan and the recovery actions in response to uncertainties arising from forecasts of future container supplies and demands at different time epochs. Di Francesco et al. (2009) addressed the repositioning of empty containers in a scheduled maritime network. A multi-scenario multi-commodity time-extended optimization model is presented to minimize inventory, handling and transportation costs while meeting demand and supply requirements in every port. Moon et al. (2010) considered the empty container repositioning together with purchasing and short-term leasing options in a seaborne network. The problem is formulated as a deterministic multi-commodity model. A linear programming-based genetic algorithm and a hybrid genetic algorithm are proposed to solve the problem. Brouer et al. (2011) considered the laden container allocation and empty container repositioning for a liner shipping company. A multi-commodity time-expanded arc-flow model is formulated, which is then decomposed and solved with a delayed column generation algorithm. The model is able to handle large scale of shipping networks. Their work focuses on tactical planning without considering the details of transshipment between services. Song and Dong (2012) dealt the laden container routing and empty container repositioning at the operational level. A shortest-path based integer programming method and a heuristic-rules based integer programming method are proposed to solve the problem. The model assumes that there are at most twice transshipments for a laden shipment in the shipping network. Epstein et al. (2012) developed an empty container logistics optimization system (ECO) to support repositioning and stocking empty containers in a large shipping company. More specifically, the multi-commodity network flow model manages the repositioning problem, whereas an inventory model determines the safety stock required at each location. Long et al. (2012) formulated a two-stage stochastic programming model for the empty container repositioning problem in a maritime shipping network with uncertainties. The sample average approximation method and the progressive hedging strategy are applied to solve the optimization problem. Di Francesco et al. (2013) addressed the ECR problem in maritime networks under possible port disruptions. The problem is modeled by a time–space network and approximated by a multi-scenario model incorporating the non-anticipativity conditions.

In the second group, the studies focus on the empty container-repositioning problem in inland networks or intermodal transportation networks. The majority of the studies in this group focused on a regional scale. Braekers et al. (2011) conducted a comprehensive literature review on empty container management problems with the focus on the regional level, i.e. the empty container repositioning between importers, exporters, inland depots and ports within a small geographical area. More specifically, Crainic et al. (1993a, b) investigated the empty container allocation problem in the inland transport network in the vicinity of a seaport. Erera et al. (2005) developed a dynamic deterministic multicomodity network flow model for an intermodal transport network. They considered integrated container booking and routing decisions including empty repositioning. Olivo et al. (2005) proposed an integer programming model for empty container flows between container ports and depots across inland transportation network; Choong et al. (2002) investigated the effect of planning horizon length on empty container repositioning for an intermodal transport network. Bourbeau et al. (2000) presented a branch-and-bound parallelization strategy for the depot location and container allocation problems. Bandeira et al. (2009) proposed a heuristic method for integrated distribution of empty and full containers in an intermodal network. Yun et al. (2011) applied the (s, S)-type inventory control policy to reposition empty containers in an inland area between customers and terminals with random demands for empties. Simulation-based optimization tool is applied to find the near optimal (s, S) policy. Dang et al. (2013) extended the above work to a port area with multiple depots considering three types of decisions: repositioning empties from overseas ports, inland repositioning between depots, and leasing from lessors. The parameterized threshold policies are adopted for empty container repositioning and a simulation-based genetic algorithm is developed to optimize the threshold parameters. Lee et al. (2012) considered the joint empty container repositioning and container fleet sizing problem in a multi-port system, in which a single-level threshold policy is used to control the inventory and flow of empty containers among ports. Infinitesimal perturbation analysis method is applied to improve the computational efficiency. Because the formulation assumes that the travel time for each pair of ports is less than one period length and the shipping service routes are not explicitly considered, the model may be more appropriately regarded as a regional (inland or intermodal) network.

As intermodal networks are usually more complicated than seaborne shipping networks and the time-scale for inland transportation and sea transportation are significantly different, most of the above studies either focus on regional intermodal system (which is essentially an inland intermodal network) or treat container movements as flows and neglect individual vessels and their schedules.

The third group treats the empty container repositioning as a constraint or deals with it as a sub-problem within other decision making problems, e.g. dynamic empty container reuse (Jula et al. 2006; Chang et al. 2008), container fleet sizing with implicit empty container repositioning (Imai and Rivera 2001), transport market pricing and competition (Zhou and Lee 2009), shipping service route design (Shintani et al. 2007; Imai et al. 2009; Meng and Wang 2011a, Song and Dong 2013; Braekers et al. 2013; Wang 2013), ship fleet planning (Meng and Wang 2011b), and ship fleet deployment (Wang and Meng 2012).

Those joint optimization problems are often complicated. Most of them either use heuristics/meta-heuristics to tackle the problems or model the empty container repositioning in less detail to make it analytically tractable. Note that the motivation and focus of the studies in this group are often not directly from the empty container repositioning viewpoint; they might have been addressed in other chapters of the book.

4 ECR Solutions—the Logistics Channel Scope Perspective

In a broad sense, empty container repositioning problem covers any issues with the aim of mitigating the causes and the impacts of empty container movements and storage. From the logistics channel scope perspective, the ECR problems could be tackled internally within the shipping company, externally in the vertical logistics channel, externally in the horizontal channel (i.e. collaboration with other shipping companies), and through technological innovations. Accordingly, this section presents the solutions to the ECR problems under the following headings: organizational solutions, intra-channel solutions, inter-channel solutions, and technological solutions.

4.1 Organizational Solutions

Container fleet is a critical asset for an ocean carrier, which represents a large amount of capital. Empty container repositioning is a key component of the container fleet management, which includes a range of decisions such as fleet sizing, container leasing in/off, laden container routing, and empty repositioning. These decisions are highly related. For example, on one hand, increasing the number of owned containers, leasing extra containers and effectively repositioning empty containers can improve container’s utilization and therefore equivalently increase the container fleet capacity. On the other hand, larger fleet size incurs capital and maintenance costs; container leasing-in and off-leasing incur extra leasing costs; while repositioning incurs additional handling and transportation cost. The interaction between laden container routing and empty container repositioning is obvious due to the facts that the laden container movements essentially drive the empty container movements, and both laden and empty containers are transported over the same network and carried by the same vehicles (vessel, train and truck).

Shipping lines are the focal company in the container transport chain, who often takes the responsibility to manage the empty container transportation. It is therefore understandable that the majority of the literature focusing on the ECR seeks internal organizational solutions from a single company perspective (explicitly or implicitly). Most of the literature in Sect. 6.3 belongs to this category. In the following, we try to link the literature on ECR to other components of the container fleet management such as fleet sizing, container leasing and laden container routing.

Container fleet sizing aims to determine how many owned containers should be kept in the fleet, which is a long-term decision since the life-time of a container is about 15 years. Mainly due to the different time scale and the complexity, only a few papers consider the combined problem of fleet sizing and empty container repositioning. Imai and Rivera (2001) presented an analytical model to address the fleet size problem for refrigerated containers where empty container movements are implied. Crainic et al. (1993a) investigated the container fleet sizing and empty allocation by focusing on the inland part of container transportation. Dong and Song (2009) optimized the container fleet size and the inventory-based empty repositioning policy simultaneously in a seaborne shipping network with zero inland transport time. Dong and Song (2012a) investigated the container fleet sizing problem in liner shipping services with uncertain customer demands and inland travel times, and quantified the impact of inland transport time on container fleet size.

Container leasing mainly concerns when and where to lease in/off empty containers, which itself is a complicated issue. Note that the ownership of the world container fleet is mainly split over ocean carriers and leasing companies (called lessors). The data from Containerization International shows that about 50–60 % of the world container fleet was owned by ocean carriers in the period from year 2001 to 2007 (Dong and Song 2012b).

There are generally two types of container leasing arrangement: master lease and term lease. The master lease is more of a service arrangement than a lease in which the customers can pick up and drop off containers according to agreed limits and locations without regard for how long the specific container has been under its control (Transport Trackers 2008). The leasing company is responsible for the full management of the containers including repositioning, storage, and maintenance. The idea behind master leasing is that the leasing company may turn around and re-lease a returned container to other parties quickly and the lessee can avoid repositioning costs. Term leases have fixed length of leases including short, medium and long terms, ranging from a single trip lease (also called spot leasing) up to eight-year terms. Under this type of arrangements, the lessee has the responsibility for repositioning and maintenance of the leased containers before reaching the fixed lease term and returning them to the lessor. Theofanis and Boile (2009) pointed out that there is a tendency that ocean carriers prefer long term leases over master leases so that they can integrate leased containers with their own equipment. Transport Trackers (2008) confirmed the decline in the use of the master lease and stated the main reason for the shift from master lease to term lease is that the premium for master leases plus the costs to lessees associated with off-leasing began to exceed the cost of hauling them back.

Although many studies have addressed the container leasing issues together with empty container repositioning, most of them consider it in an implicit way with the focus on empty container repositioning. For example, a common assumption is that: containers can be leased from lessors whenever owned containers are out of stock to meet customer demands; after leasing in, the leased containers are treated as the same as owned containers or can be returned to lessors at any future time (Crainic et al. 1993a; Lai et al. 1995; Cheung and Chen 1998; Lam et al. 2007; Song 2007a; Moon et al. 2010).

Laden container (or cargo) routing concerns the efficient flows of laden container in the shipping network to meet customer requirements. The origins and destinations of cargos are externally determined by the customers, but the physical path from the origins to the destinations could be either specified by shippers/freight forwarders or determined by the ocean carriers. Intuitively, the traditional shortest path methods could be applied to deal with cargo routing problem. Particularly, for simple networks such as a single specific route, the decision on cargo routing is straightforward and the laden container movements are often implied in the relevant ECR literature (c. f. the literature in the first group in Sect. 6.3). However, as the complexity of the shipping network increases, e.g. involving more service routes with multiple voyages, the cargo routing and its interaction with empty container repositioning become more complicated. For example, Crainic et al. (1993a) recognized the desirability of jointly optimizing laden and empty container allocation in a single mathematical model, but argued that it would be infeasible to solve given the intrinsic complexity of the problem. Most of the ECR literature dealing with general shipping networks (cf. the literature in the first group in Sect. 6.3) generally ignored the laden container routing and movements. Nevertheless, with the advance in linear and integer programming and the development of computing power in the last two decades, Erera et al. (2005) argued that the joint optimization of loaded and empty container allocation became feasible for a reasonable size of problems. A couple of papers have started to address the laden container routing and empty container repositioning simultaneously, which are discussed below.

Erera et al. (2005) formulated a large-scale multi-commodity flow model for global tank container operator by integrating container routing and empty repositioning in a single model. They confirmed the economic benefit of simultaneously considering laden and empty containers. However, their model did not consider the details of the shipping service routes and the vessel capacity was not modeled (assuming infinite shipping capacity). Bell et al. (2011) presented a frequency-based assignment model to allocate full and empty containers over shipping services by minimizing the sailing time plus container dwell time at the original port and any intermediate transshipment ports. Again the vessel capacity was not explicitly modeled. Brouer et al. (2011) studied the laden and empty container dynamic allocation problem for a liner shipping company explicitly considering the vessel capacity. A time-expanded multi-commodity flow model with additional inter-balancing constraints to control repositioning of empty containers was proposed. The aim is to maximize the profit of transported cargo subject to the cost of transport both laden and empty containers, leasing empties and rejecting demands. Their model captured the essential characteristics of the shipping networks at the tactical level, although the details of transshipment between services and the inventory of empty containers were not modeled. They demonstrated the feasibility of solving large-scale problems with simultaneously optimizing laden and empty container movements. The computational results confirmed the economic benefit of the joint planning. Song and Dong (2012) focused on dynamic operational-level planning and addressed the cargo routing and empty container repositioning in a multi-service multi-voyage shipping network in more details. The objective is to minimize the total relevant costs in the planning horizon including: container lifting on/off costs at ports, customer demand backlog costs, the demurrage (or waiting) costs at the transshipment ports for temporarily storing laden containers, the empty container inventory costs at ports, and the empty container transportation costs. Two solution methods are proposed to solve the optimization problem. The first is a two-stage shortest-path based integer programming method, which combines a cargo routing algorithm with an integer programming of the dynamic system. The second is a two-stage heuristic-rules based integer programming method, which combines an integer programming of the static system with a heuristic implementation algorithm in dynamic system. They assumed that the laden container routing from the original port to the destination port is limited with at most three service routes in order to reduce the complexity of the cargo routing sub-problem.

4.2 Intra-Channel Solutions

The container transport chain consisting of consignor, shipping line, terminal operator, inland transport operator, depot operator, and consignee can be regarded as a vertical channel from the supply chain viewpoint. Intra-channel solutions emphasize on the coordination (including improving visibility, planning collaboratively, and achieving intermodalism) across different players in the vertical channel, which is a natural extension to the organizational solutions.

The literature in the second group in Sect. 6.3, to some extent, attempts to seek intra-channel solutions explicitly or implicitly using modeling techniques. They mainly focus on the coordination of empty container management in a regional area among terminals, depots, and customers with the assumption that information visibility can be realized and a single objective can be defined (e.g. Crainic et al. 1993a, b ; Bourbeau et al. 2000; Olivo et al. 2005; Choong et al. 2002; Bandeira et al. 2009; Yun et al. 2011; Dang et al. 2013).

Apart from the modeling research, empirical concepts and practices of intra-channel solutions have also emerged in the last decade. “Street turns” or “Empty reuse” refers to reusing import containers for export loads at the consignee’s site or in its proximity where direct exchange of empty containers between consignee and consignor can be realized. The potential benefits of street turn include: (i) truck trips to and from the port can be saved; (ii) the haulier can generate more revenue in less time; (iii) the ocean carrier can save paperwork and improve the container utilization; (iv) the export customer gets the empty container sooner; (v) environmental impact can be reduced, i.e. traffic, congestion, noise, and emissions (Tioga Group 2002). However, there are some challenges and barriers to implement street turns such as: (i) the haulier must identify the opportunity for reuse and communicate the opportunity to the driver; (ii) the agreement between the haulier and the ocean carrier must allow for such reuse and the ocean carrier must be able to track and document the interchange between parties; (iii) the place of the emptied import container should be reasonably close to the next exporter, and its available time should match the loading time window for exporting; (iv) the emptied import container must be in good condition and suitable for the export load, and the container/chassis combination must be acceptable at the terminal used by the export vessel (Tioga Group 2002). From the theoretical aspect, Jula et al. (2006) analyzed the potential cost and congestion reductions through the reuse of empty containers in the Los Angeles and Long Beach port area.

The concept of “off-dock empty return depot” refers to establish a neutral point to serve as buffer storage for container interchange and reuse. Empty containers would first accumulate at an off-dock empty return depot for cleaning, maintenance and repair, and then be reused for local exports or sorted and returned to a marine terminal at off-peak hours. This concept would add extra capacity to the maritime terminal and facilitate empty returns when terminal gates are closed (Tioga Group 2002; Hanh 2003).

Another concept is “depot-direct off-hire”, which refers to the process of off-hiring and repositioning an empty container to the leasing company at an inland depot directly before returning to the maritime terminal. This concept would cut at least one truck trip from each off-hiring and repositioning cycle when considering the trips of container and chassis movements among consignee, maritime terminal and inland depot (Tioga Group 2002). While “street turn” and “off-dock empty return depot” emphasize on the coordination between customers, shipping lines, depot and terminal operators, the concept of “depot-direct off-hire” focuses on the coordination between hauliers, depot operators, shipping lines and leasing companies.

The contractual relationship between ocean carriers and inland transport companies in terms of repositioning empty containers can take quite different formats. Lopez (2003) investigated the organizational choices of ocean carriers to reposition their empty containers in the USA. Four organizational formats were discussed including spot contract with road hauliers, one-year contract with rail operators, renewable contracts with road hauliers, and renewable contracts with intermodal marketing companies. It is observed that ocean carriers do not think about transaction costs, but they do adopt some mechanisms (e.g. renewable contracts) to control and to adjust their transactions in order to reduce those costs.

Van Der Horst and De Langen (2008) discussed the coordination issues among the players in the hinterland transport chain including shipping lines, terminal operators, forwarders, hinterland transport companies, and inland depot operators. They found that the development of the coordination in practice was hindered by a lack of contractual relationships, information asymmetry, and a lack of incentives for cooperation. They proposed four coordination mechanisms including introduction of incentives, creation of an inter-firm alliance, changing the scope of the relation and management, creating collective action. One benefit of the coordination between the terminal operators, hinterland depots, and shipping lines is to reduce empty movements.

Wolff et al. (2012) conducted a questionnaire survey to gain an empirical picture of different players in container transport chain dealing with empty containers in the Baltic Sea Region. It was found that the share of “street turns” in practice was in a range of 5–10 % in Hamburg. In terms of backhaul of empty containers, shipping lines prefer to have empty inventories and even depot services directly on the terminal so that they can move their container fleets more flexibly and decrease the throughput time. A range of measures to tackle empty container management were identified including: managerial and organizational measures (e.g. using spare capacities on vessel/vehicle of the own fleet; searching for return cargo; use container pooling; use spare capacities on the vessel/vehicle of other operators’ fleet; network design of empty container depots), pricing measures (e.g. selling empties in the surplus and buy new in the deficit area; freight rate surcharge on the high demand transport leg), ICT measures (e.g. use RFID to track and trace containers; use virtual container yards; use online market), and technological measures (e.g. implement foldable containers). It is concluded that no one single measure has a crucial positive impact on empty container management, a combination of measures is more promising, the success and choice of measures are highly player dependent.

In the past decades the container terminal industry has gone through the vertical integration process. For example, shipping lines have invested in terminal operations directly or through parent companies. Most global shipping lines have now owned the dedicated container terminals in various regions, which enables them not only managing the ships more effectively but also the empty container logistics. Therefore, establishing dedicated container terminals could be regarded as an intra-channel strategic measure to tackle empty container repositioning problems.

4.3 Inter-Channel Solutions

In container shipping industry, many container transport chains co-exist. For example, there were more than 400 shipping lines in the world (Song et al. 2005) and each of them may be involved in multiple container transport chains. The container management strategies across parallel container transport chains are classified as inter-channel solutions.

Container shipping industry is very unique in terms of the popularity of horizontal integration. Although shipping lines are the competitors as service providers, they also collaborate in various formats such as alliances, slot exchange, and resource pooling.

In the last decade, we have seen the emergence of external collaboration among carriers to achieve effectiveness of container operations and reduce costs. A few third or fourth logistics parties emerged to provide internet-based support. These systems can serve as a neutral platform to facilitate container sharing among shippers, forwarders, and shipping lines. The idea is gaining increasing popularity, however “There are still pockets of resistance, but the search to reduce costs outweighs the resistance to sharing containers” (Mongelluzzo 2004). A few examples are introduced below.

SynchroNet, founded in 1996, has developed a neutral global container management tool, termed “s|InterChange”. The system enables the registered shipping companies to interchange containers between parties on an inter-continental or intra-theater level and reposition surplus containers economically to deficit areas (www.synchronetmarine.com).

International Asset System (IAS) developed a neutral platform (termed IAS InterChange) that enables ocean carriers, container lessors and NVOCC (Non-Vessel Operating Common Carrier) to interchange containers in surplus and deficit locations. The registered customers provide ISA with the data of their equipment inventory and the InterChange will match between equipment suppliers and receivers in order to avoid costly repositioning. ISA also developed another service product, called SlotXchange. This tool is able to match empty containers with available slot space on ocean-going vessels. With SlotXchange, equipment owners can quickly reposition empty containers to the destination location, whereas the vessel operators with empty space can generate additional freight revenue by offering the empty slots. (www.interasset.com).

From the modeling aspect, Song (2007b) provided a theoretical analysis to a collaborative strategy in shuttle transport systems with uncertain demands. The dynamic programming model quantifies the cost saving of the collaborative strategy under different container dispatching policies. It is identified that the factors such as the container fleet size, the variance of demands, the demand patterns (balanced or imbalanced), and the container dispatching policy have significant impacts on the performance of the collaborative strategy. For example, the collaborative strategy can achieve more cost saving in situations with smaller fleet size or higher degree of uncertainty. It is reported that the cost savings are greater than 20 % in many cases, particularly when two companies have complementing demand patterns. On the other hand, if two companies have relatively large fleet sizes, low degrees of demand uncertainty, and similar patterns of imbalanced demands, then the collaborative strategy can only achieve rather limited cost saving. This might be one of the reasons that major shipping lines are reluctant to share containers with others in severely imbalanced routes such as Asia-Europe and Trans-Pacific.

Song and Carter (2009) further analyzed the inter-channel strategies to balance container flows at the global scale. According to whether shipping lines are coordinating the container flows over different service routes and whether they are willing to share container fleets with other companies, four strategies are defined for empty container repositioning: container-sharing and route-coordination; container-sharing without route-coordination; route-coordination without container-sharing; and neither container-sharing nor route-coordination. Here route coordination refers to ocean carriers acting as a single firm to balance its container flows across different service routes. Container sharing refers to pooling container fleets among different ocean carriers. The results show that route coordination offers more opportunities to reduce empty repositioning costs than container sharing in the container industry, which may further explain the reluctance of large carriers to adopt container-sharing practices.

Vojdani et al. (2013) formulated a space-time network model to evaluate the economic benefit of container pooling by several container carriers and container leasing companies. Numerical examples with three carriers, multiple routes, and multiple ports are provided to illustrate the positive influence on cost reduction compared with non-cooperative scenarios.

Liu et al. (2013) proposed a multi-commodity network flow model in a multi-carrier scenario and provided a cooperative game for container sharing among carriers. The issue of the cost/profit allocation mechanisms is addressed in relation to the format of container sharing mechanism.

Container transport chain is closely related to other supply chains such as manufacturing and purchasing channel, recycle channel, and secondary market channel. The International Institute of Container Lessors (IICL), whose member companies represent approximately 90 % of the container leasing industry and about 40 % of the world’s chassis, reported that the amount of container dispositions in 2009 was 530,485 TEUs and the estimated new purchase in 2010 were approximately 600,000 TEUs (IICL 2010). Inter-channel solutions can also be developed by linking the empty container repositioning issue with the management of those supply chains.

4.4 Technological Solutions

Technology development and innovations facilitate the development of organizational solutions, intra-channel solutions, and inter-channel solutions. On the other hand, technological innovations could offer a complete new set of solutions to the ECR problems, which may contribute directly to the cost reduction of the empty container transportation.

Note that the solutions to ECR problems from the previous few sections (particularly intra-channel solutions and inter-channel solutions) all depend on the support of information communication and technology. To enable channel members to collaborate to deal with the ECR problem together, a pre-requisite is to ensure the container logistics visibility to the relevant channel members. In practice, various players in the container transport chain have their own tracking system. For example, RFID technology has been used in maritime terminal to track the movement of containers inside the terminal (e.g. Roberti 2005; Lirn and Chiu 2009; Chao and Lin 2010; Rizzo et al. 2011; Acciaro and Serra 2013). Container haulage companies have GPS systems attached to their trucks to identify their locations and the containers they are carrying. Shipping lines have GIS/GPS systems to track the geographic location of the ships and the containers on board. Therefore, in theory it is possible to know whether a container is on board, in maritime terminal, in inland depot or at customers’ premises. This would help shipping lines to remove the blind spot in the inland transport chain. However, because of the concern that the release of the data may be misused by other parties and may not be advantageous, companies usually keep the information proprietary. The visibility of container logistic flow is still low in the current practice.

Supply chain integration either vertically or horizontally can only be achieved by the application of information technologies. As a higher level of control over container flows are established, the need for electronic data interchange (EDI) becomes essential. Timely and accurately information exchange between supply chain members can reduce the degree of uncertainty and offer more opportunities to manage the container fleet. Recent years have also seen IT become fundamental for security issues (E-manifest) and have incited the industry to move forward as a matter of compliance to advance notice schemes for the cargo being carried (Van Der Horst and De Langen 2008).

Although the ideas behind the internet-based platforms such as “s|InterChange”, “IAS InterChange” and “IAS SlotXchange” are essentially intra-channel or inter-channel solutions, their implementation highly relies on technology development.

Foldable (collapsible) container is a technological innovation to move empty containers more efficiently. It could greatly reduce the number of lifts and moves of empty containers at maritime terminals, and storage space on board. Several foldable (collapsible) container designs have been developed. Fallpac AB developed a Fallpac container in which four units can be folded and stacked inside a fifth erected unit. This means that a package of five empty containers occupies the space of a single standard container (Konings and Thijs 2001; Moon et al. 2013). The Six-in-One Container Company introduced a six-in-one container where six containers can be folded, bundled and interlocked to the exact dimensions of a single standard container (Konings and Thijs 2001). This implies that six empty containers can be treated as one container when loading/unloading at terminals and storing on board. Staxxon has designed a folding shipping container that can be folded vertically, shrinking to as much as one-fifth their normal size. Set side by side, five containers occupy the space of a single standard container. Staxxon is starting to test its model at terminals and believes that it has the potential to be the folding container that finally convinces shippers to start switching over (http://staxxon.com/). Moon et al. (2013) reported that foldable containers are currently under development by Holland Container Innovations and Cargoshell in the Netherlands and Compact Container Systems in the US.

Theoretically, several studies have been conducted to analyze and evaluate the potential application of foldable containers in the real world. Konings and Thijs (2001) discussed several conditions that are necessary for the successful commercial applications of foldable containers. Relevant issues include the folding/unfolding complexity and cost, the production cost, the technical features of foldable containers, the choice of the logistic concept, and product marketing. Konings (2005) further analyzed the opportunities for the commercial application of foldable containers and performed more detailed cost-benefit analysis in four logistic conceptual scenarios of using foldable containers to improve empty container repositioning: port-to-port, continent-to-continent, export depot-to-import depot, door-to-door scenarios. It is reported that the use of foldable containers can lead to substantial net benefits in the total container transport chain, but also much depends on the additional costs that foldable containers may incur such as the cost of folding/ unfolding, additional exploitation costs and any additional transport to places where folding and unfolding can take place. Shintani et al. (2010) evaluated the cost savings of using foldable container in the hinterland to reposition empty containers. Based on the possible movement of empty containers and the locations available for folding and unfolding activities, three unique scenarios were proposed for investigation. Moon et al. (2013) further explored the potential cost savings by using foldable containers for repositioning empty containers at sea transport networks.

Other aspects of technological innovations such as using more efficient quay cranes and new materials to constructing containers may also contribute to the cost reduction of empty container repositioning.

5 ECR Solutions—the Modeling Technique Perspective

Broadly speaking, the ECR modeling studies may be categorized into two research streams according to the applied modeling techniques and the type of the proposed solutions. The first stream adopts the network flow models and often applies mathematical programming to produce a set of arc-based matrices. The element in each matrix is a numerical value representing the quantity of empty containers to be moved on an arc (i.e. from one node to another node) in the network. Examples of the studies in this group include: the application of linear programming (Dejax and Crainic 1987; Shen and Khoong 1995; Bourbeau et al. 2000; Choong et al. 2002; Erera et al. 2005; Olivo et al. 2005; Cheang and Lim, 2005; Song and Carter, 2009; Song and Dong 2011b), stochastic programming (Crainic et al., 1993a; Cheung and Chen 1998; Erera et al. 2009), scenario-based linear programming (Di Francesco et al. 2009), sample average approximation based linear programming (Long et al. 2012), and multi-scenario mixed-integer programming (Di Francesco et al. 2013).

The second stream aims to develop effective state-feedback control policies which often uses inventory control, dynamic programming, and simulation-based optimization methods (e.g. Li et al. 2004; Song 2005; Song 2007a; Lai et al. 1995; Li et al. 2007; Lam et al. 2007; Song and Dong 2008; Dong and Song, 2009; Yun et al. 2011; Lee et al. 2011; Song and Dong 2011b; Dang et al. 2013; Lee et al. 2012; Zhang et al. 2014). The solutions of these empty container repositioning polices are similar to those in inventory control in production systems, and they normally consist of a number of decision-making rules associated with system dynamic states such as inventory levels of empty containers. By applying the rules at a decision epoch, the number of empty containers that need to be repositioned out or into a node can be determined dynamically. Several inventory-based control policies have been proposed in the literature; e.g., the double threshold policy (Li et al. 2004; Li et al. 2007; Song and Dong 2008; Dong and Song 2009; Song and Zhang 2010; Zhang et al. 2014), the dynamic port-to-port balancing policy (Dong and Song 2009; Song and Dong 2012), the coordinated (s, S) repositioning policy (Dang et al. 2013), and the single-level threshold policy (Song 2005; Song 2007b; Lee et al. 2012). It needs to be noted that each inventory-based control policy could have a number of variations depending on the way of splitting empty containers over ports. For example, Song and Dong (2011b) has proposed two variations of the double threshold policy termed as flexible destination port policy and determined destination port policy. The concept of flexible destination port repositioning was also adopted in Di Francesco et al. (2013).

There are also a couple of attempts to combine both the inventory model and mathematical programming model to solve the ECR problems. Chou et al. (2010) proposed a mixed inventory decision-making and mathematical programming model for dealing with the ECR problem. In stage one this paper proposes a fuzzy backorder quantity inventory model for determining the optimal quantity of empty containers at a port considering stochastic import and export at the same time. In stage two, an optimization mathematical programming network model is proposed for determining the optimal number of empty containers to be allocated between ports, which is based on the results for the fuzzy backorder quantity inventory model in stage one. The utilization of the proposed model is demonstrated with a case of trans-Pacific liner route in the real world. However, they focus on a single service route. Epstein et al. (2012) initially planned to develop a single, integrated, and robust optimization model that would address the ECR optimization problem with uncertainties, but realized that the time required finding an optimal solution was too long even for small instances. They then opted for developing a two-stage solution approach, which combines a network flow model and an inventory model, termed empty container optimization (ECO) tool. The ECO tool is based on two decision models supported by a forecasting system. At stage one, an inventory model takes into account the uncertainty in container supply and demand and determines the safety stock for each node in the network. At stage two, a multi-commodity multi-period network flow model addresses the imbalance problem and supports daily empty container repositioning and inventory levels. The service level is managed by imposing the safety stock as constraints in the network flow model with the assumption of normal distributions of the forecast demand. In addition, the ECO tool uses a collaborative web-based optimization framework to address the coordination problem among multiple agents with local objectives. However, both papers Chou et al. (2010) and Epstein et al. (2012), only focused on empty container logistics. The movements and routing of laden containers were not considered.

According to earlier discussions, the most important three reasons to cause empty container movements are probably trade imbalance, dynamic operations, and uncertainties. In particular, trade imbalance is the fundamental reason. Therefore, to model the empty container repositioning problem appropriately, it is desirable to model both laden container routing and empty container repositioning in the transport network simultaneously, because trade imbalance is represented by laden container movements whereas laden container movements are determined by the laden container routing.

In the remainder of this section, we present a few specific mathematical models for empty container repositioning problems (with a focus on maritime transport networks), which represent the above mentioned modeling techniques. All models consider both laden and empty container movements simultaneously. Some of them can also handle dynamic operations and stochastic environments. We make two common assumptions:

Assumption 1

all the containers and customer demands are measured in TEUs. One FEU (forty-foot equivalent unit) is treated as two TEUs.

Assumption 2

the vessels deployed in the same service route have the similar carrying capacity.

5.1 Time-Space Multi-Commodity Network Flow Model for Laden and Empty Container Management

This section introduces a time-space multi-commodity network flow model to deal with empty container repositioning problem, which is mainly based on Brouer et al. (2011). The model considers both laden and empty container flows in the shipping network over a given planning horizon. The customer demands are deterministic, but can take different values at different time periods.

We introduce the following notations for the model in this sub-section:

P :

the set of ports;

R :

the set of shipping routes;

T :

the planning horizon;

G :

a capacitated directed acyclic graph, G: = (N, A);

N :

the set of nodes, $N = {\text{ }}\{{p^t}|p\in P;{\text{ }}0\le t\le T\};$

A :

the set of arcs, $A: = {A_G}\cup {A_R};$

A _G :

the set of uncapacitated ground arcs,

$$ {A_G}: = {\text{ }}\{({{p^t},{p^t}^{+ 1}}){\text{ }}|{p^t}\in N;{p^t}^{+ 1}\in N\}; $$

A _R :

the set of capacitated sea leg arcs

A _R : = {(p ^t, ${q^{t + {\tau_{pq}}}}$ ) | p ^t ∈ N; ${q^{t + {\tau_{pq}}}}$ ∈ N; p ≠ q; u(p ^t, ${q^{t + {\tau_{pq}}}}$ ) > 0} where τ _pq is the travel time from port p to port q; and u(.,.) represents the aggregated capacity of the corresponding arc to be defined a bit later.

Cap _r :

the vessel capacity in the route r∈ R;

A ^r :

the set of sea leg arcs in the route r ∈R over the planning horizon, i.e. A ^r : = {(p ⁰, ${q^{0 + {\tau_{pq}}}}$), …, (r ^t, ${o^{t + {\tau_{ro}}}}$) | p, q,r, o ∈P}, where t + τ _ro can be regarded as T (more precisely, it refers to the latest time period before T when one of the vessels deployed in route r is berthing at a port);

u(i, j) :

the aggregated shipping capacity of the sea leg arc (i, j) ∈ A _R , i.e. u(i, j): = $\sum_{r\in R} {\sum_{(i,j)\in {A^r}}{Ca{p_r}}}$. Namely, u(i, j) is the accumulated vessel capacity of all service routes that have a voyage covering the sea leg arc (i, j).

K :

the set of commodities to be transported in the shipping network; a commodity k ∈K is represented by (O _k , D _k , d _k ), where O _k ∈N denotes the origin node, D _k ∈N denotes the destination node, and d _k denotes the volume of the commodity (i.e. the number of containers)

y ^k _ij :

the number of laden containers of commodity k on arc (i, j);

x _ij :

the number of empty containers on arc (i, j);

C ^k _ij :

unit cost of arc (i, j) for commodity k ∈K;

C ^e _ij :

unit cost of arc (i, j) for empty containers;

C ^k _p :

unit penalty cost for lost-sales of commodity k ∈K;

The objective is to minimize the sum of the laden container transportation costs, the empty container transportation costs, and the lost-sale penalty cost. The decision variables include the laden container flows, i.e. y ^k _ij , and the empty container flows, i.e. x _ij .

$$ \mathop {\min }\limits_{y_{ij}^k,{x_{ij}}}\{\sum_{k\in K} {\sum_{(i,j)\in A} {C_{ij}^ky_{ij}^k} }+ \sum_{(i,j)\in A} {C_{ij}^ex_{ij}^{}}+ \sum_{k\in K} {C_p^k[{d_k}-\sum_{j\in N,i = {O_k}}{(y_{ij}^k-y_{ji}^k)}]}\}$$

(6.1)

subject to

$$ \sum_{j\in N} {y_{ij}^k} -\sum_{j\in N} {y_{ji}^k} \quad \le {d_k},{\text{ for }}i = {O_k},k\in K; $$

(6.2)

$$ \sum_{j\in N} {y_{ij}^k} -\sum_{j\in N} {y_{ji}^k}= \sum_{j\in N} {y_{jm}^k} -\sum_{j\in N} {y_{mj}^k},\; {\text{for}}\;\;i = {O_k},m = {D_k},k\in K; $$

(6.3)

$$ \sum_{j\in N} {y_{jm}^k}= \sum_{j\in N} {y_{mj}^k} {,} \;{\text{for}}\;\;m\in N,m \neq {O_k},m \neq {D_k},k\in K; $$

(6.4)

$$ \sum_{k\in K} {} \sum_{j\in N} {y_{ij}^k}+ \sum_{j\in N} {x_{ij}^{}}= \sum_{k\in K} {} \sum_{j\in N} {y_{ji}^k}+ \sum_{j\in N} {x_{ji}^{}},\; {\text{for}}\;\;i\in N; $$

(6.5)

$$ {x_{ij}}+ \sum_{k\in K} {y_{ij}^k} \le u({i,j}),{\text{ for }}({i,j})\in A; $$

(6.6)

$$ {y^k}_{ij}\geq 0,{x_{ij}}\geq 0,{\text{ for }}k\in K,{\text{ }}({i,j})\in A; $$

(6.7)

The constraint (6.2) represents the satisfied demand of commodity k cannot exceed the volume d _k . Constraint (6.3) represents that the same amount of commodity k will be moved out of node O _k and moved into node D _k . Constraint (6.4) represents the flow conservation of commodity k at a node m that is neither O _k nor D _k . Constraint (6.5) represents flow balancing at any node considering both laden and empty container movements. Constraint (6.6) ensures that the total flows including both laden containers and empty containers on any arc do not exceed the shipping capacity of the arc. Constraint (6.7) is the non-negative requirements for the decision variables. More accurately, we should let the decision variables only take integers. Therefore, the above model is a linear integer programming model, which can be solved using commercial software such as IBM ILOG CPLEX.

The advantages of the above model include: (i) the formulation of the model is relatively simple and easy to understand; (ii) the empty container movements are derived from laden container movements, which reflects the reality; (iii) the model can handle variable demands over different time periods because a planning horizon is introduced; (iv) the lifting-on costs at the commodity’s origin port, and lifting-off costs at the commodity’s destination port can be easily incorporated. However, there are some drawbacks with the model: (i) although transshipments are modelled over the time-space shipping network, the associated costs are not included in the objective function. This may result in unnecessary or uneconomical transshipment in the solutions; (ii) the actual path that the commodity moves in the shipping network (including the information such as which service routes to use, which ports to transship) is not easy to identify. Brouer et al. (2011) reformulated the problem into a path-based network flow model, in which a path of commodity k consists of a sequence of arcs that connect from node O _k to node D _k . This helps to identify the flow of commodity on the arcs from its original port to destination port. Nevertheless, because the arcs are not associated with service routes, it is still not obvious to identify which specific service routes that carry the commodity in the path; (iii) the number of commodities could be very large in realistic scenarios, which may become computationally intractable.

5.2 Origin-Link Based Network Flow Model for Laden and Empty Container Management

As transshipment is a very important phenomenon in container shipping industry, particularly for the hub ports (such as Singapore, Hong Kong, Rotterdam, Busan), where transshipment traffic could account over 50 % of their total throughput, this section presents another network flow model that takes into account the transshipment costs and manages both laden and empty containers simultaneously.

We make the following assumptions in this section: (i) all service routes are of weekly frequency; (ii) the weekly demands for any O-D pair are constant; (iii) it is at the tactical planning level.

We adapt the origin-link-based linear programming model to managing the flows of both laden and empty containers in a shipping network. The idea of the origin-link-based linear programming model has been applied to shipping network design and ship deployment (e.g. Alvarez 2009; Wang and Meng 2012; Wang 2014).

The following notations are introduced for the model in this sub-section.

P :

the set of ports;

R :

the set of shipping routes;

R _p :

the set of routes that call at port p ∈ P;

N _r :

the number of portcalls in the route r ∈ R;

I _r :

the set of portcall indices in the route r ∈ R, i.e. I _r : = {1, 2, …, N _r };

p _ri :

the port that corresponds to the ith portcall in route r;

I _{r, p} :

the set of portcall indices corresponding to port p in the route r ∈ R, i.e. I _{r, p} : = {i ∈ I _r | p _ri  = p};

y ^l _{o, ri} :

the number of laden containers originating from o ∈ P that are loaded at the ith portcall in the route r;

y ^u _{o, ri} :

the number of laden containers originating from o ∈ P that are unloaded at the ith portcall in the route r;

y ^f _{o, ri} :

the number of laden containers originating from o ∈ P that are carried on board on the leg i (from ith portcall to i + 1th portcall) in the route r;

y _od :

the fulfilled demands from o ∈ P to d ∈ P;

x _p :

the number of empty containers to be repositioned out of p ∈ P (into port p if it is negative);

x ^l _{o, ri} :

the number of empty containers originating from o ∈ P that are loaded at the ith portcall in the route r;

x ^u _{o, ri} :

the number of empty containers originating from o ∈ P that are unloaded at the ith portcall in the route r;

x ^f _{o, ri} :

the number of empty containers originating from o ∈ P that are carried on board on the leg i (from ith portcall to i + 1th portcall) in the route r;

D _od :

the weekly demands from o ∈ P to d ∈ P;

Cap _r :

the vessel capacity in the route r ∈ R;

C ^l _p :

unit cost of loading containers at port p ∈ P;

C ^u _p :

unit cost of unloading containers at port p ∈ P;

C ^{t, l} _p :

unit cost of transshipping laden containers at port p ∈ P;

C ^{t, e} _p :

unit cost of transshipping empty containers at port p ∈ P;

C ^p _od :

unit penalty cost for lost-sales from o ∈ P to d ∈ P;

C ^l _ri :

unit cost of transporting laden containers on vessel in leg i in the route r ∈ R;

C ^e _ri :

unit cost of transporting empty containers on vessel in leg i in the route r ∈ R;

The objective is to minimize the sum of the laden and empty container loading (lifting-on) cost, the laden and empty container unloading (lifting-off) cost, the laden and empty container transshipment cost, the lost-sale penalty cost, the laden container transportation cost on vessel, the empty container transportation cost on vessel. The decision variables include the laden container flows, i.e. y ^l _{o, ri} , y ^u _{o, ri} , y ^f _{o, ri} , y _od , and the empty container flows, i.e. x _p , x ^l _{o, ri} , x ^u _{o, ri} , x ^f _{o, ri} .

To simplify the narrative, we introduce a few intermediate variables. Let y ^l _p , y ^u _p , y ^t _p denote total number of laden container loading (including export from the port and the transshipment), total number of laden container unloading (including import into the port and the transshipment), and the number of laden container transshipment at port p. Similarly, let x ^l _p , x ^u _p , x ^t _p , denote total number of empty container loading (including repositioning out from the port and the transshipment), total number of empty container unloading (including repositioning into the port and the transshipment), and the number of empty container transshipment at port p. The linear programming model is given by,

$$\underset{\begin{aligned} {{y}_{od}},y_{o,ri}^{l},y_{o,ri}^{u},y_{o,ri}^{f},y_{p}^{l},y_{p}^{u},y_{p}^{t} \\ {{x}_{p}},x_{o,ri}^{l},x_{o,ri}^{u},x_{o,ri}^{f},x_{p}^{l},x_{p}^{u},x_{p}^{t}\end{aligned}}{\mathop{\min }}\,\left\{ \sum\limits_{p\in P}{\left[ C_{p}^{l}(y_{p}^{l}+x_{p}^{l})+C_{p}^{u}\left( y_{p}^{u}+x_{p}^{u} \right)+C_{p}^{t,l}y_{p}^{t}+C_{p}^{t,e}x_{p}^{t} \right]}\,+\sum\limits_{r\in R}{\sum\limits_{i\in {{I}_{r}}}{\left( C_{ri}^{l}\sum\limits_{o\in P}{y_{o,ri}^{f}}+C_{ri}^{e}\sum\limits_{o\in P}{x_{o,ri}^{f}} \right)}}\,+\sum\limits_{o\in P}{\sum\limits_{d\in P}{C_{od}^{p}\left( {{D}_{od}}-{{y}_{od}} \right)}} \right\}$$

(6.8)

subject to

$$ {y_{od}}\le {D_{od}}, for\; any \;o,d\in P; $$

(6.9)

$$ \sum_{r\in {R_o}}{\sum_{i\in {I_{r,o}}}{y_{o,ri}^u} }= 0, {\text{for}}\;{\text{any}}\;o\in P; $$

(6.10)

$$ \sum_{r\in {R_o}}{\sum_{i\in {I_{r,o}}}{y_{o,ri}^l} }= \sum_{p\in P} {y_{op}^{}}, {\text{for}}\;{\text{any}}\;o\in P; $$

(6.11)

$$ \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{(y_{o,ri}^u-y_{o,ri}^l)} }= {y_{op}}, for\; any\; o,p\in P,o\neq p; $$

(6.12)

$$ y_p^l = \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P} {y_{o,ri}^l} } }, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.13)

$$ y_p^u = \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P} {y_{o,ri}^u} } }, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.14)

$$ y_p^t = y_p^l-\sum_{d\in P} {{y_{pd}}}= y_p^u-\sum_{o\in P} {y_{op}^{}}, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.15)

$$ y_{o,ri}^f = y_{o,ri-1}^f-y_{o,ri}^u + y_{o,ri}^l y_{o,ri}^f = y_{o,ri-1}^f-y_{o,ri}^u + y_{o,ri}^l, {\text{for}}\;{\text{any}}\;o\in P,r\in R,i\in {I_r}; $$

(6.16)

$$ {x_p} = \sum_{o\in P} {{y_{op}}}-\sum_{d\in P} {y_{pd}^{}}, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.17)

$$ \sum_{r\in {R_o}}{\sum_{i\in {I_{r,o}}}{x_{o,ri}^u} }= 0, {\text{for}}\;{\text{any}}\;o\in P; $$

(6.18)

$$ \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P} {(x_{o,ri}^l} -x_{o,ri}^u)} }= {x_p}, {\text{for}}\;{\text{any}}\;p\in P{\text{;}}$$

(6.19)

$$ x_p^l = \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P} {x_{o,ri}^l} } }, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.20)

$$ x_p^u = \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P} {x_{o,ri}^u} } }, {\text{for}}\;{\text{any}}\;p\in P{\text{;}}$$

(6.21)

$$ x_p^t = \sum_{r\in {R_p}}{\sum_{i\in {I_{r,p}}}{\sum_{o\in P\backslash p} {x_{o,ri}^l} } }, {\text{for}}\;{\text{any}}\;p\in P; $$

(6.22)

$$ x_{o,ri}^f = x_{o,ri-1}^f-x_{o,ri}^u + x_{o,ri}^l, {\text{for}}\;{\text{any}}\;o\in P, r\in R, i\in I_r; $$

(6.23)

$$ \sum_{o\in P} {(y_{o,ri}^f + x_{o,ri}^f)} \le Ca{p_r}, {\text{for}}\;{\text{any}}\;r\in R, i\in I_r; $$

(6.24)

$$ {y^l}_{o,ri}\geq 0,{y^u}_{o,ri}\geq 0,{y^f}_{o,ri}\geq 0,{y_{od}}\geq 0,{y^l}_p\geq 0,{y^u}_p\geq 0,{y^t}_p\geq 0, $$

(6.25)

$$ {x^l}_{o,ri}\geq 0,{x^u}_{o,ri}\geq 0,{x^f}_{o,ri}\geq 0,{x^l}_p\geq 0,{x^u}_p\geq 0,{x^t}_p\geq 0 $$

(6.26)

Constraint (6.9) represents that the fulfilled demands are no more than customer demands. Equation (6.10) indicates that laden containers will not be unloaded at their original ports. Equation  (6.11) represents the total fulfilled demands from a port. It must be equal to the number of the laden container loaded from this port and originating from this port. Equation (6.12) represents the fulfilled demands from one port to another. They must be unloaded at the destination port. Equations (6.13)–(6.15) represented the total laden containers that are loaded, unloaded, and transshipped at port p. Equation (6.16) represents the flow balancing for laden containers. Equation (6.17) represents the requirements of repositioning empty container out/into port p. Equation (6.18) represents that the empty containers originating from a port will not be unloaded at this port. Equation (6.19) represents that the requirements of empty containers to be repositioned out/into a port have to be satisfied. Equations (6.20)–(6.22) represent the total empty containers that are loaded, unloaded, and transshipped at port p. Equation (6.23) represents the flow balancing for empty containers. Constraint (6.24) represents the vessel capacity constraints at each leg for all routes. Constraints (6.25)–(6.26) represent the non-negative of the relevant decision variables.

The above model has advantages: (i) the flows on arcs (links) are explicitly associated with service routes; (ii) the lifting-on and lifting-off activities are associated with port-of-calls within a service route; (iii) the transshipment activities and costs can be reasonably modelled; (iv) the model with realistic sizes of the problems is computationally affordable, because the model is static and does not involve the time dimension. The disadvantages include: (i) the model assumes constant weekly demands for individual port-pairs; therefore seasonality requires additional treatment; (ii) although transshipment lifting-on/off costs are included, the demurrage costs of transshipment cargos and transshipment empty containers are accurately modelled because of the lack of operational information. Nevertheless, since shipping services are often weekly services, it is reasonable that the transshipment dwell times may be estimated to be in the range between one day and seven days; (iii) some constraints such as vessel capacity may be satisfied at the tactical planning level, but not satisfied at the operational planning level due to the dynamic operations.

5.3 Two-Stage Path-Based Network Flow Model for Laden and Empty Container Management

This section introduces a formulation that combines the path-based network flow model with heuristic-rules based implementation algorithm. The purpose is to model the laden and empty container management at a detailed operational level, but still applicable to large-scale planning problems in terms of computational complexity. The model presented in this section is mainly based on Song and Dong (2012).

The model consists of two stages. Stage one formulates a path-based network flow model, which is a static lower-dimension integer programming model. Stage two is to implement and adjust the solution from stage one in the dynamic system using a set of dynamic decision-making rules.

We make the following assumptions in this section: (i) after laden containers are unloaded from vessels at their destination ports, they become empty and can be reused or repositioned to other ports. The inland transportation is not considered explicitly; (ii) the shipping network consists of multiple service routes, and any two ports in the shipping network can be connected by at most three service routes. The laden container routing from the original port to the destination port is limited with at most three service routes; (iii) all service routes are of weekly frequency; (iv) the weekly demands for any O-D pair are stable (it allows variations on daily basis, and even stochastic).

We introduce the following notations for the model in this sub-section:

P :

the set of ports in the system.

R :

the set of shipping service routes in the system.

R :

a shipping service route (consisting of a sequence of ports) that belongs to R. For simplicity, it also represents the set of ports in this service.

Cap _r :

the carrying capacity in TEUs of the service route r.

D _ij :

the average cumulative customer demands from port i to port j within a week.

C _i ^f :

unit lifting-off cost (per laden or empty container) at port i.

C _i ^o :

unit lifting-on cost (per laden or empty container) at port i.

C _ij ^b :

unit backlog cost of a customer demand from port i to port j per unit per period (day).

C _i ^d :

unit demurrage (or waiting) cost of a transhipment (laden) container at port i per unit per period (day).

At stage one, the laden container routing and empty repositioning problem is treated as assigning the weekly demands of laden container movements and the derived requirements of empty container movements over the given shipping network subject to vessel capacity constraints and flow balancing (i.e. total containers flow out of a port should be equal to the total containers flow into the port). The idea is similar to the model in the previous section. However, here we adopt the path-based network flow model, which includes more information about the container flows in relation to service routes so that the solutions can be relatively easily implemented at the second stage (in the dynamic operational environments). We introduce a few definitions below to explain relevant concepts in our context.

Definition 1

A port pair (p _i , p _j ) is called a leg in service route r from p _i to p _j if p _i ∈ r, p _j ∈ r, and p _j is the next port-of-call immediately after p _i on the route r. If p _j is not the next port-of-call immediately after p _i on the route r, then (p _i , p _j ) should be understood as a set of legs connecting port p _i to port p _j in the service route r.

Definition 2

For r ∈ R, p _i , p _j ∈ r, the port sequence p _i , p ₀ , p ₁, …, p _n , p _j , denoted as (p _i , r, p _j ), is defined as the shortest path on the route r from p _i to p _j if the following conditions are met: (i) p ₀ ,p ₁, …, p _n ∈ r; (ii) (p _i , p ₀), (p _l , p _l + 1) and (p _n , p _j ) are legs in the service route r for l = 0, 1, …, n-1; (iii) p _i ∉{p ₀, p ₁, …, p _n } and p _j ∉{p ₀, p ₁, …, p _n }.

Definition 3

(i) (p _i , r ₁ , p _l , r ₂ , p _j ) is defined as the shortest path from port p _i to p _j with a single transhipment port at p _l using two services r ₁ and r ₂ if (p _i , r ₁ , p _l ) is the shortest path on the route r ₁ from p _i to p _l , and (p _l , r ₂ , p _j ) is the shortest path on the route r ₂ from p _l to p _j . (ii) Similarly, (p _i , r ₁ , p _l , r ₂ , p _m , r ₃ , p _j ) is defined as the shortest path from p _i to p _j with two transhipment ports at p _l and p _m using three services r ₁, r ₂, and r ₃ if (p _i , r ₁ , p _l ) is the shortest path on the route r ₁ from p _i to p _l , (p _l , r ₂ , p _m ) is the shortest path on the route r ₂ from p _l to p _m , and (p _m , r ₃ , p _j ) is the shortest path on the route r ₃ from p _m to p _j .

From the assumptions at the beginning of this section, we only consider three types of paths for any given O-D port-pair (i, j) of customer demands, i.e. direct service path from original port to destination port (i, r, j), two different services path with a single transhipment (i, r ₁ , l, r ₂ , j), three different services path with two transhipments (i, r ₁ , l, r ₂ , m, r ₃ , j).

To simplify the narrative, we introduce three sets of paths. Let Q ₀ denote the set of all paths with direct shipment in the shipping network, i.e. Q ₀: = {(i, r, j) | r ∈ R, i, j ∈ r}; Q ₁ denote the set of all paths with a single transhipment; Q ₂ denote the set of all paths with two transhipments; and Q: = Q ₀∪Q ₁∪Q ₂ representing the set of all paths for any port-pair in the shipping network (with no more than two transhipments).

The above sets of paths can be generated in a number of ways, e.g. from shipping company’s experience and preference, or from a more systematic way. Song and Dong (2012) provided a path generation algorithm that enumerates all feasible paths for each set.

To formulate the path-based network flow model, we introduce the following notations to facilitate the narrative.

O(n):

the original port of the path n ∈ Q;

D(n):

the destination port of the path n ∈ Q;

C(n):

the transportation cost per container using the path n ∈ Q;

y(n):

the flow volume of laden containers using the path n ∈ Q;

x(n):

the flow volume of empty containers using the path n ∈ Q;

r(n):

the service route in the path n ∈ Q ₀;

T(n):

the transshipment port in the path n ∈ Q ₁;

r ₁(n):

the first service route in the path n ∈ Q ₁;

r ₂(n):

the second service route in the path n ∈ Q ₁;

W(n):

the waiting time at the transshipment port in the path n ∈ Q ₁;

T ₁(n):

the first transshipment port in the path n ∈ Q ₂;

T ₂(n):

the second transshipment port in the path n ∈ Q ₂;

r ₃(n):

the third service route in the path n ∈ Q ₂;

W ₁(n):

the waiting time at the first transshipment port in the path n ∈ Q ₂;

W ₂(n):

the waiting time at the second transshipment port in the path n ∈ Q ₂;

Using the notation in Definitions 2 ~ 3, we can observe that a direct shipment path n ∈ Q ₀ is characterized by (O(n), r(n), D(n)). A single-transhipment path n ∈ Q ₁ is characterized by (O(n), r ₁(n), T(n), r ₂(n), D(n)). A twice-transhipment path n ∈ Q ₂ is characterized by (O(n), r ₁(n), T ₁(n), r ₂(n), T ₂(n), r ₃(n), D(n)).

The first stage path-based network flow model is to seek the optimal assignment of laden and empty containers onto the paths in Q. Namely, we want to find the optimal assignment {y(n), x(n), n ∈ Q} by minimizing the following total cost:

$$ {\text{Min }}J = {J_o} + {J_f} + {J_t} + {J_b} + {J_d} $$

(6.27)

Where the cost elements include: container lifting-on costs J _o , container lifting-off costs J _f , container transportation cost J _t , customer demand backlog costs J _b , and transhipment demurrage cost J _d . Here the demand backlog cost can be interpreted as the lost-sale cost in the previous two sections. However, in multi-period planning problem, backlogged demands could be satisfied at later periods, whereas lost-sales will be lost permanently. The above cost elements are defined as,

$$ {J_o}{ =}\sum_{n\in {Q_0}}{({y(n) + x(n)})} \cdot C_{O(n)}^o + \sum_{n\in {Q_1}}{({y(n) + x(n)})} \cdot ({C_{O(n)}^o + C_{T(n)}^o}) + \sum_{n\in {Q_2}}{({y(n) + x(n)})} \cdot ({C_{O(n)}^o + C_{{T_1}(n)}^o + C_{{T_2}(n)}^o}) $$

(6.28)

$$ {J_f} = \sum_{n\in {Q_0}}{({y(n) + x(n)})} \cdot C_{D(n)}^f + \sum_{n\in {Q_1}}{({y(n) + x(n)})} \cdot (C_{D(n)}^f + C_{T(n)}^f) + \sum_{n\in {Q_2}}{({y(n) + x(n)})} \cdot ({C_{D(n)}^f + C_{{T_1}(n)}^f + C_{{T_2}(n)}^f}); $$

(6.29)

$$ {J_t} = \sum_{n\in Q} {({y(n) + x(n)})} \cdot C(n) $$

(6.30)

$$ {J_b} = \sum_i {\sum_j {\left({{D_{ij}}-\sum_{n\in Q,O(n) = i,D(n) = j} {y(n)} }\right)\cdot C_{ij}^b} } \cdot 7; $$

(6.31)

$$ {J_d} = \sum_{n\in {Q_1}}{y(n)} \cdot W(n)\cdot C_{T(n)}^d + \sum_{n\in {Q_2}}{y(n)} \cdot ({{W_1}(n)\cdot C_{{T_1}(n)}^d + {W_2}(n)\cdot C_{{T_2}(n)}^d}); $$

(6.32)

Subject to

$$ \sum_{n\in Q,O(n) = i} {({y(n) + x(n)})}= \sum_{n\in Q,D(n) = i} {({y(n) + x(n)}), {\text{for}}{\text{any}}{\text{port}}i;}$$

(6.33)

$$\begin{aligned} & \sum\limits_{n\in {{Q}_{0}},r(n)=r,(i,j)\subseteq (O(n),D(n))}{\left( y(n)+x(n) \right)+\sum\limits_{n\in {{Q}_{1}},{{r}_{1}}(n)=r,(i,j)\subseteq (O(n),T(n))}{\left( y(n)+x(n) \right)}} \\ & \sum\limits_{n\in {{Q}_{1}},{{r}_{2}}(n)=r,(i,j)\subseteq (T(n),D(n))}{\left( y(n)+x(n) \right)}+\sum\limits_{n\in {{Q}_{2}},{{r}_{1}}(n)=r,(i,j)\subseteq (O(n),{{T}_{1}}(n))}{\left( y(n)+x(n) \right)} \\ & \sum\limits_{n\in {{Q}_{2}},{{r}_{2}}(n)=r,(i,j)\subseteq ({{T}_{1}}(n),{{T}_{2}}(n))}{\left( y(n)+x(n) \right)}+\sum\limits_{n\in {{Q}_{2}},{{r}_{3}}(n)=r,(i,j)\subseteq ({{T}_{2}}(n),D(n))}{\left( y(n)+x(n) \right)} \\ & \,\le \,Ca{{p}_{r}},\text{ for any leg }\left( i,j \right)\;\;\text{ in any service route}\ r; \\\end{aligned}$$

(6.34)

$$ \sum_{n\in Q,O(n) = i,D(n) = j} {y(n)} \le {d_{ij}}, {\text{for any port-pair from port}}\;\;i\;\; {\text{to port}}j. $$

(6.35)

Equation (6.33) represents that at each port the total number of containers (laden and empty) flowing into it is equal to the total number of containers flowing out of it. Constraint (6.34) ensures that the total number of containers (laden and empty) carried on each leg for any service route does not exceed the vessel capacity (because we assumed all vessels deployed in the same service route are of the similar size). Constraint (6.35) indicates that the satisfied laden containers are no more than the customer demands. The unmet demands in the current week are backlogged and charged for a backlog cost.

It should be pointed out that the purpose of the above static integer programming model is to find the optimal {y(n), x(n), n ∈ Q}, which represent the assignment plan of laden and empty containers (aggregated over a week) onto the paths in Q.

The second stage aims to determine the container flows and storage dynamically over multiple periods in the planning horizon based on the weekly plan obtained at the first stage. We introduce the following dynamic variables first:

K :

the planning horizon.

k :

the time period (e.g. day).

V :

the set of vessels in the system.

v :

a vessel that belongs to V.

r _v :

the service route that vessel v is deployed.

$\xi_{ij}^{}(k)$ :

the customer demands from port i to j arrived in period k.

$\xi_{ij}^{{r_1}}(k)$ :

the customer demands from port i to j arrived in period k allocated to service r ₁.

$\xi_{ilj}^{{r_1}{r_2}}(k)$ :

the customer demands from port i to j arrived in period k allocated to services r ₁ and r ₂ transhipped at port l.

$\xi_{ilmj}^{{r_1}{r_2}{r_3}}(k)$ :

the customer demands from port i to j arrived in period k allocated to services r ₁, r ₂, and r ₃ transhipped at port l and m.

The above three sets of variables, $\xi_{ij}^{{r_1}}(k)$, $\xi_{ilj}^{{r_1}{r_2}}(k)$, $\xi_{ilmj}^{{r_1}{r_2}{r_3}}(k)$, represent demand routing variables (they represents the demands generated at period k to be delivered on the specified path).

s _i (k) :

the inventory level of empty containers at port i at the end of period k.

$d_{ij}^{{r_1}}(k)$ :

the cumulative demands from port i to j at time k to be satisfied using service r ₁.

$d_{0ilj}^{{r_1}{r_2}}(k)$ :

the cumulative demands from port i to j at time k using service r ₁ and r ₂ transhipped at port l, which are waiting to be satisfied at original port i at time k.

$d_{0ilmj}^{{r_1}{r_2}{r_3}}(k)$ :

the cumulative demands from port i to j at time k to be satisfied using service r ₁, r ₂, and r ₃ transhipped at port l and m, which are waiting at original port i to be satisfied at time k.

The above three sets of variables, $d_{ij}^{{r_1}}(k)$, $d_{0ilj}^{{r_1}{r_2}}(k)$, $d_{0ilmj}^{{r_1}{r_2}{r_3}}(k)$, represent the demand states at their original ports:

$d_{1ilj}^{{r_1}{r_2}}(k)$ :

the cumulative laden containers from port i to j at time k using service r ₁ and r ₂ transhipped at port l, which are waiting at the transhipment port l to be served by r ₂ at time k.

$d_{1ilmj}^{{r_1}{r_2}{r_3}}(k)$ :

the cumulative laden containers from port i to j at time k to be satisfied using service r ₁, r ₂, and r ₃ transhipped at port l and m. which are waiting at the first transhipment port l to be satisfied at time k.

$d_{2ilmj}^{{r_1}{r_2}{r_3}}(k)$ :

the cumulative laden containers from port i to j at time k to be satisfied using service r ₁, r ₂, and r ₃ transhipped at port l and m, which are waiting at the second transhipment port m to be satisfied at time k.

The above three sets of variables, $d_{1ilj}^{{r_1}{r_2}}(k)$, $d_{1ilmj}^{{r_1}{r_2}{r_3}}(k)$, $d_{2ilmj}^{{r_1}{r_2}{r_3}}(k)$, represent the transhipment states at transshipment ports:

$y_{ij}^v(k)$ :

the number of laden containers from port i to j on board of vessel v at time k. In other words, $y_{ij}^v(k)$ represents the number of the laden containers on board of vessel v at time k, whose original port is i and destination port is j. It should be pointed out that those containers may be loaded onto vessel v at a time earlier than k.

$y_{ilj}^{v{r_2}}(k)$ :

the number of laden containers from port i to l on board of vessel v at time k to be further transported to port j using service r ₂ transhipped at port l.

$y_{ilmj}^{v{r_2}{r_3}}(k)$ :

the number of laden containers from port i to l on board of vessel v at time k to be further transported to port j using service r ₂ and r ₃ transhipped at port l and m.

$y_{ilj}^{{r_1}v}(k)$ :

the number of laden containers from port l to j on board of vessel v at time k, which has been transported from port i to port l using service r ₁.

$y_{ilmj}^{{r_1}v{r_3}}(k)$ :

the number of laden containers from port l to m on board of vessel v at time k, which has been transported from port i to port l using service r ₁, and is to be further transported from port m to port j using service r ₃.

$y_{ilmj}^{{r_1}{r_2}v}(k)$ :

the number of laden containers from port m to j on board of vessel v at time k, which has been transported from port i to port l using service r ₁, and from port l to port m using service r ₂.

The above six sets of variables, $y_{ij}^v(k)$, $y_{ilj}^{v{r_2}}(k)$, $y_{ilmj}^{v{r_2}{r_3}}(k)$, $y_{ilj}^{{r_1}v}(k)$, $y_{ilmj}^{{r_1}v{r_3}}(k)$, $y_{ilmj}^{{r_1}{r_2}v}(k)$, represent laden container shipments on vessels:

$x_{ij}^v(k)$ :

the number of empty containers from port i to j on board of vessel v at time k.

Considering the multiple periods in the planning horizon, at the second stage we need to determine: (i) the dynamic demand (cargo) routing variables {$\xi_{ij}^{{r_1}}(k)$, $\xi_{ilj}^{{r_1}{r_2}}(k)$, $\xi_{ilmj}^{{r_1}{r_2}{r_3}}(k)$}, demand variables at original ports {$d_{ij}^{{r_1}}(k)$, $d_{0ilj}^{{r_1}{r_2}}(k)$, $d_{0ilmj}^{{r_1}{r_2}{r_3}}(k)$}, transhipment-at-port variables {$d_{1ilj}^{{r_1}{r_2}}(k)$, $d_{1ilmj}^{{r_1}{r_2}{r_3}}(k)$, $d_{2ilmj}^{{r_1}{r_2}{r_3}}(k)$}, and shipment-on-vessel variables {$y_{ij}^v(k)$, $y_{ilj}^{v{r_2}}(k)$, $y_{ilmj}^{v{r_2}{r_3}}(k)$, $y_{ilj}^{{r_1}v}(k)$, $y_{ilmj}^{{r_1}v{r_3}}(k)$, $y_{ilmj}^{{r_1}{r_2}v}(k)$}; (ii) the dynamic empty container inventory variables at ports {s _i (k)}; and (iii) the dynamic empty container-on-vessel variables {$x_{ij}^v(k)$}.

Song and Dong (2012) presented a heuristic algorithm to implement the static assignment plan in a dynamic multiple period situations. It is reasonable to assume that laden containers have the priority over empty containers. We summarize the heuristic algorithm below:

A heuristic implementation algorithm

Step 1: Initialisation. Note that laden containers have priority in the dynamic assignment, we can determine the laden container routing variables {$\xi_{ij}^{{r_1}}(k)$, $\xi_{ilj}^{{r_1}{r_2}}(k)$, $\xi_{ilmj}^{{r_1}{r_2}{r_3}}(k)$} for each period based on the static information in {y(n), n ∈ Q}. Other decision variables at period k = 0 are initialised to be zero except the empty container inventories at ports, which represent the initial distribution of the container fleet over ports.

Step 2: Let k = k + 1.

Step 3: For any port i: (i) Update the demand variables at original ports {$d_{ij}^{{r_1}}(k)$, $d_{0ilj}^{{r_1}{r_2}}(k)$, $d_{0ilmj}^{{r_1}{r_2}{r_3}}(k)$} by accumulating the newly generated demands and subtracting the recently satisfied demand; (ii) update the transhipment variables at ports {$d_{1ilj}^{{r_1}{r_2}}(k)$, $d_{1ilmj}^{{r_1}{r_2}{r_3}}(k)$, $d_{2ilmj}^{{r_1}{r_2}{r_3}}(k)$} by accumulating the newly generated transhipments and subtracting the ones that are recently transhipped out of the port.

Step 4: For any port i: (i) for any vessel v arriving at port i at period k, the empty container inventory variables at port {s _i (k)} is updated by adding all the laden and empty containers designated to port i from vessel v; (ii) for any vessel v departing from port i at period k, the empty container inventory variables at port {s _i (k)} is further updated by reducing the number of empty containers that are moved away from port i via vessel v (either being used to meet customer demands or repositioned out of the port).

Step 5: For any vessel v to be departing from port i at period k, if the vessel v has spare capacity on board, then

Step 5.1: Meet customer demands and load designated transhipments on vessel v as many as possible;

If there are enough residual capacity on vessel v and enough empty containers at port i, all the relevant demands at the port i can be satisfied and loaded on vessel v; Otherwise, the assignment of empty containers to customer demands and the assignment of vessel spare space to laden containers will be performed according to priority rules (e.g. whether transhipping containers have a priority; whether larger volume customers should be satisfied first); the assignment procedure terminates when either there is no more space available on board, or all relevant demands and transhipment have been loaded on the vessel. The shipment-on-vessel variables {$y_{ij}^v(k)$, $y_{ilj}^{v{r_2}}(k)$, $y_{ilmj}^{v{r_2}{r_3}}(k)$, $y_{ilj}^{{r_1}v}(k)$, $y_{ilmj}^{{r_1}v{r_3}}(k)$, $y_{ilmj}^{{r_1}{r_2}v}(k)$} are updated, and the demand and transhipment states at port i are also updated accordingly.

Step 5.2: The dynamic pushed amount of empty containers

Let E ₁ denote the dynamic planned empty containers to be repositioned out of port i by vessel v after Step 5.1 based on the optimal empty repositioning plan in stage one {x(n), n ∈ Q}. It is given by E ₁ = min{AE _i , $PE_i^{{r_v}}$, $RC_i^v$}, where AE _i represents the available empty containers at port i; $PE_i^{{r_v}}$ represents the optimal planned empty container flows out of port i via the service route r _v , obtained from x(n); and $RC_i^v$ represents the available residual capacity of vessel v. Since x(n) has been determined at Stage one, E ₁ may be regarded as the pushed amount of empty containers to be repositioned out of port i. Those empty containers can then be proportionally split among the relevant destination ports, denoted as {${{x}\prime_{ij}^{v}}(k)$}.

Step 5.3: The dynamic pulled amount of empty containers

Let E ₂ denote the maximum additional empty containers that are able to be repositioned out of port i by vessel v after Step 5.2, by taking into account the available amount of empty containers at port i and the residual capacity of vessel v. Let U _j (k) denote the requirement for empty containers at port j at time k after considering the backlogged demands, the current inventory level, the empty containers en-route, and the laden containers en-route. The amount, min{E ₂, ∑ _j U _j (k)}, is the additional planned empty containers to be repositioned out of port i by vessel v. Note that U _j (k) represents the dynamic requirements of empty containers from other relevant ports. The amount min{E ₂, ∑ _j U _j (k)}, can be regarded as the pulled amount of empty containers to be repositioned out of port i. This amount is then further split proportionally among all relevant destination ports using the paths obtained from Stage one, denoted as {${{x}''_{ij}}^v(k)$}.

Step 5.4: The total empty containers to be repositioned from port i to j via vessel v at period k is given by: $x_{ij}^{v}(k)={x}\prime_{ij}^{v}(k)+{x}"_{ij}^{v}(k)$for j ∈ r _v .

Step 6: If k < K, go to Step 2; otherwise, terminate the algorithm.

In summary, the above heuristic implementation algorithm is able to determine the dynamic cargo routing variables, empty container inventory variables at ports, demand variables at original ports, transhipment variable at ports, shipment-on-vessel variables, and empty container-on-vessel variables over the multiple periods in the planning horizon.

The advantages of the model in this section are: (i) the path-based network flow model at stage one has detailed information about the shipment movements including transhipment ports, the involved service routes and the transhipment waiting time at transhipment ports; therefore, transhipment costs (lifting costs and demurrage costs) can be more accurately modelled; (ii) because we only allow maximum twice transhipments, the sizes of the path sets are relatively limited even for realistic large-scale problems; hence, the static integer programming at stage one can be solved rather quickly. Note that the decision-making rules at stage two are executed dynamically on event driven basis, e.g. only when a vessel arrives at or departs from a port. They do not require complicated iterations or searching processes. Therefore the second stage is also computationally efficient; (iii) the heuristic-rules based method at the second stage can actually be applied to stochastic situations. The combination of the push and pull mechanisms in the heuristic implementation algorithm can reasonably handle the impact of uncertain demands and adjust the empty container repositioning dynamically.

The disadvantages of the model are: (i) if we allow more than twice transhipment in the path sets, the number of paths could increase exponentially. Nevertheless, in practice it is rare for a laden container shipment to have more than two transhipments. The main reason is that transhipment will incur additional lifting-on/off costs which are quite significant among the total transport cost. (ii) at the second stage, the dynamic operational model assumes that laden containers become empty immediately after being unloaded from vessels at their destination ports. Further research is required to incorporate the inland transportation into the model.

5.4 Apply Solutions From Mathematical Programming Models to Stochastic Situations

In general, mathematical programming models such as linear programming or integer programming are often limited within deterministic situations. The solutions may be regarded as arc-based matrices to represent the plan of laden and empty container flows over the shipping network. As the model is deterministic, the direct application of its solution in practice may not be easily achieved due to the discrepancies between the model and the reality, especially in a stochastic dynamic environment. Multi-scenario-based method could reduce the discrepancy between the plan and the reality, but cannot eliminate the discrepancy.

A commonly used approach to implement the deterministic solution into stochastic dynamic environment is the rolling horizon policy. Namely, arc-based planning decisions are generated from the optimization models for all the periods of the planning horizon, but only the decisions in the first period of the planning horizon are implemented. Then, in the next period, when new information becomes available, some forecasts are updated and deterministic models are solved again to produce new decisions in the next planning horizon (Long et al. 2012; Di Francesco et al. 2013). However, Di Francesco et al. (2009) stated that there is no paper quantifying what is actually lost in terms of operations efficiency and profitability by using deterministic models used in a rolling-horizon fashion.

Another approach to implement the deterministic solution into stochastic dynamic environment is based on operational rules to make the solution feasible. Dong et al. (2013) presented two types of operational rules. The first type attempts to follow the deterministic solution whenever possible, e.g. assign the flows to the arcs as specified in the solution, but may assign less amount than the solution if it is not able to (e.g. if there are no enough empty containers that are available to be repositioned out due to the uncertainties in the system, the unsatisfied part of the repositioning plan will be neglected). For instance, the plan requires repositioning 1000 empty containers out of the port according to the arc-based matrices, but the total number of empty containers on hand at the port is only 900; in this case, only 900 empty containers will be repositioned out, and the 100 unsatisfied requirements in the plan will be disregarded. The second type includes a compensation mechanism during the course of solution implementation. A shadow matrix for each arc-based container flow matrix is created to store the cumulative unsatisfied flow requirements. Whenever a vessel calls at a port, both the cumulative unsatisfied flow requirements specified in the shadow matrix and the current flow requirements specified in the arc-based matrix will be tried to meet. Under these operational rules, the arc-based matrices are used as guidance to move the laden and empty containers over the shipping network in response to the dynamically changing environment. However, again it is an open question whether the above implementation of the optimal solution from the deterministic models is near optimal in stochastic situations and how to measure the degree of the closeness.

5.5 Inventory Control-Based Simulation Model for Laden and Empty Container Management

This section presents an inventory-based simulation model to address the management of both laden and empty containers in stochastic and dynamic situations.

It is noted that there are a rather limited number of papers that addressed the operations of container carriers between ports using simulation. Rensburg and He (2005) stated that they found only one reference (i.e. Lai et al. 1995) to a simulation model of ocean container carrier operations in the literature. Lai et al. (1995) developed a simulation model to optimize a type of heuristic allocation policy for a shipping company to transport empty containers from the Middle East to ports in the Far East. Li et al. (2007) used simulation to compare the performance of their threshold policies in three-port and four-port shipping routes. The above two papers focused on developing empty repositioning policies and showing their effectiveness in specific shipping routes. The purpose of the simulation was not designed for policy evaluation in general shipping networks. Rensburg and He (2005) described a generic simulation model of ocean container carrier operations including transporting containers from depots to customers according to requirements and from port to port according to vessels’ schedules. However, their focus was not on the performance evaluation of empty container repositioning policies and no numerical results were reported. Song et al. (2005) simulated the global container-shipping network focusing on business competition between ocean carriers, in which the empty container repositioning was modeled implicitly rather than explicitly.

In the following, we present an event-driven simulation tool that can serve as a platform to evaluate and optimize inventory control-based empty container repositioning policies taking into account the stochastic nature and dynamic operations of the container shipping industry (Dong et al. 2008).

The key components of container maritime transport system include containers, vessels, ports/terminals, shipping networks and customer demands. These components interact with each other and form a dynamic container shipping system. Although individual shipping companies may manage and operate their systems differently, the basic and essential parts are similar. We make the following assumptions: (i) shipping services are on weekly basis; (ii) container unloading occurs at the vessel arrival event epoch and container loading occurs at the vessel departure epoch; (iii) laden containers that are unloaded at the destination ports will become empty containers and available for reuse after a number of weeks (many literatures assuming immediately available).

Suppose that a fleet of container vessels travel on a shipping network according to a pre-determined schedule, and we then observe a sequence of vessel arrival events into ports and vessel departure events out of ports in chronological order. These events essentially drive the evolution of the dynamic system. Robinson (2004) pointed out that: “each event occurs at an instant in time and marks a change of state in the system”. In our case, the containers on board of vessels (both laden and empty) will not change until an event occurs. This is because no lifting-on or lifting-off activities are performed between two consecutive events.

With respect to a vessel arrival event, when a vessel arrives at a port, both the laden and empty containers onboard that are destined to, or transshipped at, the current port are usually unloaded from the vessel. The unloaded empty containers are immediately available for reuse; while unloaded laden containers at their destination ports may become empty after a number of weeks. This time varies for different ports, which represents the aggregated inland transportation time. For a transshipment container, it will be staying at the port waiting for a vessel in another service route to continue its journey.

With respect to a vessel departure event, customer demands at the current port are accumulated from the time when the last vessel (in the same direction) departed from this port to the time one day before the current vessel’s departure. The one-day in advance reflects the fact that a certain period of time is required at port to prepare for loading (Song et al. 2005). The accumulated demands will be satisfied using the empty containers in inventory. If they are not sufficient, extra empty containers may be leased from lessors to meet demands. However, due to the physical constraints of vessel capacity, some demands may not be able to be carried by the current vessel; in which case customers may turn their business to other shipping companies and therefore the demands could be lost. This reflects the high competitive business environment of the container shipping industry and the customers’ emphasis on just-in-time delivery. On the other hand, shipping lines may try to persuade their customers to wait for the vessel arriving next week; in which case the customer demands could be regarded as backlogged and delayed by one or more weeks. Apart from meeting customer demands, the shipping company has to make decisions on repositioning empty containers. If there are stocks of empty containers remaining at the port after meeting customer demands (e.g. those ports in west-coast America which have many more imports than exports), the operational decisions include how many empty containers need to be repositioned out of the current port, which destination ports to go and in what proportion.

The decisions on empty container repositioning are based on parameterized rules, usually represented by threshold policies. For example, in the literature, double threshold policy, or (s, S)-type inventory control policy, has been used to determine the number of empty container flow in/out of a port/depot dynamically (e.g. Li et al. 2004; Li et al. 2007; Song and Dong 2008; Dong and Song 2009; Song and Zhang 2010; Song and Dong 2011b; Dang et al. 2013; Zhang et al. 2014). The simplest threshold policy is using a single threshold-level at each port/depot to control the inventory and flows of empty containers (e.g. Song 2005; Song 2007b; Lee et al. 2012).

Apart from the input data and output data, the simulator includes the following key modules: Simulation Manager module (it controls the simulator, which takes input information from the Input Data module and sets up a the running environment for the simulator), Inventory Control Policy module (it selects customer demand satisfaction and laden container routing rules, and selects an empty container repositioning policy from a list of inventory-based control policies), Simulation Processing module (it handles the vessel arrival and departure events and the laden and empty container loading/unloading activities), and Cost Calculation module, as shown in Fig. 6.2.

Fig. 6.2

Flowchart of an inventory control-based simulation model (based on Dong et al. 2008)

The inventory control-based simulation model offers a great flexibility in handling dynamic and stochastic situations because the specific empty container repositioning decisions are determined dynamically rather than in advance. However, two issues deserve more research. Firstly, what types of inventory control-based repositioning policies are appropriate in complicated shipping networks. Secondly, how the control parameters used in these inventory control-based policies can be determined efficiently.

6 Conclusions and Further Research

Empty container repositioning is an important phenomenon in the container shipping industry. It has been an on-going issue since the beginning of containerization and will remain as a key issue in the future due to the nature of the industry. The critical factors that cause empty container movements include the trade imbalance, dynamic operations, uncertainties, size and type of equipment, lack of visibility and collaboration within the transport chain, and transport companies’ operational and strategic practices. Among these factors, we believe that the trade imbalance, dynamic operations and uncertainties are probably the most important factors, whereas the lack of visibility and collaboration and the transport companies’ practices provide opportunities for tackling the ECR problems.

By understanding the process of container storage and flows in the container transport chain, it can be seen that shipping lines are not the only ones that are affected by the ECR problem and should tackle the ECR problem, but also other players associated with the transport chain may be affected and are able to contribute to the solutions to the ECR problems. A large number of studies have been conducted to deal with the ECR problems from different angles using different methods in the last three decades. We classified the solutions to the ECR problems into four categories according to the logistics channel scope: organizational solutions, intra-channel solutions, inter-channel solutions, and technological solutions.

Due to the importance of the first three causes to the ECR (i.e. trade imbalance, dynamic operations and uncertainties), we believe that it is desirable to build models by taking into account all these three factors. In particular, trade imbalance could be more realistically modeled by considering both laden and empty container movements in a single model. We present three mathematical programming models, a time-space multi-commodity network flow model, an origin-link based network flow model, and a two-stage path-based network flow model. The third model includes a second stage to implement the static assignment plan into dynamic operation situations. We then discuss the common approached to incorporate the solutions from mathematical programming models into dynamic stochastic environments. We also present an inventory control-based simulation model, which is flexible to model the laden and empty container movements in complex dynamic stochastic environments. To some extent, the above models reflect the recent advances in the ECR modeling techniques in two broad research steams: network flow models and inventory control-based models.

As empty container repositioning problem is closely related to other issues in the container shipping, further research is required to integrate ECR with other decisions such as network design and vessel management. Apart from continuing pursuing more efficient and effective organizational solutions to the ECR problems, it is also interesting to seek appropriate intra-channel, inter-channel, and technological solutions since empty container repositioning will affect all stakeholders associated with the container transport chain.