Jump to content

Jillian Beardwood

Edit links
From Wikipedia, the free encyclopedia

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.

Early life

[edit]

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]

Mathematics career

[edit]

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.[4]

The Beardwood-Halton-Hammersley Theorem

[edit]

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]

Later career

[edit]

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.[1]

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).[1]

Publications

[edit]
  • Beardwood, J.; Halton, J.H.; Hammersley, J.M. (1959), "The Shortest Path Through Many Points", Proceedings of the Cambridge Philosophical Society[3]
  • Beardwood, J, "The Space-averaging of Deterrent Functions for Use in Gravity Model Distribution Calculations," Transport and Road Research Laboratory Report, Vol. 462, 1972[10]
  • 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.[11]
  • J.E. Beardwood, "The evaluation of benefits in constrained and congested situations," Traffic Engineering & Control, Vol. 31, No. 4, April 1990.[12]
  • 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[13]
  • 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[6]
  • 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.[14]

References

[edit]
  1. ^ a b c Baker, Anne Pimlott (2023). "Beardwood, Jillian Elizabeth (1934–2019), mathematician and transport planner". Oxford Dictionary of National Biography. doi:10.1093/odnb/9780198614128.013.90000380990. ISBN 978-0-19-861412-8. Retrieved 30 June 2023.
  2. ^ "The Beardwood–Halton–Hammersley Theorem" (PDF).
  3. ^ a b Beardwood, Jillian; Halton, J. H.; Hammersley, J. M. (21 October 1959). "The shortest path through many points". Mathematical Proceedings of the Cambridge Philosophical Society. 55 (4): 299–327. doi:10.1017/S0305004100034095. S2CID 122062088 – via Cambridge Core.
  4. ^ a b Beardwood, Julia (6 February 2020). "Jillian Beardwood obituary" – via www.theguardian.com.
  5. ^ Applegate, D. Traveling Salesman Problem. p. 23. Princeton, 2007
  6. ^ a b Beardwood and Elliott, J. and J. (25 October 1985). Roads Generate Traffic. University of Sussex, 1990. p. 43. ISBN 9780860501527.
  7. ^ Trunk Roads and the Generation of Traffic The Standing Advisory Committee on Trunk Road Assessment, p. 90
  8. ^ Mogridge, Martin J.H. (1990). Travel in Towns. Macmillan Press. p. 277. ISBN 9781349117987.
  9. ^ “The Bicycle: Vehicle for a Small Planet”, Marcia D. Lowe, 1989 p. 18]
  10. ^ "the space-averaging of deterrent functions for use in gravity model distribution calculations". TRL. 13 June 2008.
  11. ^ National Transport Models: Recent Developments and Prospects edited by Lars Lundqvist, Lars-Göran Mattsson
  12. ^ Transportation Research Board
  13. ^ Beardwood, Jillian E. (1 May 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.
  14. ^ Beardwood, Jillian E.; Kirby, Howard R. (1 December 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Jillian_Beardwood&oldid=1234627242"