Methods for the Solution of the Combined Trip Matrix Estimation and Stochastic User Equilibrium Assignment Problem



Methods for the Solution of the Combined Trip Matrix Estimation and Stochastic User Equilibrium Assignment Problem

Authors

ZHANG X, MAHER M J, Napier University and VAN VLIET D, University of Leeds, UK

Description

The trip matrix is a table containing traffic demands from each origin to each destination in a road network. It is an essential source of information in every aspect of the transport planning process. It can be estimated from traffic counts on road links

Abstract

The trip matrix is a table containing traffic demands from each origin to each destination in a road network. It is an essential source of information in every aspect of the transport planning process. It can be estimated from traffic counts on road links by a matrix estimation method. The input to a matrix estimation problem consists of a target trip matrix, the observed link flows, and link choice proportions (the proportions of each origin-destination pair passing along each link) in the road network. Normally, the estimated matrix is such that it is as close as possible to the target matrix whilst the resultant links flows are as close as possible to the observed link flows.

On the other hand, given a trip matrix, a set of link choice proportions can be determined by a traffic assignment model. An equilibrium assignment model needs to be included in the matrix estimation so as to achieve consistency in route choices and to model congestion effects in the network. This can either be a user equilibrium WE) assignment model or a stochastic user equilibrium (SUE) assignment model. A SUE assignment model is preferable because it accounts for both congestion effects and drivers' differences in route choice. In the combined matrix estimation and equilibrium assignment problem, there are two linked optimisation problems: the matrix estimation (ME) problem with fixed link choice proportions and the equilibrium assignment (EA) problem with a fixed trip matrix. In this problem, we may seek a solution pair, trip matrix and link choice proportions, which are mutually consistent. Alternatively, we may seek a bi-level solution with the ME objective function being optimised with respect to the matrix and the link flows constrained by UE or SUE conditions.

Several solution methods for the combined ME and UE problem have been proposed in the literature (Hall et at., 1980; Fisk, 1988; Yang et al., 1992; Heydecker et al., 1994; and Yang, 1995). With the exception of Yang (1995), all these algorithms are similar in that they involve solving the two sub-problems alternately until a mutually consistent solution is approached. However, convergence is not guaranteed (Fisk, 1984; Maher and Zhang, 1999). Yang (1995) proposed two algorithms, which also involve alternate optimisation of the two sub-problems. The first algorithm is essentially an alternate algorithm mentioned above. The second algorithm is different in that for each solution of the matrix estimation problem, the UE assignment is approximated by a linear relationship between link flows and the trip matrix. The approximation needs complicated sensitivity analysis methods for non-linear programming problems or variational inequalities (Tobin and Friesz, 1988). Maher and Zhang (1999) have shown that, in an example of a two-link network, the first algorithm converges to the mutually consistent solution and the second to the bi-level solution. More recently, the authors have developed two efficient algorithms for the solution of combined ME and UE assignment problem (Zhang and Maher, 1998; Maher and Zhang, 1999): one algorithm for the mutually consistent solution and the other for the bi-level solution. In an example in which the true solutions can be found by a direct search, the authors showed that the algorithms converge to the correct solutions.

In this paper, we apply the two solution methods to the combined ME and SUE problem, using the logit-SUE assignment method developed by Maher (1998). In addition, we propose another algorithm for the mutually consistent solution for the combined problem. The algorithms will be applied to two practical networks. The formulation of the problem is given in the next section, which is followed by the description and test of the algorithms in the subsequent two sections. The description of the algorithms will be brief; more details can be found in Zhang and Maher (1998) and Maher and Zhang (1999). Conclusions are drawn in the last section.

Publisher

Association for European Transport