Project: Advancing Methods For Evaluating Network Reliability C8
Reference: STP 14/5/20
Last update: 31/12/2009 15:21:24
The objectives of this research are to develop methods to evaluate the vulnerability of a transport network and to develop a dynamic supply model to aid the analysis of travel time variability.
The project aims to develop an advanced analysis framework for the vulnerability of a transport network by introducing the dependent probabilities of link failures; defining an innovative framework for analysing cases when normal activities are not maintained through the K-terminal reliability and maximum-flow concepts and to develop a practical algorithm based on standard traffic assignment models to analyse these issues. All the methods developed will be tested to validate the analysis and demonstrate the practicality of the algorithms.
Univ of Leeds, Leeds, LS2 9JT
Cost to the Department: £49,912.00
Actual start date: 01 January 2003
Actual completion date: 04 May 2004
ADVANCING METHODS FOR EVALUATING NETWORK RELIABILITY
Author: David Watling, Agachai Sumalee, Richard Connors, Chandra Balijepalli
Publication date: 30/04/2004
Summary of results
- Reliability, and its impact on traffic network modelling and appraisal, has become a topic of increasing interest to the Department since the mid-1990s. Various completed and on-going studies have had the objective to explore: the impacts of both 'normal' day-to-day variation, as well as incident-induced impacts; the effects on private and public transport network assignment; the methodology by which the behavioural response of travellers may be accommodated; the empirical evidence for journey time variability, and the deduction of explanatory models of such variation; and the techniques available for accommodating these impacts in the appraisal process and benefit calculations. In the present report, the findings of a study funded under the Department's "New Horizons" programme are reported, in which the objective has been to advance the modelling methodology for transport network reliability assessment still further. This research, as proposed, pursued two independent strands of enquiry.
The first strand was concerned with the development of a generally applicable framework for assessing network reliability, especially in the light of unexpected capacity reductions to the links of the network (due, for example, to accidents, breakdowns, unplanned maintenance, snow, rain or flooding). A theoretically justifiable measure of system reliability that might be used as part of a multi-objective appraisal - analogous to that adopted in other disciplines concerned with reliability of networks - has been proposed, based on the probability of trip travel times exceeding some threshold tolerance. This measure is sensitive to the behavioural adaptation of travellers and the network density (availability of alternative routes), and effectively takes account of the probability of all the enormous number of combinations of network link states that may prevail in an unreliable situation. Secondly, a conceptual modelling framework was proposed, which is able to incorporate alternative behavioural assumptions (response to unreliability) and alternative network assignment approaches. For illustrative purposes, we chose to show how it may be implemented with a new kind of 'partial' equilibrium, in which the driver population is a mix of informed and uninformed drivers regarding the degraded capacities, but this assumption is not critical as the approach is quite general.
For the generic modelling framework proposed above in this first strand of research, two algorithms - which in principle could be linked to any existing network assignment software - were tested for dealing with (a) the potentially enormous computational demands of the approach, and (b) the complexity of dealing with potentially correlated link capacity degradations, where for example snow may simultaneously affect a number of parts of the network (and which is typically neglected in the simplified studies of reliability found in the transport research literature). The first algorithm tested was based on an adaptation of a method reported for studying electrical network failures, in which an ordering of the network states is performed according to their probability of occurrence, in order to reduce the computational demands. We successfully implemented this approach in combination with the SATURN software, and verified the logic and rationale of the approach on a small-scale network. However, we found the computational demands in ordering the network states to be so high to make this algorithm infeasible for the scale of network typically considered in transport. Therefore, a new purpose-built algorithm was developed and tested. This algorithm is based on a combination of theoretical constructs. In simple terms, the idea is to first reduce the state space (number of network states) by a 'partition algorithm', so we may relatively quickly identify those states that clearly lead to 'reliable' or 'unreliable' performance (according to the theoretical definition of system reliability mentioned above). This algorithm specifically exploits a 'monotone' property of our system reliability measure and transport networks, which effectively says that if a given degraded set of capacity states leads to unreliable performance, then if we degrade any single one of the link states by any more, then certainly that will be unreliable too. While that may sound obvious, it is a very important mathematical property exploited by the partition algorithm. In the second stage of this approach, Monte Carlo simulation is used to estimate the reliability measure from the reduced space, though we adopt a specialised form of stratified Monte Carlo simulation to further enhance the efficiency of the approach. In tests with the SATURN model in a network of some 89 links and 182 inter-zonal movements, the method was shown to be computationally efficient and produce robust results. Time limitations did not allow us to perform tests in larger scale networks or in combination with alternative network assignment models, yet our experience suggests both should be computationally feasible within the general solution approach we have adopted.
The second strand of research is much more closely related to on-going Department research in the network reliability area. In particular, the aim was to investigate the way in which day-to-day travel time variability might be represented in a traffic assignment model in the context of dynamic traffic phenomena, particularly in the case of transient over-saturation. Specifically, we focused on first reviewing alternative modelling approaches for a single link that reflect such dynamic phenomena (though not the day-to-day variability), and selected one such approach for further development. This approach was one recently proposed in the research literature, which had been shown to possess attractive theoretical results and reproduce sensible dynamic phenomena. The approach adopted a form of generalised travel time-flow function, in which the travel time at any given departure time is a function of the weighted average of the in-flow at the time a vehicle enters a link and the out-flow at the time at which it exits the link. Since the time the vehicle exits the link requires knowledge of the travel time, this is a kind of circular definition (consistency condition) rather than an explicit function. If one additionally incorporates the requirement for first-in-first-out behaviour of flows, then it may be shown that deriving the time-dependent travel times from such a model requires the solution to a first order ordinary differential equation, which can be solved numerically using some carefully-designed mix of backwards and forwards differencing. This approach was implemented in MATLAB, and a series of numerical results reported.
The particular contribution of the present work was to extend this dynamic link modelling approach to include additional terms to reflect the impact of day-to-day variability in the dynamic in-flow profile on the dynamic profile of expected travel times (i.e. 'expected' in the sense of average over days, but with the time-dependence within a day still retained in a profile). This was achieved by the use of an approximation method, recently proposed by one of the researchers for the within-day static case, and now extended to the time-dependent case. This extension is, in general, non-trivial, especially as it requires second derivatives of the dynamic travel time functions with respect to the dynamic flow profiles, namely differentiating a relationship that may only be available in implicit form. Several theoretical and numerical strategies were proposed for computing these derivatives, and these were tested in a series of numerical experiments. The approximation method was shown to provide a good reflection of the impact of variability in a wide range of circumstances, although there were a number of cases in which its performance was poorer. This poorer performance appeared not to be so directly related to the approximation itself, as to the nature of the dynamic traffic flow model being adopted, and our conclusion was that further research of appropriate dynamic traffic flow relationships was needed (even without the impact of day-to-day variability), both from an empirical and theoretical perspective.
In conclusion, we believe that the first strand of research on a network reliability framework and solution algorithm is sufficiently far developed to warrant careful consideration as a tool for practical appraisal of reliability, both in the urban and inter-urban cases, notwithstanding the need to have some fuller scale testing of the method with larger networks and alternative network assignment packages, and the need to consider more fully the way in which a multi-objective appraisal method may be implemented incorporating such a measure of system reliability. The second strand of research has led to techniques that, while somewhat further away from practical implementation, have made major progress, we believe, on incorporating both within-day and between-day variation into the kind of travel time relationships required for dynamic traffic assignment. Further research is clearly needed, on both the form of the link travel time relationships and the implementation of such relationships in a full network dynamic traffic assignment.