COMPUTING SCIENCE

# Trains of Thought

Computing with locomotives and box cars takes a one-track mind

Guided by an unseen hand, a grimy railroad tank car negotiates a series of switch points in the tracks, veering right, then right again, then left. Next comes a lime-green box car, which makes two lefts. I observe these events from the control tower of a railroad facility called a hump yard, where freight cars sort themselves into trains bound for various destinations. It is an eerie scene. The cars glide silently downhill through the maze of tracks, seeming to steer themselves, as if each car knows just where it wants to go. This is an illusion; a computer two floors below me is making all the decisions, setting the switches a moment before each car arrives. But I can't shake the impression that the hump yard itself is a kind of computer—that the railroad cars are executing some secret algorithm.

It's not such a far-fetched notion. In 1994 Adam Chalcraft and Michael Greene, who were then at the University of Cambridge, and later Maurice Margenstern of the University of Metz, designed railroad layouts that simulate the operation of a computer. The machine is programmed by setting switch points in a specific initial pattern; then a locomotive running over the tracks resets some of the switches as it passes; the result of the computation is read from the final configuration of the switches.

These constructions are wonderfully ingenious, although admittedly they have little to do with the day-to-day running of real railroads. Even at a more practical level, though, brawny steel rails and brainy silicon chips have surprisingly rich connections. The work of the hump yard is a case in point. Algorithms for sorting are a specialty of computer science, but railroads were sorting freight cars decades before the first electronic computer was built. Methods invented by rail workers have served as metaphor and inspiration for the development of algorithms and data structures in computer science; conversely, the theoretical analysis of algorithms has suggested ways for railroads to improve their operations.

What a Way to Run a Railroad

Railroads were the epitome of high tech in the later years of the 19th century. Even more than dot-com businesses of recent times, they were a magnet for capital investment and intellectual talent. They dominated the economy; nine of the eleven companies in the earliest precursor of the Dow-Jones stock average were railroads. Technological innovations bloomed: Pneumatic brakes in 1869, automatic signals a decade later. Like the Internet today, railroads transformed aspects of daily life and culture, knitting together distant regions and even changing the way people kept time.

Trains have also become a part of our mental furniture. They appear in paintings, poems, novels, songs, legends and figures of speech; children are still strangely enchanted by them. In the sciences, too, trains have made an impression. Einstein worked out some of his ideas on special relativity by thinking about hypothetical events inside railway carriages. Trains are also common props in the problems found at the end of the chapter in mathematics and physics textbooks.

Somewhat more challenging than a typical textbook problem are
various railway-switching puzzles that began appearing in the 1880s.
W. W. Rouse Ball presented a few of them in his *Mathematical
Recreations and Essays*, first published in 1892. A good
example of the genre was discussed at length by A. K. Dewdney in
1987. Eastbound and westbound trains are chuffing toward each other
on a single track; they stop just in time to avert disaster, at a
place where a short siding parallels the main track. The siding,
which connects to the main line through switches at both ends, can
hold only one car or locomotive. The question is: Can the trains get
past each other, so that both of them can continue in their original
direction, pulling the same cars in the same order? (You might want
to try finding a solution on your own before reading on or peeking
at the diagram under the subheading "On the Right Track," *below*.)

If each train consisted of a single engine, unaccompanied by any cars, the problem would be easy: Just have one engine (say the eastbound one) duck into the siding while the other engine proceeds along the main track; afterward, the eastbound engine can exit the siding and continue on its way without obstruction. In fact, this scheme works no matter what the length of the westbound train.

What if *both* trains have several cars? The trains can still
pass, but the crews will have a busy day, coupling and uncoupling
cars and throwing switches. The basic idea is to break the eastbound
train into single cars and pass them through the siding one at a
time. (The westbound train remains intact throughout the procedure.)
The eastbound engine can slip by in the way described previously;
for the rest of the process, the westbound train does all the work.
First it moves forward and grabs the leading eastbound car; then the
train backs up into the siding and uncouples the car, leaving it
there. Now the train performs a maneuver called a runaround, backing
out of the eastern end of the siding, driving forward along the main
track until it is clear of the western switch, then reversing again
into the siding in order to push the eastbound car out and hitch it
to the waiting eastbound locomotive. The runaround procedure is
repeated for each of the remaining eastbound cars; for each one the
crew has to perform three hitching and three unhitching operations,
and the westbound train reverses direction twice.

Track Topology

Playing with a puzzle like this one will quickly acquaint you with a salient fact about railroads: They are one-dimensional. Rail cars cannot jump over or go around one another. Indeed, if a rail line has no switch points—if it is an unbranched length or loop of track—then the order of the cars is absolutely invariant. So is their orientation, or polarity; each car always faces in the same direction along the track. As a matter of fact, even in the presence of sidings like the one in Dewdney's puzzle, no rearrangement of the cars can ever alter their orientation; you can shuffle their sequence but you cannot change the direction they are facing. Certain other configurations of tracks and switches, however, do allow the orientation to be reversed.

Railroad switches (also known as turnouts, or points) have roughly the same geometry as highway on-ramps and off-ramps:

The action of the switch is asymmetrical. A train departing
*A* and moving from right to left can be steered either to
*B* or to *C*, but trains traveling from left to right
have no choices. The switch does not allow a turn from *B* to
*C* or from *C* to *B* (except by going through
the switch toward *A* and then backing up). For trains headed
right to left, a switch in this configuration is called a
*facing-point* switch; for those going left to right it is a
*trailing-point* switch.

Switches combine with straight and curved sections of track to form
the basic structural motifs of railroad layouts. The simplest such
element (other than an unbranched length of track) is a
*lead*, or *stub*: a dead-end branch connected to the
main track by a switch at one end. Depending on a train's direction
of travel, leads are entered either head-on through a facing-point
switch or by backing up through a trailing-point switch.

A *siding*, as mentioned above, is a parallel track with
connections to the main line at both ends; the two switches face in
opposite directions, which means that a train can run through the
siding and return to the main track still going the same way. A
*turnaround* *loop* has a jug-handle shape, with two
switches that face in the same direction; turnarounds are rare
except at the terminus of a rail line. Finally there is the
*wye*, a configuration of three switches joining three
tracks, and allowing a train on any track to reach either of the
other tracks. Turnarounds and wyes differ from other track elements
in that they change a car's orientation: The car can go in facing
east and come out facing west.

Some versions of the passing puzzle have the trains confronting each other at a wye instead of a siding. The third track attached to the wye is a short spur, with room for just one car. Despite this change in topology, essentially the same procedure can be used to get the trains past each other. Again the intact westbound train shuttles back and forth, parking the eastbound cars one at a time on the spur, then doing a runaround before pulling them out and shoving them along to the east. But there's a difference: The cars come out of the spur with reversed orientation. Turning them to face in the right direction takes another pass through the wye.

Can the trains pass if all they have to work with is a one-car, dead-end lead? Around 1900 Sam Loyd published a solution for trains of length 4 and 5. It takes 33 reversals of direction.

Another famous railroad puzzle asks if a train can make a U-turn at
a wye with a one-car-length spur. A suitable unit of measure for the
work done in turning the train around is the effort expended in
moving a single car through its own length. For a train of
*n* cars, Dewdney gave an algorithm requiring an amount of
work proportional to *n* ^{3}; in essence, *n*
cars move through *n* car-lengths *n* times. In 1988
Nancy Amato, Manuel Blum, Sandra Irani and Ronitt Ruvinfeld (all
then at the University of California, Berkeley) found an
improvement, reducing the effort required to *n*
^{2}log_{2} *n.*

Tracking Data

Sidings, wyes and other devices for directing trains inspired some of the earliest ideas about managing the flow of information through a computer program. In 1961 Edsger W. Dijkstra included a diagram of a railroad wye in a memorandum about methods of translating the new programming language Algol 60. In parsing an expression such as 3x(5+2), the seven symbols are read from left to right, but they must be acted on in a different order: First the subexpression inside the parentheses is evaluated by adding 5 and 2, then the result of this operation is multiplied by 3. Dijkstra showed that the reordering can be accomplished by temporarily storing the operators (such as x and +) in a data structure called a stack. The stack is a first-in, last-out storage device; in this case the x sign goes in first, followed by the + sign, but they come out in the opposite order. Dijkstra chose to explain this principle in terms of a railroad wye. One of the three tracks serves as input, one as output, and the third provides the first-in, last-out storage.

A few years later Donald E. Knuth, in the first volume of *The
Art of Computer Programming*, gave railroading
interpretations of three important data structures: the stack, the
queue and the double-ended queue, or deque. The queue is the
simplest of these—at least for railroaders. A queue is a
first-in, first-out data structure, and so it is represented by a
simple straight length of track. Cars put in at one end of the queue
come out the other end in the same order. A deque is an arrangement
of tracks allowing cars to be added at either end and removed from
either end (but there is no access to cars in the middle of the
train). Knuth illustrates a deque by a complicated layout of two
back-to-back jug-handle loops, requiring four switches. The same
functions can also be accomplished by an ordinary siding, provided
that trains are allowed to back up in order to pass through a
trailing-point switch. (The siding and the double-jug-handle layouts
differ in their effect on the orientation of the cars.)

On the Right Track

Routing and sorting are at the heart of railroad logistics. Cars enter the system from many points of origin, and they must be hauled to many destinations. Other transportation networks, such as shipping lines and the postal system, also sort their cargoes according to destination, but they do not have to deal with the strict one-dimensional constraint of railroad tracks.

Computer science offers a fully-stocked toolbox of methods for sorting—for putting things in order. The textbooks are filled with such algorithms: merge sort, insertion sort, selection sort, shell sort, heap sort, quick sort, bubble sort. It seems there's a sorting algorithm adapted to every imaginable purpose—except maybe the sorting of railroad cars.

When computer scientists evaluate the performance of a sorting algorithm, the usual practice is to measure the mental work done (deciding where each item goes) while ignoring the physical labor of actually moving things. An algorithm is judged to be more efficient if it requires fewer decisions, regardless of how often or how far the data have to be moved. This convention is reasonable when the things being sorted are bits and bytes of data, represented by packets of electric charge with a mass of maybe a zeptogram. The situation is different when you are sorting 100-ton rail cars.

Railroad sorting is usually done in two stages. First, a batch of cars going to the same general area is made up into a train; then the cars within a train are arranged in the best linear order for delivery to their individual destinations. The hump yard is mainly concerned with the first phase of this process. An incoming train is pushed slowly up a hill, and at the crest a worker "pulls the pin" to uncouple each car in turn. The separated car then rolls down the other side of the hill into a fan of diverging tracks. In a large yard there might be 40 or 50 of these "classification" tracks, where trains are assembled.

As each car comes over the hump, switches have to be set to direct it to the correct track. Years ago this was done by workers yanking on iron levers. Other workers, called runners, rode along on the coasting freight cars, cranking the hand brake to regulate speed so that the car would retain just enough momentum to couple with any other cars already on the classification track. The runners and the switch tenders are gone now. An unseen computer sets the switches and controls each car's speed through a mechanism called a retarder, which squeezes a passing car's wheels to slow it down. The speed is measured by radar units much like those used by the highway patrol. Each car is identified (so that the computer knows where to send it) by a radio-frequency ID tag.

From a computational point of view, the hump yard is an array of
queues arranged in parallel. Each car coming over the hump is
steered onto a specific track, where the car is appended to the rear
of the queue of cars already present there. When the train is
complete, a locomotive extracts the line of cars from the far end of
the classification track. Because of the first-in, first-out
property of a queue, this process does not change the order of the
cars within each train. (To be more precise: If car *A* is
ahead of car *B* in the incoming train, and if *A* and
*B* are both directed to the same classification track, then
*A* remains in front of *B* in the outgoing train.)

Solitaire Sorting

The second phase of the freight-car sorting process—putting
the cars in order for delivery—is typically done in smaller,
local switching yards. These are humpless "flat yards";
the cars are moved by engines rather than gravity. The tracks can be
arranged as queues, as in a hump yard, or as stacks—dead-end
leads—so that cars have to be pushed in and pulled out from
the same end. Suppose a train has cars numbered 1 through
*n*, but on arrival at the yard they are scrambled in some
arbitrary order; the departing train should have the cars in
ascending sequence, with car 1 just behind the engine and car
*n* at the end. How many classification tracks are needed to
achieve this result? How many times do cars have to be pushed onto
and pulled out of the tracks? These are questions of obvious
practical importance to railroaders. They are also questions that
yield to mathematical and algorithmic analysis.

Robert Tarjan of Stanford University answered some of the questions in 1972. Here are a few of his results:

If a switch yard has an internal loop, allowing cars at the output
to be brought back to the input for further processing, then
*any* sequence can be sorted. Conversely, in the absence of
such loops, no finite network of stacks, queues or deques can sort
all possible sequences, even if the individual storage elements are
of unbounded capacity.

If the yard consists of *m* queues arranged in parallel, then
a train can be fully sorted if and only if the longest decreasing
subsequence has no more than *m* cars. (The cars of a
decreasing subsequence don't have to be consecutive; for example, in
the sequence 1635492 the longest decreasing subsequence is 6542.)
For a yard with *m* parallel stacks, it's the longest
*increasing* subsequence that governs. But these constraints
are somewhat artificial. They apply only if cars must always move
from the input to a stack or a queue and then directly to the
output. Real rail yards are more flexible; cars can be pulled from
one stack and pushed onto another. When moves like this are allowed,
it's harder to determine which sequences can be sorted.

In 2000 Elias Dahlhaus, Peter Horak, Mirka Miller and Joseph F. Ryan showed that a version of the switch-yard problem is NP-complete (which means, roughly speaking, that there's no efficient algorithm for solving it). Specifically, they proved it is difficult to decide how many tracks are needed.

Chinese mathematicians have taken a somewhat different and more-pragmatic approach to train-sorting problems, apparently in response to a request from Chinese railroad officials. (The exact provenance of these ideas is somewhat murky. In 1976 an American delegation to China heard a lecture on the subject by Ma Chung-fan; notes on this talk were written up by Henry O. Pollak and published in a National Academy of Sciences report. A 1983 paper by Zhu Yongjin and Zhu Ruopeng covers similar ideas but does not mention Ma.)

Pollak's lecture notes present an example: Use an array of stacks to sort the 10-car sequence 6324135726. (Cars with the same number are going to the same destination and thus should be grouped together.) Here I am going to consider the same example but look at it from a different point of view.

One approach to sorting the example sequence resembles a game of
solitaire, building multiple stacks of cars in nondecreasing order.
Working from the rear of the train toward the front, we examine the
number on each car and push the car onto a stack. Suppose the car we
have just reached bears number *k*. If there is exactly one
nonempty stack whose topmost element is greater than or equal to
*k*, then we put the car on that stack. If there are multiple
stacks with a top element greater than or equal to *k*, we
choose the stack with the smallest top entry. If no stack qualifies
to receive car *k*, then we have to start a new stack.

For the sequence 6324135726, we begin with the rightmost 6, which necessarily starts a new stack. We push 2 onto the same stack, but the 7 starts a second stack, which can also accept 5 and 3. The 1 then goes on the first stack, and the 4 inaugurates a third stack. Working through the rest of the sequence, we finally reach this configuration of four stacks:

Now the cars can be pulled out of the stacks in nondecreasing order; following the guidelines indicated by the colored blocks, this final assembly step will take seven "pulls." The sorted sequence, of course, is 1223345667.

In his Beijing lecture, Ma gave an alternative sorting procedure; I'm going to call it the Chinese solitaire algorithm. It partitions the sequence in a way that requires just four pulls to assemble the sorted train. Here is the final state of the four stacks:

It's easy to confirm that this configuration can be reached from the original train order, and that four pulls do indeed yield the properly sorted sequence. But by what rule were the numbers dealt into these particular groups? Both the notes on Ma's lecture and the paper by Zhu and Zhu give a rather convoluted algorithm. In trying to explain it I can do no better than quote the lecture notes:

Start at the leftmost (in this case the only) 1, put down all 1s,
all 2s to the right of the last 1, 3s to the right of the last 2 if
you have covered *all* the 2s, etc. In this case, the first
subset defined in this way is 12.... The next subset takes the other
2 and the second 3...; it can't get to the first 3. The next subset
takes the first 3, the 4, the 5, and second 6; the last subset is 67.

This procedure works, but there's an easier way to generate the same partitioning: Repeatedly scan from left to right, and on each pass extract the longest possible nondecreasing subsequence starting with the leftmost number. In the example considered here, the first such subsequence is 67, followed by 3456, then 23 and finally 12.

Zhu and Zhu give a proof that the Chinese solitaire algorithm allows
the train to be assembled with the minimal number of pulls from the
classification tracks. But the proof counts *only* pulls.
What about "pushes"—the train movements needed to
place the cars on the stacks in the first place? For the example
sequence, the Chinese algorithm has the worst possible performance
in this respect: Ten separate pushes are needed to stack up the 10
cars. The *non*-Chinese solitaire method is somewhat better,
at seven pushes. Taking the sum of pushes and pulls, the two methods
score a tie at 14. I don't know whether some other technique can do better.

All the Livelong Day

From the mathematical literature on railroad sorting, one might get the impression that putting the train in order is the end of all difficulties. The cars can then be dropped off at their destinations, one by one, without further thought. Train crews tell a different story. A memoir by Ralph E. Fisher, who worked on the Boston and Maine Railroad until the 1950s, refers to the process of making deliveries as a chess game. "Figuring out all these moves required no small skill if they were to be done in the shortest time and the least amount of motion."

Inspired by Fisher's stories, I offer the little puzzle
(*right*). The task is simply to deliver cars 1, 2 and 3 to
destinations *A*, *B* and *C*. The cars are
already in delivery order. The procedure shown requires six
reversals, three couplings and six uncouplings, for a total of 15
steps. Is there a better solution? Would some other initial
permutation of the cars be more efficient? Is there a *worse* permutation?

The chess game of making freight-car deliveries is one aspect of railroading that has gotten easier in recent years. Many of the spur lines used for such local runs have been closed. Much rail freight is now shipped in containers or piggy-back trailers that are lifted off the train at a central terminal and delivered by truck. Such "intermodal" transport doubtless has several advantages. One of them is escape from the tyranny of the one-track mind.

© Brian Hayes

EMAIL TO A FRIEND :