Jillian Beardwood

Last updated • 4 min readFrom 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.

Contents

Early life

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

Mathematics career

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

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

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

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. The name comes from the Monte Carlo Casino in Monaco, where the primary developer of the method, physicist Stanislaw Ulam, was inspired by his uncle's gambling habits.

<span class="mw-page-title-main">Geodesic</span> Straight path on a curved surface or a Riemannian manifold

In geometry, a geodesic is a curve representing in some sense the shortest path (arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. It is a generalization of the notion of a "straight line".

<span class="mw-page-title-main">Percolation theory</span> Mathematical theory on behavior of connected clusters in a random graph

In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger connected, so-called spanning clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles Network theory and Percolation.

<span class="mw-page-title-main">John Hammersley</span> British mathematician

John Michael Hammersley, was a British mathematician best known for his foundational work in the theory of self-avoiding walks and percolation theory.

Route assignment, route choice, or traffic assignment concerns the selection of routes between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting model, following trip generation, trip distribution, and mode choice. The zonal interchange analysis of trip distribution provides origin-destination trip tables. Mode choice analysis tells which travelers will use which mode. To determine facility needs and costs and benefits, we need to know the number of travelers on each route and link of the network. We need to undertake traffic assignment. Suppose there is a network of highways and transit systems and a proposed addition. We first want to know the present pattern of traffic delay and then what would happen if the addition were made.

<span class="mw-page-title-main">Transport network analysis</span> Spatial analysis tools for geographic networks

A transport network, or transportation network, is a network or graph in geographic space, describing an infrastructure that permits and constrains movement or flow. Examples include but are not limited to road networks, railways, air routes, pipelines, aqueducts, and power lines. The digital representation of these networks, and the methods for their analysis, is a core part of spatial analysis, geographic information systems, public utilities, and transport engineering. Network analysis is an application of the theories and algorithms of graph theory and is a form of proximity analysis.

<span class="mw-page-title-main">Pathfinding</span> Plotting by a computer application

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

<span class="mw-page-title-main">Transportation forecasting</span>

Transportation forecasting is the attempt of estimating the number of vehicles or people that will use a specific transportation facility in the future. For instance, a forecast may estimate the number of vehicles on a planned road or bridge, the ridership on a railway line, the number of passengers visiting an airport, or the number of ships calling on a seaport. Traffic forecasting begins with the collection of data on current traffic. This traffic data is combined with other known data, such as population, employment, trip rates, travel costs, etc., to develop a traffic demand model for the current situation. Feeding it with predicted data for population, employment, etc. results in estimates of future traffic, typically estimated for each segment of the transportation infrastructure in question, e.g., for each roadway segment or railway station. The current technologies facilitate the access to dynamic data, big data, etc., providing the opportunity to develop new algorithms to improve greatly the predictability and accuracy of the current estimations.

Bootstrapping is any test or metric that uses random sampling with replacement, and falls under the broader class of resampling methods. Bootstrapping assigns measures of accuracy to sample estimates. This technique allows estimation of the sampling distribution of almost any statistic using random sampling methods.

<span class="mw-page-title-main">Journey planner</span> Specialized search engine for travelling

A journey planner, trip planner, or route planner is a specialized search engine used to find an optimal means of travelling between two or more given locations, sometimes using more than one transport mode. Searches may be optimized on different criteria, for example fastest, shortest, fewest changes, cheapest. They may be constrained, for example, to leave or arrive at a certain time, to avoid certain waypoints, etc. A single journey may use a sequence of several modes of transport, meaning the system may know about public transport services as well as transport networks for private transportation. Trip planning or journey planning is sometimes distinguished from route planning, which is typically thought of as using private modes of transportation such as cycling, driving, or walking, normally using a single mode at a time. Trip or journey planning, in contrast, would make use of at least one public transport mode which operates according to published schedules; given that public transport services only depart at specific times, an algorithm must therefore not only find a path to a destination, but seek to optimize it so as to minimize the waiting time incurred for each leg. In European Standards such as Transmodel, trip planning is used specifically to describe the planning of a route for a passenger, to avoid confusion with the completely separate process of planning the operational journeys to be made by public transport vehicles on which such trips are made.

Gordon Frank Newell was an American scientist, known for his contributions to applied mathematics, in particular traffic flow analysis and queueing theory. Newell authored over one hundred articles and wrote several books. The Gordon–Newell theorem is named after him and his colleague William J. Gordon. Their algorithms helped form the basis of most modern automatically controlled and networked traffic-light control systems.

Proximity analysis is a class of spatial analysis tools and algorithms that employ geographic distance as a central principle. Distance is fundamental to geographic inquiry and spatial analysis, due to principles such as the friction of distance, Tobler's first law of geography, and Spatial autocorrelation, which are incorporated into analytical tools. Proximity methods are thus used in a variety of applications, especially those that involve movement and interaction.

The k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths. A variation of the problem is the loopless k shortest paths.

First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time.

<span class="mw-page-title-main">Alice Guionnet</span> French mathematician

Alice Guionnet is a French mathematician known for her work in probability theory, in particular on large random matrices.

References

  1. 1 2 3 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. 1 2 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. 1 2 Beardwood, Julia (6 February 2020). "Jillian Beardwood obituary" – via www.theguardian.com.
  5. ↑ Applegate, D. Traveling Salesman Problem. p. 23. Princeton, 2007
  6. 1 2 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.