Synthesis of railway signaling layout from local capacity specifications

Abstract

We present an optimization-based synthesis method for laying out railway signaling components on a given track infrastructure to fulfill capacity specifications. The specifications and the optimization method are designed to be suitable for the scope of signaling construction projects and their associated interlocking systems, but can be adapted to related problems in, e.g., highway, tram, or airport runway designs. The main synthesis algorithm starts from an initial heuristic over-approximation of required signaling components and iterates towards better designs using two main optimization techniques: (1) global simultaneous planning of all operational scenarios using incremental SAT-based optimization to eliminate redundant signaling components, and (2) a derivative-free numerical optimization method using as cost function timing results given by a discrete event simulation engine, applied on all the plans from (1).

Synthesizing all of the signaling layout might not always be appropriate in practice, and partial synthesis from an already valid design is a more practical alternative. In consequence, we focus also on the usefulness of the individual optimization steps: SAT-based planning is used to suggest removal of redundant signaling components, whereas numerical optimization of timing results is used to suggest moving signaling components around on the layout, or adding new components. Such changes are suggested to railway engineers using an interactive tool where they can investigate the consequences of applying the various optimizations.