# Optimal Container Routing in Liner Shipping Networks Considering Repacking 20 ft Containers into 40 ft Containers

Authors: Shuaian Wang; Xiaobo Qu; Tingsong Wang; Wen Yi
Journal: Journal of Advanced Transportation
 (2017)

---

## Abstract

The volume of a 40 ft container is twice as large as that of a 20 ft container. However, the handling cost (loading, unloading, and transshipment) of a 40 ft container is much lower than twice the corresponding handling cost of two 20 ft containers. Enlightened by this observation, we propose a novel container routing with repacking problem in liner shipping, where two 20 ft containers can be repacked to a 40 ft container in order to reduce the handling cost. We develop a mixed-integer linear programming model that formulates the routing decisions and the repacking decisions in a holistic manner. An illustrative example is reported to demonstrate the applicability of the model. Results show that the benefit of repacking is the most significant when containers are transshipped several times.


---

## Body

## 1. Introduction

Maritime transportation is the backbone of international trade. Around 80 per cent of global trade by volume and over 70 per cent by value are carried by sea. Among all the sea cargos, about half in monetary terms are containerized [1]. Containers are transported by shipping lines on regularly serviced ship routes. At the port of origin, containers are loaded onto ships by quay cranes; and at the port of destination, containers are discharged from ships by quay cranes. Containers may also be transshipped between their origin ports and destination ports. In fact, transshipment is a common operation in container shipping. As reported by [1], the total container trade volumes amounted to 160 million twenty-foot equivalent units (TEUs) in 2013, whereas world container port throughput was estimated at 651 million TEUs. These numbers mean that on average a container was transshipped (651-2×160)/160≈2 times (the throughput data for ports also include empty containers.).Container routing determines how to transport containers from their origins to their destinations in a liner shipping network. Take Figure1 as an example, which shows a liner shipping network consisting of three ship routes. Containers from Singapore to Hong Kong can be transported on either ship route 1 or ship route 2. If there are many containers to be transported from Singapore to Jakarta, then containers from Singapore to Hong Kong should be transported on ship route 2 to reserve the capacity on ship route 1 for containers from Singapore to Jakarta. In addition to different ship routes on which containers can be transported from origin to destination, another complicating factor is transshipment. For instance, containers from Hong Kong to Colombo can be transported on ship route 2, or they can be transported on ship route 1 to Singapore and transshipped to ship route 2 and then transported to Colombo. The choice of direct shipment on ship route 2 is preferable because otherwise it would involve a high transshipment cost at Singapore. However, if there are many containers to be transported from Hong Kong to Xiamen or from Xiamen to Singapore, then the choice of transshipment at Singapore from ship route 1 to ship route 2 has to be adopted. Consequently, it is not an easy task to determine the optimal container routing.Figure 1
An illustrative liner shipping network [8].Container routing determines the container handling cost. Table1 shows the handling costs for two types of laden containers at three ports: D20 means dry 20 ft container, and D40 is dry 40 ft container. In terms of cargo capacity, a D40 is equivalent to two D20s. However, Table 1 clearly indicates in the three rows “Ratio” that the ratio of the cost of handling a D40 and that of handling a D20 is strictly less than 2. In fact, all the ratios in Table 1 are less than 1.5, and some ratios are even 1 or very close to 1. This is because both the handling of a D20 and the handling of a D40 involve one quay crane move (we note that nowadays some quay cranes can handle one D40 or two D20s in each move.). Therefore, to reduce container handling costs, a shipping line should try to transport more D40s instead of D20s as a D40 can hold as much cargos as two D20s.Table 1
Laden container handling cost (USD/container) at three ports (source: [11]).
Port Type Loading Discharge Transshipment A (a major transshipment port in Europe) D20 248 324 183 D40 256 332 198 Ratio 1.03 1.02 1.08  B (a major transshipment port in Southeast Asia) D20 118 118 145 D40 148 148 145 Ratio 1.25 1.25 1  C (an export-driven port in Southeast Asia) D20 110 110 71 D40 156 156 106 Ratio 1.42 1.42 1.49


### 1.1. Container Repacking

As the handling cost of a D40 is much lower than that of two D20s, it might be advantageous to unpack two D20s and repack them to one D40. In the sequel, we use “TEU” and “D20” interchangeably and use “forty-foot equivalent unit (FEU)” and “D40” interchangeably. The load, transshipment, and discharge cost (USD/container) of a TEU at a portp is denoted by c^pT, c-pT, and c~pT, respectively. The load, transshipment, and discharge cost (USD/container) of an FEU at port p∈P is denoted by c^pF, c-pF, and c~pF, respectively. We further let cp2T→F be the cost of repacking two TEUs into one FEU and cpF→2T be the cost of unpacking one FEU to two TEUs (Since multiple rehandling of containers would increase the risk for damage and therefore may increase insurance costs, we can include in cp2T→F and cpF→2T the extra insurance costs. Moreover, repacking requires consent from shippers and we can include in the rehandling cost the component of discount for shippers who agree for their cargos to be repacked.).Figure2 shows an example of transporting two TEUs from port p2 to port p5. The two TEUs need to be transshipped twice. If they are transported as two TEUs, as shown in Figure 2(a), then, at the port of origin, that is, p2, two TEUs are loaded; at p3, two TEUs are transshipped; at p4, two TEUs are transshipped; and, at the destination port p5, two TEUs are discharged. Therefore, the total container handling cost is (1)2c^p2T+2c-p3T+2c-p4T+2c~p5T.Figure 2
Container packing with the same origin and destination.
(a)
Two TEUs fromp2 to p5 without repacking (b)
Two TEUs fromp2 to p5 with repacking at p2 and unpacking at p5If these two TEUs are repacked into an FEU at the origin port and unpacked at the destination port, as shown in Figure2(b), then, at the port of origin, that is, p2, one FEU is loaded; at p3, one FEU is transshipped; at p4, one FEU is transshipped; and, at the destination port p5, one FEU is discharged. Moreover, container repacking and unpacking costs are incurred at p2 and p5, respectively (The FEU is unpacked at p5 into two TEUs because the two TEUs from port p2 to port p5 actually have different inland destinations.). Therefore, the total container handling and packing cost is(2)cp22T→F+c^p2F+c-p3F+c-p4F+c~p5F+cp5F→2T,which may be considerably smaller than (1).Not only can TEUs with the same origin and destination ports be repacked into FEUs, as shown in Figure2, TEUs with different origins and destinations can also be repacked into FEUs. For example, in Figure 3, one TEU is from p2 to p5 and the other TEU is from p1 to p6. If they are transported as TEUs throughout their trips, as shown in Figure 3(a), the total handling cost is(3)c^p1T+c^p2T+2c-p3T+2c-p4T+c~p5T+c~p6T.They may be repacked into an FEU at the transshipment port p3 and unpacked as two TEUs at transshipment port p4, as shown in Figure 3(b). At p3, since two TEUs are unloaded and one FEU is loaded in the transshipment process, the total transshipment cost is calculated as half of the sum of the transshipment cost of two TEUs and the transshipment cost of one FEU, that is, c-p3T+0.5c-p3F. Similarly, the transshipment cost at p4 is calculated as c-p4T+0.5c-p4F. Therefore, the total container handling and packing cost is(4)c^p1T+c^p2T+c-p3T+0.5c-p3F+cp32T→F︸Cost  atp3+c-p4T+0.5c-p4F+cp4F→2T︸Cost  atp4+c~p5T+c~p6T,which may be smaller than (3) if the container packing cost is small. Of course, the benefit of repacking TEUs into FEUs in Figure 3(b) is not as significant as Figure 2.Figure 3
Container packing with different origins and destinations.
(a)
One TEU fromp2 to p5 and one TEU from p1 to p6 without repacking (b)
One TEU fromp2 to p5 and one TEU from p1 to p6 with repacking at p3 and unpacking at p4 (c)
One TEU fromp2 to p5 and one TEU from p1 to p6 with repacking at p2 and unpacking at p5Container packing may also affect how the containers are transported. For example, in Figure3(c), the container shipment demand (the number of containers to be transported from one port to another in a week) is the same as Figures 3(a) and 3(b). Containers are transported as follows in Figure 3(c): one TEU is transported from p1 to p2; at p2, the TEU is unloaded and repacked with another TEU whose origin is p2 into an FEU; the FEU is loaded/transshipped at p2 and transported to p5; at p5, the FEU is unpacked to two TEUs, one of which has arrived at its destination and the other should be transported to its destination p6. To compute the handling cost of the two TEUs at p2, we assume that there are two TEUs with origin p1 and another two TEUs with origin p2 that are repacked into two FEUs at p2 (hence, the handling cost is doubled). The two TEUs with origin p1 are actually transshipped at p2, and therefore the handling cost is (2c-p2T+c-p2F)/2. The two TEUs with origin p2 are actually loaded at p2, and therefore the handling cost is c^p2F. Consequently, the total handling cost at p2 in the example of Figure 3(c) is(5)2c-p2T+c-p2F/2+c^p2F2=c-p2T2+c-p2F4+c^p2F2.Similar arguments apply to the handling cost at p5. Therefore, the total container handling and packing cost in Figure 3(c) is(6)c^p1T+c-p2T2+c-p2F4+c^p2F2+cp22T→F︸Cost  atp2+c-p3F+c-p4F+c-p5T2+c-p5F4+c~p5F2+cp5F→2T︸Cost  atp5+c~p6T.In some cases, it is still possible that (6) is smaller than (3).


### 1.2. Literature Review, Objectives, and Organization

Quantitative research on container liner shipping can be classified into three categories: strategic, tactical, and operational problems [2, 3]. Strategic problems include ship fleet planning [4] and alliance formation [5]. Strategic problems involve decisions that have effects for many years, and hence it is very difficult to predict the container demand. As a result, the demand is usually simplified; for instance, containers are formulated as either TEUs, where a D40 is considered as two TEUs, or FEUs, where a D20 is considered as half an FEU. Tactical-level decisions include network design [6, 7], fleet deployment [8], speed optimization [9], and schedule design [10]. Tactical-level decisions are usually made taking into account how containers are transported in shipping networks. Nevertheless, in almost all of these studies on tactical-level problems, similar to the ones on strategic level problems, containers are formulated as either just TEUs or just FEUs. Wang [11] examined containership fleet deployment with both TEUs and FEUs; however, the TEUs are not allowed to be repacked to FEUs.Quantitative research on container terminal operations can be divided into studies on sea-side operations and studies on land-side operations. Sea-side decisions are mainly on berth allocation and quay crane assignment [12–19]. Land-side problems are mainly yard storage area planning and allocation [20–24]. There are also studies considering both container terminal operations planning and vessel scheduling [25–27]. None of the above studies related to container terminal operations has investigated the problem of repacking TEUs into FEUs.The objective of our study is to investigate how a container shipping line can transport containers in an efficient manner while accounting for the possibility of repacking two TEUs into one FEU to reducing the handling costs. We systematically examine this problem and develop a holistic model that incorporates both container routing and container repacking. Hence, we address a practical problem that is significant for container shipping industry.The remainder of the paper is organized as follows: Section2 describes the problem. Section 3 proposes a mixed-integer linear programming model that captures both container routing and container repacking. Section 4 reports a case study. Section 5 concludes.


## 1.1. Container Repacking

As the handling cost of a D40 is much lower than that of two D20s, it might be advantageous to unpack two D20s and repack them to one D40. In the sequel, we use “TEU” and “D20” interchangeably and use “forty-foot equivalent unit (FEU)” and “D40” interchangeably. The load, transshipment, and discharge cost (USD/container) of a TEU at a portp is denoted by c^pT, c-pT, and c~pT, respectively. The load, transshipment, and discharge cost (USD/container) of an FEU at port p∈P is denoted by c^pF, c-pF, and c~pF, respectively. We further let cp2T→F be the cost of repacking two TEUs into one FEU and cpF→2T be the cost of unpacking one FEU to two TEUs (Since multiple rehandling of containers would increase the risk for damage and therefore may increase insurance costs, we can include in cp2T→F and cpF→2T the extra insurance costs. Moreover, repacking requires consent from shippers and we can include in the rehandling cost the component of discount for shippers who agree for their cargos to be repacked.).Figure2 shows an example of transporting two TEUs from port p2 to port p5. The two TEUs need to be transshipped twice. If they are transported as two TEUs, as shown in Figure 2(a), then, at the port of origin, that is, p2, two TEUs are loaded; at p3, two TEUs are transshipped; at p4, two TEUs are transshipped; and, at the destination port p5, two TEUs are discharged. Therefore, the total container handling cost is (1)2c^p2T+2c-p3T+2c-p4T+2c~p5T.Figure 2
Container packing with the same origin and destination.
(a)
Two TEUs fromp2 to p5 without repacking (b)
Two TEUs fromp2 to p5 with repacking at p2 and unpacking at p5If these two TEUs are repacked into an FEU at the origin port and unpacked at the destination port, as shown in Figure2(b), then, at the port of origin, that is, p2, one FEU is loaded; at p3, one FEU is transshipped; at p4, one FEU is transshipped; and, at the destination port p5, one FEU is discharged. Moreover, container repacking and unpacking costs are incurred at p2 and p5, respectively (The FEU is unpacked at p5 into two TEUs because the two TEUs from port p2 to port p5 actually have different inland destinations.). Therefore, the total container handling and packing cost is(2)cp22T→F+c^p2F+c-p3F+c-p4F+c~p5F+cp5F→2T,which may be considerably smaller than (1).Not only can TEUs with the same origin and destination ports be repacked into FEUs, as shown in Figure2, TEUs with different origins and destinations can also be repacked into FEUs. For example, in Figure 3, one TEU is from p2 to p5 and the other TEU is from p1 to p6. If they are transported as TEUs throughout their trips, as shown in Figure 3(a), the total handling cost is(3)c^p1T+c^p2T+2c-p3T+2c-p4T+c~p5T+c~p6T.They may be repacked into an FEU at the transshipment port p3 and unpacked as two TEUs at transshipment port p4, as shown in Figure 3(b). At p3, since two TEUs are unloaded and one FEU is loaded in the transshipment process, the total transshipment cost is calculated as half of the sum of the transshipment cost of two TEUs and the transshipment cost of one FEU, that is, c-p3T+0.5c-p3F. Similarly, the transshipment cost at p4 is calculated as c-p4T+0.5c-p4F. Therefore, the total container handling and packing cost is(4)c^p1T+c^p2T+c-p3T+0.5c-p3F+cp32T→F︸Cost  atp3+c-p4T+0.5c-p4F+cp4F→2T︸Cost  atp4+c~p5T+c~p6T,which may be smaller than (3) if the container packing cost is small. Of course, the benefit of repacking TEUs into FEUs in Figure 3(b) is not as significant as Figure 2.Figure 3
Container packing with different origins and destinations.
(a)
One TEU fromp2 to p5 and one TEU from p1 to p6 without repacking (b)
One TEU fromp2 to p5 and one TEU from p1 to p6 with repacking at p3 and unpacking at p4 (c)
One TEU fromp2 to p5 and one TEU from p1 to p6 with repacking at p2 and unpacking at p5Container packing may also affect how the containers are transported. For example, in Figure3(c), the container shipment demand (the number of containers to be transported from one port to another in a week) is the same as Figures 3(a) and 3(b). Containers are transported as follows in Figure 3(c): one TEU is transported from p1 to p2; at p2, the TEU is unloaded and repacked with another TEU whose origin is p2 into an FEU; the FEU is loaded/transshipped at p2 and transported to p5; at p5, the FEU is unpacked to two TEUs, one of which has arrived at its destination and the other should be transported to its destination p6. To compute the handling cost of the two TEUs at p2, we assume that there are two TEUs with origin p1 and another two TEUs with origin p2 that are repacked into two FEUs at p2 (hence, the handling cost is doubled). The two TEUs with origin p1 are actually transshipped at p2, and therefore the handling cost is (2c-p2T+c-p2F)/2. The two TEUs with origin p2 are actually loaded at p2, and therefore the handling cost is c^p2F. Consequently, the total handling cost at p2 in the example of Figure 3(c) is(5)2c-p2T+c-p2F/2+c^p2F2=c-p2T2+c-p2F4+c^p2F2.Similar arguments apply to the handling cost at p5. Therefore, the total container handling and packing cost in Figure 3(c) is(6)c^p1T+c-p2T2+c-p2F4+c^p2F2+cp22T→F︸Cost  atp2+c-p3F+c-p4F+c-p5T2+c-p5F4+c~p5F2+cp5F→2T︸Cost  atp5+c~p6T.In some cases, it is still possible that (6) is smaller than (3).


## 1.2. Literature Review, Objectives, and Organization

Quantitative research on container liner shipping can be classified into three categories: strategic, tactical, and operational problems [2, 3]. Strategic problems include ship fleet planning [4] and alliance formation [5]. Strategic problems involve decisions that have effects for many years, and hence it is very difficult to predict the container demand. As a result, the demand is usually simplified; for instance, containers are formulated as either TEUs, where a D40 is considered as two TEUs, or FEUs, where a D20 is considered as half an FEU. Tactical-level decisions include network design [6, 7], fleet deployment [8], speed optimization [9], and schedule design [10]. Tactical-level decisions are usually made taking into account how containers are transported in shipping networks. Nevertheless, in almost all of these studies on tactical-level problems, similar to the ones on strategic level problems, containers are formulated as either just TEUs or just FEUs. Wang [11] examined containership fleet deployment with both TEUs and FEUs; however, the TEUs are not allowed to be repacked to FEUs.Quantitative research on container terminal operations can be divided into studies on sea-side operations and studies on land-side operations. Sea-side decisions are mainly on berth allocation and quay crane assignment [12–19]. Land-side problems are mainly yard storage area planning and allocation [20–24]. There are also studies considering both container terminal operations planning and vessel scheduling [25–27]. None of the above studies related to container terminal operations has investigated the problem of repacking TEUs into FEUs.The objective of our study is to investigate how a container shipping line can transport containers in an efficient manner while accounting for the possibility of repacking two TEUs into one FEU to reducing the handling costs. We systematically examine this problem and develop a holistic model that incorporates both container routing and container repacking. Hence, we address a practical problem that is significant for container shipping industry.The remainder of the paper is organized as follows: Section2 describes the problem. Section 3 proposes a mixed-integer linear programming model that captures both container routing and container repacking. Section 4 reports a case study. Section 5 concludes.


## 2. Problem Description

Consider a setR of ship routes, regularly serving a group of ports denoted by set P. Ship route r∈R can be expressed as (7)pr1⟶pr2⟶⋯⟶prNr⟶pr1,where Nr is the number of ports of call and pri is the ith port of call, i=1,2,…,Nr. Define Ir≔{1,2,…,Nr}. The voyage from port of call i to port of call i+1 is called leg i and leg Nr is the voyage from port of call Nr to the first port of call. In Figure 1, three ship routes are shown: ship route 1 has three legs, ship route 2 has five legs, and ship route 3 has three legs. Each ship route has a weekly service frequency, which means that each port of call is visited on the same day every week. A string of homogeneous ships with a capacity of Vr (TEUs) is deployed on ship route r to maintain the weekly frequency. The liner services are similar to bus services [28].Represent byW the set of origin-to-destination (OD) port pairs, which is a subset of P×P. There are two types of containers to ship: TEUs (T) and FEUs (F). The demand for OD pair (o,d)∈W is denoted by nodT and nodF (containers/week) for TEUs and FEUs, respectively. Containers can be transshipped at any port from their origins to their destinations. The loading, unloading, and transshipment costs should be included in making container routing and repacking decisions.As aforementioned, two TEUs may be repacked into an FEU to reduce handling cost. From the practical point of view, we assume that a TEU can be repacked and unpacked at most once. The repacking and unpacking costs should also be included in making container routing and repacking decisions.It should be noted that two TEUs can only be repacked into an FEU at container yards. In other words, the repacking activity could not be carried out on ships. For example, in Figure3(c), the TEU with origin p1 must be unloaded from ships at p2 so as to be repacked with the TEU from p2 into an FEU (and hence handling cost of the TEU with origin p1 at p2 is incurred).The container routing with repacking problem aims to determine where to repack TEUs into FEUs and where to unpack the FEUs, and how to transport both TEUs and FEUs in order to minimize the total handling and packing cost, while allowing containers to be transshipped at any port in a liner shipping network.


## 3. Mixed-Integer Linear Programming Model

### 3.1. Demand Reformulation for Container Repacking

For each OD pair(o,d)∈W, we define yodpq,T as the number of TEUs that are repacked at port p∈P and unpacked at port q∈P. Let Z+ be the set of nonnegative integers. We have(8)yodpq,T∈Z+,∀o,d∈W,∀p∈P,∀q∈P.Therefore, the number of TEUs that are transported for OD pair(o,d)∈W without repacking, denoted by nodT4, is(9)nodT4=nodT-∑p∈P∑q∈Pyodpq,T,∀o,d∈W(10)nodT4≥0,∀o,d∈W.Note that (8) and (9) imply that nodT4 is an integer. The total loading and unloading cost of the nodT4 TEUs for all OD pairs is(11)CnodT4=∑o,d∈Wc^oT+c~dTnodT4.The transshipment cost of these nodT4 TEUs is not a constant as it depends on container routing.The number of TEUs with origin porto∈P and repacked into FEUs at port p∈P, denoted by nopT1, is(12)nopT1=∑d∈P∑q∈Pyodpq,T,∀o∈P,∀p∈P.In (12), o=p means that the TEU is repacked at its origin port. Hence, for this TEU, the loading cost is equal to half the loading cost of an FEU at port o. If o≠p, the loading cost of a TEU at port o, half the transshipment cost of a TEU, and a quarter of the transshipment cost of an FEU at port p should be considered. In either case, the repacking cost at port p should be considered. Therefore, the sum of the total handling cost excluding the transshipment cost between port o and port p (these TEUs may be transshipped when they are transported from port o to port p) and the repacking cost for these nopT1 TEUs is(13)CnodT1=∑o∈Pc^oF2nooT1+∑o∈P∑p∈P∖oc^oT+c-pT2+c-pF4nopT1+∑o∈P∑p∈Pcp2T→F2nopT1.The number of TEUs that are unpacked from FEUs at portq∈P and transported from port q∈P to their destination port d∈P, denoted by nqdT3, is(14)nqdT3=∑o∈P∑p∈Pyodpq,T,∀q∈P,∀d∈P.If q=d, the TEU is unpacked at its destination port. Hence, the discharge cost of half an FEU at port d should be considered. Otherwise, the discharge cost of a TEU at port d, half the transshipment cost of a TEU, and a quarter of the transshipment cost of an FEU at port q should be included. In either case, the unpacking cost at port q should be incorporated. Therefore, the sum of the total handling cost excluding the transshipment cost between port q and port d (these TEUs may be transshipped when they are transported from port q to port d) and the unpacking cost for these nqdT3 TEUs is(15)CnodT3=∑d∈Pc~dF2nddT3+∑d∈P∑q∈P∖dc~dT+c-qT2+c-qF4nqdT3+∑q∈P∑d∈PcqF→2T2nqdT3.The last reformulated demand is the transportation of the repacked containers, which are FEUs. The number of FEUs to be transported from portp∈P where they are repacked to port q∈P where they are unpacked, denoted by npqF2, is(16)npqF2=∑o∈P∑d∈Pyodpq,T2,∀p∈P,∀q∈P,npqF2∈Z+,∀p∈P,∀q∈P.Note that, for the npqF2 FEUs, the handling costs at port p and port q are already included in the calculation in (13) and (15). The transshipment cost between port p and port q (if any) depends on container routing.FEUs in the original demandnodF do not need further processing for modeling. The total loading and unloading cost of nodF FEUs is(17)CnodF=∑o,d∈Wc^oF+c~dFnodF.The transshipment cost of these nodF containers is not a constant as it also depends on container routing.We usen^odT and n^odF (containers/week) to represent the reformulated demand of TEUs and FEUs for OD pair (o,d)∈W, respectively. The total reformulated demand is(18)n^odT=0,o=dnodT1+nodT3+nodT4,∀o,d∈W,o≠d,n^odF=0,o=dnodF+nodF2,∀o,d∈W,o≠d.We define vectorn of decision variables for formulating container repacking:(19)n≔nodT1,nodT3,nodT4,n^odT,nodF2,n^odF,∀o,d∈W;yodpq,T,∀o,d∈W,∀p∈P,∀q∈P.The domain of n, represented by set N, is all vectors n in (19) that satisfy (8), (9), (10), (12), (14), (16), and (18).


### 3.2. Mathematical Model for Container Routing with Repacking

We have already characterized container repacking decisions using vectorn∈N. To formulate container routing, we simply consider the new container shipment demand shown in (18). The decision variables for formulating container routing are as follows. z^riod,T and z~riod,T are the number of TEUs per week from (o,d)∈W loaded and discharged at port of call i on ship route r, respectively (note that when calculating z^riod,T and z~riod,T, a transshipped TEU is considered as being discharged once and being loaded once); friod,T is the number of TEUs per week from (o,d)∈W flowing on leg i on ship route r (we define fr0od,T≔frNrod,T); z-pT is the total number of TEUs from all OD pairs transshipped at port p∈P per week. z^riod,F, z~riod,F, friod,F, and z-pF are defined correspondingly for FEUs. We define the vector of container routing decision variables:(20)x≔z^riod,T,z~riod,T,friod,T,z^riod,F,z~riod,F,friod,F,∀r∈R,∀i∈Ir,∀o,d∈W;z-pT,z-pF,∀p∈P.The container routing with repacking problem, with decisions in (19)-(20), can be formulated as an integer linear optimization model [29, 30]:(21)minn∈N,x∑p∈Pc-pTz-pT+c-pFz-pF+CnodT1+CnodT3+CnodT4+CnodF,subject to(22)fr,i-1od,T+z^riod,T=friod,T+z~riod,T,∀r∈R,∀i∈Ir,∀o,d∈W(23)z-pT=∑r∈R∑i∈Ir,pri=p∑o,d∈Wz^riod,T-∑d∈Pn^pdT,∀p∈P(24)∑r∈R∑i∈Ir,pri=pz^riod,T-z~riod,T=n^odT,p=o-n^odT,p=d,∀o,d∈W,∀p∈P0,otherwise(25)fr,i-1od,F+z^riod,F=friod,F+z~riod,F,∀r∈R,∀i∈Ir,∀o,d∈W(26)z-pF=∑r∈R∑i∈Ir,pri=p∑o,d∈Wz^riod,F-∑d∈Pn^pdF,∀p∈P(27)∑r∈R∑i∈Ir,pri=pz^riod,F-z~riod,F=n^odF,p=o-n^odF,p=d,∀o,d∈W,∀p∈P0,otherwise(28)∑o,d∈Wfriod,T+2friod,F≤Vr,∀r∈R,∀i∈Ir(29)z^riod,T∈Z+,z~riod,T∈Z+,friod,T∈Z+,∀r∈R,∀i∈Ir,∀o,d∈W(30)z^riod,F∈Z+,z~riod,F∈Z+,friod,F∈Z+,∀r∈R,∀i∈Ir,∀o,d∈W.The objective function (21) minimizes the total handling and repacking and unpacking cost. Constraint (22) is the TEU flow conservation equation. Constraint (23) defines the total number of transshipped TEUs at each port. Constraint (24) requires that the reformulated TEU demand is fulfilled. Equations (25)–(27) define the corresponding constraints for FEUs. Constraint (28) imposes ship capacity constraint on each leg of each ship route. Constraints (29)-(30) enforce the integrality of the number of containers.Note that as packing and unpacking containers take time, we can further incorporate constraints into the model related to the maximum number of containers that can be packed or unpacked. For instance, if ship A arrives at a port on Monday, ship B arrives at the port on Wednesday, and ship C arrives at the port on Friday, then there are two days’ time to pack ships A and B’s 20 ft containers into 40 ft containers to be loaded onto ship C. Taking into account the packing efficiency of the port, the maximum number of containers that can be packed can be calculated.


## 3.1. Demand Reformulation for Container Repacking

For each OD pair(o,d)∈W, we define yodpq,T as the number of TEUs that are repacked at port p∈P and unpacked at port q∈P. Let Z+ be the set of nonnegative integers. We have(8)yodpq,T∈Z+,∀o,d∈W,∀p∈P,∀q∈P.Therefore, the number of TEUs that are transported for OD pair(o,d)∈W without repacking, denoted by nodT4, is(9)nodT4=nodT-∑p∈P∑q∈Pyodpq,T,∀o,d∈W(10)nodT4≥0,∀o,d∈W.Note that (8) and (9) imply that nodT4 is an integer. The total loading and unloading cost of the nodT4 TEUs for all OD pairs is(11)CnodT4=∑o,d∈Wc^oT+c~dTnodT4.The transshipment cost of these nodT4 TEUs is not a constant as it depends on container routing.The number of TEUs with origin porto∈P and repacked into FEUs at port p∈P, denoted by nopT1, is(12)nopT1=∑d∈P∑q∈Pyodpq,T,∀o∈P,∀p∈P.In (12), o=p means that the TEU is repacked at its origin port. Hence, for this TEU, the loading cost is equal to half the loading cost of an FEU at port o. If o≠p, the loading cost of a TEU at port o, half the transshipment cost of a TEU, and a quarter of the transshipment cost of an FEU at port p should be considered. In either case, the repacking cost at port p should be considered. Therefore, the sum of the total handling cost excluding the transshipment cost between port o and port p (these TEUs may be transshipped when they are transported from port o to port p) and the repacking cost for these nopT1 TEUs is(13)CnodT1=∑o∈Pc^oF2nooT1+∑o∈P∑p∈P∖oc^oT+c-pT2+c-pF4nopT1+∑o∈P∑p∈Pcp2T→F2nopT1.The number of TEUs that are unpacked from FEUs at portq∈P and transported from port q∈P to their destination port d∈P, denoted by nqdT3, is(14)nqdT3=∑o∈P∑p∈Pyodpq,T,∀q∈P,∀d∈P.If q=d, the TEU is unpacked at its destination port. Hence, the discharge cost of half an FEU at port d should be considered. Otherwise, the discharge cost of a TEU at port d, half the transshipment cost of a TEU, and a quarter of the transshipment cost of an FEU at port q should be included. In either case, the unpacking cost at port q should be incorporated. Therefore, the sum of the total handling cost excluding the transshipment cost between port q and port d (these TEUs may be transshipped when they are transported from port q to port d) and the unpacking cost for these nqdT3 TEUs is(15)CnodT3=∑d∈Pc~dF2nddT3+∑d∈P∑q∈P∖dc~dT+c-qT2+c-qF4nqdT3+∑q∈P∑d∈PcqF→2T2nqdT3.The last reformulated demand is the transportation of the repacked containers, which are FEUs. The number of FEUs to be transported from portp∈P where they are repacked to port q∈P where they are unpacked, denoted by npqF2, is(16)npqF2=∑o∈P∑d∈Pyodpq,T2,∀p∈P,∀q∈P,npqF2∈Z+,∀p∈P,∀q∈P.Note that, for the npqF2 FEUs, the handling costs at port p and port q are already included in the calculation in (13) and (15). The transshipment cost between port p and port q (if any) depends on container routing.FEUs in the original demandnodF do not need further processing for modeling. The total loading and unloading cost of nodF FEUs is(17)CnodF=∑o,d∈Wc^oF+c~dFnodF.The transshipment cost of these nodF containers is not a constant as it also depends on container routing.We usen^odT and n^odF (containers/week) to represent the reformulated demand of TEUs and FEUs for OD pair (o,d)∈W, respectively. The total reformulated demand is(18)n^odT=0,o=dnodT1+nodT3+nodT4,∀o,d∈W,o≠d,n^odF=0,o=dnodF+nodF2,∀o,d∈W,o≠d.We define vectorn of decision variables for formulating container repacking:(19)n≔nodT1,nodT3,nodT4,n^odT,nodF2,n^odF,∀o,d∈W;yodpq,T,∀o,d∈W,∀p∈P,∀q∈P.The domain of n, represented by set N, is all vectors n in (19) that satisfy (8), (9), (10), (12), (14), (16), and (18).


## 3.2. Mathematical Model for Container Routing with Repacking

We have already characterized container repacking decisions using vectorn∈N. To formulate container routing, we simply consider the new container shipment demand shown in (18). The decision variables for formulating container routing are as follows. z^riod,T and z~riod,T are the number of TEUs per week from (o,d)∈W loaded and discharged at port of call i on ship route r, respectively (note that when calculating z^riod,T and z~riod,T, a transshipped TEU is considered as being discharged once and being loaded once); friod,T is the number of TEUs per week from (o,d)∈W flowing on leg i on ship route r (we define fr0od,T≔frNrod,T); z-pT is the total number of TEUs from all OD pairs transshipped at port p∈P per week. z^riod,F, z~riod,F, friod,F, and z-pF are defined correspondingly for FEUs. We define the vector of container routing decision variables:(20)x≔z^riod,T,z~riod,T,friod,T,z^riod,F,z~riod,F,friod,F,∀r∈R,∀i∈Ir,∀o,d∈W;z-pT,z-pF,∀p∈P.The container routing with repacking problem, with decisions in (19)-(20), can be formulated as an integer linear optimization model [29, 30]:(21)minn∈N,x∑p∈Pc-pTz-pT+c-pFz-pF+CnodT1+CnodT3+CnodT4+CnodF,subject to(22)fr,i-1od,T+z^riod,T=friod,T+z~riod,T,∀r∈R,∀i∈Ir,∀o,d∈W(23)z-pT=∑r∈R∑i∈Ir,pri=p∑o,d∈Wz^riod,T-∑d∈Pn^pdT,∀p∈P(24)∑r∈R∑i∈Ir,pri=pz^riod,T-z~riod,T=n^odT,p=o-n^odT,p=d,∀o,d∈W,∀p∈P0,otherwise(25)fr,i-1od,F+z^riod,F=friod,F+z~riod,F,∀r∈R,∀i∈Ir,∀o,d∈W(26)z-pF=∑r∈R∑i∈Ir,pri=p∑o,d∈Wz^riod,F-∑d∈Pn^pdF,∀p∈P(27)∑r∈R∑i∈Ir,pri=pz^riod,F-z~riod,F=n^odF,p=o-n^odF,p=d,∀o,d∈W,∀p∈P0,otherwise(28)∑o,d∈Wfriod,T+2friod,F≤Vr,∀r∈R,∀i∈Ir(29)z^riod,T∈Z+,z~riod,T∈Z+,friod,T∈Z+,∀r∈R,∀i∈Ir,∀o,d∈W(30)z^riod,F∈Z+,z~riod,F∈Z+,friod,F∈Z+,∀r∈R,∀i∈Ir,∀o,d∈W.The objective function (21) minimizes the total handling and repacking and unpacking cost. Constraint (22) is the TEU flow conservation equation. Constraint (23) defines the total number of transshipped TEUs at each port. Constraint (24) requires that the reformulated TEU demand is fulfilled. Equations (25)–(27) define the corresponding constraints for FEUs. Constraint (28) imposes ship capacity constraint on each leg of each ship route. Constraints (29)-(30) enforce the integrality of the number of containers.Note that as packing and unpacking containers take time, we can further incorporate constraints into the model related to the maximum number of containers that can be packed or unpacked. For instance, if ship A arrives at a port on Monday, ship B arrives at the port on Wednesday, and ship C arrives at the port on Friday, then there are two days’ time to pack ships A and B’s 20 ft containers into 40 ft containers to be loaded onto ship C. Taking into account the packing efficiency of the port, the maximum number of containers that can be packed can be calculated.


## 4. An Illustrative Example

We use the shipping network in Figure4 to demonstrate the applicability of the proposed model. There are three ship routes, and all ship routes are deployed with ships of a capacity of 5000 TEUs. There are three OD pairs, where all containers are TEUs. The container handling costs are assumed to be the same at all ports: c^pT=c~pT=100, c-pT=150, c^pF=c~pF=120, and c-pF=160. We consider four groups of repacking and unpacking costs: group 1 with cp2T→F=cpF→2T=50, group 2 with cp2T→F=cpF→2T=85, group 3 with cp2T→F=cpF→2T=200, and group 4 with cp2T→F=cpF→2T=250. We also consider four possible packing decisions: in decision 1, no container is repacked and unpacked; in decision 2, only containers from Shanghai to Colombo are repacked and unpacked; in decision 3, containers from Shanghai to Colombo and containers from Xiamen to Singapore are repacked and unpacked; and, in decision 4, all containers are repacked and unpacked.Figure 4
Another illustrative liner shipping network.The results are shown in Table2, and the minimum total cost in each repacking and unpacking cost group is highlighted in bold. We can see that when the repacking and unpacking costs are low (i.e., 50 USD), all TEUs should be repacked and unpacked. When the repacking and unpacking costs are higher, for example, when they are 200 USD, only TEUs from Shanghai to Colombo should be repacked and unpacked because they are transshipped twice and can take the largest advantage of handling FEUs instead of TEUs. When the repacking and unpacking costs are extremely high (i.e., 250 USD), it is no longer viable to repack TEUs into FEUs. Interestingly, those TEUs that are transshipped many times usually originate from a remote small port and are destined for another remote small port, and there are not many shipping services available. As a result, the shippers may have no choice but to agree to allow their cargos to be repacked during the trip from origin to destination. Another implication is that the packing costs may affect the routing of containers. If a port has very low packing costs, shipping companies may transship containers at this port for the sake of unpacking and repacking containers, and this will bring business to the port.Table 2
Results.
Total handling and packing cost(×1000 USD) c p 2 T → F = c p F → 2 T 50 USD 85 USD 200 USD 250 USD No repacking 1900 1900 1900 1900 Containers from Shanghai to Colombo repacked 1560 1630 1860 1960 Containers from Shanghai to Colombo and from Xiamen to Singapore repacked 1360 1500 1960 2160 All containers repacked 1330 1505 2080 2330


## 5. Conclusions

This paper has proposed a novel container routing with repacking problem in liner shipping. When routing containers, TEUs can be repacked into FEUs to reduce the handling cost as the handling cost of an FEU is much lower than twice the handling cost of a TEU. To the best of our knowledge, this is a new research topic that has not been dealt with in the literature. We developed a mixed-integer linear programming model that formulates the routing decisions and the repacking decisions in a holistic manner. The model could help container shipping lines to transport containers more efficiently. An illustrative example was reported to demonstrate the applicability of the model. Results show that the benefit of repacking two TEUs into an FEU is the most significant when containers are transshipped several times.Container routing not only is significant to liner shipping companies as an independent problem but also serves as a subproblem in a number of tactical-level decision problems such as network alteration and fleet deployment. How to address tactical-level decision problems while considering container repacking is an interesting future research direction.



---

*Source: 8608032-2017-01-31.xml*