liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Heuristic for the Bilevel Origin–Destination Matrix Estimation Problem
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
2008 (English)In: Transportation Research Part B: Methodological, ISSN 0191-2615, Vol. 42, no 4, 339-354 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
Origin-Destination matrix; Sensitivity analysis; User-equilibrium
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-11461DOI: 10.1016/j.trb.2007.09.005OAI: oai:DiVA.org:liu-11461DiVA: diva2:17898
Note
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/Available from: 2008-04-03 Created: 2008-04-03 Last updated: 2013-12-10
In thesis
1. The Origin-Destination Matrix Estimation Problem: Analysis and Computations
Open this publication in new window or tab >>The Origin-Destination Matrix Estimation Problem: Analysis and Computations
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

For most kind of analyses in the field of traffic planning, there is a need for origin--destination (OD) matrices, which specify the travel demands between the origin and destination nodes in the network. This thesis concerns the OD-matrix estimation problem, that is, the calculation of OD-matrices using observed link flows. Both time-independent and time-dependent models are considered, and we also study the placement of link flow detectors.

Many methods have been suggested for OD-matrix estimation in time-independent models, which describe an average traffic situation. We assume a user equilibrium to hold for the link flows in the network and recognize a bilevel structure of the estimation problem. A descent heuristic is proposed, in which special attention is given to the issue of calculating the change of a link flow with respect to a change of the travel demand in a certain pair of origin and destination nodes.

When a time-dimension is considered, the estimation problem becomes more complex. Besides the problem of distributing the travel demand onto routes, the flow propagation in time and space must also be handled. The time-dependent OD-matrix estimation problem is the subject for two studies. The first is a case study, where the conventional estimation technique is improved through introducing pre-adjustment schemes, which exploit the structure of the information contained in the OD-matrix and the link flow observations. In the second study, an algorithm for time-independent estimation is extended to the time-dependent case and tested for a network from Stockholm, Sweden.

Finally, we study the underlying problem of finding those links where traffic flow observations are to be performed, in order to ensure the best possible quality of the estimated OD-matrix. There are different ways of quantifying a common goal to cover as much traffic as possible, and we create an experimental framework in which they can be evaluated. Presupposing that consistent flow observations from all the links in the network yields the best estimate of the OD-matrix, the lack of observations from some links results in a relaxation of the estimation problem, and a poorer estimate. We formulate the problem to place link flow detectors as to achieve the least relaxation with a limited number of detectors.

Place, publisher, year, edition, pages
Institutionen för teknik och naturvetenskap, 2007. 40 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1102
Keyword
Traffic modelling, Travel demand, Origin--Destination matrix, Traffic flow observation, Detector allocation, Estimation., OD-matris, Trafikflödesobservation, Detektorallokering, Skattning, Trafikmodellering, Reseefterfrågan
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-8859 (URN)978-91-85831-95-1 (ISBN)
Public defence
2007-06-15, K2, Kåkenhus, Linköpings universitet, Campus Norrköping, Norrköping, 13:15 (English)
Opponent
Supervisors
Available from: 2007-06-04 Created: 2007-06-04 Last updated: 2013-08-30
2. Origin-destination matrix estimation from traffic counts
Open this publication in new window or tab >>Origin-destination matrix estimation from traffic counts
2003 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

For most kind of analyses in the field of traffic modeling, there is a need for origin-destination (OD) matrices, which specify the travel demands between the origin and destination nodes in the network. The process of obtaining OD-matrices is long, complicated and expensive. The counting of traffic, which provides link flow observations, therefore is an opportune possibility for easily up-dating the information on the travel demand. This thesis concerns the estimation of OD-matrices from traffic counts. 

We will consider the problem to estimate OD-matrices for both time-indepenent and time-dependent models. Many models have been suggested for the time-independent case, where the quantities represent and average situation. If a user equilibrium is assumed for the link flows in the network, a bilevel problem structure is recognized, where the link flows are implicitly expressed as a traffic assignment of the present OD-matrix. A descent heuristic, which is an adaptation of the well-known projected gradient method, is proposed. Special attention is given to the problem of approximating the Jacobian matrix, which expresses the change of a certain link flow with respect to a unit change of the travel demand in a certain pair of origin and destination.

When a time dimension is introduced, the estimation problem becomes more complex. Besides the problem of distributing the travel demand onto different routes, the flow propagation with respect to time must be handled. A general time-dependent extension of the estimation problem is given and the complications with dynamic traffic assignment are discussed. In a case study, the conventional solution technique is improved by introducing pre-adjustment schemes, which the structure of the information provided by the OD-matrix and the link flow observations.

Place, publisher, year, edition, pages
Linköpings Universitet: Linköpings universitet, 2003. 4 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1057
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-38828 (URN)45788 (Local ID)91-7373-785-2 (ISBN)45788 (Archive number)45788 (OAI)
Presentation
2003-11-28, Sal TP45, Hus Täppan, Linköpings Universitet, Campus Norrköping, Linköping, 10:15 (Swedish)
Opponent
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-12-10

Open Access in DiVA

fulltext(194 kB)522 downloads
File information
File name FULLTEXT01.pdfFile size 194 kBChecksum SHA-1
ee69448d4936e5369e5eaf93514ee6e7a553684e5ad354122c38fc67047d0876d92291f2
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Lundgren, JanPeterson, Anders

Search in DiVA

By author/editor
Lundgren, JanPeterson, Anders
By organisation
Department of Science and TechnologyThe Institute of Technology
In the same journal
Transportation Research Part B: Methodological
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 522 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 254 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf