MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > March-April 2007 > Article Detail

COMPUTING SCIENCE

Trains of Thought

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

Brian Hayes

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





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Letters to the Editors: Getting Personal

Letters to the Editors: Global Changes

Letters to the Editors: Powerful Questions

Subscribe to American Scientist