TDP-NW: Benchmark Instances for the Train Dispatching Problem with No-Wait Constraints

The datasets contain benchmark instances for the Train Dispatching Problem with No-Wait Constraints (TDP-NW), a problem format that is a variation of the DISPLIB format. We generalize the format beyond the no-wait constraints with time offsets on resource reservations and releases, and with overlap reservations. With this we can express railway operations at a microscopic level, capturing train velocity and exclusive infrastructure usage where the network requires it. Problem Description In the TDP-NW, each train i is modeled by a directed acyclic graph (DAG) of operations. An operation has a duration, some resource reservations/releases, and successor operations. An arc links two operations that are feasible for a train to execute consecutively; on a subset of arcs a no-wait constraint is enforced, modeling that the train is not allowed to wait at the end of an operation, e.g. because its end velocity is not zero; on all remaining arcs the train may wait. A feasible solution selects, for each train, a source-to-target path through its DAG and assigns start times to its operations so that the no-wait/running-time constraints hold and resource usage is exclusive apart from overlaps. The objective is to minimize the total cost, composed of weighted delay costs for late arrivals and fixed costs for the operations used. The constraints and objective are stated precisely in Feasible Solution, once the instance notation is introduced. Instance Format (JSON) Each instance file contains a single JSON object with a version (schema version), num_resources ($|U|$, the resource-id domain size) and a trains array. Each train $i$ is represented by a DAG $G^{i}=(V^{i}, A^{i})$ of operations. Operations Each train has an ops array listed in topological order (the nodes $v \in V^i$), where each operation $v$ has: Field Notation Description d $\delta_v \in \mathbb{N}$ Running time of the operation successors arcs $(v, u) \in A^i$ Indices of successor operations $u$ in the DAG lb / ub bounds on $t_v \in \mathbb{Z}$ Lower/upper bounds on the start time (optional). The lower bound is mandatory for the source operation, since start times may be negative and an explicit floor is needed. p $\lambda \in \mathbb{N}$ Fixed cost incurred if this operation is used (optional, default 0) no_wait boolean If true, the no-wait constraint $t_v + \delta_v = t_u$ is enforced on all successors $u$; otherwise $t_v + \delta_v \leq t_u$ (optional, default false) rv / rvo / rl / rlo $R^{i}_{v}$ Resource reservations/releases of this operation, see below Resource usages are grouped into four optional buckets. Each bucket is an array of [offset, [resource_ids]] pairs, where offset $\in \mathbb{Z}$ is the time offset (whole seconds) from $t_v$ shared by all resources listed in that pair (denoted $t_s$ for reservations and $t_e$ for releases in the table below), and each $r_x \in U = \{0, \ldots, |U|-1\}$ identifies a shared resource. For example "rv": [[-9, [430]], [65, [403, 410]]] reserves resource 430 at $t_v-9$ and resources 403, 410 at $t_v+65$. Bucket Notation Description rv reservation, $t_s$ Resources reserved at $t_v + t_s$ rl release, $t_e$ Resources released at $t_v + t_e$ rvo / rlo As rv / rl, but for overlap usages (see below) Within an operation a given resource appears at most once per bucket. An overlap reservation refers to the extended route reservation when a train is stopping, for example in a station. There are often several possible overlaps for a route to choose from. While the overlap resource restricts other trains from using that same resource, it does not restrict another train from using the same resource as overlap, hence the separate buckets to distinguish the two resource usages. A resource reserved in one operation and released in a later one is held by every operation in between. These passthrough usages are not stored explicitly; they must be inferred from an operation's predecessors. The following assumptions hold on the reservation and release of resources: Every reservation of $r_x$ on a path has a corresponding release downstream, or the resource remains unreleased at the target operation, meaning that the train occupies that resource for infinite time. If more than one train has the same unreleased resource at the target operation and there is no way to avoid its reservation, only one of them can reach its target operation. To avoid infeasibility in that case it is reasonable to use a large constant as the release time for unreleased resources at the target operation. For every release there exists at least one corresponding reservation upstream. Operations between the reserving and releasing operation of a resource also hold the resource. If no reserving operation for $r_x$ is on a train's path, the resource is unused. After a resource is released the same resource might be reserved again. Example scenarios are a train reversing direction, or overlaps, where a train releases a track section ahead after stopping, which might get reserved again after the train gets permission to accelerate from the standstill. Objective Components Each train has an objective array of objective components, each with: Field Notation Description alt_ops Indices of the operations this component applies to. These operations are mutually alternative (exactly one is selected in any source-to-target path). threshold $\theta \in \mathbb{Z}$ Delay threshold coeff $c \in \mathbb{R}_{\geq 0}$ Cost per unit of delay (optional, default 0) increment $\gamma \in \mathbb{N}$ Fixed cost incurred when the operation is delayed, i.e. when $t_v + \delta_v > \theta$ (optional, default 0) The cost of an objective component given that operation $v$ is selected is$\text{cost} = c \cdot \max(0,\; t_v + \delta_v - \theta) + \gamma \cdot H(t_v + \delta_v - \theta)$, where $H$ is the Heaviside step function that takes the value 1 for positive arguments and 0 otherwise.Note that the delay is measured at the arrival of $v$ and not the departure, which is a difference compared to the DISPLIB definition (Kloster et al., 2025). Solution Format The solution format is the same as defined in DISPLIB. A solution is an array of events, each event is a timed operation of a train, with keys: "train", "operation", "time". All events are sorted by time and topologically. Feasible Solution A feasible solution selects, for each train, a path from source to target in the DAG and assigns finite start times to the selected operations such that: Time windows -- start time bounds $\texttt{lb} \leq t_v \leq \texttt{ub}$ are respected. Successor constraints -- for no-wait arcs: $t_v + \delta_v = t_u$; otherwise: $t_v + \delta_v \leq t_u$. Exclusive resource usage -- each resource $r_x \in U$ is used by at most one train at a time; simultaneous use is allowed only if every train holding the resource holds it as an overlap. The objective minimizes the sum of all objective components and fixed costs of the used operations. Datasets tdpnw_instances_1_2026-06-27.zip This dataset contains 32 instances from three different dispatching regions in Germany. We want to thank DB InfraGO (Zieger & Richta, 2025) for providing the dispatching data from which the problem instances were created, representing real-life dispatching situations considering time horizons of 20, 40, 60, and 90 minutes. The instances are anonymized such that they contain no reference to train or infrastructure objects, or the trains' velocities. Additionally, the threshold value of each objective component is normalized by its shortest-path lower bound. The solutions shown in the following table are computed using a timeout per iteration of 10 seconds. After 50 seconds we start fixing 5% of the decisions for conflicts which have been unchanged for at least 4 iterations. The best known lower bounds (LB*) are computed from a different configuration with a time limit per instance of 20 minutes. Instance Trains Nodes Resources Conflicts UB LB LB* Time [s] fbzm_dh_20_0 40 19314 810 117 2172.21 1836.21 2172.21 58.41 fbzm_dh_20_1 48 16003 928 127 2311.17 2311.17 2311.17 39.69 fbzm_dh_20_2 44 18396 806 418 3245.90 2344.65 3038.27 141.27 fbzm_dh_40_0 48 24717 906 80 1177.18 1177.18 1177.18 34.28 fbzm_dh_40_1 49 36616 887 135 1572.11 1327.39 1572.11 71.27 fbzm_dh_60_0 83 52231 928 397 5000.44 3792.61 4604.97 124.75 fbzm_dh_60_1 85 46917 932 365 2602.12 1802.90 2399.12 152.18 fbzm_dh_60_2 77 40889 933 180 1739.01 1572.72 1739.01 70.32 fbzm_large_dh_20_0 56 18710 1131 271 2329.97 1863.78 2280.65 100.56 fbzm_large_dh_20_1 56 21945 1145 335 3764.98 2486.41 3060.13 92.54 fbzm_large_dh_20_2 49 27794 1306 357 2672.22 2450.80 2563.02 195.20 fbzm_large_dh_20_3 48 32261 1278 201 2152.21 2152.21 2152.21 15.62 fbzm_large_dh_20_4 39 11057 894 158 1233.10 1170.69 1233.10 50.17 fbzm_large_dh_40_0 86 63760 1471 910 3448.25 1877.44 2199.39 176.60 fbzm_large_dh_40_1 86 70543 1463 1668 23981.02 2661.29 2748.79 245.34 fbzm_large_dh_60_0 113 80503 1482 1695 13442.58 3394.11 4304.85 369.67 fbzm_large_dh_60_1 107 67923 1453 1092 6732.99 4482.21 4823.57 266.61 fbzm_large_dh_90_0 134 118681 1536 2212 8577.28 4396.40 4549.91 394.20 mbzs_dh_20_0 47 15769 1008 135 1346.30 1346.30 1346.30 4.51 mbzs_dh_20_1 41 25314 1202 255 3123.87 2960.89 3123.87 94.69 mbzs_dh_20_2 38 10463 1115 111 1228.02 1228.02 1228.02 7.50 mbzs_dh_20_3 45 39916 1294 274 2334.40 2177.63 2334.40 103.17 mbzs_dh_20_4 46 23593 1383 317 2665.67 1773.07 2658.38 136.36 mbzs_large_dh_40_0 63 5778 445 400 5211.96 5209.46 5209.46 37.90 mbzs_large_dh_60_0 46 4718 454 141 2662.33 2662.33 2662.33 4.59 rbzs_dh_20_0 64 12567 812 246 2056.27 2056.27 2056.27 16.86 rbzs_dh_20_1 58 10940 663 378 2724.21 1912.85 2581.41 74.05 rbzs_dh_20_2 60 15629 810 359 3060.58 2419.52 2985.64 119.58 rbzs_dh_20_3 64 12498 767 466 5012.52 2912.90 4297.96 129.59 rbzs_dh_20_4 66 10817 727 348 5340.66 4056.77 5135.64 87.17 rbzs_dh_60_0 120 50457 1148 338 3133.21 2818.75 3130.55 71.42 rbzs_dh_90_0 148 70779 1111 1208 9290.57 5337.03 6048.29 197.84 displib_problems_2025-09-17_tdpnw.zip This dataset contains 112 instances converted from DISPLIB 2025 benchmark problems (Kloster et al., 2025) using the displib_to_tdpnw.py converter included in the repository git.zib.de/lstaerk/tdpnw-instances. If you use that benchmark dataset, check out displib.github.io to find out how to cite their work. Tools The repository git.zib.de/lstaerk/tdpnw-instances ships two Python scripts: tdpnw_checker.py, which verifies that a solution is feasible for a given instance and reports the objective value it computes, and displib_to_tdpnw.py, which converts a problem from the DISPLIB format into the TDP-NW format.