Kernel Regression for Travel Time Estimation via Convex Optimization

Abstract: 

We develop an algorithm aimed at estimating travel time on segments of a road network using a convex optimization framework. Sampled travel time from probe vehicles are assumed to be known and serve as a training set for a machine learning algorithm to provide an optimal estimate of the travel time for all vehicles. A kernel method is introduced to allow for a non-linear relation between the known entry times and the travel times that we want to estimate. To improve the quality of the estimate we minimize the estimation error over a convex combination of known kernels. This problem is shown to be a semi-definite program. A rank-one decomposition is used to convert it to a linear program which can be solved efficiently.

Author: 
Blandin, Sébastien
El Ghaoui, Laurent
Bayen, Alexandre
Publication date: 
December 1, 2009
Publication type: 
Conference Paper
Citation: 
Blandin, S., El Ghaoui, L., & Bayen, A. (2009). Kernel Regression for Travel Time Estimation via Convex Optimization. Proceedings of the 48h IEEE Conference on Decision and Control (CDC) Held Jointly with 2009 28th Chinese Control Conference, 4360–4365. https://doi.org/10.1109/CDC.2009.5400534