Gantry crane and shuttle car scheduling in modern rail–rail transshipment yards

Abstract

Modern rail–rail transshipment yards serve as hub nodes in railway networks and enable a rapid consolidation of containers among freight trains. The container transshipment is executed by parallel gantry cranes supported by a sorting system, where shuttle cars preposition containers to relieve the cranes from excessive movement along the spread of the yard. An important decision problem in this context is the scheduling of the gantry cranes, which is considerably complicated by the need to synchronize cranes and shuttle cars whenever container moves are executed via the sorting system. We formalize the resulting interdependent crane and shuttle car scheduling problem, introduce suited solution algorithms, and apply them in order to explore important managerial aspects. Our main findings in this regard are that the position of the sorter either in the middle of the tracks or at the outside has negligible impact on yard performance, while it is a challenging task to match the number of cranes with an appropriate fleet size of shuttles.

Appendices

Appendix A: Complexity of CSCSP

In this section we prove NP-hardness in the strong sense of CSCSP. At first sight, this complexity status directly follows from its relation to the asymmetric traveling salesman problem (ATSP). If we have neither split moves nor precedence constraints, our problem decomposes into m ATSPs. This relationship, however, is not sufficient for proving NP-hardness. All start and target positions of container moves lie along parallel lines, i.e., on the tracks or the sorter. This results in specially structured distance matrices and there are plenty special cases of the traveling salesman problem with similar prerequisites that turn out being solvable in polynomial time (see Burkard et al. 1998 for a survey).

Our reduction is from the 3-Partition problem instead, which is well-known to be strongly NP-hard (Garey and Johnson 1979).

3-Partition: Given 3q integers $a_1,\ldots ,a_{3q}$ with $\frac{B}{4}< a_j < \frac{B}{2}$. Does there exist a partition of set $\{1,2,\ldots ,3q\}$ into q subsets $A_1,\ldots ,A_q$ such that $\sum _{j \in A_i} a_j = B$ for each $i=1,\ldots ,q$?

The transformation scheme for an instance of 3-Partition to an instance of CSCSP is as follows: We have $m=2$ cranes and a single shuttle vehicle $o=1$. The job set contains $q+1$ split moves going from crane 2 to crane 1 and $3q+1$ direct moves all located in the area of crane 1. Among these direct moves are 3q moves that build the counterpart jobs corresponding to the integer values of 3-Partition. Additionally, we have a single start move. The shuttle move of each of the $q+1$ split moves takes $\frac{B}{2}$ time units, whereas of the belonging in- and out-moves have negligible processing time. The processing times of the counterpart jobs equal $p_j=\frac{a_j}{2}$, i.e., half of the integer values they refer to. Setup time $\tau _{ji}$ also equals $\frac{a_j}{2}$. Note that all counterpart jobs are assumed to start along the same vertical line, the start line, so that executing a job j and moving back to the start line takes the crane $a_j$ time units. The single start job has a processing time of $\frac{B}{2}$ and pickup ($\delta ^{\mathrm{out}}$) as well as set-down times ($\delta ^{\mathrm{in}}$) equal zero. The question we ask is whether a makespan of $Z \le (q+\frac{1}{2})\cdot B$ can be realized.

Fig. 8

Schedule structure of a transformed CSCSP instance

The given makespan induces that the shuttle vehicle has to be loaded instantaneously in crane area 2 and then continuously moves between both crane areas as it is depicted in Fig. 8a. Otherwise the given bound Z on the makespan will inevitably be exceeded. The total workload of crane 1 equals the makespan, so that idle time must not occur. The only possibility to fill the time span up to the first arrival of the shuttle at crane area 1 without idle time is the execution of the start move. Due to the restrictions of the integer values of 3-Partition no subset of direct moves fits into this gap. To not delay the shuttle vehicle crane 1 has to process it instantaneously upon arrival. This leaves exactly q gaps of B time units each for scheduling the counterpart jobs between any arrival of the shuttle and the one-to-one map** between both problems is directly available.

The only remaining aspect to detail is how the considered processing times of the container moves can occur given a container yard setting (see Fig. 8b). We assume that each crane moves one distance unit per time unit in longitudinal direction and has infinite velocity in lateral direction. All direct (split) moves have their start (target) positions along the start line, which is also the initial start position of crane 1. To give all container moves enough space along the start line we, thus, have to introduce $4q+2$ tracks. Along the start line, the crane moves with infinite velocity, so that the out-moves require no processing time. Time is only consumed by the direct moves, which require the way from the start line towards their respective target position (i.e., their processing time) and the setup time back to the start line in order to process another move.

Appendix B: Complexity of MFP

In this section, we prove that the mode feasibility problem applied in stage 3 of our decomposition approach (see Sect. 3.3) is strongly NP-complete even if $|V|=1$, i.e., only a single shuttle is available.

Consider an infinite velocity of cranes, so that $\Psi ^{Cr}_{\mu j}=\emptyset$ for all $\mu \in M_j$ and $j \in J^V$ and only a single shuttle, i.e., $|V|=1$, then MFP equals the following discrete interval scheduling problem (DISP), which was shown to be strongly NP-complete by Nakajima and Hakimi (1982): consider a set J of jobs to be processed on a single machine. Each job $j \in J$ is assigned a set of alternative processing intervals (or modes). If a specific processing interval of a job is selected, this means that during the complete time span from the fixed start to the end of the interval the machine is occupied by this job. The DISP decides whether all jobs can be processed, i.e., exactly one mode per job is selected, on a single machine without overlap. MFP is a generalization of this problem, which completes the proof.