# Exact Algorithms for Practical Instances of the Railcar Loading Problem at Marine Container Terminals

Authors: ManWo Ng; Dung-Ying Lin
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

With the growth in global trade and its environmental footprint, sustainable modes of freight movement are increasingly important in today’s globalized world. This study focuses on on-dock rail, where the rail terminal is located within the marine container terminal. On-dock rail has in recent years become an essential mode of transportation to move containers out of congested marine container terminals. This study contributes to the literature by presenting tailored exact solution algorithms for a recently proposed optimization model to optimize the loading of double-stack trains. In particular, a 3-stage solution framework is presented for the case when rail cars have a single well. A complementary solution algorithm for the case when a rail car has multiple wells is also provided. Our results show that computational times can be drastically reduced, from 2+ hours to a matter of seconds, rendering the model suitable for practical use.


---

## Body

## 1. Introduction

According to the UN Conference on Trade and Development (UNCTAD), over 80 percent of global merchandise trade by volume and more than 70 percent by value are transported using the maritime mode of transportation. To manage this (growing) trade volume, there is a critical need to effectively manage the maritime transportation system, including the rapidly growing containerized trade. This has in recent years led to numerous advances in improved ocean container shipping management strategies (e.g., see [1–3]).Rail, especially on-dock rail—where the rail terminal is located within the marine container terminal—is increasingly being recognized as a sustainable and necessary mode of transportation to move containers in and out of congested marine container terminals. This trend fits within the broader call in the maritime industry to reduce ocean shipping’s carbon footprint [4]. In response to this call, maritime researchers have examined a range of alternatives, from the use of alternative fuels, to the setting of emission standards, speed optimization, and the use of shore power (e.g., see [5–7]).To maximize rail’s capacity, it is critical to build trains that are fully utilized when leaving the marine container terminal. Our focus in this study was on double-stack trains. For single-stack trains—that are subject to very different loading constraints—the reader is referred to the literature (e.g., see [8]). A limited number of studies have appeared in the literature that examined the problem of loading double-stack trains, with each study valid under its own set of assumptions appropriate for the geography and operating environment. To the best of our knowledge, Pacanovsky et al. [9] was the first research appearing in the literature discussing the problem of loading double-stack trains. In their work, an inland rail yard was considered where containers arrive continuously and a location on a double-stack train needs to be assigned immediately upon arrival. A heuristic was used to assign the containers. Lai et al. [10] presented an optimization model to optimize the aerodynamics of intermodal freight trains carrying both containers and trailers. It was noted that despite commercial decision support software being available, deciding where to place containers on (double-stack) trains was still “a largely manual process” in practice. Lang et al. [11] examined the loading of double-stack trains in China. While one of their goals was to maximize rail car maximization, their key focus appears to be on keeping the vertical center of gravity low. It is interesting to note that their loading constraints are very different from the model considered in this study. This is most likely due to the different equipment designs in China. For instance, they reported the possibility of loading two 20′ containers on top of two other 20′ containers, which is not common practice in the United States. Upadhyay et al. [12] presented a model for double-stack train loading tailored to the practice in India. As Lang et al. [11], they reported the possibility of loading two 20′ containers on top of two other 20′ containers. In addition to this key difference, Upadhyay et al. [12] also considered other constraints and practices in India that are uncommon in the United States. Most recently, Ng and Talley [13] presented an integer optimization model to load double-stack trains at marine container terminals. Unlike other models discussed above, Ng and Talley’s model is tailored to the practice at U.S. container ports. The above-related works are summarized in Table 1, in terms of two key variables: the country for which the model was developed and whether the model has been developed for marine container terminals.Table 1
Summary of key studies of double-stack rail optimization.
StudyCountryMaritimePacanovsky et al. [9]United StatesNoLai et al. [10]United StatesNoLang et al. [11]ChinaNoUpadhyay et al. [12]IndiaNoNg and Talley [13]United StatesYesThe current research is inspired by Ng and Talley [13]. The main focus in Ng and Talley [13] was on presenting a model that captured real-world operating practice. (Before proceeding, it is recommended that the reader reviews the model by Ng and Talley [13], which is summarized in Appendix A. For a more detailed discussion, the reader is referred to the original work.) The resulting model was solved for small problem instances with an off-the-shelf commercial solver. When the number of containers and rail cars is more realistic, i.e., larger, it becomes computationally prohibitive when using off-the-shelf solvers. (As we shall demonstrate in Section 5, it can take more than 2 days to find an optimal loading plan for practical instances of the problem, when using off-the-shelf solvers.) Marine container terminals need answers quickly for the model to be useful in practice. In this study, we exploit the problem structure to develop tailored solution methods for the rail loading problem. As shall be demonstrated, computational times will be drastically reduced, making the model suitable for practical use.The remainder of this study is organized as follows. In Section2, a tailored, three-stage solution method is provided to solve the optimization model. Section 3 considers an extension of the model in which rail cars can have multiple wells. A new solution framework is provided for this case. Section 4 illustrates the proposed methods with detailed computational results. Section 5 concludes the study.


## 2. Three-Stage Solution Approach for Single-Well Rail Cars

To solve model (P) in Appendix A, a tailored 3-stage solution approach is proposed in this section. The reader is advised to study the model formulation and its notation in Appendix A first before proceeding. The proposed method decomposes the problem into three stages. The first two stages determine an effective lower bound, while the final stage calculates a sharp upper bound for the objective function in model (P).


### 2.1. The First Stage

Note that the utilization of a rail car can be either 100%, 50%, or 0%. In the first stage, we try to maximize the number of 100% utilization cars. To this end, the following procedure is followed:(1)
The objective function is changed toMaxZ1=∑j∑kyjk1 in model (P). Furthermore, an additional constraint 1/2∑i∈Ihxik+∑m∈Mhvmk+∑j∈Jhyjk2=∑j∈Jhyjk1, ∀k∈K, is added to ensure that there must be an upper-level container if the lower level is loaded with containers. This constraint forces the rail cars to be loaded to 100% utilization.(2)
If the number of 100% utilization cars (sayQ) is equal to the number of available cars, i.e., Q=K, then the optimal solution is 100%.(3)
On the other hand, ifQ<K, then there is at least one rail car that cannot be loaded to 100% utilization. In this case, the containers that have not been assigned a rail car will be transferred to the next stage.In other words, the first stage solves the following programP1:(1)Z1=Max∑j∑kyjk1.s.t.Constraints (A.2)–(A.19).(2)12∑i∈Ihxik+∑m∈Mhvmk+∑j∈Jhyjk2=∑j∈Jhyjk1,∀k∈K.As this formulation only finds 100% utilization cars, the solution space is small. As will be shown in the numerical experiment in Section4, this formulation (or more accurately, its linearized version) can be solved efficiently using commercial optimization packages (i.e., CPLEX).


### 2.2. The Second Stage

WhenQ<K, the solution method enters the second stage. In this case, there must be at least one rail car that cannot be loaded to 100% utilization. In this second stage, we then try to maximize the number of 50% utilization cars.In this stage, the containers that have been assigned to the rail cars and the rail cars loaded with 100% utilization in the first stage are no longer considered. The interest in the second stage is only in the remaining containers and rail cars that have not been assigned/loaded.It is to be noted that in the second stage no rail cars will achieve 100% utilization. That is, we can discard constraints (A.8) and (A.12). Also, we eliminate constraint (2) from the first stage because the remaining containers will be loaded on the cars with a maximum utilization of 50% only and we cannot force the car’s utilization to 100%.In other words, the second stage solves the following programP2:(3)Z2=Max14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl,s.t.Constraints (A.2)–(A.7), constraints (A.9)–(A.11), constraint (A.13), and constraints (A.14)–(A.19).As the first stage, this second-stage problem can be efficiently solved using CPLEX. Proposition1 now is as follows.Proposition 1.
Z1+Z2 is a lower bound to model (P).Proof.
Since the first stage identifies 100% utilization cars and the second stage the 50% utilization rail cars, the first two stages together provide a feasible solution to the original problem.Q.E.D.


### 2.3. The Third Stage

Because of the sequential nature of the first two stages, the loading plan thus far is generally suboptimal. To improve on the utilization, a third stage is introduced. In the third stage, we first derive an upper bound on the utilization. After that, we solve the original formulation considering all containers and rail cars with an additional constraint that bounds the value of objective function. Before presenting the details, we introduce the following notation.(i)
Z¯: the sum of the objective values from the first two stages of the solution method, i.e., Z¯=Z1+Z2.(ii)
ah: the numbers of 20′ laden containers destined for hub h that are not loaded in the first two stages.(iii)
bh: the numbers of 20′ empty containers destined for hub h that are not loaded in the first two stages.(iv)
ch: the numbers of 40′ containers destined for hub h that are not loaded in the first two stages.(v)
n: the number of remaining rail cars that are not loaded with any containers after the first two stages.(vi)
a: a=∑h∈Hah/2, which represents the maximum possible number of 50% utilization cars for the remaining 20′ laden containers ah.(vii)
b: b=∑h∈Hbh/2, which represents the maximum possible number of 50% utilization cars for the remaining 20′ empty containers bh.(viii)
c: c=∑h∈Hch, which represents the maximum possible number of 50% utilization cars for the remaining 40′ laden containers.Recall that |K| denotes the number of rail cars that can be loaded. The following result can then be derived.Proposition 2.
Z¯=Z¯+m×0.5/K is an upper bound for model (P).Proof.
Using the above notation, note that at mostm=mina+b+c,n additional rail cars can be loaded with containers after the first two stages of the solution method, each with 50% utilization. Therefore, it follows that Z¯=Z¯+m×0.5/K is an upper bound. Q.E.D.
Based on the upper and lower bounds in propositions1 and 2, we can introduce the following constraint to the model (P):(4)Z¯≤14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl≤Z¯.
Then, we solve the following formulationP3 in this third stage with all the original containers and rail cars as input:(5)Z=Max14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl,s.t.
Constraints (A.2)–(A.19).(6)Z¯≤14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl≤Z¯.
As will be demonstrated in our numerical experiments, constraint (6) is critical in finding optimal solutions with limited computational effort. Figure 1 summarizes our 3-stage solution framework.Figure 1
Three-stage solution framework.


## 2.1. The First Stage

Note that the utilization of a rail car can be either 100%, 50%, or 0%. In the first stage, we try to maximize the number of 100% utilization cars. To this end, the following procedure is followed:(1)
The objective function is changed toMaxZ1=∑j∑kyjk1 in model (P). Furthermore, an additional constraint 1/2∑i∈Ihxik+∑m∈Mhvmk+∑j∈Jhyjk2=∑j∈Jhyjk1, ∀k∈K, is added to ensure that there must be an upper-level container if the lower level is loaded with containers. This constraint forces the rail cars to be loaded to 100% utilization.(2)
If the number of 100% utilization cars (sayQ) is equal to the number of available cars, i.e., Q=K, then the optimal solution is 100%.(3)
On the other hand, ifQ<K, then there is at least one rail car that cannot be loaded to 100% utilization. In this case, the containers that have not been assigned a rail car will be transferred to the next stage.In other words, the first stage solves the following programP1:(1)Z1=Max∑j∑kyjk1.s.t.Constraints (A.2)–(A.19).(2)12∑i∈Ihxik+∑m∈Mhvmk+∑j∈Jhyjk2=∑j∈Jhyjk1,∀k∈K.As this formulation only finds 100% utilization cars, the solution space is small. As will be shown in the numerical experiment in Section4, this formulation (or more accurately, its linearized version) can be solved efficiently using commercial optimization packages (i.e., CPLEX).


## 2.2. The Second Stage

WhenQ<K, the solution method enters the second stage. In this case, there must be at least one rail car that cannot be loaded to 100% utilization. In this second stage, we then try to maximize the number of 50% utilization cars.In this stage, the containers that have been assigned to the rail cars and the rail cars loaded with 100% utilization in the first stage are no longer considered. The interest in the second stage is only in the remaining containers and rail cars that have not been assigned/loaded.It is to be noted that in the second stage no rail cars will achieve 100% utilization. That is, we can discard constraints (A.8) and (A.12). Also, we eliminate constraint (2) from the first stage because the remaining containers will be loaded on the cars with a maximum utilization of 50% only and we cannot force the car’s utilization to 100%.In other words, the second stage solves the following programP2:(3)Z2=Max14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl,s.t.Constraints (A.2)–(A.7), constraints (A.9)–(A.11), constraint (A.13), and constraints (A.14)–(A.19).As the first stage, this second-stage problem can be efficiently solved using CPLEX. Proposition1 now is as follows.Proposition 1.
Z1+Z2 is a lower bound to model (P).Proof.
Since the first stage identifies 100% utilization cars and the second stage the 50% utilization rail cars, the first two stages together provide a feasible solution to the original problem.Q.E.D.


## 2.3. The Third Stage

Because of the sequential nature of the first two stages, the loading plan thus far is generally suboptimal. To improve on the utilization, a third stage is introduced. In the third stage, we first derive an upper bound on the utilization. After that, we solve the original formulation considering all containers and rail cars with an additional constraint that bounds the value of objective function. Before presenting the details, we introduce the following notation.(i)
Z¯: the sum of the objective values from the first two stages of the solution method, i.e., Z¯=Z1+Z2.(ii)
ah: the numbers of 20′ laden containers destined for hub h that are not loaded in the first two stages.(iii)
bh: the numbers of 20′ empty containers destined for hub h that are not loaded in the first two stages.(iv)
ch: the numbers of 40′ containers destined for hub h that are not loaded in the first two stages.(v)
n: the number of remaining rail cars that are not loaded with any containers after the first two stages.(vi)
a: a=∑h∈Hah/2, which represents the maximum possible number of 50% utilization cars for the remaining 20′ laden containers ah.(vii)
b: b=∑h∈Hbh/2, which represents the maximum possible number of 50% utilization cars for the remaining 20′ empty containers bh.(viii)
c: c=∑h∈Hch, which represents the maximum possible number of 50% utilization cars for the remaining 40′ laden containers.Recall that |K| denotes the number of rail cars that can be loaded. The following result can then be derived.Proposition 2.
Z¯=Z¯+m×0.5/K is an upper bound for model (P).Proof.
Using the above notation, note that at mostm=mina+b+c,n additional rail cars can be loaded with containers after the first two stages of the solution method, each with 50% utilization. Therefore, it follows that Z¯=Z¯+m×0.5/K is an upper bound. Q.E.D.
Based on the upper and lower bounds in propositions1 and 2, we can introduce the following constraint to the model (P):(4)Z¯≤14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl≤Z¯.
Then, we solve the following formulationP3 in this third stage with all the original containers and rail cars as input:(5)Z=Max14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl,s.t.
Constraints (A.2)–(A.19).(6)Z¯≤14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl≤Z¯.
As will be demonstrated in our numerical experiments, constraint (6) is critical in finding optimal solutions with limited computational effort. Figure 1 summarizes our 3-stage solution framework.Figure 1
Three-stage solution framework.


## 3. Case ofN-Well Rail Cars

Model (P) assumes that rail cars have a single well. While this is a possible scenario, what is more common in practice is to have rail cars that consist of multiple wells N, with the most common case being N = 5 (TTX, 2020) (https://www.ttx.com/about/equipment/). Figure 2 shows a 5-well rail car. In this case, the 3-stage framework no longer applies as it was tailored to the single-well case. In this section, a new solution technique is developed for the case of N-well rail cars, where N > 1.Figure 2
A 5-well rail car.To ensure that all well cars that are part of the rail car are dispatched toward the same hub, an additional constraint is introduced. In particular, for anN-well rail car (N>1), this additional constraint is as follows:(7)∑i=Nm+1Nm+Nuih=NuNm+1hh∈H,m=0,1,…,KN−1.For example, supposeN=5, then constraint becomes ∑i=5m+15m+5uih=5u5m+1h. Note that m indexes the number of N-well rail cars. For example, if there are three N-well rail cars, then the index m takes on the values 0, 1, and 2.Unfortunately, including constraint (7) does not allow the resulting optimization problem to be solved efficiently. To alleviate this, we derive an upper bound (UB) on the utilization as follows. In Section 4, we will demonstrate that the UB derived is very sharp and can significantly reduce the computational efforts required to solve the formulation. Recall from Section 2 that ah, bh, and ch represent the number of 20′ laden, 20′ empty, and 40′ containers to hub h, respectively. Further, let Fh and Hh be the minimum numbers of fully loaded (i.e., 100% utilization) and half-loaded (i.e., 50% utilization) rail cars for hub h, respectively. Then, the following three steps can be used to calculate the UB on the utilization when constraint (7) is present.Step 1.
(estimate the minimum number of cars required).
In the first step, we ignore the weight limit and attempt to load all containers with the minimum number of cars. In particular, we create groups for each two randomly selected 20′ laden containers and groups for each two randomly selected 20′ empty containers. As the 20′ containers can only be placed in the lower level, we load these groups to the cars first. Therefore, the minimum number of cars required to load the 20′ containers can be estimated asai/2+bi/2, as the weight limit is not considered in this step. Then, we try to load the 40′ containers on top of the groups of 20′ containers without considering the weight limit. Two scenarios are possible.(i)
ai/2+bi/2≥chBecause the number of 20′ containers required to load the cars with only 20′ laden and empty containers (ai/2+bi/2) is greater than the number of 40′ containers (ch), in this case, the number of cars that can be fully loaded Fh is equal to the number of 40′ containers ch. The remainder of the cars can only be half-loaded, and the number of this type of cars Hh is ah/2+bh/2−ch. Therefore, Fh=ch and Hh=ah/2+bh/2−ch in this scenario, respectively.(ii)
ah/2+bh/2<chIn this case, the number of 20′ containers is not enough to create the cars with 100% utilization using the combination of 20′ and 40′ containers. There can be multiple cars with only one 40′ container in the lower level of cars. We can estimateFh＝ah/2+bh/2+ch−ah/2+bh/2/2, where the first term ah/2+bh/2 is the number of fully loaded cars with a combination of 20′ and 40′ containers. In the second term, ch−ah/2+bh/2 is the remaining 40′ containers that cannot be combined with 20′ containers to form 100% utilization cars. Therefore, ch−ah/2+bh/2/2 represents the number of 100% utilization cars with only 40′ containers, since only when two 40′ containers are loaded to a car can that car have a utilization of 100%. Further, the minimum number of half-loaded cars is Hh=ch−ah/2+bh/2mod2. If Hh=1, there can be a 50% utilization car with one 40′. Hh=0, otherwise.Step 2.
(bounding the number ofN-well cars).
In this step, we bound the number ofN-well cars and subsequently determine how to distribute the single-well cars to these N-well cars.(i)
LetB be the number of N-well cars (N > 1) and S be the number of remaining unloaded single-well cars. Then, B=K/N,S=K−N×B (i.e., if N=5, B=K/5,S=K−5×B), where K represents the number of total single-well cars. If a single-well car is with 100% utilization, we choose to load it first to the N-well car. Let Mh be the number of fully loaded N-well cars for hub h and Uh,i be the utilization rate according to different loading approach i for partially loaded N-well cars for hub h. The following procedure estimates the number of N-well cars. If Fh≥N and B>0, we want to know how many fully loaded cars can be sent for each hub h.In this case, for each hub, we want to know how many fully loaded cars can be sent. LetMh=minFh/N,K/N, and we can update Fh←Fh−N×Mh and B←B−Mh.(ii)
IfFh<NSinceFh is the remaining full car and Hh is the remaining half-loaded car to hub h, we can update Uhi as follows:Forh = 1 to H{Fori = 1 to Fh+Hh/N{Uhi=1×Fh+0.5×minN−Fh,Hh/NFh←Fh−FhHh←Hh−minN−Fh,Hh}}In the equationUh,i=1×Fh+0.5×minN−Fh,Hh/N, the term 1×Fh is the utilization contributed by the 100% utilization cars in the N-well car. The term 0.5×minN−Fh,Hh is the utilization contributed by the rest of the cars in the N-well car.(iii)
LetNn∀n=1,2,…,R be the utilization for N-well cars that are not fully loaded. We sort Uh,i in descending order and assign cars into the big cars accordingly. Then, Fh=0,Hh=Hh−minN−Fh,Hh.Step 3.
(calculate the UB).
The last step calculates the UB. If the number of fully loaded cars is greater than or equal to the number of single cars that need to be assigned (∑hFh≥S), UB=ZN¯=S×1+N×∑hMh+N×∑nNn/K. The terms S×1, N×∑hMh, and N×∑nNn are the utilization contribution of single cars, the utilization contribution of fully loaded N-well cars, and the utilization contribution of partially loaded N-well cars, respectively.
Otherwise, if the number of fully loaded cars is less than the number of single cars that need to be assigned (∑hFh<S), UB=ZN¯=1×∑hFh+0.5×minS−∑hFh,∑hHh+N×∑hMh+N×∑nNn/K. In this case, 1×∑hFh, 0.5×minS−∑hFh,∑hHh, N×∑hMh, and N×∑nNn are the utilization contributions of 100% utilization single car, 50% utilization single car, fully loaded N-well car, and partially loaded N-well car, respectively.
To summarize, whenN-well rail cars are present (with N > 1), the following optimization problem is solved:(8)Z=Max14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl.
s.t.
Constraints (A.2)–(A.19) and constraint (7) and(9)14K∑k∑ixik+∑k∑mvmk+2∑l∑k∑jyjkl≤ZN¯.


## 4. Numerical Demonstration

### 4.1. Single-Well Rail Cars

To validate the proposed solution approach, we generated weights for the containers and weight limits of the rail cars according to real-world empirical distributions. (For a more detailed discussion of the weight data, see [13].) The cargo weight and car weight limit are between 10,000 and 100,000 and 140,000–180,000, respectively. The tolerance factor of a rail car is set to 1 in all cases (cf. Appendix A). The proposed 3-stage solution approach was implemented in the C# programming language. The numerical experiments were conducted on a Windows-based machine with an Intel 3.40 GHz CPU and 16 GB of memory.Table2 lists representative results for the 3-stage solution approach for 8 different instances of the problem. The CPLEX column shows the objective values found by CPLEX and the CPU time used when CPLEX is used to solve the problem instance. (All optimization problems are linearized first using the same techniques as in Ng and Talley [13] before CPLEX is applied.) For example, in Instance 1 the optimal utilization is 60%, and it took over 2562 seconds (42.7 minutes) to find this solution. This would make this “brute force” approach unacceptably slow for practical purpose.Table 2
Empirical results.
CPLEXStage 1Stage 2Stage 3Instance 1#20′ = 30 #40′ = 10 #Car = 20Objective value0.6000.5000.6000.600CPU time (sec)2562.7580.0390.1820.182CPU time saved—100.00%99.99%99.99%Optimality gap—16.67%0.00%0.00%Instance 2#20′ = 30 #40′ = 10 #Car = 25Objective value—0.4000.4800.480CPU time (sec)172,800∗0.0860.2400.240CPU time saved—100.00%100.00%100.00%Optimality gap—16.67%0.00%0.00%Instance 3#20′ = 30 #40′ = 10 #Car = 30Objective value0.6170.5000.6000.617CPU time (sec)111,617.9030.1510.7741.015CPU time saved—100.00%100.00%100.00%Optimality gap—18.92%2.70%0.00%Instance 4#20′ = 60 #40′ = 20 #Car = 30Objective value—0.6670.8000.817CPU time (sec)172,800∗0.1920.5641.583CPU time saved—100.00%100.00%100.00%Optimality gap—18.37%2.04%0.00%Instance 5#20′ = 60 #40′ = 20 #Car = 35Objective value—0.5710.7000.700CPU time (sec)172,800∗0.1047.5187.518CPU time saved—100.00%100.00%100.00%Optimality gap—18.37%0.00%0.00%Instance 6#20′ = 10 #40′ = 30 #Car = 15Objective value0.9000.8000.9000.900CPU time (sec)128,876.3245.2305.4215.421CPU time saved—100.00%100.00%100.00%Optimality gap—11.11%0.00%0.00%Instance 7#20′ = 10 #40′ = 30 #Car = 20Objective value—0.6000.8000.800CPU time (sec)172,800∗18.95319.35919.359CPU time saved—99.99%99.99%99.99%Optimality gap—25.00%0.00%0.00%Instance 8#20′ = 15 #40′ = 45 #Car = 20Objective value—0.9200.9600.960CPU time (sec)172,800∗60.0211252.6281252.628CPU time saved—99.97%99.28%99.28%Optimality gap—4.17%0.00%0.00%∗The CPU time is limited to about 2 days.When using the proposed 3-stage solution approach, the computation time can be drastically reduced. (Each of the stages is solved using CPLEX, applied to the respective linearized problems.) For example, for Instance 1, the column “Stage 1” shows the solution found after the first stage of the solution approach: a utilization of 50% (i.e., an optimality gap of 16.67% compared with the optimal utilization of 60%). This required just 0.039 seconds, i.e., a reduction of essentially 100%. To further improve this solution, the column “Stage 2” shows the solution after the second stage. As can be seen, the utilization has improved to 60% (recall that this is the optimal solution). The second stage took 0.182 seconds to find, which is a 99.99% reduction compared with the CPLEX column. While in this specific instance, the optimal solution was found after 2 stages, sometimes stage 3 is required (see column “Stage 3”), as was the case in Instance 3 in Table2. In Instance 3, the utilization improved from 0.5 to 0.6 to 0.617, which is the optimal solution.It is interesting to note that for 5 of 8 problem instances (instances 2, 4, 5, 7, and 8), CPLEX failed to find the optimal solution after 2 hours (172,800 seconds), which is the maximum computational time that was allotted to each instance. (In these instances, no objective values have been reported in Table2.) On the other hand, our 3-stage solution approach was able to solve each of the instances to optimality within seconds.


### 4.2.N-Well Rail Cars

SinceN  =  5 is the most common in practice, we will present empirical results for this case in this section. The same problem data as for the single-well experiment in the previous section have been used. The results are summarized in Table 3. Note that we have repeated the optimal utilization from the single-well model for comparison purpose.Table 3
Empirical results forN  =  5.
Instance no.Single-well car model5-well car model5-well car model with UBObjective valueTime (sec)Objective valueTime (sec)Objective valueUB10.60010.9010.6001.3200.6000.60020.480318.3290.4801.2640.4800.48030.6173600.2370.6171.4350.6170.61740.81733.4070.81732.6040.8170.81750.7003600.1830.7006.4250.7000.70060.90014.2170.90012.6850.9001.00070.800521.0590.750126.2430.7500.80080.96013.3690.9401.6240.9400.940There are a number of interesting findings. First, compared to the single-well case, the 5-well rail car model can result in lower utilization since it introduces the additional constraint (7). For example, in instances 7 and 8 the utilizations are 0.75 and 0.94, respectively, which corresponds to a decrease of 6.25% and 2.08% compared with the single-well car model. Second, the upper bounds derived in this research are very sharp. Note that besides instances 6 and 7, the upper bounds derived are the exact optimal solutions. Finally, introducing the upper bound into the model indeed significantly reduces the computational efforts when solving the 5-well rail car model. For example, it can reduce the computational time from more than 1 hour to just a little over 1 second (cf. instance 3).


## 4.1. Single-Well Rail Cars

To validate the proposed solution approach, we generated weights for the containers and weight limits of the rail cars according to real-world empirical distributions. (For a more detailed discussion of the weight data, see [13].) The cargo weight and car weight limit are between 10,000 and 100,000 and 140,000–180,000, respectively. The tolerance factor of a rail car is set to 1 in all cases (cf. Appendix A). The proposed 3-stage solution approach was implemented in the C# programming language. The numerical experiments were conducted on a Windows-based machine with an Intel 3.40 GHz CPU and 16 GB of memory.Table2 lists representative results for the 3-stage solution approach for 8 different instances of the problem. The CPLEX column shows the objective values found by CPLEX and the CPU time used when CPLEX is used to solve the problem instance. (All optimization problems are linearized first using the same techniques as in Ng and Talley [13] before CPLEX is applied.) For example, in Instance 1 the optimal utilization is 60%, and it took over 2562 seconds (42.7 minutes) to find this solution. This would make this “brute force” approach unacceptably slow for practical purpose.Table 2
Empirical results.
CPLEXStage 1Stage 2Stage 3Instance 1#20′ = 30 #40′ = 10 #Car = 20Objective value0.6000.5000.6000.600CPU time (sec)2562.7580.0390.1820.182CPU time saved—100.00%99.99%99.99%Optimality gap—16.67%0.00%0.00%Instance 2#20′ = 30 #40′ = 10 #Car = 25Objective value—0.4000.4800.480CPU time (sec)172,800∗0.0860.2400.240CPU time saved—100.00%100.00%100.00%Optimality gap—16.67%0.00%0.00%Instance 3#20′ = 30 #40′ = 10 #Car = 30Objective value0.6170.5000.6000.617CPU time (sec)111,617.9030.1510.7741.015CPU time saved—100.00%100.00%100.00%Optimality gap—18.92%2.70%0.00%Instance 4#20′ = 60 #40′ = 20 #Car = 30Objective value—0.6670.8000.817CPU time (sec)172,800∗0.1920.5641.583CPU time saved—100.00%100.00%100.00%Optimality gap—18.37%2.04%0.00%Instance 5#20′ = 60 #40′ = 20 #Car = 35Objective value—0.5710.7000.700CPU time (sec)172,800∗0.1047.5187.518CPU time saved—100.00%100.00%100.00%Optimality gap—18.37%0.00%0.00%Instance 6#20′ = 10 #40′ = 30 #Car = 15Objective value0.9000.8000.9000.900CPU time (sec)128,876.3245.2305.4215.421CPU time saved—100.00%100.00%100.00%Optimality gap—11.11%0.00%0.00%Instance 7#20′ = 10 #40′ = 30 #Car = 20Objective value—0.6000.8000.800CPU time (sec)172,800∗18.95319.35919.359CPU time saved—99.99%99.99%99.99%Optimality gap—25.00%0.00%0.00%Instance 8#20′ = 15 #40′ = 45 #Car = 20Objective value—0.9200.9600.960CPU time (sec)172,800∗60.0211252.6281252.628CPU time saved—99.97%99.28%99.28%Optimality gap—4.17%0.00%0.00%∗The CPU time is limited to about 2 days.When using the proposed 3-stage solution approach, the computation time can be drastically reduced. (Each of the stages is solved using CPLEX, applied to the respective linearized problems.) For example, for Instance 1, the column “Stage 1” shows the solution found after the first stage of the solution approach: a utilization of 50% (i.e., an optimality gap of 16.67% compared with the optimal utilization of 60%). This required just 0.039 seconds, i.e., a reduction of essentially 100%. To further improve this solution, the column “Stage 2” shows the solution after the second stage. As can be seen, the utilization has improved to 60% (recall that this is the optimal solution). The second stage took 0.182 seconds to find, which is a 99.99% reduction compared with the CPLEX column. While in this specific instance, the optimal solution was found after 2 stages, sometimes stage 3 is required (see column “Stage 3”), as was the case in Instance 3 in Table2. In Instance 3, the utilization improved from 0.5 to 0.6 to 0.617, which is the optimal solution.It is interesting to note that for 5 of 8 problem instances (instances 2, 4, 5, 7, and 8), CPLEX failed to find the optimal solution after 2 hours (172,800 seconds), which is the maximum computational time that was allotted to each instance. (In these instances, no objective values have been reported in Table2.) On the other hand, our 3-stage solution approach was able to solve each of the instances to optimality within seconds.


## 4.2.N-Well Rail Cars

SinceN  =  5 is the most common in practice, we will present empirical results for this case in this section. The same problem data as for the single-well experiment in the previous section have been used. The results are summarized in Table 3. Note that we have repeated the optimal utilization from the single-well model for comparison purpose.Table 3
Empirical results forN  =  5.
Instance no.Single-well car model5-well car model5-well car model with UBObjective valueTime (sec)Objective valueTime (sec)Objective valueUB10.60010.9010.6001.3200.6000.60020.480318.3290.4801.2640.4800.48030.6173600.2370.6171.4350.6170.61740.81733.4070.81732.6040.8170.81750.7003600.1830.7006.4250.7000.70060.90014.2170.90012.6850.9001.00070.800521.0590.750126.2430.7500.80080.96013.3690.9401.6240.9400.940There are a number of interesting findings. First, compared to the single-well case, the 5-well rail car model can result in lower utilization since it introduces the additional constraint (7). For example, in instances 7 and 8 the utilizations are 0.75 and 0.94, respectively, which corresponds to a decrease of 6.25% and 2.08% compared with the single-well car model. Second, the upper bounds derived in this research are very sharp. Note that besides instances 6 and 7, the upper bounds derived are the exact optimal solutions. Finally, introducing the upper bound into the model indeed significantly reduces the computational efforts when solving the 5-well rail car model. For example, it can reduce the computational time from more than 1 hour to just a little over 1 second (cf. instance 3).


## 5. Concluding Remarks

On-dock rail has become an essential and sustainable mode of transportation to move containers out of congested marine container terminals. To help marine container terminals maximize rail’s capacity in practice, it is critical to have both models and solution methods that are practice-ready.This study contributed to the latter. Using a recently introduced rail capacity maximization model, we demonstrated that—when using a commercial off-the-shelf solver—the computational times for realistic problem instances are prohibitively long for the model to be practically useful. To address this issue, new and tailored exact solution methods were developed in this research. Particularly, a 3-stage solution framework has been proposed for the case when rail cars have a single well. To complement this case, a solution method for the case when a rail car has multiple wells has also been provided. In the computational study, our results show that computational times can be dramatically reduced from 2+ hours to a matter of seconds, rendering the model suitable for practical use.There are at least three possible future research directions. First, while the model captures the most salient features observed in practice, it is possible to further extend the model to incorporate less common container types, most notably tank and hazardous cargo containers. Second, stochasticity during the planning and operation (i.e., random disruption or stochastic demand arrival) can also be incorporated. However, this might increase the computation times, which brings us to the last future research direction. Third, while our solution approach is highly efficient, it might be interesting to explore other solution methods, especially when considering different model extensions. For example, evolutionary algorithms have generally shown to be effective in addressing large-scale real-world problems; e.g., see Zhao and Zhang [14, 15].



---

*Source: 3927268-2022-01-28.xml*