Open this publication in new window or tab >>2015 (English)In: Transportation Research Part C: Emerging Technologies, ISSN 0968-090X, E-ISSN 1879-2359, Vol. 55, p. 231-245Article 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.
Keywords
SPSA, Origin-destination (OD) matrix estimation, Stochastic approximation, k-means clustering, Gradient estimation bias
National Category
Transport Systems and Logistics
Identifiers
urn:nbn:se:kth:diva-171910 (URN)10.1016/j.trc.2015.01.016 (DOI)000358092100017 ()2-s2.0-84936985083 (Scopus ID)
Note
QC 20150811
2015-08-112015-08-102024-03-18Bibliographically approved