> T-ITS-05-11-0137.R2 < 1 Abstract— Route planning in uncertain and dynamic networks has recently emerged as an active and intense area of research, both due to industry needs and technological advances. This paper investigates methods to predict travel times along the arcs and estimate arrival times at the nodes of a stochastic and dynamic network in real time. It is shown that, under fairly mild conditions, the developed travel and arrival time estimators are unbiased and that the error variance of the arrival time estimator is bounded. Simulation results are used to demonstrate the efficiency of the proposed algorithm. Index Terms— Travel time estimator, Arrival time estimator, Dynamic stochastic network, Route planning, Kalman filter. I. INTRODUCTION n many traffic networks, especially in major cities, traffic congestion has already reduced mobility and system reliability. In addition to contributing to drivers’ inefficiency, traffic congestion is a major source of air pollution, wasted energy, and increased maintenance cost caused by the volume of vehicles on the roadways. Furthermore, the delay caused by congestion significantly increases the cost of freight movements in the transportation industry and reduce the possibility of just-in-time delivery set by customers (shippers, manufacturers, retailers, etc.). Nowadays, customers are more willing to do business with reliable companies committed to meet their needs. In the transportation industry, it is widely expected that the deployment of advanced technologies such as the use of information technologies can reduce the level of uncertainties, including delays, to a manageable level. These technologies Manuscript received November, 2005. This work was supported by the National Center for Metropolitan Transportation Research (METRANS) located at the University of Southern California and the California State University at Long Beach. H. Jula is with the School of Science, Engineering and Technology, Pennsylvania State University - Harrisburg, Middletown, PA 17057-4898 USA (corresponding author, phone: 717-948-6382; fax: 717-948-6352; e-mail: [email protected]). M. Dessouky, is with the Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA 90089-0193 USA (e-mail: [email protected]). P.A. Ioannou is with the Electrical Engineering Department, University of Southern California, Los Angeles, CA 90089-2562 USA (e-mail: [email protected]). include: vehicle tracking (such as GPS), wireless communication, navigable map databases, and real-time information services. Whereas in the past, once the drivers left their origins, it was difficult for them to adjust their routes according to traffic congestion, these technologies make accurate real-time routing a possible reality. The focus of this paper is to improve the routing in uncertain and dynamic environments by developing techniques that can be easily implemented in real-time using new but currently available computer and information technologies. Recently, route planning in uncertain and dynamic networks has emerged as an active and intense area of research, both due to industry needs and technological advances [1]-[4]. In particular, Kim et al. studied optimal vehicle routing in a non-stationary stochastic network [5]. They developed decision making procedures based on a Markov decision process model for determining the optimal driver attendance time, departure times, and routing policies. The methodology was used to develop routing strategies for the stochastic shortest path problem. The authors concluded that real-time traffic information combined with historical data can significantly reduce the expected total costs and vehicle usage. Ichoua et al. investigated the time-dependent vehicle routing problem (TDVRP) with soft time-windows [6]. They presented a time-dependent speed model to calculate the travel times between two nodes. Tabu Search was used to find good routes for the TDVRP problem. Jula et al. considered truck route planning for non-stationary stochastic networks with time-windows at customer locations [7]. They developed a methodology to estimate the truck arrival times, and proposed an approximate solution method to find the least-cost route while meeting the required time-windows at the customer locations. This paper investigates methods to estimate travel times along the arcs and arrival times at the nodes of a dynamic and stochastic network, a step prior to dynamic route planning. Despite its importance and practical application for real-time routing, especially in major cities with traffic congestion, research efforts on developing arrival time estimators have been very limited [8],[9]. On the other hand, real-time travel time estimators have just received attention. In [10] and [11], Real-Time Estimation of Travel Times along the Arcs and Arrival Times at the Nodes of Dynamic Stochastic Networks Hossein Jula, Member, Maged Dessouky, and Petros A. Ioannou, Fellow, IEEE I> T-ITS-05-11-0137.R2 < 2the authors proposed a linear regression method to predict travel times on freeways. Performing numerous experiments on California freeway segments, they observed that there exists a linear relation between the future and instantaneous travel times. More precisely, they have shown that the future travel time on a segment of a highway can be described by a linear model using the instantaneous and historical travel times on that segment. A linear dynamical model was also developed in [12] and [13] to predict travel times on a segment of a highway. The historical data is used to determine a transition function from the current instant of time to the immediate future. The work, however, does not elaborate on how this function can be obtained. Other researches have used Artificial Neural Networks (ANN) [14], [15], and statistical methods [14],[16] extensively to predict travel times on freeway segments. In this paper, given a route in a dynamic stochastic transportation network, we develop a methodology to estimate arrival times at the nodes of that route. To estimate the arrival times, we first develop a technique to predict the travel times on the arcs of the network by combining historical data with real-time measurements of travel times along the arcs. The technique is developed based on a predictor-corrector form of the Kalman filter in which available historical data are used for predicting the travel