Home
Alphabetical
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Railway Layout Problems

 

a Lego toy railway layout

Problem

Looking at some track constructions of a toy train, I noticed that sometimes the train would get "stuck" in a loop, and that some places could not be reached no matter how you played with the switches:  it was necessary to pick up the train and move it to the desired spot.  This is not very pleasing.

Each layout has this property:  either it is one for which we have to pick up the train to get it to certain spots, or it is one where we can get the train to any spot by only playing with the switches.  This raises the question:  by just looking at the layout, can we determine if it is possible to reach all points from all other points, in both senses of travel, by only playing with the switches?

Consider a simple oval:

Figure 1: a simple oval

Obviously it is possible to get to any point from any point, but it is not possible to turn the train around without picking it up.  The formulation of the question above requires that any point can be reached coming from either direction, and the simple oval layout does not allow it.

(Note:  requiring both senses of travel is somewhat stricter than just requiring that any point can be reached from any other point, but it is perhaps easier to deal with.  But I don't know as I have not tried to solve the less restrictive problem).

Now consider an oval with two switches and an extra segment:

A1 A2 B2 C2 B1 C1 2 1

Figure 2: an oval with two switches and a diagonal

Let us give a name to each section of rail between the switches.  There are three such sections:  A, B and C.  Each has two end points which we number 1 and 2.  Starting from point A1 and travelling towards point A2, we can then go around the oval, but taking the segment B2-B1 the train can be turned around and travel the oval in the other sense. However, once that has been done, there is no way to turn the train around once more.  Worse: starting from C1 and travelling in the direction of C2, it is not possible at all to turn the train around, and points on segment B1-B2 can not be reached at all!

A more explicit formulation of the problem is:

Given any point and a sense of travel, can any other point be reached in any sense of travel?

The answer for the simple oval with no switches is no.  The answer is also no for the oval with two switches of the above layout.

Can we compute the answer if we are given the layout?  To answer that question we need some formal way to express the topology of a layout, so we can feed it into a program.

Writing up a layout

Definitions:

A segment is a stretch of track between two switches.

A point is defined as a position on a segment plus one of the two senses of travel along the segment.

A point is reachable if the train can get to it by using only the switches present in the layout and if the train can reach that point in both of the two senses of travel along the segment.

A layout is All Points Reachable (APR) if the train can start from any point and reach any other point.

On a simple oval with no switches, any geometric point can be reached from any starting point, but since the train cannot be reversed, the oval is not an APR layout.

Normalising layouts

We assume there are no sidelines, i.e. rail segments that end, as can be found in sorting yards.  Obviously a train cannot reverse once it gets onto a segment that ends, and such layouts do not have the APR property.  But the part of the layout without the sidelines may still be APR.  If a given layout has ending segments, remove them and all switches that lead to them to get a normalised layout.

A normalised layout is one in which all segments are between two switches.

Furthermore, sometimes two switches touch, with no rail segments between them.  In that case a theoretical segment is introduced between the touching points:

1 2

Figure 3: a theoretical segment between touching switches

This does not change the topology.

Topological Observations

Crossings can be replaced by bridges, since no change of segment is possible at a crossing.  Bridges do not count topologically (see figure 5).

Starting from any point on a segment is topologically equivalent to starting from the endpoint corresponding to the sense of travel.  Thus it is sufficient to consider only the endpoints.

On a normalised layout the number of switches must always be even: adding a single switch adds an ending segment and to connect that again to the rest of the layout another switch is needed.

A normalised layout may be thought of as starting out as a single-segment oval.  Adding a switch splits a segment into two, but since another switch must be added, two new segments are created.

The number of segments is always equal to three times the number of pairs of switches (except for the case of no switches):

0 switches 1 segment
2 switches 3 segments, 1x3
4 switches 6 segments, 2x3
6 switches 9 segments, 3x3
8 switches 12 segments, 4x3

Summary of Assumptions

The layout has only switches and segments, all segments are between two switches and all switches are separated by a segment.  A theoretical segment is introduced between switches that touch each other.  There are no sidelines.

Conventions

All segments have been given a name, all switches have been numbered.  Example:

A1 A2 B2 C2 B1 C1 1

Figure 4: the elements of a switch.

In figure 4 there is a switch numbered 1 with three segments attached to it:  segment A is the incoming segment, segments B and C are outgoing.  A switch is not symmetrical:  it branches into two from point A2, i.e. it is not possible to go from C1 to B1 using only that switch.

Each segment has two endpoints numbered 1 and 2, e.g. segment A begins at A1 and ends at A2, likewise for B and C. Numbering the endpoints allows us to indicate the direction of travel.  Travelling in the sense A1 to A2 is noted simply as A1 (the starting point of the section when travelling in that sense), travelling in the opposite direction, i.e. from A2 to A1, is simply noted as A2.

To describe a switch it is then sufficient to indicate the endpoints connected to it and to be able to distinguish the incoming point from the two outgoing ones.  The switch of figure 4 would be noted as:

1 A2 B1 C1

meaning it is switch number 1, its incoming point is connected to point 2 of segment A and it gives the choice to go from A2 to point 1 of segment B or to point 1 of segment C (no preference, i.e. the notation 1 A2 C1 B1 would be just as good).

A more complex layout

Using the notation of the example switch above, the layout

A1 A2 B1 B2 C1 C2 D1 D2 F1 E1 E2 H2 I1 G1 H1 F2 G2 I2 1 2 3 4 5 6

Figure 5: a more realistic layout.

is topologically completely described by the table:

1 A1 G2 I2
2 A2 B1 C2
3 B2 C1 D1
4 D2 E1 F1
5 G1 H1 F2
6 I1 E2 H2

Note that there is a crossing (light blue) but that does not allow any change of segment, and there is a bridge (gradient light blue) which also does not allow any change of segment, hence neither has any effect on the answer to the question of reachability, nor on how we write the table of switches.

Note again that the names of the segments are unimportant as long as they are unique, and that there is no preferred sense for numbering the endpoints.

Switch 2 of figure 5 allows travelling A1-A2-B1-B2 or A1-A2-C2-C1 when using the ingoing end, and from the other side we can go B2-B1-A2-A1 or C1-C2-A2-A1.

Starting from A1 it is possible to choose to go to B2 or C1, but starting from B2 or C1 we will always end up at A1.

Any point that can be reached from point B2, when travelling in the sense B1-B2, can also be reached from A1 when travelling in the sense A1-A2, provided we set switch 2 accordingly.  Recursively applying this observation we realise that any point reachable from B2 can also be reached from any point that allows us to get to A1 (travelling in that sense) and so on.  There must be some simple program that allows us to calculate reachable points by starting from the switch table.

The Connection Matrix

Let us study the oval with two switches of figure 3.  It is described by

1 C1 A1 B1
2 A2 B2 C2

Observation

As noted in the topological observations, although the number of points to start travelling from is infinite there are only six meaningful points to consider:  starting at any point on segment B, when travelling in the sense from B1 to B2, is equivalent to starting from B1 in the sense B1-B2.  So we can conveniently use the notation B1 to mean "start on a point of segment B, in the sense B1 to B2".

Therefore all the points and senses of travel can be summarised by listing only the six meaningful points A1, A2, …, C2.

The matrix

Now let us use a table for checking which points can be reached from which other points, by making a square table:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

In the left hand column we write the six points where we start from, and at the top are the points that can be reached from those points.  Such a table is also called a matrix.

Switch 1 is noted

1 C1 A1 B1

and since it is therefore at the C1 end of the C segment, we must start at the other end, viz. C2, in order to travel over it.  Having gone over it, we may arrive at either A1 or B1. The switch allows us to go from C2 to A1 or B1.  We can put this in the matrix by ticking two cells:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

Likewise, for the second switch we need to start at the other end, viz. A1, in order to use it, and it leads to ticking two more cells of the matrix:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

But we can also travel a switch in the other sense, i.e. for switch 1 we can go from either A2 (the other end of A1) or B2 (the other end of B1) to C1. Likewise via switch 2 from B1 or C1 to A2, which gives four more entries in the matrix:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

So for any switch noted n X1 Y1 Z1 we have to check the boxes for X2-Y1, X2-Z1,(changing the X1 into X2 to go forward through the two choices) and Y2-X1, Z2-X1 (changing the Y1 to Y2 and Z1 to Z2 to go backwards ending on the same track X1).

Obviously we could also check the diagonal cells because we can always go from A1 to A1, A2 o A2 etc. but this does not add any new information.

"Multiplying" the matrix

Looking at the matrix we see that from A1 we can get to B2, but the line of B2 says we can get to C1, hence we can also go from A1 to C1.  We should tick off the C1 column of the A1 row.  Thus we can complete the table by adding to the row of a certain point all the checkmarks of the rows corresponding to the points we can get to from that point.  If we do that we get:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

This can be repeated again, using the new information we have just filled in.  Indeed, now we know that B1 is reachable from A1, we can also get to A2.  We get:

A1 A2 B1 B2 C1 C2
A1
A2
B1
B2
C1
C2

How often do we need to repeat this process?  Certainly not more than 6 times, i.e. the number of rows or columns of our square matrix, because then every point has had the possibility to show its connections to any of the other five.  Adding more information may stop before 6 iterations, and in fact in this case it does after two and the final result is the same as above.

The resulting matrix is not full:  from A2 we cannot get to A1.  That may sound crazy, but remember that we should think of it as:

Starting at point A2, and thus travelling in the direction of A1, it is impossible to get (back) to point A1 with the train travelling in the sense A1 to A2

and that is certainly true.

I show on a different page a program to compute the APR property from a given switch table.

 


Valid XHTML 1.0 StrictValid CSS

next planned revision: