An obscure bit of history...

Hi there.

I wonder if anyone out there can help me out with some research I am
doing.

In the mid-1950s British Railways approached J. Lyons and company
(proprietors of the Lyons Corner House chain of tea-shops) to use the
then revolutionary LEO computer to calculate the distances between
each of BR's 5,000 or so stations. Basically they wanted to know the
shortest distance -- irrespective of what route it took -- between any
two stations on the network.

I am researching the LEO/BR "job", and have been fortunate enough to
track down the original project manager/programmer on the job and have
interviewed him about *how* it was done. I'm now trying to understand
the historical context behind the requirement.

It was done round about 1955/56. I have heard from one source that the
requirement was as result of some statute or act of Parliament. I've
also heard a rumour that it was something to do with some sort of
distance-based charging structure: but have no idea if this was an
internal BR accounting thing or if the fare structure was being
revised.

I guess from the date that it can't have been part of the Beeching
reforms, and must instead have been part of the modernisation
programme which preceded it.

Has anybody heard of this? If so, any idea what the driver for it
would have been.

Many thanks.

Tim.

"Tim" <timgreeningjackson@**********> wrote in message
news:53601019-ba26-45bd-a30c-c8c7e8595517@x35g2000hsb.************.com...
> Hi there.
>
> I wonder if anyone out there can help me out with some research I am
> doing.
>
> In the mid-1950s British Railways approached J. Lyons and company
> (proprietors of the Lyons Corner House chain of tea-shops) to use the
> then revolutionary LEO computer to calculate the distances between
> each of BR's 5,000 or so stations. Basically they wanted to know the
> shortest distance -- irrespective of what route it took -- between any
> two stations on the network.
>
> I am researching the LEO/BR "job", and have been fortunate enough to
> track down the original project manager/programmer on the job and have
> interviewed him about *how* it was done. I'm now trying to understand
> the historical context behind the requirement.
>
> It was done round about 1955/56. I have heard from one source that the
> requirement was as result of some statute or act of Parliament. I've
> also heard a rumour that it was something to do with some sort of
> distance-based charging structure: but have no idea if this was an
> internal BR accounting thing or if the fare structure was being
> revised.
>
> I guess from the date that it can't have been part of the Beeching
> reforms, and must instead have been part of the modernisation
> programme which preceded it.
>
> Has anybody heard of this? If so, any idea what the driver for it
> would have been.
>
> Many thanks.
>

I've no idea Tim but it sounds interesting. Can you post your results when
you get them please?

Many thanks
Kev

Peter Lawrence wrote:
> On Mon, 14 Jul 2008 22:58:31 -0700 (PDT), Tim
> <timgreeningjackson@**********> wrote:
>
> Not authorative, but a crude count of the Pre Grouping Railway Atlas
> gives about 8000 stations in 1923. So there are likely to have been
> at least 7000 in 1956.
>
> This is confirmed by C. Wolmar's book which quotes over
> 7000 stations in 1962. It seems the authoritative source is a bok
> on Railway Statistices1900-1970.

Cheers. Thanks for that.

> I suspect the exercise was part of the British Transport Commission's
> attempts to 'rationalise' fares and charges. The LT History records
> that many fare anomalies were removed, and then gradually reinstated
> following complaints. (I recall that about this time the one fare
> from Epsom to the SR London termini was replaced by six different
> mileage-based fares!)

I presume, though, that the push to calculate the distances at that time
was either due to the modernisation programme or -- perhaps more
prosaically -- due to the fact that the means to calculate them (LEO)
had just come to hand.

From my calculation, to calculate the distances between 7,000 separate
places would require 24,500,000 calculations. So a computer -- even one
with only 2,048 words of store like LEO would be attractive.

In message <487e7030$0$2520$da0feed9@news.zen.co.uk>, at 23:03:28 on
Wed, 16 Jul 2008, Tim Greening-Jackson
<zen167520_AT_zen_co_uk@?.?.invalid> remarked:
>I presume, though, that the push to calculate the distances at that
>time was either due to the modernisation programme or -- perhaps more
>prosaically -- due to the fact that the means to calculate them (LEO)
>had just come to hand.
>
>From my calculation, to calculate the distances between 7,000 separate
>places would require 24,500,000 calculations. So a computer -- even one
>with only 2,048 words of store like LEO would be attractive.

If trying to solve the problem by brute force, then you'll get a very
large number of calculations required. But there are many very simple
ways to optimise the search - although some of the techniques were still
in the research labs when I was at college in 1970.

The most obvious optimisation is to abandon the route you are exploring
as soon as the mileage exceeds your currently discovered minimum. eg If
you've already discovered that Waterloo-Portsmouth is no more than 73
miles via Haselemere, you abandon any alternative route (perhaps via
Basingstoke) as soon as it exceeds 73 miles. viz At Eastleigh which is
also 73 miles from London.

In practice you can truncate the process even quicker by working
backwards from the destination as well (you won't find any shorter route
from London to Portsmouth Harbour than starting from the already known
shortest route from London to Hilsea).
--
Roland Perry

Roland Perry wrote:
> In message <487e7030$0$2520$da0feed9@news.zen.co.uk>, at 23:03:28 on
> Wed, 16 Jul 2008, Tim Greening-Jackson
> <zen167520_AT_zen_co_uk@?.?.invalid> remarked:
>> I presume, though, that the push to calculate the distances at that
>> time was either due to the modernisation programme or -- perhaps more
>> prosaically -- due to the fact that the means to calculate them (LEO)
>> had just come to hand.
>>
>> From my calculation, to calculate the distances between 7,000 separate
>> places would require 24,500,000 calculations. So a computer -- even
>> one with only 2,048 words of store like LEO would be attractive.
>
> If trying to solve the problem by brute force, then you'll get a very
> large number of calculations required. But there are many very simple
> ways to optimise the search - although some of the techniques were still
> in the research labs when I was at college in 1970.
>
> The most obvious optimisation is to abandon the route you are exploring
> as soon as the mileage exceeds your currently discovered minimum. eg If
> you've already discovered that Waterloo-Portsmouth is no more than 73
> miles via Haselemere, you abandon any alternative route (perhaps via
> Basingstoke) as soon as it exceeds 73 miles. viz At Eastleigh which is
> also 73 miles from London.
>
> In practice you can truncate the process even quicker by working
> backwards from the destination as well (you won't find any shorter route
> from London to Portsmouth Harbour than starting from the already known
> shortest route from London to Hilsea).

The algorithm used was fairly a "brute force" one, based on working out
the minimum distance to successive adjacent nodes. But its use of brute
force is quite smart, as it splits the network in to regions and
considers the "difficult" (ie multiply connected nodes) I've re-created
it in Python, and the key bit is below:

def process_network(self):
while 1:
complete=1
for r in junctions:
for c in junctions:
if r != c or self.distances[r][c] != maxint:
first = self.distances[r][c]
for n in junctions:
if n != r and n != c and r!= c and
self.distances[c][n] != maxint:
next = self.distances[c][n]
distance = first + next
print "%s->%s->%s = %d + %d = %d" % (r,
c, n, first, next, distance)
if distance < self.distances[r][n]:
self.insert_distance(r, n, distance)
print self
complete=0
if complete: break

The problem was actually solved by Roger Coleman 15 years before you
were at college, and to put it in it's appropriate historical context
was done as Kuhn was developing the "Hungarian Method" solution to the
Travelling Salesman problem.

To say it was done on a machine which couldonly hold 2,048 16-bit words
--- and that had to contain the "operating system", program and data ---
and for which there wasn't even an assembler (they had to write the
object code down by hand in BCD) it's quite remarkable.

On 14 Jul, 22:28, Tim <timgreeningjack...@**********> wrote:

> I am researching the LEO/BR "job", and have been fortunate enough to
> track down the original project manager/programmer on the job and have
> interviewed him about *how* it was done. I'm now trying to understand
> the historical context behind the requirement.

Have you tried Bletchley Park? Quite a lot of records and expertise on
early computing seem to be migrating there.

Ian

On 17 Jul, 16:15, "BH Williams" <bhwilli...@letra.co.uk> wrote:

> But does the Travelling Salesman solution factor in the best place to get a
> decent cup of tea....?

Not to mention the farmer's daughter.

Ian

The Real Doctor wrote:
> On 14 Jul, 22:28, Tim <timgreeningjack...@**********> wrote:
>
>> I am researching the LEO/BR "job", and have been fortunate enough to
>> track down the original project manager/programmer on the job and have
>> interviewed him about *how* it was done. I'm now trying to understand
>> the historical context behind the requirement.
>
> Have you tried Bletchley Park? Quite a lot of records and expertise on
> early computing seem to be migrating there.
>
> Ian

I've got the computing side of it pretty much covered, thanks. It's the
Railway side that I'm struggling to understand. So I presume that
somewhere like Kew would be more likely as a source of useful
information. No?

Tim Greening-Jackson wrote:
> The Real Doctor wrote:
>> On 14 Jul, 22:28, Tim <timgreeningjack...@**********> wrote:
>>
>>> I am researching the LEO/BR "job", and have been fortunate enough to
>>> track down the original project manager/programmer on the job and have
>>> interviewed him about *how* it was done. I'm now trying to understand
>>> the historical context behind the requirement.
>>
>> Have you tried Bletchley Park? Quite a lot of records and expertise on
>> early computing seem to be migrating there.
>>
>> Ian
>
> I've got the computing side of it pretty much covered, thanks. It's the
> Railway side that I'm struggling to understand. So I presume that
> somewhere like Kew would be more likely as a source of useful
> information. No?

Would the NRM have some archive material?
--
Bruce Fletcher
Stronsay, Orkney
(Remove dentures to reply)

"Bruce Fletcher (Stronsay, Orkney)" <ricardianteeth@btinternet.com> wrote
in message news:7fmdnSGpsZ0byR3VnZ2dnUVZ8qTinZ2d@bt.com...
> Tim Greening-Jackson wrote:
>> The Real Doctor wrote:
>>> On 14 Jul, 22:28, Tim <timgreeningjack...@**********> wrote:
>>>
>>>> I am researching the LEO/BR "job", and have been fortunate enough to
>>>> track down the original project manager/programmer on the job and have
>>>> interviewed him about *how* it was done. I'm now trying to understand
>>>> the historical context behind the requirement.
>>>
>>> Have you tried Bletchley Park? Quite a lot of records and expertise on
>>> early computing seem to be migrating there.
>>>
>>> Ian
>>
>> I've got the computing side of it pretty much covered, thanks. It's the
>> Railway side that I'm struggling to understand. So I presume that
>> somewhere like Kew would be more likely as a source of useful
>> information. No?
>
> Would the NRM have some archive material?



According to A2A, the LMA seem to have the archives of J Lyons and Company
Limited.

MB