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