The study investigates how different line‑sorting strategies influence the performance of an incremental heuristic for the Periodic Event Scheduling Problem (PESP). The heuristic, originally proposed by Lindner and Liebchen, builds a timetable by adding lines one by one to a growing subinstance and solving each intermediate instance with the ConcurrentPESP solver. In the present work the authors examined 27 distinct sorting rules that combine measures based on the number of arcs, arc weights, weighted span, and lower bounds, together with three connectivity rules that either minimise or maximise the number of connections between the current subinstance and the remaining lines. The sorting rules are applied to the 16 railway instances of the benchmark library PESPlib. Each iteration of the heuristic was given 60 seconds of wall time for the full optimisation routine (full_opt) while the fixing routine (fix_opt) was left unconstrained. Experiments were run on an Intel Xeon E3‑1270 processor with 32 GB of RAM.

The results show that sorting strategies that incorporate arc weights consistently outperform those based on lower bounds or raw arc counts. In particular, weight‑based rules such as w‑t (weight of transfer arcs), ws‑o (weighted span of outgoing arcs), and max‑ws‑dd (maximum weighted span of transfer and dwelling arcs) produced the best solutions for most instances. Connectivity also plays a role: while min‑connectivity runs never yielded the best gaps, max‑connectivity runs delivered the best solutions for a few instances, indicating that early optimisation of highly connected subinstances can be beneficial. Figure 1 of the report visualises the relative best gaps of each sorting, and Figure 2 aggregates the gaps over all instances, confirming the dominance of weight‑based sortings. The study reports five new incumbent solutions for PESPlib, improving the best known objective values by up to 2 %. The improvements are quantified in Table 1: R2L2 improved by 0.54 % using max‑w‑t, R2L4 by 0.06 % with ws‑o, R3L3 by 1.89 % with ws‑dd, R3L4 by 1.36 % with max‑ws‑dd, and R4L3 by 0.09 % with ws‑o. These gains demonstrate that even modest changes in the line‑ordering can lead to measurable improvements in timetable quality.

The collaboration behind the work involves four researchers: Patricia Ebert, Berenike Masing, Niels Lindner, and Ambros Gleixner. The team is based at the Zuse Institute Berlin and the Hochschule für Technik und Wirtschaft Berlin. Funding for the project was provided by the German Federal Ministry of Education and Research (BMBF) through the Research Campus MODAL (grant number 05M20ZBM), supporting Berenike Masing’s participation. The study was conducted in 2023, building on earlier publications that introduced the PESPlib benchmark and the ConcurrentPESP solver. The authors report no conflicts of interest. The work contributes to the ongoing effort to improve practical timetable optimisation by refining the incremental construction process and offers a set of empirically validated sorting heuristics that can be adopted in future timetable planning systems.