Jillian Beardwood (1934–2019) was a British mathematician known for the Beardwood-Halton-Hammersley Theorem. 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". 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 honors and a master’s degree in 1956.
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 Beardwood-Halton-Hammersley Theorem
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.
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. "All that increases in road capacity do is allow people to abandon public transport in favour of the car". 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.
- Beardwood, J.; Halton, J.H.; Hammersley, J.M. (1959), "The Shortest Path Through Many Points", Proceedings of the Cambridge Philosophical Society
- Beardwood, J, “The Space-averaging of Deterrent Functions for Use in Gravity Model Distribution Calculations,” Transport and Road Research Laboratory Report, Vol. 462, 1972
- Williams I.N. and Beardwood J.E. (1993). A residual disutility based approach to incremental transport models. Proceedings of Seminar D, Planning and Transport Research and Computation, Summer Annual Meeting, 1993. PTRC Education and Research Services Ltd, London, pp. 11–22.
- J.E. Beardwood, “The evaluation of benefits in constrained and congested situations,” Traffic Engineering & Control, Vol. 31, No. 4, April 1990.
- Jillian E. Beardwood, “Subsample and Jackknife: A general technique for estimation of sampling errors, with applications and examples in the field of transport planning,” Transportation Research Part A, Vol 24A, No 3, pp. 211–15, May 1990
- J. Beardwood and J. Elliott, “Roads Generate Traffic,” Planning and Transport Research and Computation (International) Co. Meeting, Summer Annual Meeting, University of Sussex, England, from 15 to 18 July, 1985
- J. Beardwood, H. Kirby, “Zone definition and the gravity model: The separability, excludability and compressibility properties,” Transportation Research, Vol. 9, No. 6 (1975), pp. 363–69.
- "The Beardwood–Halton–Hammersley Theorem" (PDF).
- Beardwood, Jillian; Halton, J. H.; Hammersley, J. M. (October 21, 1959). "The shortest path through many points". Mathematical Proceedings of the Cambridge Philosophical Society. 55 (4): 299–327. doi:10.1017/S0305004100034095 – via Cambridge Core.
- Beardwood, Julia (February 6, 2020). "Jillian Beardwood obituary" – via www.theguardian.com.
- Applegate, D. Traveling Salesman Problem. p. 23. Princeton, 2007
- Beardwood and Elliott, J. and J. Roads Generate Traffic. University of Sussex, 1990. p. 43.
- Trunk Roads and the Generation of Traffic The Standing Advisory Committee on Trunk Road Assessment, p. 90
- Mogridge, Martin J.H. (1990). Travel in Towns. Macmillan Press. p. 277.
- “The Bicycle: Vehicle for a Small Planet”, Marcia D. Lowe, 1989 p. 18]
- "the space-averaging of deterrent functions for use in gravity model distribution calculations". TRL. June 13, 2008.
- National Transport Models: Recent Developments and Prospects edited by Lars Lundqvist, Lars-Göran Mattsson
- Transportation Research Board
- Beardwood, Jillian E. (May 1, 1990). "Subsample and jackknife: A general technique for the estimation of sampling errors, with applications and examples in the field of transport planning". Transportation Research Part A: General. 24 (3): 211–215. doi:10.1016/0191-2607(90)90058-E – via ScienceDirect.
- Beardwood, Jillian E.; Kirby, Howard R. (December 1, 1975). "Zone definition and the gravity model: The separability, excludability and compressibility properties". Transportation Research. 9 (6): 363–369. doi:10.1016/0041-1647(75)90007-6 – via ScienceDirect.