A Heuristic for the Bilevel Origin–Destination Matrix Estimation Problem
2008 (English)In: Transportation Research Part B: Methodological, ISSN 0191-2615, Vol. 42, no 4, 339-354 p.Article in journal (Refereed) Published
In this paper we consider the estimation of an origin–destination (OD) matrix, given a target OD-matrix and traffic counts on a subset of the links in the network. We use a general nonlinear bilevel minimization formulation of the problem, where the lower level problem is to assign a given OD-matrix onto the network according to the user equilibrium principle. After reformulating the problem to a single level problem, the objective function includes implicitly given link flow variables, corresponding to the given OD-matrix. We propose a descent heuristic to solve the problem, which is an adaptation of the wellknown projected gradient method. In order to compute a search direction we have to approximate the Jacobian matrix representing the derivatives of the link flows with respect to a change in the OD-flows, and we propose to do this by solving a set of quadratic programs with linear constraints only. If the objective function is differentiable at the current point, the Jacobian is exact and we obtain a gradient. Numerical experiments are presented which indicate that the solution approach can be applied in practice to medium to large size networks.
Place, publisher, year, edition, pages
Institutionen för teknik och naturvetenskap , 2008. Vol. 42, no 4, 339-354 p.
Origin-Destination matrix; Sensitivity analysis; User-equilibrium
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-11461DOI: 10.1016/j.trb.2007.09.005OAI: oai:DiVA.org:liu-11461DiVA: diva2:17898
Original publication: Jan T Lundgren and Anders Peterson, A Heuristic for the Bilevel Origin–Destination Matrix Estimation Problem, 2008, Transportation Research Part B: Methodological, (42), 4, 339-354. http://dx.doi.org/10.1016/j.trb.2007.09.005. Copyright: Elsevier B.V., http://www.elsevier.com/2008-04-032008-04-032013-12-10