An Extended Space‐Time Network With Explicit Incompatibility Modelling for High‐Speed Railway Timetabling

High‐speed railway systems face increasing operational challenges due to rising passenger demand and complex infrastructure constraints. However, traditional space‐time network models for train timetabling may lack detailed representation of real‐world incompatibility constraints, limiting their practical applicability. This study proposes an extended space‐time network that explicitly incorporates train headway constraints through enhanced incompatibility modelling. The model classifies section arcs into eight operation‐specific types based on train movements at adjacent stations, enabling precise representation of distinct headway constraints. To address the limitations in existing arc incompatibility descriptions, two novel concepts are introduced: N‐incompatible arc sets and pairwise N‐incompatible arc sets. A 0‐1 integer programming formulation is developed to maximize train timetabling profits while strictly enforcing all headway and station capacity constraints. For large‐scale problems, a Lagrangian relaxation algorithm with model reformulation techniques is proposed to efficiently solve real‐world instances. Computational experiments on the Beijing–Shanghai high‐speed railway line demonstrate the model’s ability to generate conflict‐free timetables within acceptable computation time. This work enhances the conceptual framework of incompatibility modelling and bridges the gap between theoretical models and practical timetable generation by explicitly capturing heterogeneous train operations and intricate incompatibility relationships.