Jillian Beardwood (20 December 1934 – 28 October 2019)[1] was a British mathematician known for the Beardwood-Halton-Hammersley Theorem.[2] Published by the Cambridge Philosophical Society in a 1959 article entitled "The Shortest Path Through Many Points", the theorem provides a practical solution to the "travelling salesman problem".[3] The authors derived an asymptotic formula to determine the length of the shortest route for a salesman who starts at a home or office and visits a fixed number of locations before returning to the start.
Beardwood was born in Norwich, England in 1934. After attending The Blyth School for Girls, she studied mathematics at St. Hugh's College, Oxford, earning first-class honours and a master's degree in 1956.[4]
After university, Beardwood accepted a position at the newly formed United Kingdom Atomic Energy Authority (UKAEA), where she was one of four postgraduate students selected to study with John Hammersley, a professor at Trinity College, Oxford. In that position, Beardwood gained access to the Ferranti Mercury computer at the UKAEA's research facility at Harwell, as well as to the ILLIAC II computer at the University of Illinois. She was later promoted to Senior Scientific Officer at the UKAEA, where she specialized in Monte Carlo methods and algorithms for modeling complex geometrical situations.
The problem of determining the shortest closed path through a given set of n points is often called the "travelling salesman problem". A salesman, starting at and finally returning to his base, visits (n-1) other towns by the shortest possible route. If it is large, it may be prohibitively difficult to calculate the total mileages for each of the (n-1)! orders in which the towns may be visited, and to choose the smallest total.
As a practical substitute for an exact formula to determine the length of the shortest path, the Beardwood-Halton-Hammersley Theorem derived a simple asymptotic formula for the shortest length when n is large. The travelling salesman problem can involve either fixed or random points distributed over a certain region. The Theorem established that the shortest length between random points is asymptotically equal to a non-random function of n. For large n the distinction between the random and the non-random versions of the problem effectively vanishes. David L. Applegate described this in 2011 as a "famous result", and said "The remarkable theorem of Beardwood-Halton-Hammersley has received considerable attention in the research community, "with demonstrated uses in probability theory, physics, operations research and computer science.[5]
After leaving the UKAEA in 1968, Beardwood worked in transport modeling for the UK government's Road Research Laboratory. In 1973, she joined the staff of the Greater London Council (GLC) where she directed the transport studies group until the GLC was dissolved in 1987. Her team helped to plan the M25 orbital motorway around London and early congestion pricing systems.
One of Beardwood's most cited studies for the GLC, "Roads Generate Traffic", found that highway construction encourages people to drive and leads to increased congestion.[6] [7] "All that increases in road capacity do is allow people to abandon public transport in favour of the car".[8] Beardwood's research accurately predicted that the M25 would quickly exceed its maximum capacity. It has been cited in support of policies encouraging the use of bicycles and other alternatives to cars.[9] Similarly, her later work included a study which predicted that the proposed East London River Crossing would quickly become congested if there were no significant routes available to provide relief.
After the GLC's dissolution, Beardwood was employed in (and was a retained consultant to) the private sector, including for the transport planning consultancy MVA, Marcial Echenique and Partners Ltd and WSP Group. She also worked in academic posts, as a senior research fellow at the London School of Economics and as a lecturer in transport planning at the Polytechnic of Central London (1989–90).