Top banner
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo

COMPUTING SCIENCE

Trains of Thought

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

Brian Hayes

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.

Rail carsClick to Enlarge Image

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

Railroad-track topologyClick to Enlarge Image

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:

Click to Enlarge Image

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.

Devices and data structuresClick to Enlarge Image

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 2log2 n.

Tracking Data

A railroad workerClick to Enlarge Image

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.

A train-passing puzzleClick to Enlarge Image

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:

Click to Enlarge Image

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:

Click to Enlarge Image

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."

Getting cars to their destinationsClick to Enlarge Image

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


comments powered by Disqus
 

EMAIL TO A FRIEND :


Bottom Banner