Shunting operations at flat yards: retrieving freight railcars from storage tracks

In this paper, we study the railcar retrieval problem (RRT) in which specified numbers of certain types of railcars must be withdrawn from the storage tracks of a flat yard. This task arises as part of daily operations of railcar maintenance workshops. The objective is to minimize the total cost of the shunting operations. We describe the RRT formally, present a mixed-integer program formulation and prove the general case to be NP-hard. For some special cases, exact algorithms with polynomial runtimes are proposed. We also analyze several intuitive heuristic solution approaches motivated by current real-world planning routines. We evaluate their average performances in simulations with different scenarios and provide their worst-case performance guarantee. We show that although the analyzed heuristics result in much better solutions than the naïve planning approach, on average, they are still 30–50% from the optimal objective value and may result in costs up to 14 times higher in the worst case. Therefore, we conclude that optimization should be implemented in practice to save valuable resources. Furthermore, we analyze the impacts of yard layout and the widespread organizational routines on retrieval costs in detailed computational experiments.

The authors cooperated with Dr. Christian Otto at DB Schenker Rail and are very grateful to him for his valuable insights into the planning issues of railcar maintenance.

Authors and Affiliations

1. Management Science and Operations Research, Helmut Schmidt University – University of the Federal Armed Forces Hamburg, Holstenhofweg 85, 22043, Hamburg, Germany

   Florian Jaehn

2. Management Information Science, University of Siegen, Kohlbettstraße 15, 57068, Siegen, Germany

   Alena Otto

3. Logistics and Supply Chain Management, University of Mannheim, PO Box 10 34 62, 68131, Mannheim, Germany

   Kilian Seifried

Corresponding author

Correspondence to Alena Otto.

Appendix: Detailed proof of Proposition 5

Proof

Observe that the ratio \(\frac{\mathrm{WLBH}(I)}{\mathrm{Opt}(I)}\) cannot be greater than \(\frac{N+1}{3} \cdot \frac{z_1}{z_0}\) for all instances with \(\mathrm{Opt}(I) \ne 2\cdot z_0\), \(\mathrm{Opt}(I) \ne 2\cdot z_1\), or \(\mathrm{Opt}(I) \ne z_0+z_1\). Indeed, if an optimal solution consists only of one block, i.e., \(\mathrm{Opt}(I)=z_0\) or \(\mathrm{Opt}(I)=z_1\), then the WLBH will retrieve all the railcars in one block as well. Further, it is straightforward to see that \(\mathrm{WLBH}(I)\) cannot be larger than \(N\cdot z_1\). Hence, if an optimal solution consists of three or more blocks, i.e., \(\mathrm{Opt}(I)\ge 3\cdot z_0\), \(\frac{\mathrm{WLBH}(I)}{\mathrm{Opt}(I)}\) is necessarily lower than \(\frac{N+1}{3} \cdot \frac{z_1}{z_0}\). Therefore, we have to examine only the cases where an optimal solution consists of two blocks to prove that \(\frac{N+1}{3} \cdot \frac{z_1}{z_0}\) is indeed an upper bound for the approximation ratio for the WLBH. In the following, we provide explanations only for the set of instances \(\mathcal {I}'\) with \(\mathrm{Opt}(I')=2\cdot z_0, \forall I'\in \mathcal {I}'\). The proofs for the cases of \(\mathrm{Opt}(I)=2\cdot z_1\) and \(\mathrm{Opt}(I)=z_0+z_1\) are equivalent.

Step 1: General idea. We introduce additional notation. Assume for some instance \(I'\in \mathcal {I}'\) that the WLBH retrieves \(\mathcal {N}_1\) single-car blocks, \(\mathcal {N}_2\) blocks with two railcars each, \(\ldots \), and \(\mathcal {N}_N\) blocks with N railcars each, where \(\mathcal {N}_f\) are nonnegative integers.

To find the largest possible estimate for \(\frac{\mathrm{WLBH}(I')}{\mathrm{Opt}(I')}\) for instances \(I'\in \mathcal {I}'\), we look for instances with the worst possible objective value of the WLBH (i.e., those for which the WLBH withdraws railcars in the largest possible number of blocks, each with a cost of \(z_1\)).

Consequently, we set up an optimization model:

Our objective 7 is to construct an instance \(I'\) for which the WLBH retrieves railcars in as many blocks as possible. The number of railcars retrieved by the WLBH exactly corresponds to the number of railcars in workshop order N (constraint 9), and the decision variables are nonnegative integers (constraints 10). Constraint 8 restricts the number of single-car blocks (i) given that an optimal solution consists of two blocks and (ii) because of the WLBH algorithm. We will prove constraint 8 in step 2 below.

In the optimal solution, \(\overline{\text {{WLBH}}}\le \frac{2\cdot N+2}{3}\). We can see this, for example, by examining the LP-relaxation of the problem. Because of constraint 9, we can rewrite the objective function as \(N-\sum _{f=2}^N {(f-1)\cdot \mathcal {N}_f}\) and see that we have to maximize \(\mathcal {N}_1\) because \(\mathcal {N}_f\) has negative coefficients in the objective function for all \(f>1\). Therefore, constraint 8 is binding. Taking constraints 8 and 9 as equalities and substituting them into the objective function, we obtain expression \(\frac{2\cdot N+2-\sum _{f=3}^N {(f-3)\cdot \mathcal {N}_f}}{3}\). This expression reaches its maximum of \(\frac{2\cdot N+2}{3}\) when \(\mathcal {N}_f=0\) for \(f>3\). Therefore, the optimal objective value is \(\overline{\text {WLBH}}\le \frac{2\cdot N+2}{3}\) and, for instances \(I'\in \mathcal {I}'\), \(\frac{\mathrm{WLBH}(I')}{\mathrm{Opt}(I')}\le \frac{N+1}{3}\cdot \frac{z_1}{z_0}\).

Step 2: Proof of constraint 8. The main idea of the proof is as follows: At some iteration, for instance, \(I'\in \mathcal {I}'\), the WLBH withdraws a railcar of some type \(t^{*}\) that is currently critical. We denote the vector of the remaining demand (i.e., of the still-requested railcars) as \((n'_1, \ldots , n'_T)\). There is necessarily a railcar of this type \(t^{*}\) belonging to the not-yet-withdrawn railcars of any optimal solution \(X^{*}\) of instance \(I'\). The WLBH always retrieves the largest possible block of railcars containing the currently critical type. Because some \(X^{*}\) may contain all the railcars of the largest block, we will examine the properties of the blocks of not-yet-withdrawn railcars in \(\mathcal {X}^{*}\), which is the set of railcars belonging to all the optimal solutions of some instance \(I'\in \mathcal {I}'\). For this purpose, we introduce several definitions. Afterward, we formulate an observation.

Definition

Let us denote the railcars retrieved by the WLBH up to iteration m inclusively as \(\mathcal {X}^{\mathrm{WLBH}}_m\). We call a set of successively positioned railcars \(\{i, i+1, \ldots , i+l\} \subseteq \mathcal {X}^{*}\), \(i, \ldots , i+l \notin \mathcal {X}^{\mathrm{WLBH}}_m\) with \(|\{j\in \{i,i+1,\ldots ,i+l\} | u(j)=t\}|\le n'_t, \forall 1 \le t \le T\) as a remaining block \(B^{( l )}_m\) after iteration m.

In other words, we receive a remaining block if we delete the railcars of \(\mathcal {X}^{\mathrm{WLBH}}_m\) from \(\mathcal {X}^{*}\) and take a sequence of successively positioned remaining railcars.

Definition

We say that b remaining blocks at iteration m form a remaining solution \(\mathcal {B}_m=\{B^{( 1 )}_m, \ldots , B^{( b )}_m\}\), if they do not overlap (\({B^{( l )}_m} \cap {B^{( l' )}_m}={\varnothing , 1\le l , l' \le b}\)), represent separate blocks (i.e., \({B^{( l )}_m} \cup {B^{( l' )}_m}\) is not a remaining block, \(1\le l , l' \le b\)) and contain only still-requested railcars \(\left( |\{j\in \bigcup _{ l =1}^b {B^{( l )}_m}| u(j)=t\}| = n'_t, \forall 0 \le t \le T \right) \). We may alternatively denote an optimal solution of instance \(I''\) as \(\mathcal {B}_0\) (i.e., the remaining solution at iteration 0).

The example in Fig. 6 has only one optimal solution in which \(\mathcal {X}^{*}=\{52, 53, 54, 69, 70, \ldots , 79\}\). In the first iteration, the WLBH withdraws railcars \(\{2,3,4\}\). Thus, we no longer need railcars of types 1 and 2, and we can remove railcars 53, 72 and 76 from \(\mathcal {X}^{*}\). In this case, the remaining solution is unique and consists of five remaining blocks \(\mathcal {B}_1=\{\{52\}, \{54\}, \{69, 70, 71\}, \{73, 74, 75\},\{77, 78, 79\}\}\). However, for some instances \(I'\) in some iterations, there may be several distinct remaining solutions.

Observation 1

Let \(\mathcal {B}_{m-1}\) be a remaining solution, \(m \ge 1\) and \(\mathcal {B}_{m}\) is received from \(\mathcal {B}_{m-1}\) as a result of iteration m of the WLBH (i.e., \(\mathcal {B}_{m-1}\) contains all but \(|\mathcal {X}^{\mathrm{WLBH}}_m(I')\setminus \mathcal {X}^{\mathrm{WLBH}}_{m-1}(I')|\) elements of \(\mathcal {B}_{m}\)).

• If the WLBH retrieves a single-car block at iteration m, then the number of remaining blocks decreases by one: \(|\mathcal {B}_m|=|\mathcal {B}_{m-1}|-1\).

• If the WLBH retrieves a two-railcar block at iteration m, then the number of remaining blocks may increase by maximally one: \(|\mathcal {B}_m|\le |\mathcal {B}_{m-1}|+1\).

• If the WLBH pulls out an f-railcar block with \(f\ge 3\) at iteration m, then the number of remaining blocks may maximally increase by f: \(|\mathcal {B}_m|\le |\mathcal {B}_{m-1}|+f\).

In the following, we will provide justification for Observation 1.

Case of a single-car block. Let the WLBH retrieves a single-car block at iteration \(m \ge 1\). Due to the WLBH algorithm, all the remaining blocks \(B^{( l )}_{m-1}\) containing a railcar of the currently critical type \(t^{*}\) are single-car blocks. Therefore, regardless of whether the WLBH pulls out one of the remaining blocks, the number of remaining railcar blocks will decrease by one: \(|\mathcal {B}_m|=|\mathcal {B}_{m-1}|-1\).

Case of an f-railcar block, \(f\ge 2\). Let the WLBH retrieves an f-block, \(f\ge 2\). We obtain \(\mathcal {B}_{m}\) by deleting exactly one railcar from \(\bigcup _{ l =1}^b {B^{( l )}_{m-1}}\), where \(B^{( l )}_{m-1}\in \mathcal {B}_{m-1} \forall 1\le l \le b\), for each railcar retrieved by the WLBH at iteration m. If a deleted railcar is located somewhere in the middle of a multiple-car remaining block \(B^{( l )}_{m-1}\), then the number of the remaining blocks increases by one. Because the WLBH retrieves an f-railcar block, the number of the remaining blocks may increase by up to f: \(|\mathcal {B}_m|\le |\mathcal {B}_{m-1}|+f\).

Case of a two-railcar block. Let the WLBH retrieves a two-railcar block. From the paragraph above, it follows that the number of remaining blocks cannot increase by more than two: \(|\mathcal {B}_m|\le |\mathcal {B}_{m-1}|+2\). We strengthen this bound and show that the number of remaining blocks cannot actually increase by more than one. Indeed, at least one of the railcars retrieved by the WLBH at iteration m belongs to the currently critical type \(t^{*}\). Because there are no remaining blocks \(B^{( l )}_{m-1}\) containing type \(t^{*}\) with more than two railcars (otherwise the WLBH would retrieve a larger block in this iteration), it is impossible to increase the number of the remaining blocks by picking a railcar of type \(t^{*}\). Therefore, the number of remaining railcar blocks may maximally increase by one: \(|\mathcal {B}_m|\le |\mathcal {B}_{m-1}|+1\).

Let us construct an upper bound on the number of single-car blocks \(\mathcal {N}_1\) that can be retrieved by the WLBH for some instance \(I'\in \mathcal {I}'\) based on Observation 1. Because we examine \(I'\in \mathcal {I}'\) with \(\mathrm{Opt}(I')=2\cdot z_0\), then \(|\mathcal {B}_0|=2\) for any remaining solution before the first iteration of the WLBH. According to Observation 1, after the WLBH has retrieved some f-car block, the number of blocks in a remaining solution increases by f if \(f>2\) and by 1 if \(f=2\). Therefore, the number of single-car blocks \(\mathcal {N}_1\) cannot be greater than \(\left( 2+\sum _{f=3}^N {f \cdot \mathcal {N}_f}+\mathcal {N}_2\right) \). As a consequence, we have proven constraint 8 for instances \(I'\in \mathcal {I}'\). \(\square \)

Reprints and permissions