Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
c-SPSA: Cluster-wise simultaneous perturbation stochastic approximation algorithm and its application to dynamic origin-destination matrix estimation
KTH, School of Architecture and the Built Environment (ABE), Transport Science, Transport planning, economics and engineering.
KTH, School of Architecture and the Built Environment (ABE), Transport Science, Transport planning, economics and engineering. Department of Civil and Environmental Engineering, Northeastern University, Boston, MA, United States .
KTH, School of Architecture and the Built Environment (ABE), Transport Science, Transport planning, economics and engineering.ORCID iD: 0000-0002-4106-3126
2015 (English)In: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 55, 231-245 p.Article in journal (Refereed) Published
Abstract [en]

The simultaneous perturbation stochastic approximation (SPSA) algorithm has been used in the literature for the solution of the dynamic origin-destination (OD) estimation problem. Its main advantage is that it allows quite general formulations of the problem that can include a wide range of sensor measurements. While SPSA is relatively simple to implement, its performance depends on a set of parameters that need to be properly determined. As a result, especially in cases where the gradient of the objective function changes quickly, SPSA may not be as stable and even diverge. A modification of the SPSA algorithm, referred to as c-SPSA, is proposed which applies the simultaneous perturbation approximation of the gradient within a small number of carefully constructed "homogeneous" clusters one at a time, as opposed to all elements at once. The paper establishes the theoretical properties of the new algorithm with an upper bound for the bias of the gradient estimate and shows that it is lower than the corresponding SPSA bias. It also proposes a systematic approach, based on the k-means algorithm, to identify appropriate clusters. The performance of c-SPSA, with alternative implementation strategies, is evaluated in the context of estimating OD flows in an actual urban network. The results demonstrate the efficiency of the proposed c-SPSA algorithm in finding better OD estimates and achieve faster convergence and more robust performance compared to SPSA with fewer overall number of function evaluations.

Place, publisher, year, edition, pages
2015. Vol. 55, 231-245 p.
Keyword [en]
SPSA, Origin-destination (OD) matrix estimation, Stochastic approximation, k-means clustering, Gradient estimation bias
National Category
Transport Systems and Logistics
Identifiers
URN: urn:nbn:se:kth:diva-171910DOI: 10.1016/j.trc.2015.01.016ISI: 000358092100017Scopus ID: 2-s2.0-84936985083OAI: oai:DiVA.org:kth-171910DiVA: diva2:845398
Note

QC 20150811

Available from: 2015-08-11 Created: 2015-08-10 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Jenelius, Erik

Search in DiVA

By author/editor
Tympakianaki, AthinaKoutsopoulos, Hans N.Jenelius, Erik
By organisation
Transport planning, economics and engineering
In the same journal
Transportation Research Part C: Emerging Technologies
Transport Systems and Logistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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