Institute for Transport Studies (ITS)

Noisy optimisation in transport

Supervisor: Dr Ronghui Liu

Microscopic traffic simulation models1 have become extremely popular and widely-used in recent years. Such models are very detailed, as they track the movement and predict the driver behaviour for each individual vehicle in a road network on a second-by-second basis. They are Monte Carlo in nature and allow for a random mix of vehicle types, vehicle performance and driver behaviour. As a consequence they are capable of accurately describing real-world traffic behaviour; however, they are very computationally intensive, and produce outputs of system performance (such as total vehicle travel time or delay) that are "noisy": that is, subject to random error.

Determining the optimal traffic signal settings in an urban road network (that is, the timings that will minimise the total delay) is far from straightforward; there are typically a huge number of local minima so that any simple-minded search procedure will tend to become trapped in the nearest local minimum. When the traffic model that estimates the total delay for any given set of timings is so detailed and is also noisy, this combinatorial optimisation problem becomes even more challenging.

A number of heuristic approaches have been tried, including one known as the cross entropy method2. Work on this was carried out in a recent ITS research project, funded by the Leverhulme Trust, and was shown to provide an efficient, systematic iterative approach to the problem of finding the optimal timings3. Nevertheless the problem is computationally demanding. Other approaches are possible, including one known as a Trust Region method and there are early indications that this might prove to be even more efficient, and allow problems of practical size to be solved. If so, this would be a significant advance in the usefulness of microscopic traffic simulation models.

The proposed PhD research would investigate the formulation and application of the trust region approach, comparing its performance with that of other techniques such as the cross entropy method. The project would therefore build on the findings from the Leverhulme project, and would aim to develop a method that would enable the optimal signal timings to be found, using a microscopic traffic simulation model of road networks of practical size.

It should be noted that, although the problem has been posed here in terms of signal optimisation, there are many optimisation problems in transport that involve the use of Monte Carlo models. The methods to be developed in the project, therefore, will have wide application, beyond that of signal optimisation.

The project would suit someone with strong mathematical skills, and with a keen interest in the application of those skills through modelling and the development of software. For further information, contact Dr. Ronghui Liu (r.liu(at)its.leeds.ac.uk).

References

1. SIAS. Available at http://www.sias.com/ng/spoverview/spintroduction.htm

2. Rubinstein, R. Y. and Kroese, D.P. (2004) The Cross-Entropy Method: a Unified Approach to Combinatorial Optimization, Monte-Carlo Simulation, and Machine Learning. Springer.

3. Maher M.J., Liu R. and Ngoduy D. (2011). Signal optimisation using the cross entropy method.Transportation Research Series C: Emerging Technologies,http://dx.doi.org/10.1016/j.trc.2011.05.018.

4. Ngoduy D. And Maher M.J. (2012). Calibration of second order traffic models using continuous cross entropy method. Transportation Research Series C: Emerging Technologies, 24, 102-121.

Search site