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
The Origin-Destination Matrix Estimation Problem: Analysis and Computations
Linköping University, Department of Science and Technology. Linköping University, The Institute of Technology.
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 [en]
Traffic modelling, Travel demand, Origin--Destination matrix, Traffic flow observation, Detector allocation, Estimation.
Keyword [sv]
OD-matris, Trafikflödesobservation, Detektorallokering, Skattning, Trafikmodellering, Reseefterfrågan
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-8859ISBN: 978-91-85831-95-1 (print)OAI: oai:DiVA.org:liu-8859DiVA: diva2:23558
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
List of papers
1. A Heuristic for the Bilevel Origin–Destination Matrix Estimation Problem
Open this publication in new window or tab >>A Heuristic for the Bilevel Origin–Destination Matrix Estimation Problem
2008 (English)In: Transportation Research Part B: Methodological, ISSN 0191-2615, E-ISSN 1879-2367, 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
Keyword
Origin-Destination matrix; Sensitivity analysis; User-equilibrium
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-11461 (URN)10.1016/j.trb.2007.09.005 (DOI)
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: 2017-12-13
2. Methods for Pre-Adjusting Time-Dependent Origin–Destination Matrices: an Application to Gothenburg
Open this publication in new window or tab >>Methods for Pre-Adjusting Time-Dependent Origin–Destination Matrices: an Application to Gothenburg
2003 (English)In: Proceedings of the 10th World Congress and Exhibition on Intelligent Transport Systems and Services, Madrid, Spain, November 16–20, 2003, no 2436Conference paper, Published paper (Refereed)
Abstract [en]

We present a number of schemes for adjusting time-dependent travel demand information with respect to link flow observations. The aim is to utilize the structure of the given OD-matrix, which is compounded from different sources, for making simple overall adjustments. These pre-adjustments are then followed up with a complete OD-estimation procedure, such as that in Contram. Numerical results from the city of Gothenburg are presented.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14467 (URN)
Conference
10th World Congress and Exhibition on Intelligent Transport Systems and Services, Madrid, Spain, November 16–20
Available from: 2007-06-04 Created: 2007-06-04 Last updated: 2013-12-10
3. A Heuristic for the Estimation of Time-Dependent Origin Origin–Destination Matrices from Traffic Counts
Open this publication in new window or tab >>A Heuristic for the Estimation of Time-Dependent Origin Origin–Destination Matrices from Traffic Counts
2007 (English)In: Nordic MPS ’04, Norrköping, Sweden, October 21–23, 2004 and The 10th Jubilee Meeting of the EURO Working Group on Transportation, Poznan, Poland, September 13–16, 2005 and Transportforum, Linköping, Sweden, January 11–12, 2006, 2007Conference paper, Published paper (Refereed)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-14468 (URN)
Conference
The 10th Jubilee Meeting of the EURO Working Group on Transportation, Poznan, Poland, September 13–16, 2005
Available from: 2007-06-04 Created: 2007-06-04 Last updated: 2015-01-14
4. Allocation of Link Flow Detectors for Origin-Destination Matrix Estimation-A Comparative Study
Open this publication in new window or tab >>Allocation of Link Flow Detectors for Origin-Destination Matrix Estimation-A Comparative Study
2010 (English)In: COMPUTER-AIDED CIVIL AND INFRASTRUCTURE ENGINEERING, ISSN 1093-9687, Vol. 25, no 2, 116-131 p.Article in journal (Refereed) Published
Abstract [en]

Origin-destination (OD) matrices are essential for various analyses in the field of traffic planning, and they are often estimated from link flow observations. We compare methods for allocating link flow detectors to a traffic network with respect to the quality of the estimated OD-matrix. First, an overview of allocation methods proposed in the literature is presented. Second, we construct a controlled experimental environment where any allocation method can be evaluated, and compared to others, in terms of the quality of the estimated OD-matrix. Third, this environment is used to evaluate and compare three fundamental allocation methods. Studies are made on the Sioux Falls network and on a network modeling the city of Linkoping. Our conclusion is, that the most commonly studied approach for detector allocation, maximizing the coverage of OD-pairs, seems to be unfavorable for the quality of the estimated OD-matrix.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-53695 (URN)10.1111/j.1467-8667.2009.00625.x (DOI)
Available from: 2010-02-01 Created: 2010-02-01 Last updated: 2014-08-14
5. A Novel Model for Placement of Detectors for Origin–Destination Matrix Estimation
Open this publication in new window or tab >>A Novel Model for Placement of Detectors for Origin–Destination Matrix Estimation
Manuscript (Other academic)
Identifiers
urn:nbn:se:liu:diva-14470 (URN)
Available from: 2007-06-04 Created: 2007-06-04 Last updated: 2010-01-13

Open Access in DiVA

fulltext(538 kB)6560 downloads
File information
File name FULLTEXT01.pdfFile size 538 kBChecksum MD5
e90a3af23d3beca7de485303d0297451c790819d05537375345299ed43ccdd65031754d1
Type fulltextMimetype application/pdf

Authority records BETA

Peterson, Anders

Search in DiVA

By author/editor
Peterson, Anders
By organisation
Department of Science and TechnologyThe Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 6560 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 3252 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