' 3.: 0
31 s
trivi-

 

 

A
.I\1 . ‘
.5 u.l.v->V

cubllrp..‘vll.
Air]

 

II
c‘.‘l|
\I. vullclvflq.
.> o’l‘. . vital} 0‘“
\v.ol.v|cl.'. .vvi.,‘¢.'u
[Ova’érlr‘oi
o il1v.1II>-‘

 

 

YII’IJI'P
I! ll‘ .l L. .11] laxvllvirlal I‘ll

L. .
ill-I 1-0.1 Q. 2

2‘331.‘. III b})vv.v

b. ‘7'! ti ‘ .‘I!$..7. u . :I-JEESS
‘I.l.._.¢Vo:....7. .i.".:.

‘ . ‘ r i. ll'ul.‘ I .
. ‘ . . c flatnacl' p

. 1 fit.»
. . .‘I'k'vxl, :1 dd .1 1: Jolt!

‘9‘

 

IHIIIIHIHHIIVIWIITIVEIRWWWIIllHHIllHlI L

3 1293 00899 0198

 

 

 

 

 

 

 

 

 

 

 

 

 

 

This is to certify that the
dissertation entitled
Travel Time Predictions Under Dynamic Route

Guidance With A Recursive Adaptive Algorithm

presented by

Chronis Stamatiadis

has been accepted towards fulfillment
of the requirements for

Doctor of Philosophy degreein Civil Engineering

 

 

/"-" b / '
[ZZZ/62m c. Nan/g)

 

Major professor \

 

MS U is an Affirmative Action/Equal Opportunity Institution 0-12771

 

r \
LIBRARY
Illehlgan State
University

L A

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.

u DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

 

 

 

 

 

 

 

 

 

 

fir—Wfi

MSU Is An Affirmative ActiorVEqual Opportunity Institution
cmmmut

 

TRAVEL TIME PREDICTIONS UNDER DYNAMIC ROUTE
GUIDANCE WITH A RECURSIVE ADAPTIVE ALGORITHM

By

Chronis Stamatiadis

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Civil and Environmental Engineering

1992

ABSTRACT

TRAVEL TIME PREDICTIONS UNDER DYNAMIC ROUTE
GUIDANCE WITH A RECURSIVE ADAPTIVE ALGORITHM

By
Chronis Stamatiadis

The key element of a dynamic route guidance system is the knowledge of the
travel times on the links in the network, for all time periods in a planning
horizon. In real time systems, where route guidance will be performed on-line,
the travel times required for the evaluation of alternative routes, have not yet
occurred. Therefore the ability to make predictions of such travel times with

reasonable accuracy is essential to the route evaluation process.

Many researchers have developed models to estimate future travel times with
the usage of traffic assignment models based on some equilibrium principal.
The efficiency of such models is based on the assumption that drivers will fol-
low the suggestions given by the guidance system, and that a large percentage
of traffic is equipped to receive such information from the system. These condi-
tions may be realistic if guidance systems have been proven efficient enough
to attract drivers to actually use them.

Thus, alternative models, that will still operate in real time, have to be
devised which will give us the capability of short term travel time predictions.
Such models will have to be based on historical data, and they must represent
the dynamics of travel times, including variations due to traffic incidents, with

sufficient accuracy to be used by the motorists. In this study we examined the

effectiveness of a route guidance system based on the travel time predictions
performed by such a model. Predictions are made through the application of a
recursive identification algorithm for all the links in the network. The predic-
tion model utilizes a recursive least squares (RLS) algorithm and its input
variables include both historical information of the travel time on the link
under consideration, and its average travel time in the current time period
based on observations from previous days. In addition, travel time informa-
tion from upstream and downstream links is incorporated so information

about evolving traffic waves is considered before such waves reach the link.

The prediction model is applied to a small network with 21 decision nodes and
38 links, and its performance is examined under normal and congested traffic
conditions. We consider different structures of the model for improving travel
time predictions especially in the case of congestion due to a traffic incident.
We also experimented with different frequency rates with which the system is
updating predictions on travel times. Obviously, there is a trade off between
the number of predictions that we can perform with some reasonable accuracy
and the rate with which we update such predictions. Finally different scenar-
ios for market penetration of route guidance systems are considered, for exam-
ining how travel time savings change as the percentage of equipped vehicles

increases.

iv

7b my wife Filio and
to my parents Neofytos and Polymnia

ACKNOWLEDGMENTS

I would like to express my great intellectual debt to my academic advisor Dr.
Vlfilliam C. Taylor, for his guidance and advise during the course of my studies

and this research.

I also want to express my appreciation to Dr. Francis X. Mckelvey, Dr. Richard
W. Lyles, and Dr. Habib Salehi for serving as members on the guidance com-
mittee and for their assistance. My gratitude is also extended to Dr. Majid

Nayeri for his valuable assistance.

Finally, I want to express my thanks to my wife Filio and my brother Niki, for
providing their support and encouragement. My parents have provided con-
tinuous encouragement and moral support through the years and my appreci-

ation for them cannot be expressed with words.

 

Table of Contents

 

List of Tables ................................................................................................. ix
List of Figures ............................................................................................... xii
Chapter 1: Introduction ....................................... . ............... . ....... ........ 1
Chapter 2: Literature Review...... ................................................ . ..... .....6
2.1 Route Guidance Systems ..................................................................................... 6
2.2 Expected Benefits of IVHS ............................................................................... 11
2.2.1 Alleviation of Congestion ........................................................................ 12
2.2.2 Findings on Effectiveness of Route Guidance Systems .......................... 13

2.3 Prediction of Traffic Conditions ....................................................................... 20
2.3.1 Equilibrium Models ................................................................................. 22

2.3.2 Real Time Adaptive Forecasting ............................................................. 29

2.4 Summary of Literature Review ......................................................................... 36
Chapter 3: Prediction Model of Travel Times.. ................................ . 38
3.1 Introduction ....................................................................................................... 38
3.2 Operating Framework ....................................................................................... 39
3.3 Structure of Prediction Model ................... 41
3.3.1 Input Variables to the Prediction Model .................................................. 42

3.3.2 Model Formulation .................................................................................. 45

3.4 Prediction Algorithm ........................................................................... . .............. 48

vii

3.4.1 Time Invariant Parameters ....................................................................... 48
3.4.2 Time Varying Parameters ........................................................................ 50
3.4.3 Initialization of Prediction Algorithm ...................................................... 52
3.5 Stochastic Interpretation of the RLS Algorithm ............................................... 53
Chapter 4: Simulation Model ................................................................ 56
4.1 Introduction ....................................................................................................... 56
4.2 Modelling Elements .......................................................................................... 58
4.2.1 Representation Of Network In The Simulation Model ............................ 58
4.2.2 Representation Of Traffic In The Simulation Model ............................... 60
4.3 Description Of The Simulation Model .............................................................. 62
4.3.1 Event 1: Updating The Minimum Path Tables Of The Network ............. 65
4.3.2 Event 2: Entrance Of Vehicle In The Network ........................................ 73
4.3.3 Event 3: Exit Of A Vehicle From A Link ................................................ 83
4.3.4 Events 4 & 5: Start& End Of A Traffic Incident ..................................... 90
4.4 Conclusions from the Development of the Simulation Model .......................... 92
Chapter 5: Application of the Prediction Model .......................... ....94
5.1 Introduction ....................................................................................................... 94
5.2 Test Network ..................................................................................................... 95
5.3 Structure of the Prediction Model ................................................................... 101
5.3.1 Autoregressive Models .......................................................................... 104
5.3.1.1 Normal Traffic Conditions ............................................................ 105
5.3.1.2 Congested Conditions Due to Traffic Accident ............................ 1 17

5.3.2 Autoregressive Models Including the Average Travel Time of
the Link .................................................................................................. 123
5.3.2.1 Normal traffic Conditions .............................................................. 123
5.3.2.2 Congested Conditions Due to a Traffic Accident .......................... 134
5.3.3 Models Including the Convection Term ................................................ 137

5.3.3.1 Normal Traffic Conditions ............................................................ 138

viii

5.3.3.2 Congested Conditions Due to Traffic Accident ............................ 151

5.3.4 Models Including the Congestion Term ................................................ 157
5.3.4.1 Normal Traffic Conditions ............................................................ 158

5.3.4.2 Congested Conditions Due to Traffic Accident ............................ 162

5.3.5 Discussion of the Results and Further Developments ........................... 172

5.4 Effect of Time Step Length on Predictions ..................................................... 179
5.4.1 Effect of Time Interval under Normal Traffic Conditions .................... 181
5.4.2 Effect of the Time Interval under Congested Traffic Conditions .......... 186
Chapter 6: Effectiveness of Route Guidance System ......... 189
6.1 Introduction ..................................................................................................... 189

6.2 Effectiveness of Route Guidance System at Different Levels of Market
Penetration ...................................................................................................... 190

Chapter 7: Summary and Conclusions ............................................. 200

 

List of Tables

 

Table 2.1 : Percent of Speed Improvement with Market Penetration of Prescriptive

Route Guidance Sysrems ................................................................................ 20
Table 5.1 : Adjacency List of Test Network .................................................................... 97
Table 5.2 : Origin - Destination Matrix ........................................................................... 99
Table 5.3 : Lengths, Free Flow Maximum occupancies and Free Flow travel Times

of Links of Network. 99
Table 5.4 : Prediction Errors of Link 15 for the Morning Period under Normal Traf-

fic Conditions (300 Observation, 06:00 - 11:00) ......................................... 106
Table 5.5 : Prediction Errors of Link 15 for the Evening Period under Normal Traf-

fic Conditions (300 Observation, 14:00-19:00) ........................................... 107
Table 5.6 : Parameters for Autoregressive Models at the End of the Evening Period

(19:00) of the Second Simulated Day (7t = 1.00). ........................................ 108
Table 5.7 : Percent Difference of Prediction Error of Autoregressive Models with

No Predictions case for Morning Period (06:00-11:00) ............................... 112
Table 5.8 : Percent Difference of Prediction Error of Autoregressive Models with

No Predictions case for Evening Period (14:00-19:00) ............................... 113
Table 5.9 : Prediction Errors of Link 12 for Morning Period under Normal Traffic

Conditions and Different Values of the Forgetting Factor (300 Observa-

tions, 06:00-11:00) ....................................................................................... 115
Table 5.10 : Prediction Errors of Link 12 for Evening Period (300 Observations,

14:00-19:00) under Normal Traffic Conditions and Different Values of

the Forgetting Factor .................................................................................... 116
Table 5.11 : Prediction Errors of Link 19 with Autoregressive Models and Different

Table 5.12 :

Values of the Forgetting Factor under Congested Conditions due to a
Traffic Accident (50 Observations 08:00 - 10:30) ........................................ 118

Prediction Errors of Link 15 with Autoregressive Models Including the
Average Travel time of the Link under N ormal Traffic Conditions -
Morning Period (300 Observations 06:00-1 1 :00) ........................................ 124

ix

Table 5.13 :

Table 5.14:

Table 5.15 :

Table 5.16:

Table 5.17 :

Table 5.18:

Table 5.19:

Table 5.20 :

Table 5.21

Table 5.22 :

Table 5.23

Table 5.24

Table 5.25 :

Prediction Errors of Link 15 with Autoregressive Models Including the
Average Travel time of the Link under Normal Traffic Conditions -
Evening Period (300 Observations 14:00-19z00) ......................................... 124

Percent Difference of Prediction Error of AR Models Including the Av-
erage Link Travel Time Term from the No Predictions Case - Morning
Period (06:00-1 1:00) .................................................................................... 132

Percent Difference of Prediction Error of AR Models Including the Av-
erage Link Travel Time Term from the No Predictions Case - Evening
Period (14:00-19:00) .................................................................................... 133

Prediction Errors of Link 19 with Autoregressive Models Including the
Average Travel Time of the Link under Congested Traffic Conditions
Due to Accident - (150 Observations 8:00-10:30) ....................................... I35

Prediction Errors of Link 15 with Models Including the Convection
Term - Normal Traffic Conditions - Morning Period (300 Observations
06:00-l 1:00) ................................................................................................. 139

Prediction Errors of Link 15 with Models Including the Convection _
Term - Normal Traffic Conditions - Evening Period (300 Observations
14:00-19:00) ................................................................................................. 140

Percent Difference of Prediction Error of Models Including the Convec-
tion Term from the Case of No Predictions - Morning Period (06:00-
11:00) ........................................................................................................... 144

Percent Difference of Prediction Error of Models Including the Convec-
tion Term from the Case of No Predictions - Evening Period (14:00-
19:00) ........................................................................................................... 145

: Percent Difference of Prediction Errors of Models Including the Convec-

tion Component Over the No Predictions Case, Autoregressive Models
and Models Including the Average Travel Time ......................................... 146

Prediction Errors of Link 19 with Autoregressive Models Including the
Average Travel Time and the Convection Component of the Link under
Congested Traffic Conditions Due to Accident - (150 Observations
08:00-10:30) ................................................................................................. 152

: Prediction Errors of Link 15 with Models Including the Congestion Term

- Normal Traffic Conditions. Morning Period (300 Observations 06:00-
1 1:00) ........................................................................................................... 159

: Prediction Errors of Link 15 with Models Including the Congestion Term

- Normal Traffic Conditions. Evening Period (300 Observations 14:00-

l9:00) ........................................................................................................... 160
Prediction Errors of Link 12 During Traffic Accident on Link 19 (150
Observations 8:00— 10:00) ............................................................................. 163

X

Table 5.26: Prediction Errors of Link 12 with Models Including the Congestion Term
- Congested Traffic Conditions (150 Observations 8:00-10:00) .................. 166

Table 5.27 : Prediction Errors of Model with Time Varying Forgetting Facror for
Link 19 - Congested Traffic Conditions Due to Accident - 150 Observa-
tions 08:00-10:30 .......................................................................................... 176

Table 5.28 : Prediction Errors of Link 15 for Different Time Steps h ............................ 182

Table 6.1 : Travel Times and Percent Differences of Smart and Non Smart Vehicles
for Different Market Penetration Levels. ..................................................... 195

Table 6.2 : Travel Times of Smart and Non Smart Vehicles for Different Market
Penetration Levels when Information is Updated Every 30 Seconds .......... 198

 

List of Figures

 

Figure 2.1
Figure 2.2

Figure 3.1

Figure 3.2
Figure 3.3

Figure 3.4

Figure 3.5
Figure 4.1
Figure 4.2
Figure 4.3
Figure 4.4
Figure 4.5

Figure 4.6
Figure 4.7
Figure 5.1
Figure 5.2
Figure 5.3
Figure 5.4

Figure 5.5

: Implementation of ADIS and ATMS ............................................................. 8
: Sensitivity of System Benefits to Incident Duration .................................... 19
: Operating Framework for Prediction Model of Travel Conditions on

the Network. ................................................................................................. 40
: Block Diagram of Travel Conditions of a Link ........................................... 42

:- Relation Between the Travel Times of Two Links in Sequence (Sim— '

ulated Observations, Sampling Interval 60 seconds) ................................... 44

: Relation Between the Travel Times of Two Links in Sequence with

an Accident on the Downstream Link (Simulated Observations, Sam-

pling Interval 60 seconds) ............................................................................ 44
: Link Layout for Prediction Model of Link I - Equation (3.3) ...................... 46
: Flow Chart of Main Function of Simulation Program ................................. 63
: Flow Chart of Event 1: Update the Minimum Path Tables ......................... 66
: Violation of Principle of Optimality in Dynamic Networks ........................ 70
: Flow Chart of Event 2: Entrance of a Vehicle in the Network .................... 74
: Relationship Between Link Travel Time and Link Occupancy Based

on the BPR Function .................................................................................... 77
: Flowchart of Event of Exit of a Vehicle from a Link. ................................. 84
: Flow Chart of Selection of Next Two Links of Path ................................... 88
: Test Network Layout ................................................................................... 96
: Traffic Generation Pattern at Nodes 1, 2, and 3. ......................................... 98
: Smoothed Five-Minute Average Travel Times of Links 19 and 22 .......... 102

: 1 Step Predictions of Travel Times of Link 15 with Autoregressive

Model of Order 3 - Normal Traffic Operations, Morning Period .............. 110

: 10 Step PrediCtions of Travel Times of Link 15 with Autoregressive

xii

Figure 5.6

Figure 5.7

Figure 5.8

Figure 5.9

Figure 5.10 :

Figure 5.11 :

Figure 5.12 :

Figure 5.13 :

Figure 5.14 :

Figure 5.15 :

Figure 5.16 :

Figure 5.17 :

Figure 5.18 :

Figure 5.19 :

xiii
Model of Order 3 - Normal Traffic Operations, Morning Period .............. 110

: 1 Step Predictions of Travel Times of Link 15 with Autoregressive

Model of Order 5 - Normal Traffic Operations, Evening Period ............... 111

: 10 Step Predictions of Travel Times of Link 15 with Autoregressive

Model of Order 5 - Normal Traffic Operations, Evening Period ............... 111

: Parameters of Autoregressive Model of Order 3 - Forgetting Factor

l=1.000 ...................................................................................................... 114

: Parameters of Autoregressive Model of Order 3 - Forgetting Factor

1:0.975 ...................................................................................................... 1 14

1 Step Ahead Predictions of Travel Times of Link 19 with Autore-
gressive Model of Order 1 and 7t=1.00 - Congested Traffic Conditions
Due to Accident .......................................................................................... 120

10 Step Ahead Predictions of Travel Times of Link 19 with Autore-
gressive Model of Order 1 and 1:100 - Congested Traffic Conditions
Due to Accrdent120

1 Step Ahead Predictions of Travel Times of Link 19 with Autore-
gressive Model of Order 1 and 2:080 - Con gested Traffic Conditions
Due to Accident .......................................................................................... 121

10 Step Ahead Predictions of Travel Times of Link 19 with Autore-
gressive Model of Order 1 and 1:0.80 - Con gested Traffic Conditions
Due to Accident .......................................................................................... 121

1 Step Ahead Predictions of Travel Times of Link 15 with Autore-
gressive Model of Order 3, Including the Average Travel Time -
7t=1.00 - Normal Operating Conditions — Morning Period ......................... 129

10 Step Ahead Predictions of Travel Times of Link 15 with Autore-
gressive Model of Order 3, Including the Average Travel Time -
1:100 - Normal Operating Condition - Morning Period .......................... 129

1 Step Ahead Predictions of Travel Times of Link 15 with Autore-
gressive Model of Order 3, Including the Average Travel Time -
k=l.00 -Norma1 Operating Conditions - Evening Period .......................... 130

10 Step Ahead Predictions of Travel Times of Link 15 with Autore-
gressive Model of Order 3, Including the Average Travel Time -

1:1.00 - Normal Operating Conditions - Evening Period ......................... 130
Value of Parameters Corresponding to Connector Links (11 and 16)
in the Convection Term .............................................................................. 142
Value of Parameters Corresponding to the Major Arterial Link (8) in

the Convection Term .................................................................................. 142

Figure 5.20 :

Figure 5.21 :

Figure 5.22 :

Figure 5.23 :

Figure 5.24 :

Figure 5.25 :

Figure 5.26 :
Figure 5.27 :
Figure 5.28 :
Figure 5.29 :
Figure 5.30 :
Figure 5.31 :
Figure 5.32 :
Figure 5.33 :
Figure 5.34 :

Figure 5.35 :

xiv
1 Step Predictions and Observed Values of Travel Times of Link 15 —

Model Including the Convection Component - Normal Traffic Condi-
tions - Morning Period - 1:1.00, ma=2 ...................................................... 147

10 Step Predictions and Observed Values of Travel Times of Link 15
- Model Including the Convection Component - Normal Traffic Con-
ditions - Morning Period - 1:100, ma=2 ................................................... 147

1 Step Predictions and Observed Values of Travel Times of Link 15 -
Model Including the Convection Component - Normal Traffic Condi-
tions - Evening Period - 7t=1.00, ma=2 ...................................................... 148

10 Step Predictions and Observed Values of Travel Times of Link 15
- Model Including the ConveCtion Component - Normal Traffic Con-

ditions - Evening Period - 2:100, ma=2 ................................................... 148
5 Step Predictions with Model Including the Convection Term (4) and
with Model Including the Average Travel Time Only (0) ......................... 150

Parameter Corresponding to the Average Travel Time Term from
Model Including the ConveCtion Term (dc) and from Model Including

the Average Travel Time Only (d,,,)150
1 Step Predictions of Travel Times of Link 19 with Model Including
the Convection Term - Congested Traffic Conditions - 7L=1.00 ................ 155
10 Step Predictions of Travel Times of Link 19 with Model Including
the Convection Term - Congested Traffic Conditions - 1:100 ................ 155
1 Step Predictions of Travel Times of Link 19 with Model Including
the Convection Term - Con gested Traffic Conditions - 1:080 ................ 156
10 Step Predictions of Travel Times of Link 19 with Model Including
the Convection Term - Congested Traffic Conditions - 1:080 ................ 156
Convergence of Parameters of Congestion Term to Zero Under Nor-
mal Traffic Conditions. .............................................................................. 161
Contribution of the Congestion Term to the l-Step Ahead Predictions
Under Normal Traffic Conditions. ............................................................. 161
Value of the Congestion Term from Link 19 for the 1 Step Travel
Time Predictions of Link 12 - ra=2 ............................................................ 168
Value of the Congestion Term from Link 19 for the 1 Step Travel
Time Predictions of Link 12 - ra=10 .......................................................... 168
1 Step Predictions of Travel Times of Link 12 with Models Including
the Congestion Term - ra=10, 1:1.00 ........................................................ 170

10 Step Predictions of Travel Times of Link 12 with Models Includ-
ing the Congestion Term - ra=10, 71.=1.00 .................................................. 170

XV

Figure 5.36 : 1 Step Predicfions of Travel Times of Link 12 with Models Including

the Congestion Term - ra=10, 3.=0.90 ........................................................ 171
Figure 5.37 : 10 Step Predictions of Travel Times of Link 12 with Models Includ—

ing the Congestion Term - ra=10, 1:0.90 .................................................. 171
Figure 5.38 : 1 Step Ahead Predictions of Travel Time of Link 19 with Time Vary-

ing Forgetting Factor .................................................................................. 177
Figure 5.39 : 10 Step Ahead Predictions of Travel Time of Link 19 with Time

Varying Forgetting Factor .......................................................................... 177
Figure 5.40 : Behavior of Mean Absolute Error for Different Time Steps under

Normal Traffic Conditions ......................................................................... 183
Figure 5.41 : Behavior of Mean Square Error for Different Time Steps under Nor-

mal Traffic Conditions ............................................................................... 183
Figure 5.42 : 2 Step Predictions of Travel Times of Link 15 with Time Step h=10

minutes ....................................................................................................... 185
Figure 5.43 : Value of Components of Prediction Model for Link 15 with Time ,

Step h=10 minutes ...................................................................................... 185
Figure 5.44 : Behavior of Mean Absolute Error for Different Time Steps under

Congested Traffic Conditions .................................................................... 188
Figure 5.45 : Behavior of Mean Square Error for Different Time Steps under Con-
' gested Traffic Conditions ........................................................................... 188
Figure 6.1 : Hourly Average Travel Time - Market Penetration 10% .......................... 190
Figure 6.2 : Hourly Average Travel Time - Market Penetration 30% .......................... 191
Figure 6.3 : Hourly Average Travel Time - Market Penetration 50% .......................... 191
Figure 6.4 : Hourly Average Travel Time - Market Penetration 70% .......................... 192
Figure 6.5 : Hourly Average Travel Time - Market Penetration 90% .......................... 192
Figure 6.6 : Travel Time Profile for Different Levels of Market Penetration ............... 195
Figure 6.7 : Comparative Travel Time Profiles for Information Updates Every 60

and Every 30 Seconds ................................................................................ 198

Chapter 1

 

Introduction

 

During recent decades, an enormous effort has been made to improve the
mobility of individuals, especially in urban areas where demand is concen-
trated and supply of transportation facilities is restricted. This effort included
massive expenditures for providing the means to satisfy such demand, like the
construction of the freeway system and the rapid transit system in most of the
major metropolitan areas. The hope. behind the implementation of such
immense projects was that demand will be accommodated by provision of
more highways. At the same time operational characteristics of vehicles are
greatly improved, regarding safety, emissions, efficiency, and performance.
The tramc management systems like traffic signal systems and ramp meter-
ing strategies, have also been improved so they respond to variations in traffic

demand and conditions.

However, travel demand has been increasing continuously due to socioeco-
nomic factors like the increase of car ownership - and therefore an increase in
access to a private automobile by more individuals - as well as the increased

need to travel in today’s urban areas where the spatial distribution of activi-

2
ties is widely spread. In many metropolitan areas the growth of automobile

usage has already outpaced infrastructure investments, and in the near
future it is expected that this will also be the casein several other high growth
urban areas. Expected levels of delay are measured in billions of vehicle
hours, and the increased usage of automobile will result in an increase in the
number of traffic accidents (Grenzeback and Woodle 1992). The estimated
losses from such delays and accidents, are claimed to be a few hundred billion
dollars annually. Traffic congestion is regarded as one of the major problems of
urban areas and it is often compared with societal problems like crime, access

to health care, or housing.

On the other hand economic and environmental control policies place limits on
increasing the physical road capacity. Both social and environmental conse-
quences of such projects may be far more severe than their expected benefits.
In addition, congestion relief benefits may not last very long, due to the rate of
demand for even more mobility. These two contradicting phenomena - an
increase in demand and an inability to increase the capacity of traffic net-
works to serve this demand - contribute to the creation of traflic congestion,

especially on commuting corridors during peak periods.

For these reasons, the attention in transportation planning has turned to
studies of how to effectively use the existing capacity, rather than constructing
new freeways. The potential of using modern technologies, like advances in
communications and computers, as well as a higher level of sophisticated con-
trol systems and sensors, are greatly enhancing the possibility of success of
such an approach. The usage of such technologies in the transportation sys-

tem is housed under the term Intelligent Vehicle - Highway Systems (IVHS),

3
and the technologies used are referred to as IVHS technologies.

IVHS includes the systems that use advanced technologies to control and
improve mobility on a traffic network. For example, traffic operations can be
improved when traffic management is based on processing of real time infor-
mation regarding the travel conditions on the elements of a network. VVrthout
real time information the decisions of individual travelers regarding the time
that they will realize their trip, the mode that they will use and the route that
will be followed are often based on information that is incomplete and not
accurate. When real time information is used, such decisions will approach
the optimal ones and the development and application of new and sophisti-

cated control strategies will be possible.

While IVHS as defined above is quite comprehensive, there are four sub-
systems that can be distinguished and are generally accepted:

(1) The Advanced Driver Information Systems (ADIS);

(2) The Advanced Traffic Management Systems (ATMS);

(3) The Commercial Vehicle Operations; (CVO); and

(4) The Advanced Vehicle Control Systems (AVCS);

Technologies included in the ADIS category are the ones that can navigate the
driver through a network, provide information about alternative routes and
congestion and reveal the location of service stations, restaurants, or rest
areas. Driver information systems can vary based on (Koutsopoulos and
Yoblanski 1991):

(1) the ability to provide real time information;

(2) the type of information that they provide;

4
(3) the ability to address a single vehicle or all the vehicles at a location on

the network; and
(4) the communication capabilities of the system linking the vehicles on
the road with the traffic control center, ranging from no communica-

tion, to one-way or two-way communication.

On the other hand, ATMS includes traffic management systems that operate
in real time, so the system will respond to changes in the traffic demand, or
even anticipate when and where such changes will occur and apply the appro-

priate strategy in order to avoid congestion.

Commercial vehicle operations are based on ATMS and ADIS but are eon-
cerned mostly with issues like weigh in motion, vehicle tracking, efficient
vehicle dispatching, and timely pickups or deliveries. These are operations
which can be performed more efficiently through IVHS. On the other, hand
advanced vehicle control systems (AVCS) will not make direct use of informa-
tion about traffic conditions, but they will improve safety and potentially the
capacity of a network by assuming partial or complete control of the vehicle.
AVCS includes systems that aim to help the driver in the task of driving, like
lane keeping systems, enhanced night vision systems, adaptive cruise control,

and so forth.

In this study we are concerned with the first subsystem which is closely
related with vehicle navigation and route guidance problems of traffic on a
network. The key element of a route guidance system, is the knowledge of the
“travel cost” on the links in the network, for all time periods in a planning

horizon. In real time systems, where route guidance will be performed on-line,

5
these travel costs have not yet occurred. A reasonable assumption is that the

aspect that travelers will be willing to optimize in their trip is their travel
time. Therefore the ability to make predictions for such travel times with rea-

sonable accuracy is essential to the route evaluation process.

In the following a review of the existing literature relevant to the problem of
dynamic route guidance, and short term prediction of travel times is pre-
sented. In the next chapter the proposed travel time prediction model is dis-
cussed. In chapter 4, a traffic simulation program is presented, which will be
used for testing the prediction model. The structure of the prediction model is
examined in chapter 5, while the effectiveness of the model incorporated
within a route guidance system is presented in chapter 6. Finally chapter 7

presents the conclusions drawn from this research.

Chapter 2

 

Literature Review

 

2.1 Route Guidance Systems

Route guidance systems can be defined as those systems that, when the driver
provides the destination of his/her trip, are capable of guiding him/her
through the most desirable route. Depending on the way that the system rep-
resents traffic and the way it performs the routing, we can distinguish three
alternative route guidance systems (Chen and Underwood 1991):

(1) Static guidance systems, where the costs of the links of the network are
assumed to be independent of the time and the amount of traffic that
traverse them (constant link travel cost).

(2) Simple dynamic route guidance systems, where link costs are allowed to
vary with time but traffic is still routed through the network based on
a static approach to route selection. This is the case when the guided .
vehicle receives information only at the beginning of the trip regarding
current link costs.

(3) Dynamic route guidance systems, where the routing of a vehicle depends
not only on the time of departure but on the location of the vehicle as
well. In this class of guidance systems link costs vary with time and

the most desirable route is reexamined each time the vehicle reaches a

6

new decision node.
In addition to this classification, depending on the type of information that
guidance systems use as a base, route suggestions may be further classified to
responsive, in the cases that use real time data, and unresponsive if they use

only historical data obtained from previous days.

For the first two classes of route guidance systems, the determination of the
most desirable path can be obtained by using a fastest path algorithm, like the
Dijkstra’s algorithm, based on Bellman’s principal of optimality. In dynamic
route guidance systems, such static algorithms will not be sufficient. In this
case more complex, and consequently of higher computational effort, algo-
rithms are required, which are capable of finding the minimum path in

dynamic networks (Kaufman and Smith 1990).

The most probable scenario of implementing a dynamic route guidance system
is depicted in Figure 2.1 (Chen and Undewood 1991), which also follows the
market penetration scenario 'of such systems. Initially ADIS will serve only as
a navigation system. Such systems are already successfully in use, like the
Advanced Mobile Traffic Information and Communication Systems and the
Road Autonomous Communication Systems in Japan or the DEMETER in
Europe (French 1990). In this case, information is not provided in real time or
the informationsystem performs only “yellow pages” functions. Actual condi-
tions on the network are not known to the driver. Such systems often operate
by relating the current position of a vehicle obtained by either the Geographic
Position System (GPS) or by dead reckoning, with a digital map. The geo-
graphic information of the digital map is stored in a CD-ROM, and navigation

advice is often displayed on an in-vehicle monitor. Communications between

Navigation and Dynamic Coordination of

Communications Route Guidance Guidance with ATMS
Coordination of

Multimodal Guidance With

Guidance Dispatch

Transit _ __. l .._ .. .. . .
Information COORDNATIONSTAGE :33" 1'

 

 

V V

“FORMATION “AGE ’ 1 . : '-

 

 

 

Tune

(Source: Chen & Underwood 1991)

Figure 2.1: Implementation of ADIS and ATMS.

 

9
the vehicle and the traffic control center at this level of systems is not

required.

In the next stage, where dynamic route guidance will be possible, information
will be broadcast by the system in real time. As is shown in Figure 2.1, at this
stage ADIS plays only an advisory role on which is the current optimal route.
When information about current and projected traffic conditions is used for
guiding traffic, this information has to be updated continually. In this case
communication links have to be established, so the information transmitted
by the traffic management center (system) will be received by the vehicles on
the network which are equipped with some special receivers. The system has
to be capable of collecting and processing information about the traffic condi-
tions continuously on the elements of the network and then broadcast the pro-

cessed information back to the traffic on the network.

In a route guidance system, information received by the equipped vehicles
may be either in the form of descriptions about the traffic conditions on the
elements of the network, in which case the driver will have to select the opti-
mum path based on his judgement, or in the form of suggestions on which is
the current optimum route to follow, or the best time to start the trip. While it
could be argued that guidance in the descriptive form is meaningless when
with a simple computing device prescriptive information can be obtained, such
guidance could be more helpful in the case where the driver wants to avoid a
part of the city for security reasons, or a driver wants to stay on the freeway

system.

Field tests of such systems are under way in the United States, Europe, and

10
Japan. For example the Autoguide system in London is the first dynamic

route guidance system. Based on real time information, minimum travel time
routes are calculated and updated regularly by the traffic control center. This
information is transmitted to the network, so equipped vehicles can receive it
when they approach “decision nodes”. The decision nodes are intersections
equipped with electronic signposts which transmit directions to the equipped
vehicles, related with the movements of the intersection, i.e. straight ahead,
turn right or turn left. The optimum paths are selected based on average con-
ditions on the network for a specific time, day and weather conditions, as well
as current information regarding unusual events. This information is updated
in rather long time intervals (every 15 minutes), except in the case when an
incident has occurred, and in this situation the frequency of updating. the
transmitted information is increased. The operation of Autoguide is reactive
to traffic conditions, meaning that it will divert traffic only when congestion is
already evident. A similar system Ali-Scout (or as it is lately renamed to Euro-
Scout) is also under testing in the city of West Berlin, and soon it will be tested
in Oakland County, Michigan. This system combines the characteristics of
Autoguide with a digital map for displaying the vehicle location and the direc-
tions to be followed (Boyce 1989, French 1990).

Here it should be noted that the concept of such systems is not new; The idea
of alleviation of congestion based on guiding traffic had its origins back in the
1960’s. These efforts however were either not successful due to the limited
capabilities of the available technologies at that time or not feasible due to the

excessive cost of implementing them (Rosen et al., 1970).

In the last stage, dynamic route guidance systems will be coordinated with

11
ATMS, through the use of traffic assignment models. The route guidance sys-

tems described in the advisory stage, in a situation with congestion, will
divert all equipped traffic to one single new optimum path. Without more
sophisticated coordination, which can be achieved through dynamic traffic
assignment models, congestion will be created on the alternative routes. This
is because there is no consideration of the effect of the diverted traffic on the
travel conditions of the new path. Such strategies will be effective only while
the percentage of the equipped vehicles is low. When a large number of vehi-
cles are equipped, everybody will be receiving the same information which will
result in the possible transfer of the congestion to another part of the network.
Such transfer of congestion is often referred as guidance system induced con-
gestion (Boyce 1989, Kaufman et a1. 1990). Although extensive research
results are available for the static situation, where traffic demand is consid-
ered constant, there are just a handful of theoretical configurations for the

dynamic approach.

2.2 Expected Benefits of IVHS
The main benefit expected from the implementation of IVHS is alleviation of

congestion that costs society and the environment a great deal. In addition,
new technologies are expected to contribute to improvements in safety and
productivity of the transportation system. IVHS and mostly AVCS are sup- '
posed to contribute to accident prevention in contrast to most accident coun-
termeasures applied currently, that aim to reduce the severity of traffic
accidents. Early detection of pending hazards, which is one of the promises of
AVCS, will result in providing the driver with the critical time required to
react and avoid the accident. Nevertheless potential opposite effects have to

12
be acknowledged. There are some inherent risks of automated highways, and

possible distraction of the driver from current in-vehicle information devices

may jeopardize his/her safety.

2.2.1 Alleviation of Congestion
In the literature, two types of congestion are conveniently distinguished:

(1) Recurrent congestion that occurs during certain time periods of the day
or certain days of the year, due to a high demand that exceeds the
capacity of the elements of the network; and

(2) Non recurrent congestion that occurs due to unexpected circumstances
like traffic accidents or vehicle breakdowns, which can greatly affect
the capacity of the system. Such a reduction in capacity leads to con-
gestion, and it is time independent.

It is claimed that IVHS will reduce delays due to both recurrent and non
recurrent congestion. Up to date results suggest that benefits of ADIS systems
will be marginal under conditions of recurrent congestion (Al-Deek and
Kanafani 1991). However the benefits that will accrue in the case of non recur-
rent congestion are expected to be much more significant, since the occurrence
of such congestion is random, and thus its effects cannot be anticipated by the
unequipped driver. On the other hand, some of the effects of recurrent conges-
tion can be anticipated even without ADIS, when drivers have previous expe-
rience on the network. Provision of information about the development of
congestion to the drivers in real time can be used for diversion of traffic either
in space or in time. For example, drivers can be directed to either divert from
a congested link of the system to an alternative one with higher level of ser-

vice, or they can simply choose to postpone their time of departure. The basic

13
difference between the two diversion options lies in the time that they can be

implemented. While diversion in time has to be administered before the begin-

ning of the trip, diversion in space can be performed before or during the trip.

Here we consider the case where in the situation of congestion, appropriately
equipped vehicles will divert from the originally selected path, en-route, based
on “intelligent” suggestions made by the system. However, it should be noted
that in large metropolitan areas, congestion is a daily phenomenon not just for
a short time period but for several hours. In such areas congestion is spilled
even on beltways which were originally designed for through traffic in order to
avoid local effects. Before we appraise the benefits of IVHS it is useful to con-
sider if there is any capacity left on the network that is not used, and its usage
could improve the situation. If the answer is no, then information on traffic
conditions on the network, even in real time, will not contribute anything to
the travelers. Under this condition, the application of advanced technologies
may help to lead travelers to alternative modes like rapid transit or ride shar-

ing which will possibly qualify them to use HOV facilities.

2.2.2 Findings on Effectiveness of Route Guidance

Systems
The expected benefits of NHS, and more specifically of route guidance sys-
tems, will be a reduction in congestion. Several studies have dealt with the
effectiveness of route guidance systems, based mostly on simulation models.
Depending on the configuration of the route guidance system, reductions in
average trip time ranging from 2 to 50 percent were noted (G.A.O. 1991).
Although the possible effectiveness of route guidance systems has such a wide

14
range, one aspect that all the studies which examined different levels of mar-

ket penetration agree is that for high market penetration levels, equipped

traffic does not get as much travel time improvement as at low levels.

The issue of reliability of the broadcast information was examined by Chen
and Mahmassani (1991), where the supplied travel time was compared to
actual travel times experienced in the network after the information was
broadcast. Because of the dynamic character of traffic on a network a recom-
mended path may actually be less than optimal as traffic congestion evolves.
Furthermore drivers may not switch from their current path unless they know
that the time savings from the alternative route are meaningful. VVrth a series
of simulations the authors examined various combinations from a set of vari-
ables:

(1) different scenarios of information sources including no information at
all, information only at the beginning of the trip, only enroute informa-
tion, or both;

(2) two different behavioral rules for drivers switching routes one where
drivers are willing to accept any improvement in their travel, regard-
less of how small (myopic rule) and one where the new path has to be
more than 20% better than the current path and at least one minute
less; and

(3) different levels of market penetration.

In their results it was found that reliability of information worsens as market
penetration increases when drivers behave myopically and both sources of
information are available. For the other cases the reliability of information is
better at 10% of market penetration than at 100%, but no trends are obvious

for the cases in between. Also at high market penetration, equipped traffic

15
performs better than the rest of the traffic when the behavioral rule is

employed, a fact that is attributed to the less “unproductive” path switches

due to the indifference band of 20% improvement.

When the reliability of the broadcast information is high, users with access to
information experience meaningful travel time improvements. This is true
since information is reliable if there have not been many switches that would
result in congested routes. Similar results were reported by Hamerslag and
van Berkum (1991) where, after simulating a set of different urban networks,
it was found that the amount of car-kilometers traveled decreases as the

uncertainty of the information available to the drivers decreases.

In an extension of the same study by the authors (Mahmassani and Chen
1991) it was found that when both sources of information are used this has
positive results only at low levels of market penetration. These benefits
decrease rapidly as market penetration increases and often are less than
those obtained with one source of information only. Also home based informa-
tion only, at high levels of market penetration has negative effects, while ben-

efits due to en-route information appear to be more robust.

Koutsopoulos and Lotan (1989) investigated the effect of variables like level
and amount of information, level of congestion, spatial extent of information
and portion of informed drivers, on the system performance under a route
guidance system.The results from this study indicated that the total benefits
that will accrue from advanced driver information systems will be marginal.
Based on simulation results from a small network, the average travel time

benefits when perfect information is available was found to be only 4.4%. In

16
the study it was noted that as the level of available information increases, the

travel time of the shortest path also increases, since more drivers can make
more intelligent decisions; and thus the alternative routes become more
crowded. Also as traffic demand increases the benefits per driver (both
equipped and unequipped) increase moderately, until the volume over the
capacity ratio assumes values in the vicinity of 1.5. After this point, such ben-
efits start to decrease. The benefits experienced by equipped drivers appear to
decrease as the congestion level increases. Thus the value of the information
provided to the drivers decreases too, since the opportunity to identify better
paths is reduced. Also, when perfect information is available for the entire
network, travel times decreases by approximately 4% as compared to the case

when travel times are known only for the main routes.

Koutsopoulos and Yoblanski (1991) examined design aspects of a route guid-
ance system, with a low market penetration of IVHS. Variables included the
location of information nodes (locations where equipped vehicles can update
information), frequency of information updates made by the system, and the
intelligence of the system. The system was assumed to be of either low or high
intelligence. In the case of low intelligence, route suggestions by the system
were based on current traffic conditions on the network on the basis that such
conditions will not change and in the case of incident occurrences the system
would take into account only delays due to queues. In the case of high intelli-
gence, expected delays due to incidents are taken into account based on
expected time of arrival at the queue. Also in this scenario, minimum paths

were calculated based on projected traffic conditions.

Their results were based on a small network simulated with a microscopic

17
simulation program. From their findings it is indicated that there are no sig-

nificant reductions in the average travel time of the network that was simu-
lated by the introduction of ADIS, except in the case of a traffic accident.
When the density of information nodes increases, the intelligence of the sys-
tem has little bearing on the average travel times of the equipped vehicles.
However the reliability of the trip (the standard deviation of the travel time)
is increased when each node is an information node. Also, a frequency of
updating information every 3 minutes was almost as good as updating infor-
mation immediately, while for longer than 3 minutes between information

updates, the route guidance system becomes less effective.

Al-Deek and Kanafani (1991) have examined the effect of diverting traffic on
the time savings for a small network with two alternative paths to a destina-
tion, in the case when an incident occurs on the higher capacity path. Parame-
ters like the capacity of the alternative path, the amount of traffic that arrives
at the decision point and the duration, severity and location of the incident
were considered. Based on this simple network, the authors found that travel
time savings of equipped traffic decreases rapidly once a queue starts forming
on the alternative route. When the proportion of diverted traffic exceeds a crit-
ical value - which depends on the demand arriving at the decision point and
the capacity of the alternative path - benefits to the equipped traffic decrease.
When the duration of the incident increases, the benefits from the route guid-
ance system also increase, but not in a linear manner. When incidents are
very long (in the example network over 60 minutes) the increase in benefits
vanishes, and for very short incidents (less than 15 minutes), there is no bene-
fit of a guidance system (Figure 2.2). The same pattern is true for the severity

of the incident, with severity defined as reduction of capacity. It is noted that

18
for severe incidents (with more than 60% reduction in capacity), and of short

duration, benefits are more sensitive to the duration than to the severity of
the incident. If the alternative route is very long it is never used, while when
the travel time of the alternative route has competitive free flow travel time to
the free flow travel time of the route with the incident, the benefits from the

system are maximized.

Halati and Boyce (1991) have also examined the effectiveness of various in-
vehicle navigation systems in the situation of a traffic incident, but on a real-
istic network (Irvine network, Orange County, California). They simulated dif-
ferent types of drivers, including drivers that are familiar or unfamiliar with
the network, drivers that are equipped or unequipped, and drivers that. are
compliant or non-compliant with the route suggestions supplied by the guid-
ance system. The guidance systems that were considered included two
descriptive systems, one with a static map and one with a map system and the
added capability of identifying congested segments of the network, and two
prescriptive systems where the best path was given to the driver. The two pre-
scriptive systems differ in the aspect that the more advanced one includes a
map display. The authors found that while there was no significant differences
between the first two systems, there was substantial improvement to the sys-
tem operations when the dynamic route guidance system was employed. The
incident occurred on a freeway section of the network, and the freeway speeds
were improved by 0.9%, 11.8% and 53% for 10%, 30% and 50% market pene-
tration of the guidance system respectively. The dynamic route guidance sys-
tem improved the performance of the surface network too, where the
improvements for the entire network were found to be 4.5%, 17.2% and 37.2%
for 10%, 30% and 50% market penetration levels (Table 2.1).

System Percent Savings

19

 

 

 

 

 

40
30 _‘
E
>
-1 .2
E
20 fl 2
.9.
‘5
-4 E
8
E
10 "‘
‘7 Reduction in Capacity = 75%
o
l T I l l T l
10 20 30 40 50

Incident Duration (Minutes)

(Source Al-Deek and Kanafani 1991)

Figure 2.2: Sensitivity of System Benefits to Incident Duration

 

20

Table 2.1: Percent of Speed Improvement with Market Penetration of Prescriptive
Route Guidance Systems.

 

 

 

 

 

 

 

 

Market Penetration
10% 20% 50%
Freeway Subsystem 0.9 11.8 53.0
Surface Street Subsystem 9.6 23.9 26.6
Entire Network 4.5 17.2 37.2

 

 

 

In the more advanced system, where drivers also have a map display, it was
assumed that more drivers divert from the congested path but less drivers fol-
low the alternative route suggested by the system. The result was a slight
worsening for low levels of market penetration, while when 50% of the drivers
were equipped, the navigation system appears to compensate for the lower
compliance rate, and there is an improvement of approximately 4% over the

simple dynamic guidance system.

2.3 Prediction of Traffic Conditions
The problem that is recognized in the existing literature is that at least in the

last two stages of implementation of route guidance systems where dynamic
route guidance will be employed, the required optimum routes are based on
traffic conditions that vary with time, and in real time, these conditions have
not yet occurred. A more sophisticated handling of such situations will be to

guide traffic through a given network with a guidance system which is based

21
not only on the current traffic conditions but also on expected conditions. In

other words, the route selection process must be based not only on where traf-
fic is currently, but where traffic will be - or more precisely where it is
expected to be - in the short term future. Such estimations of future traffic
conditions have to be based on a sophisticated prediction model which will
assess the impacts of traffic variations due to both recurrent and non recur-

rent congestion.

Obviously, two fundamental characteristics of such prediction systems are
their operational speed and their responsiveness to actual traffic conditions.
Their speed should be at least as fast as the real tramc system, or even faster.
This is required, so there will be enough time for the prediction system to per-
form the predictions, and for the route guidance system to evaluate the alter-
native routes in real time. Nevertheless, the high speed of the prediction
system should not be achieved at the cost of the accuracy of the predictions. In
addition the prediction system must be able to respond to both expected and
unexpected changes in the traffic conditions, i.e. recurrent or non recurrent
congestion. This can be achieved only if the system is capable of collecting the
necessary data in real time, and processing such data with the required speed
and accuracy, so it will periodically update the information transmitted to the
drivers. This way the route guidance system itself will be responsive to such

changes in traffic conditions (Chen and Underwood 1991).

There are two strands followed in the development of prediction models, and
each may be best applicable at different levels of market penetration of
dynamic route guidance systems. The first is based on the traffic assignment
models, which are believed to be most efficient when the majority of the traffic

22
will be equipped with such guidance system, while the second is based on

adaptive control theory.

2.3.1 Equilibrium Models

Lately, a lot of attention is concentrated on estimating future travel costs with
the use of dynamic traffic assignment models, based on some equilibrium
principal. The basic concept of the application of such models is that, in the
case when all trips are assigned to a network by the system in such a way that
some optimization condition is satisfied, the future traffic volumes on each ele-
ment of the network will be known, and future trips will be assigned in such a
manner that the optimization condition will remain valid. A fundamental dis-
crimination of such models can be made based on their objective function. The
value that is optimized may be either the delays experienced by each individ-
ual driver, in which case optimization is referred to as user optimum solution,
or the total delays experienced within the transportation system, in which
case optimization is referred to as system optimum. Generally these two opti-

mal conditions do not result in the same solution.

In system optimum modeling, the firndamental goal is to assign traffic so the
marginal costs for all alternative routes being used will be equal, under a
given demand function. Although it is not known how much the total delays
would be reduced in the system optimum case, we can speculate that in very
congested networks we may have significant savings, so even the longer
routes may be shorter than those obtained by the user optimum, Of course, in
this case the incentive for drivers to follow such routes is strong. However, the

inherent problem with such an approach is that it may advise drivers to follow

23
extremely long routes in order to minimize total delays. In the case that the

route guidance system will be actuated by the driver and it will not be manda-
tory, drivers whose travel time is worse when using the system will choose not
to use it. Since one of the main reasons for developing route guidance systems
is to reduce congestion, and therefore reduce the delays that individual driv-
ers are experiencing, improvements in the system performance should not be

obtained at the expense of individual drivers.

An alternative objective function can be obtained under the user optimum
approach. Based on the principal of optimizing each individuals travel cost,
which is often referred to as Wardrop’s first principal, traffic is assigned in
such a way that the travel cost for all the routes that are used is equal to the
minimal route travel cost. Under such a condition, no driver will use a route
from his origin to his destination if a shorter route exists. Therefore traffic
assigned on the network can no longer improve their cost by switching to

alternative routes (Sheffi 1985).

Most of the equilibrium models developed for modeling traffic assignment do
not consider the dynamics of the transportation system. For example, traffic
demand is assumed to be constant over the analysis period and consideration
of changes in the traffic conditions due to changes in traffic demand across
time is not present. Vehicles are assigned to a static route and therefore are
present on all the links of this route simultaneously. Of course such models
are not appropriate for route guidance systems since traffic demand is very
dynamic, especially during peak commuting periods. In addition, since guid-
ance systems have to be responsive to actual conditions on the network, they

have to be able to change the route while the trip is taking place if non recur-

24
rent congestion occurs, a function which cannot be represented with static

modeling. Nevertheless the static formulation of the traffic assignment prob-
lem provides the framework for developing dynamic traffic assignment models

that may be used in dynamic route guidance systems (Boyce 1988).

In their pioneering work, Merchant and Nemhauser (1978), considered a
dynamic traffic assignment problem through mathematical programing for
optimizing the total delays in a network with many origins and one destina-
tion. The model was based on Wardrop’s second principal, which requires
equal marginal costs for all the used paths, which was generalized in order to
be applicable to a dynamic formulation. The planning horizon was divided into
equal time intervals, and the demand was assumed to be constant for each
time interval. The resulting model was a discrete time, nonlinear, non convex
mathematical programming problem, which proved to be a generalization of
the static system optimum model. The model does not include explicit capacity
restrictions for the links, since in the optimal solution there should not be any
large link volumes. The number of vehicles exiting a link during each time
interval is a function only of the volume of the link. However, this formulation
does not allow transmission of congestion from an already congested link to
other links upstream. In the same context, Carey (1987) has extended the
Merchant and Nemhauser model for multi origin multi destination networks,

and managed to reform it in a nonlinear, convex form.

Recently, the approach of optimal control theory is utilized where the problem
of Optimal traffic assignment is formulated as an equivalent continuous time
optimal control problem, and a performance index has to be optimized (Friesz

et al, 1989, Ran et a1, 1992, Vlfie, 1990). For example, Wie (1990) formulated

25
the dynamic user optimum traffic assignment model as an optimal control

problem for a single destination network, Wie et al. (1991) extended the same
model for multi destination networks. The optimality conditions are derived
based on Pontryagin minimum principal, and the optimal solution represents
the temporal evolution of traffic flows based on the dynamic generalization of
Wardrop’s first principal:

“If; at each instant in time, for each origin-destination pair; the instanta-
neous expected unit travel costs for all paths that are being used are
identical and equal to the minimum instantaneous expected unit path
cost, the corresponding time varying flow pattern is said to be user opti-
mized.”

These models describe the case where the driver has complete knowledge of
the current traffic conditions on all the alternative paths from the present
position to the destination, and route choices are based only on current condi-
tions. Still congestion is depicted by using exit functions only of the volume of
the link, and in the multi destination case, these functions have to be linear.
Also the ernstence and the uniqueness of an optimal solution based on this

model is not established.

So far, the relationship between travel cost and link flow in not represented
explicitly. For example, in the case where link travel cost is the travel time
required to traverse the link, such a representation is necessary so optimal
solutions will be realistic. As it is noted by Ran et a1 (1992), when the objective
function is optimized, the speed with which vehicles travel on the links may
assume unrealistic large values, with the extreme situation of traffic traveling
instantaneously. Therefore in their model formulation, Ran et a1 (1992), have
included constraints regarding the time that vehicles can arrive at any node
using the link free flow travel times. Similar to the model developed by Wie,

the instantaneous travel time between a decision node and the destination

26
node is found based on the current link travel times, but here the dynamic

user optimum is defined as follows:

“If for each origin destination pair; at each instant of time, W-
W the travel times for all routes that are being used equal the
minimal instantaneous route travel time, the dynamic traffic flow over
the network is in a dynamic user optimum state.”

which is different from the definition in VVie’s model where route travel times
are equal at each instant in time while here, travel times are equal to the min-
imum instantaneous travel time only at each decision node. Their optimal
control problem is convex with respect to the control variables, so it provides a
unique optimal solution, and the model is implemented on a small network
with four links and four nodes and two alternative paths. The model was
reformulated as a discrete time non linear problem and the planning period
was divided into K=6 equal time intervals, in which the dynamic user opti-

mum was achieved.

Lafortune et a1 (1991) have approached the problem by modeling the traffic
network as a discrete time, integer valued dynamical system. The model
describes the state transition function which gives the possible states at time
t+1 as a function of the state at time t. The state of the system is defined as the
number of vehicles on each link with the same destination and the same earli-
. est ein't time from the links. The control variables correspond to the assign-
ment of such platoons of vehicles on the same link with the same destination 1
and the same exit time from the link on downstream links at the nodes of the
network. Constraints regarding the capacity of the links as well as headways
between vehicles are taken into account, so congestion can propagate on the
network, and vehicles cannot traverse the links rapidly. However the model

formulation is based on a-priori knowledge of the demand levels for all time

27
periods for the entire planning horizon under consideration. As it is noted by

the authors, this allows representation of recurrent congestion only, while non
recurrent congestion due to unexpected events is not modeled, and thus the

model cannot be applied in real time route guidance systems.

Papageorgiou (1990, 1991) has studied the problem of dynamic macroscopic
traffic assignment for a multi destination network also via the optimal control
approach. As in the models developed by Wie et al (1991), Lafortune et al
(1990) and Ran et a1 (1992) traffic flows on the links consist of subflows with
different destination nodes. The behavior of the drivers is represented with
the “splitting rates” at each decision node, which are the control variables of
the optimal control problem, while a parameter reflecting the compliance rate
of drivers to suggested routes by the system is also incorporated. Optimal con-
ditions are derived through feedback regulation, so the model can be imple-
mented in real time route guidance systems. The model does not include any
present or future information about demand levels, and perturbations to the
system can be controlled via the feedback control. The modeling framework
can be applied for either a system optimum or a user optimum solution. It is
interesting to note that for the simple network that the model was tested on,
the system optimum solution was marginally better than the user optimum
one. Also a general formulation of the model is presented, so other control
measures such as traffic signals and ramp metering can be included, and opti-
mization can be performed for both splitting rates and control measures

simultaneously.

However, the model developed by Papageorgiou (1990) has not been tested on

congested networks, where the effectiveness of the feedback rule may not be

28
as good. Route selection, based on the splitting rates, is based on current val-

ues of travel costs (travel times) and not future traffic conditions on the link.
In addition a feedback control is a good control approach for error actuated
systems. In dynamic route guidance systems though, a more s0phisticated
approach, based on anticipation of the future states of the system would be

more advantageous.

As has been noted, the purpose of the dynamic traffic assignment models is to
describe with a mathematical model the evolution of a control variable, like
link traffic flows, in a time varying system. In the case of high market pene-
tration of route guidance systems with the majority of the drivers who have
the system actually using it, the effectiveness of such models will be good. In
fact, if all drivers are equipped and follow exactly the suggested routes then
such models will be very accurate. However, as long as the percentage of
equipped drivers is small to medium, dynamic traffic assignment models seem
to be inappropriate, since they fail to describe the behavior of driver ‘s who do
not have knowledge of the optimum route. If drivers do not have perfect
knowledge of the traffic conditions on the network, or if all drivers do not have
uniform information, then they cannot chose the optimum route, which will
result not only in increasing their travel time, but the travel time of other
users who share the same route. In this case application of traffic assignment
models would not adequately model the evolution of traffic patterns, and their

predicting capability would be significantly reduced.

Another issue which must be taken into account is that the output of such
models is aggregated flows. Often in the user optimal model formulation and

under congested traffic conditions, there is more than one optimum path

29
which can be followed. Since the route guidance system should not direct all

drivers to one path, to avoid guidance system induced congestion, the system
must be able to allocate drivers to the alternative equal cost paths. If such a
mechanism does not exist, then the decision making process in the selection of
a route to be followed in a specific trip, from the driver’s perspective, is not

improved at all.

2.3.2 Real Time Adaptive Forecasting

A different approach for obtaining predictions of traffic characteristics is by
treating traffic variables as stochastic processes. Instead of predicting the evo-
lution of traffic based on a deterministic model, traffic characteristics are
treated as random variables which change with time, and therefore they con-
stitute stochastic processes. The data needed to describe such variables con-
sist of time series data, since they are repeated observations of the same
variable over time. Then, models based on the characteristics of the time
series can be developed, with which predictions on the traffic characteristics

can be performed.

A difficulty that exists with time series models is that they often are based on
the assumption of stationarity of the stochastic process. A stochastic process
{X, , t e T}, where T is the time set where observations are made, is said to be

stationary if (Brockwell and Davis 1987):

(1) EIX,I2<°° VtET
(2) EX=m VIET
(3) Cov(X,,X,+,)=y(r) Vt,reT

Strictly speaking, traffic variables like traffic flow or travel time are not sta-

30
tionary stochastic processes, since such variables are related with the time of

the day and possibly the day of the week. Nevertheless, these variables can be
treated as asymptotically stationary with certain conditions. Such conditions
could be given time periods, locations and environmental conditions (Lu
1990). Alternatively, the process of a traffic variable can be transformed to a

stationary process with appropriate differencing.

Time series models have been used for specific applications such as incident
detection and freeway occupancy estimation. For example Ahmed and Cook
(1980, 1982) have deve10ped a technique to detect occurrences of traffic inci-
dents automatically by monitoring fiows on a network, based on a time series
model. Based on observation of flows on different freeways they found that
traffic flow time series were best represented by an autoregressive-moving
average model with integration (ARIMA) model of low order (0,1,3). With this
model formulation they perform predictions for the traffic flows and construct
the 95% confidence band for these predictions. When the actual observations
(collected in real time) were out of the 95% confidence band the alarm is acti-
vated for the existence of an incident. Because of reliability problems of traffic
detectors which may create data gaps, Davis and Nihan (1984) developed a
time series based model (ARMA) for detecting changes in traffic flow charac-

teristics, despite some missing data point.

Kyte et a1 (1989) examined the problem of modeling freeway traffic flow with
the use of a multivariate transfer function model. The relationship between
freeway occupancies of a roadway segment with occupancies at upstream and
downstream sections was demonstrated based on occupancy observations on a

series of adjusted freeway segments. One of the segments was representing a

31
bottleneck condition, and the resulting congestion effects on upstream traffic

were examined. The speed with which traffic waves are transmitted from one
segment to another was represented with the cross correlation function of the
occupancies of the two segments. For example if the shock wave from the bot-
tleneck requires n time steps to propagate to the upstream segment, the cross

correlation function was found to have the form:

for k=n

a
Y“) -{0 for k¢n (2'1)

In regions without congestion, the model included only terms from upstream
traffic and a low order ARIMA model, while for congested regions terms from
both upstream and downstream traffic characteristics were included.

However, the main operation of time series models is as historical trend track-
ing models. The calculated parameters of such models are constant (not time
varying) and often computed off line. Therefore, the responsiveness of such
time invariant models to changes in the traffic characteristics is significantly
restricted, especially when unexpected variations occur. In dynamic route
guidance the models that will be used for predicting future traffic conditions
must be able to adapt to the dynamics of the transportation system. Methods
for allowing the parameters of the model to vary with time are available, and
they are included under the more general context of adaptive prediction models.
An adaptive prediction model can be seen as a system which has structure _
that is adjustable and it is improved with a learning process through contact
with the environment of the system. Such models include, among others, the

Kalman filters and the adaptive filters.

A classic example of filtering in traffic science is given by Gazis and Knapp

(1971). They developed a method for estimating the number of vehicles on a

32
roadway segment based on real time measurements of speed and flow at the

ends of the segment. The model consisted off:
(1) a part where the average travel time of vehicles was estimated periodi-
cally based on the time series of speeds;
(2) a “rough estimation” of the number of vehicles based on the travel time
estimation; and A
(3) a “sequential estimator” of the number of vehicles on the roadway seg-
ment.
The sequential estimator was an application of the discrete Kalman filter
where the estimations of the number of vehicles was obtained based on the
rough estimation from the second part of the model and the error of the previ-
ous estimate. The model was tested using data from three sequential links
consisting of the three sections of the Lincoln ’Ihnnel (downgrade, level and
upgrade sections). Speed measurements were obtained for every 5 and 10 sec-
onds for examining two different sampling rates, and it was found that the 10
second sampling period produced better results. The model was very accurate
and the percentage of the time that the errors between the estimated value of
number of vehicles and the actual one was less than 10% was greater than

99% for all three sections.

In the above example the model developed by Gazis and Knapp (1971) was
used for estimating flows at time I, based on observations of the input vari-
ables at the same time interval, and no prediction was performed. Neverthe-
less the same model could be utilized for performing predictions of traffic flows
in the short term future. For example, Okutani and Stephanedes (1984) devel-
oped two models based on the discrete the linear Kalman filter, for adap-

tively predicting traffic volumes on the links of a network. They used traffic

33
data from three previous time intervals, and the input vector to the filter con-

sisted of:

(1) observations of traffic volumes on upstream links; and

(2) observations of traffic volumes on the link under consideration.
In one of their models they used observations of the same day for which the
predictions were performed, without any differencing. However, under the
assumption that traffic flow fluctuates in a similar fashion from day to day,
the parameters h(d,t) that were used in this model for the day ((1) and the time
interval (I) were updates of the parameters obtained at the same time interval
one week ago h(d-1,t):

h(d,t) = h(d-1,t)+e(d-l,t) (2.2)
where e(d-1,t) is some noise variable. In the second model, in order to assure
the stationarity of the time series, they difference the observed traffic volumes
at the day under consideration with the ones that were observed one week ago
at the same time interval. By doing so, variations due to both time of the day

and day of the week were eliminated.

The results obtained were compared with those when the UTCS-2 model
(Urban Traffic Control System-second generation) was used. Their results
were always at least 80% better than those of UTCS-2. The model that incor-
porated the one week differencing, always performed better than the one ‘with-
out differencing. In the same study it was found that there was no significant
improvement of the predictions when observations for more than three previ-
ous time intervals were used. The robustness of the models were indicated by
the fact that their performance was not significantly affected when predictions

for times longer than one time interval ahead were obtained.

34
In an effort to explain the existing interrelationship between traffic control

strategies and the resulting traffic patterns, Stephanedes et a1 (1990) devel-
oped a model for predicting behavioral characteristics of traffic flow in real
time. Based on an extended (non linear) Kalman filter their method was used
for prediction of traffic demand at the entrance ramps of a freeway and predic-
tion of diversion of this demand. In this study two models were developed, one
for predicting arriving traffic at the entrance of a ramp, based on historical
information of the same variable, and a second model for predicting the pro-
portion of traffic that enters the ramp. From a previous study conducted by
the authors it was found that the factors that affect the decision of a driver to
divert from entering a freeway ramp are the rate with which vehicles enter
the ramp, the rate with which vehicles enter the freeway, and the numbier of
cars on the ramp. Socioeconomic characteristics of the driver did not appear to
be relevant. Therefore, the second model, which calculates the utility attrib-
uted by the drivers to enter the ramp, relates the entering proportion of traffic
to the ramp with the current freeway entering rate and the number of cars on

the ramp from the previous time interval.

The above models were applied on a freeway corridor in Minneapolis, where
flows approaching freeway ramps, and diversion of freeway demand was pre-
dicted in real time. After implementing the method for a typical weekday it
was found that the average error for the predictions of diverted traffic was
ranging from 5.4 to 8.8%, while the average error of the predictions of the
approaching traffic was ranging from 6.1 to 13.4%. The authors note that the
error of the second model would be smaller if in the model for predicting the
approaching traflic historical information of the upstream traffic was also
included as in Okutani and Stephanedes (1984).

35
A requirement for implementing such adaptive models is knowledge of the

second order statistics of the stochastic process. In the case when no prior sta-
tistics are available, but the estimates must relay only on the available data,
we need to approach the problem of predicting traffic characteristics with dif-
ferent adaptive prediction models. In such models the statistics of the process
are learned by the adaptive processor while the prediction system is in opera-
tion (Papoulis 1984). For example, Lu (1990) used such an adaptive prediction
model for predicting traffic volumes on a road segment. The prediction model
was based on the least mean squares algorithm (LMS), where the estimation
of the coefficients of the linear model is made recursively and it is based on the
latest observations of the input variable (traffic volume) and the instanta-
neous error of the last prediction. The model searches for a set of coefficients
that will minimize the instantaneous error in the gradient direction by setting
to zero the first derivative of the expectation of the squared error, so it can be
seen as a “steepest decent algorithm”. Although this method is simple to apply,
due to the small number of computations, the convergence of the algorithm is
not very rapid in the case of a high perturbation (i.e. due to a traffic incident)

in the input variable.

Alternatively the Gauss-Newton method can be utilized for obtaining the esti-
mations of the parameters of the model that minimize the sum of the squared
errors. The Gauss-Newton method shows faster convergence and as it is
shown by Ljung and Soderstrom (1983) such methods can be more robust in
respect to design aspects of the model. In a different type of problem Nihan
and Davis (1987, 1989) have compared the Newton-Gauss method for estimat-
ing origin destination matrices for freeways segments or signalized intersec-

tions from input-output traffic counts. In their approach the parameters of the

36
model represented the portions of traffic leaving a specific origin and destined

for a specific exit of the freeway segment or leg of the intersection. The param-
eters must obviously satisfy the constraints of non negativity and they must
total to unity. These constraints are not handled directly by the model, but the
estimated proportions are modified in a two stage process (estimation and
adjustment) so they will satisfy the required constraints. The results were
compared with the ones obtained from off line prediction models based on
maximum likelihood estimators, and the ordinary least squares methods. In
all cases the results obtained from the Gauss Newton algorithm were much
better. In comparing the results from two models based on the Gauss Newton
method, one with employing the constraints for the parameters and one with-
out, the models converged in the same proportions, a fact that indicates the

robustness of the method.

2.4 Summary of Literature Review

Due to the alarming rate of increase of traffic congestion in most of the major
metropolitan areas over the last decade, research is focused on procedures for
improving the performance of existing networks with technological means.
Such procedures include the development of route guidance systems.
Advanced route guidance systems should be able not only to navigate vehicles
through a network, but guide them through the most desirable path. A key '
issue, though, of such a system is that the computation of the most desirable

path is based on an estimation of future states of the network.

Several studies have tried to evaluate the benefits of dynamic route guidance

systems and the results range from marginal to improvements of travel time

37
up to 50%. The majority of these studies show that route guidance systems

will not have a great effect on reducing recurrent congestion, but most of the
benefits will accrue during traffic incidents. Factors like traffic demand,
capacity of the roadway system, market penetration level and behavioral
characteristics of the drivers affect the performance of route guidance sys-
tems. Results are based on simulation models where traffic is assigned based

on a user equilibrium.

However, none of these studies have included a model for estimating the
future states of the network, but they try to maintain the status of the user
equilibrium by updating routing suggestions periodically. Models for estimat-
ing future states are based mainly on traffic assignment models, which. are
developed by extending static models to include the time dimension. Such
models treat traffic as aggregated volumes and usually they cannot distin-
guish between equipped and unequipped traffic, and assume that drivers
have uniform information, and thus react in a uniform manner to the prevail-
ing traffic conditions. Therefore it seems that such models will be best applica-
ble when the market penetration of route guidance systems will be relatively

high, and thus drivers will indeed have perfect information.

Alternatively, prediction models based on the time series of the traffic charac-
teristics can be used. Such models, dynamic by structure and readily applica-
ble in real time, have been used mostly for estimating and/or predicting traffic
volumes on roadway segments. Although the potentials of such models are
good, they have not been used in route guidance systems. In this study we con-
sider the application of such a model that can adapt its parameters depending

on input which consists of the current traffic conditions on the network.

Chapter 3

 

Prediction Model of Travel Times

 

3.1 Introduction

The general purpose of this study is to examine the potential of time adaptive
control techniques for predicting traffic characteristics in real time. More spe-
cifically we will attempt to develop a model formulation that is capable of pre-
dicting traffic characteristics under a variety of traffic conditions, i.e. normal
traffic conditions or congested conditions. Under the notion that a prediction
model is a system itself, adaptive control techniques characterize this system
by estimating the system parameters. The key elements of system identifica-
tion is first the structure of the model, and second the estimation of its param-

eters.

Because prediction based on the adaptive system will be performed in real
time, its operation has to be automatic. Therefore, it is essential to have a
good understanding of all aspects of the problem so the structure of the model
can be formulated. The structure of the model may not be readily identifiable,
either because of our limited knowledge of mechanisms describing the system
and the complexity of such mechanisms, or because the system is changing in

an unexpected manner, i.e. in the case of a traffic incident. In this case,

38

39
observed changes in the value of the variables produced by the system can be

used to reconstruct the model. In this study we develop a model which is based

on the observed values of traffic characteristics.

3.2 Operating Framework
The framework for a model incorporating real time adaptive prediction of traf-
fic conditions consists of three subsystems (Figure 3.1):

(1) The traffic network that is equipped with appropriate devices for col-
lecting information regarding current travel conditions;

( 2) The traffic control center that is capable of processing this information,
performing predictions for short term future traffic conditions, and
broadcasting this information back to the traffic on the network; and

(3) The vehicles that are equipped with some special device that enables
them to receive information and evaluate their path towards their des-
tination.

As travel conditions change throughout the duration of the trip, equipped
vehicles would use the latest information to reevaluate their routes at the end
of each link. Once a vehicle has entered a road segment defining a link of the
selected route it cannot divert from that specific link. When it is exiting the
link, it is considered to have a new origin and an optimum route for the
remainder of the trip is recalculated, based on the latest estimates and predic-
tions of travel conditions. Thus, vehicles can divert from the selected path en-
route, if a better path from their current position towards their destination is
calculated. Such diversion from the originally selected route could occur either
because of poor predictions of travel conditions .on the links, or because of the

occurrence of an unexpected incident on one of the downstream links after

4O

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Current'l'raffic Traffic Advisory Center
Conditions
>
Historical Informa-
tion of Traffic Condi-
T tions
Vehicle On Board Computer l .
Predicted Traffic Prediction
Calculation of Minimum Conditions Model
Path from Current Node to <———
Destination

 

 

 

 

 

 

 

 

 

Figure 3.1: Operating Framework for Prediction Model of Travel Conditions on
the Network.

41
departure.

3.3 Structure of Prediction Model

Let the traffic network be represented by a graph G{N ,° L}. The graph consists
by two subspaces, the subspace N that includes the set of vertexes (or nodes)
in the network, and the subspace L that includes the directed arcs of the net-
work, where each arc is represented by an ordered pair of points from the
space N (L c N xN ). Nodes may represent either a junction of two roads or
highway segments, or points where the physical characteristics associated
with each arc change. Arcs represent the physical path (i.e. road or highway
segment) from one node to another, and they will be referred to as links. Obvi-
ously the property which apply to subspace L is:

(i,j)¢(j,i) Vi,jeN

If we assume that the traffic control center is collecting data regarding traffic
conditions on the links of the network in discrete time t=1,2,3, , then such
observations comprise time series data. If the observed value of a traffic vari-
able at time t, used in the prediction model is denoted by x(t), then the
sequence of such observations up to time t can be arranged in a vector:

x‘ = {x(t), x(t- 1), x(1)} (3.1)
Ifmore than one observable variable is used for the prediction of the state of a '
link, we denote such variables as x’1,x‘2, .The model describing the state
that a link (i ,1) is in at time t can be parametrized in terms of a set of unknown
parameters which can be arranged in a vector 0. Then the model will have the

general form:

y(t) = fl6;x‘1,x‘2, ...)+£(t) (3.2)

 

 

 

42
e (01
X (t) Y (I)
—~ Unknown System >

 

 

 

Figure 3.2: Block Diagram of Travel Conditions of a Link

where y(t) is the variable indicating the state of the link at time t, 80) is a
noise term of unspecified character, and f (.) is a known function of

xi, x‘z, and 0. This concept is illustrated in Figure 3.2.

The indicator variable y (t) of the state of the link has to be a variable that can
be directly related to the cost associated with traversing this road segment.
Under the assumption that the aspect that drivers want to minimize is their
travel time, the state of a link (iJ) at time I, will be expressed as the time

required to traverse this link at time t.

3.3.1 Input Variables to the Prediction Model

The input variables to the prediction model, 1:3, 1:3, , can be observations of
either travel times, speeds, or traffic volumes and densities. Measurement of
travel times has the inherent drawback of some delay, since estimations can
be obtained only after a vehicle exits the link. On the other hand volumes and
densities can be estimated as soon as a vehicle enters the link. However, in the
case of congestion, simple volume measurements are clearly not a good choice,
since their usage can be misleading. As is discussed by Mauro (1991), an inci-

dent near the entrance of the link will result in low occupancies but high

43
travel times. In addition, if no traffic is flowing through the bottleneck, no esti-

mation of the travel time of the link will be possible either. Therefore proce-
dures detecting the existence and the length of traffic queues (i.e. image
processing devices) are necessary. Then, based on such information, the travel
time of the link can be estimated based on some impedance function. In the
following it is assumed that the system is capable of estimating current travel

times of all the links of the network.

The value of the parameter vector 0 of the model for a link (U) will be esti-
mated based on the information contained in vectors x}, with k=1,2,... . Let
Thu-)0) be the travel time of link (iJ) at time t to be predicted. The first input
variable to the model will be the past history of the travel time of the link
under consideration (iJ) until time (t-l), so x‘1 = 772,1) . This is under the

assumption that future states of the link are related to current and past states

of the same link.

In addition, there is obviously some relationship with upstream and down-
stream traffic conditions. Perturbations of traffic patterns either on upstream
or downstream links will be transmitted to the link under consideration. For
example upstream traffic events will affect downstream traffic patterns with
some time lag required by the vehicles on the upstream link to reach the
downstream link. Therefore, travel times on upstream links should affect
travel times on subsequent links. On the other hand when the capacity on a
downstream link is reduced below the prevailing demand as a result of a traf-
fic incident or due to recurrent congestion, a bottleneck is created. Such condi-
tions are known to affect traffic patterns not only on the link with the incident
but to the upstream links as well. Figure 3.3 and Figure 3.4 illustrate the rela-

44

 

 

 

 

 

      
 

 

 

 

 

 

155 T r I r I r T
150 ~ ~
’8
145- -
”g .
:5; 140- 1
F Upstream Link
7, 135 r- ..
E
1-
-g 130» ~
5 Do L'nk
125 _ wnstream 1 ‘
120 4 1 1 1 n 1 g 1 1
14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19
Time of Day (Hours)
Figure 3.3: Relation Between the Travel Times of Two Links in Sequence
(Simulated Observations, Sampling Interval 60 seconds)
I“ I Y Y I I I I
{...-i
1400 ~ Downstream Link ; E ‘
.......... 1 ‘.
13 1200 - l : -
g a a
g 1000 - g l _
g E
5: 800 ~ 3 ..
z» s
E 600 F l Upstream Link
a l
5 400 r a
200 - _ _ _ E
06 63 i 73 s 83 5 93 10 103 11
Time of Day (Hours)

Figure 3.4: Relation Between the Travel Times of Tho Links in Sequence with an
Accident on the Downstream Link (Simulated Observations, Sampling Interval
60 seconds)

45
tionship between upstream and downstream traffic. In the first figure where

there are no incident occurences travel time on the downstream link depends
on travel times of the upstream link. In the second figure an incident occurs
on the downstream link at time 09:00:30.2 at which point the relation is
reversed until the end of the incident approximately 15 minutes later, and

downstream travel times affect travel times on the upstream link.

Finally there is a strong diurnal pattern which has to be taken into account.
This pattern is related to the demand level which varies not only by time of
day but by day of week as well. Therefore variable T(,J)(t) is related to some
variable that describes this diurnal pattern, for example the expected travel

time on link (ij) at time I, based on observations of T(i.j)(‘) fi-om previous days.

3.3.2 Model Formulation

For the sake of simplicity in the remainder of this section we shall denote
links with a single character i.e. l = (i J). Under the assumption that the model
for predicting the travel time of link I at time t is linear in its parameters, then
it can be written as:

A(q") . 1,0) = 28k(q‘1)-Tk(t)+ 2 Cp(q'1) - rp(:)+d- i,(:)+e(z) (3.3)
ke I p e 0

where l is the set of links ending at node i, 0 is the set of links starting at node
j, and T,(t) is the average travel time of link I for the time interval I, obtained
from previous days (Figure 3.5). This term is included to express the diurnal
pattern of travel times of link I. The noise term 80) is assumed to be a
sequence of independent random variables with mean value equal to zero. The

terms A, B and C are polynomials of the form:

46

A(q") -_- 1+a,~q‘1+a2-q‘2+...+an'q’" (3.4.a)
Bk(q-l) = bkl ' q—l 4'ka q-2+ ... +bkmt'q-Mk (3.4.b)
and
C (4“) = c -q"+c -q‘2+ +c -q"P (34c)
p p1 p2 ... Prp o o

and q’1 is the delay operator, for example (1'1 - T,(t) = T ,(t— 1) . We will refer
to the first term of equation (3.3) which includes the past history of the travel
times from link I as the autoregressive term, to the term with the history of the
upstream links as the convection term, to the term with downstream link
travel times as the congestion term, while the term with the average travel

time of link I as the diurnal term.

Let 0={k,,k2,...,k0} and E={p,,p2,...,pE} be the elements of the link sets 0 and E
respectively. By introducing vector notation equation (3.3) reduces to:
73(1) = 9“. (p(t) + e(t) (3.5)

where 0 is the parameter vector:

 

Figure 3.5: Link Layout for Prediction Model of Link I - Equation (3.3)

47

T _
8 _ {E21, an, bk,1’ ..., bklmk" b101, ..., bkomto’ CP11’ ..., prl’

.00, p51, one, pErPE,

c c d] (3.6)

and (p(t) is the vector with the observations:

(p (t) =[—T,(t— 1), -T,(t- n), Tk!(t— 1), Tha‘mh)’ Tk0(t- 1),
...,Tko(t—mko), T 1(1- 1), Tp‘(t- rm)’ TPE(t- 1), TP£(t— rp2’% (3.7)

A natural guess of T,(t), denoted as Mr) , will be:
7‘10) = éT- (p(t) (3.8)

where, of course, we need some estimation 0 , of the parameter vector 0. -

Equation (3.8) gives the one step ahead prediction for the travel time of link I.
The t-step ahead predictions are obtained by successively using 1: one step
ahead predictions. Let T,(t+ 1| t- 1:0(t- 1)) be the t-step ahead prediction of
the travel time of link I at time (t + I) based on observations up to time (t - 1),
with the parameter vector 0(t - 1) estimated also based on observations up to

time (t - 1). The t-step ahead prediction will be calculated as:
m.» 1|: —1;é(:- 1)) = é(:-1)T-o(z+ r) (3.9)

where 60+ 1) will be similar to (3.7) but it will include observed values up to
time (t - 1) and expected values after this point. For example consider the sim-
ple case where the model (3.3) is given by:
A(q“) . 1,0) = e(:) (3.10)
then:
0T = [a,, ...,a] (p(t) = [ma-1), ...,-T,(:-n)] (3.11)

48
Ift = 2 then (50+ 1) will be

7P (H 2) = [—T,(t+ 1| t— 1:0(1- 1)), —T,(t1 t- 1:0(t- 1)),—T,(t- 1), —T,(t— n + 2)]

3.4 Prediction Algorithm

The estimation. of travel times will have to be performed on line, so the most
recently observed data will be used by the model (3.8) for the most updated
predictions. Since travel conditions on a traffic network change continuously,
it is necessary to use an algorithm that will update the parameters of the
model as new data become available. Because observations of travel times will
consist of long data sequences, processing of such data by the prediction model
will have to be sequential. Such a procedure is referred to in the literature as
recursive identification or as adaptive algorithm. The significant advantage of
such recursive identification techniques is that computational and memory
storage demands do not increase with time. Available storage memory can be
utilized for the prediction model rather than for storing the data, since we
need to store only the latest data while older data can be discarded (Ljung and
deerstrém 1983).

3.4.1 Time Invariant Parameters
A recursive identification algorithm should be able to identify changes in
travel times as such changes take place by responding to the instantaneous
error defined as:

so) = r,(:)-f,(:) = T,(:)-(‘9T . (p(t) (3.12)
The majority of recursive identification algorithms update the estimation of

the parameter vector by adding some correction to its previous estimation.

49
The correction depends on the discrepancy between the observed travel time

and the expected travel time for the same time interval, estimated based on
the previous estimation of the parameter vector: 1

6(1) = éa— 1) + L(t) 17,11) — éTa- 1) - <p(z)1 (3.13)
where L(t) is the “gain” vector, which regulates the rate with which the predic-

tion error é(r) contributes to the update of 0 .

A common technique for estimating the parameter vector is by using the least
square principle, where the sum of the squares of the differences between the
actually observed and the computed values is a minimum. If we introduce the

loss function VN(0):

Z

. 2 I
me) = 1%, (m) — 911111)] (3.14)
t = 1
then VN(0) becomes minimum when:
N -1 N
0 = [2 (p(t) - 01(1)] - 2 (11(1) - T,(t) (3.15)
t = l t = 1

assuming that the inverse exists. Then with simple calculations we can

rewrite (3.14) in a recursive form:

6(1) = 6(1- 1) +-:- -R’1(t) - (p(t)- [1,(1) - 6111- 1) - 111(1)] (3.16.a)
R(t) = R(t- 1)+%- [(p(t) - (pT(t)-R(t— 1)] (3.16.b)
where:
I
R(t) = Z 1p(s)-<pT(s) (3.17)
s = 1

given that the inverse of R(t) exists. Equation (3.16.a) has the form of (3.13) for
the recursive estimation of the parameter vector 9 , but in each iteration we

will have to find the inverse of matrix R(t). By applying the matrix inversion

50
lemma which states that:

[A+B-C-D]“ = 111-1-111'1-8-[D-A’1.B+C'1]-1-D-A'l (3.18)

and with the transformation:

1
? .
we obtain the following equivalent recursive form for (3.16.a)-(3.16.b):

em = R"(1) (3.19)

9(1) = é(1-1)+L(1)- [T,(1)—0T(1— 1) - 11(1)] (3.20.a)

P0 - 1) - (1(1)
1 + «19(1) - P(t- 1) - (1(1)

 

L (t) = (3.20.b)

P(1— 1) - (1(1) - «17(1) - P(z- 1)

T (3.20.c)
1+<p (1)-P(1—1)-(p(1)

P(t) = P(t-1)-

 

(See Ljung and deerstrém 1983, pages 17-21). The algorithm given by
(3.20.a)-(3.20.c) is the known recursive least squares algorithm (RLS).

3.4.2 Time Varying Parameters

In the previous paragraph the parameter vector was treated as time invari-
ant, with the prediction algorithm trying recursively to estimate the best esti-
mation of 0(1) at time t based on the observations up to time t, according to
criterion (3.14). However, the main reason why we need a recursive prediction
model for guiding traffic in real time, is because the dynamics of the system
are changing with time. Therefore we need to develop a technique to “track”
changes in the system, as such changes occur. Under criterion (3.14) the algo-
rithm given by (3.20.a)-(3.20.c) gives the average behavior of the system dur-
ing the period [0 , t]. In order to obtain an estimate that will be more
representative of the current traffic conditions on link I, we can modify crite-
rion (3.14) so older observations of travel times will have a discounted effect

on the optimum estimation of the parameter vector 0(t) at time t, while more

51
recent ones will be weighted more heavily. An example of such a criterion

would be (Ljung and Stiderstrém 1983):

l
. 2
v,(e) = 2 so, 1) [r,(s) -9T(p(s)] (3.21)

s = 1
where B(s,t) is a function that increases in s for given t. To incorporate criterion
(3.21) in a recursive algorithm we need a recursive formulation for function
[3(s,t). A typical function that is often used is:

B(s,t) 2 Ms) - [3(3— 1,1) = I; h 1(1)] - [3(1, t) (3.22)
j=s+l
where of course B(t,t) is the weight attributed to the latest prediction error,
and 1(1) s 1 for all j. In the case that Mi) = A then function (3.22) has an expo-
nential “forgetting pattern”: .

[3(5, 1) = 7L"‘- [5(1, 1) (3.23)
since the weight that is given to older errors of the model is found by (3.23).
The parameter 7t is chosen so 0 < )1 S 1, and it is referred to as the forgetting
factor. Often the weight attributed to the most recent prediction error B(t,t) = B
is set equal to 1. Using the transformation:

1
R(t) = 2 [3(1, w) - (p(w) - (pT(w) (3.24)

w=l

we get the recursive form of (3.16.a)-(3.16.b):
0(1) = 0(1 - 1) + R‘1(1)- (p(t) - 3- [7,(1) - 0T0 - 1) - 111(1)] (3.25.a) '

R(1) = 1(1)-R(1— 1)+(3-(p(1)-(pT(1) (3.25.b)

Again with P(t) = R'1(t) and in a similar fashion as for (3.20.a)-(3.20.c) we
can get:

9(1) = 6(1- 1) +L(1)- [r,(1)—éT(1— 1) - 11(1)] (3.26.a)

52
P(t- 1) - (1(1)

 

 

L t) = (3.26.b)
( Mt)/B+CPT(t)-P(t- 1) - @(t)
1 P(t-1)-<p(1)-<pT(t)-P(t-l)
p = __ . P _ 1 — 3.26.
(I) W) l (I ) 1(1)/[3+(pT(1)-P(1- 11%)] ( C)

which for Mt) = 1 and B = l coincides with (3.20.a)-(3.20.c). The effect of the for-
getting factor such that 0 < Mt) .<_ 1 is that the matrix P(t) in (3.26.c) will not
tend to zero. The consequence is that the gain vector L(t) will be kept large.
This means that the algorithm will always be alert so it will be able to track
changes in the dynamics of the travel times of link 1. However the compromise
for this alertness of the algorithm is that it becomes more sensitive to the ran-
dom disturbances e(t) of the measurements. For values of Mt) close to 0 the
algorithm will be very alert to changes in the system but also too sensitive to
the prediction errors, while for values of Mt) close to 1 the algorithm will

restrain its tracking capability and it will gain in insensitivity to noise.

3.4.3 Initialization of Prediction Algorithm

For the initialization of the recursive algorithm (3.26.a)-(3.26.c) we need some
initial values for the parameter vector 0(t0) and the matrix P(to). Because we
were based on the assumption that the invert of matrix R(t) exists, the initial
value of R(to) corresponding to P(to) must also be invertible. Usually we can
start the algorithm with to = 0 and an invertible matrix P(0).

The importance of the initial values diminishes with time. This can be seen if

we set equations (3.26.a)-(3.26.c) in a non-recursive form:

t -1 ‘ t
6(1) = [P“1(0)+ 2 B(p(w)(pT(w)] [P"1(0)0(0)+ 2 Bq)(w)T,(w)] - (3.27)

19:] w=1

53
where the effect of the values 0(0) and P(O) decays as the sums increase in

magnitude. Also as P'1(0) —)0 the recursive estimation of 9(t) approaches
the off-line estimation of the parameter vector. Therefore a common choice for
initial values is

0(0) = 0 and P(O) = c-I (3.28)

where c is a large constant number.

3.5 Stochastic Interpretation of the RLS
Algorithm
If instead of criterion (3.14) we choose 0(t) so the variance of the noise term e(t)

is minimized at each iteration then the following criterion results:
1 AT 2
We) = 55 [71(1) - 9 (P(t)l (3.29)
where E[-] denotes expectation. The minimum of (3.29) will be:
d T «T
[76%)] = E<p(1) 1T,(1) - 9 (1(1)) = o (330)

Because the distributions and the moments of T,(t) and (p(t) are not known we
cannot solve (3.30) analytically. An approximation can be obtained if we evalu-
ate expected values with sample means which will result in criterion (3.14).
Alternatively the Robbins and Monro recursive equation can be used where

the solution of the equation EQ (x, e(t)) = 0 is found by:

51(1) = 2(1— 1) +y(t) - Q (2(1— 1), e(t)) (3.31)
where e(t) is a stochastic process of random variables with unknown distribu-
tion, x(t) is a chosen value by the user, Kt) is a sequence of positive numbers

tending to zero, and Q(x,e(t)) is a known function of e(t) and x(t). Applying

54
(3.31) to (3.30) with x(t) = 6(t) we get:

(“9(1) = 0(1- 1)+y(1)-(p(1)- [T,(1)-éT(1-1)1p(1)] (3.32)

which for 7(t) = 7 gives the least mean square (LMS) algorithm. This algorithm
can be seen as the parallel algorithm of a “steepest descent” algorithm for
numerical minimization. Ljung and Stiderstréim (1983) suggest that if we

replace the negative gradient direction:
T 2 ‘1 T
[”510qu with the Newton direction: -|:-a%2-V(0)] - [-%V(0)]

the efficiency of (3.29) is increased significantly. Then the natural variation of

the Robbins and Monro equation will be:

52(t) = 2(t— 1) +70) - V"(i(t — 1), e(t))_l - Q(i(t- 1), e(t)) (3.33)
From (3.29) we get that:
2
fine) = 5111(1) - (9(1)) (3.34)

which is independent of 9, and is the autocorrelation matrix of the observation
vector. Then from (3.34) the autocorrelation matrix can be determined as the
solution R of:

51¢(t)~<pT(z)—R1 = o (3.35)
From Robbins and Monro equation we find that the estimate of gig—:WO), R(t),

at time t will be:

R(t) = R(t- 1) + 7(1) - [e(t) - 07(1)-R(1- 1)] (3.36)
and from (3.33) we get the stochastic recursive estimation of 0(1) based on the
Newton direction:

60) = 9(1—1)+y(1)-R“(1—1)-(p(1)- [T,(1)-éT(1_1)(p(1)] (3.37)

The algorithm (3.36)-(3.37) is the stochastic Newton algorithm. For )(t) = 1/t

55
we get the algorithm (3.16.a)-(3.16.b). If we introduce the transformation:

3(1) = R(t)/7(1) (3.38)

then algorithm (3.36)-(3.37) with simple calculations can be written as:

9(1) = (“9(1-1)+§“(1-1).(p(1). [T,(1)-éT(1— 1)(p(1)] (3-39.a)

 

 

3(1) = K" ”RE; ”(0] .§(1—1)+(p(1)-(pT(1) (3.39.b)
which for 1(1) = ll" ”(1301-le and s = 1 coincides with algorithm

(3.16.a)-(3.16.b).

The interpretation of the RLS algorithm as a stochastic Newton algorithm
reveals some powerful aspects of the method. Convergence is a measure of the
speed with which the algorithm converges or “identifies” the true value of the
parameter vector 0. It is well recognized that the stochastic Newton algorithm
derived here converges much faster than the stochastic gradient algorithm
(LMS), and it is generally more insensitive to the choice of the initial values.
Haykin (1986) reports that the RLS algorithm converges faster than the LMS
algorithm at least by an order of magnitude. By utilizing the inverse of the
autocorrelation matrix the RLS algorithm becomes self-orthogonalizing since it
decorrelates the successive tap inputs. Of course the compromise lays on the
considerably higher computational complexity of the algorithm as opposed to
the LMS one. The computational complexity of the RLS algorithm increases
with the size of the parameter vector M. The number of multiplications
required by this method is 3M(3+M)/2, while for the LMS algorithm it is only
2M+1.

Chapter 4

 

Simulation Model

 

4.1 Introduction

For evaluating the performance of the RLS filter, it was decided to use a simu-
lation model, where vehicular movements on a network would be modeled.
This approach was favored for two reasons: First because real world data of
travel times on a sequence of links for extended time periods were not avail-
able, and second because it was realized that the availability of real time
information about travel conditions (in terms of travel times) to a portion of

drivers will alter the travel patterns on the network .

For the later reason, it became obvious that testing the performance of the
travel time prediction model based on the RLS filter will require the predic-
tion model to be incorporated within the simulation model. Because the usage .
of an existing simulation package would require access to the source code of
the program, in order to make alterations to the path selection routines, as
well as to incorporate the prediction model, it was decided to develop the sim-

ulation model.

Never the less, models already developed were considered to some extent.

56

57
From previous comprehensive studies of previously developed traffic simula-

tion programs (Van Aerde and Yagar 1988a, Underwood 1990), it was found
that the majority of the models were developed for a specific subsystem of the
transportation system, and none except the INTEGRATION model, were suit-
able for applications in IVHS technology. From this work it was deterrrrined
that integrated models, in the sense of incorporating different subsystems in
one model, has clear advantages. For example, individual subsystems could be
identified for the freeway system, the traffic signal controlled network, or the
mass transportation system. This is true since in integrated control, defined
as the simultaneous control of subsystems, each subsystem could augment the
weaknesses of the others, so the whole system would operate in a higher level
than if each subsystem was controlled independently (Yagar 1983). The inte-
gration of freeways and signalized arterials constitute the most plausible
application of such models, and in the INTEGRATION model these two sub-
systems are combined with the interactions between them modelled. (Van

Aerde and Yagar 1988a,1988b).

In the development of our model, integration would be desirable. However, its
complexity, especially when considering semiactuated or fully actuated sig-
nals (the case which tends to be the rule in real world traffic networks), made
it impossible due to time limitations and this task is reserved for the future.
In this simulation model the freeway system, including possibly major arteri-
als, but without consideration of traffic signals, is modelled. This is believed to
be adequate for the purpose of developing the model to examine the applicabil-

ity of adaptive algorithms in travel time predictions.

The option of using a simulation language for a model of this scope (like

58
SLAM-II, or GPSS) was also rejected basically due to the limited capacity of

such packages in their personal computer version (i.e. size of network, number
of entities simultaneously on the network, etc.). Therefore the simulation
model was developed in FORTRAN computing language, so it can run on a
personal computer and includes a real time graphics module. In the following

paragraphs the basic concepts for the simulation model are given.

4.2 Modelling Elements
The basic elements of the system that had to be modelled are the network,
represented by a directed graph denoted as G{N;L} and the entities that

traverse the network.

4.2.1 Representation Of Network In The Simulation

Model

The graph representation of the network consists by the two subspaces, N , the
subspace of the nodes of the graph and L, the set of the links of the graph, as
in paragraph 3.3. In addition to the properties of subspace L, introduced at
that point: V

(1) (ij) :6 (Li) V ij 6 N
we introduce the following properties for the same subspace:

(2) (iJ)e L=>i¢jViJe N

(3) (ty) 6 L :5 there is only one pair of(ij) : (iJ) e L
Property (1) is necessary by the definition of the graph to be directed. Proper-
ties (2) and (3) are utilized for simplifying various procedures in the simula-
tion program, and it is believed that they do comply with the reality of traffic

networks. In case any of these restrictions has to be removed, this can be

59

achieved by introducing a dummy node.

A sequence of links traversed by an entity defines a path, denoted by the set of
links traversed. For example a path with n links will be:
Pathi1—1in+1 = {(11,12) ,(12, 1'3) (in, 1M0} (4,1)

The traffic network is represented to the simulation model through a matrix
graph G{N,’L} in terms of the adjacency of each vertex to any other vertex of
the graph. Such a matrix representation, denoted as A, is called vertex adja-
cency list of a graph G{N;L}, and is defined as:

(1) the rows of the matrix correspond to the vertices of G, and

(2) 0,7 = the f" adjacent vertex to the i‘" vertex if (i J) 6 L.
The matrix A is of dimension n*k where n is the number of nodes in the graph,
and k is the maximum number of adjacent nodes to any node of the graph.
Nodes are labeled with a unique label for each node number, and for simplicity
in the programming of the simulation model, the labels associated with each

node have to be in sequence starting from label 1.

There are three different types of nodes, generation nodes, destination or ter-
mination nodes, and transfer nodes. Vehicles are generated only at generation
nodes, and may exit the network only at destination nodes. Any node in the
network can be a generation or/and a destination node but the label of each
generation and destination node has to be identified to the model. Generation
and destination nodes form two new subspaces of N defined as:

(1) 0 = {i.‘i is a generation node A i e N}

(2) D = {ii is a destination node A i e N}.

Each link of the network (iJ) i ,j e N, is described by a set of variables associ-

60
ated with the traffic engineering properties of the link as well as aspects of

incident occurrences on the link. Links are numbered in the order that they
appear in the vertex adjacency list, for example link 1 is the link from node 1

to node 4, while link 7 is the link from node 5 to node 6.

4.2.2 Representation Of Traffic In The Simulation
Model

The entities that traverse the links of the network represent the vehicles on
the traffic network. Several macroscopic traffic simulation models (like CON-
TRAM or FREFLOW) or signal optimization models (like TRANSYT) repre-
sent traffic as packets of vehicles that move together as platoons, and instead
of tracing individual vehicles they trace the movement of whole platoons.
Another class of macroscopic models simulates traffic flow based on the fluid
flow analogy. Both of these classes of models examine the status of the net-
work and the development of traffic (platoons or fluid portions) in a sequence
of discrete points in time, equally spaced. The microscopic model NETSIM
simulates movements of individual vehicles in great detail, but individual
vehicles do not have specified destinations, and turning movements at the
nodes of the network are prescribed with percentages. The majority of both
macroscopic and microscopic models are able to model recurrent congestion

and reflect the impact of any bottlenecks and the spill back of congestion.

The modelling of traffic flow in a system operating within the IVHS technol-
ogy must be combined with a traffic routing component so traffic having a spe-

cific destination can be directed into the network realistically. Such a

component is present in a few models like INTEGRATION, CONTRAM and

61
SATURN (Underwood 1990). In addition to this, it must be possible to model

traffic holdback due to bottlenecks caused by either excessive demand or traf-
fic incidents, so the interaction of traffic conditions on adjacent links can be

included in the model.

The development of this model was made under these constraints. The model
traces individual vehicles, and each vehicle maintains its identity throughout
the network. By keeping the identity of individual vehicles, it was possible to
assign specific attributes to each vehicle identifiable at any point, as well as to
collect statistics on individual trips. Such attributes include the destination of

the trip, the vehicle type, the generation time, and so forth.

From the point in time that a vehicle enters the network, it is assigned to a
destination node and to a vehicle category. The origin destination matrix,
denoted OD, from all origin nodes to all destination nodes is assumed to be a-
priori known, so each vehicle can be assigned to a destination node stochasti-

cally, based on the percentages supplied in the 0D matrix.

In this analysis two different vehicle categories are modelled, depending on
the type of information that they have available during their trip on the net-
work. The first category replicates the behavior of traffic that is not equipped
with any “smart” device for receiving information regarding the traffic condi-
tions on the network, but they base their decision on selecting their path on
experience they have acquired from past utilization of the network. Such vehi-
cles are characterized as “non-smart”, as opposed to the second category of
vehicles modelled, characterized as “smart”. These vehicles base their path

selection decision process on present as well as projected travel conditions on

62
the network. This second category of vehicles replicates traffic that is

equipped with “smart” devices for receiving and processing such information.
The percentage of vehicles created from each category has to be given to the
model so each vehicle will be categorized as “smart” or “non-smart” at the time

of its entrance into the network.

4.3 Description Of The Simulation Model

The simulation model is discrete and event oriented, meaning that it describes
changes in the system that occur at discrete points in time. The isolated point
in time where the state of the system changes is the event time, and such
changes are dictated by the logic describing each event. Changes in the state
of the system have to occur in a time ordered sequence, and events occur at
prescribed times during the simulation. Therefore the primary function of a
discrete event simulation model is scheduling events in a “calendar” file, so
they will be processed in chronological order, and advance the simulation clock

at the time of the event in execution.

The general logic of the simulation model is depicted in Figure 4.1. The first
step of the model is to read the input data file, containing information about
the network, as well as the starting and ending time of the simulation run.
The run is initialized by setting the simulation clock to the starting time, .
which coincides with the time of the very first event in the calendar. Then the
first event is called for processing, and after it is executed it is removed from
the calendar. The simulation clock is advanced to the time of the next event in
the calendar, and this process is repeated till the simulation clock exceeds the

end time at which point the simulation run is completed.

 

Read Input Data
File

 

 

 

 

I

 

 

Initialize Simulation
Variables

 

 

 

63

 

l‘

 

 

Advance Simulation Clock

 

 

 

    

End of Simulation?

 

 

      
 

  

Is this the
Initial Run?

 

Call Output

 

 

 

 

End

D

 

Execute lst Event
1n Calendar

 

 

1/T

 

 

I Event 1

 

 

   

{Event 2 ..... Event 5

 

 

 

 

Remove lst event
from Calendar

 

 

 

 

 

Figure 4.1: Flow Chart of Main Function of Simulation Program

64
The simulation model is microscopic at the vehicle level. In-link movements of

vehicles are not modelled, but in essence vehicles wait on the link until their
travel time is expired, and then they are transferred to the subsequent link of
their path. In this level of modelling the events that were modelled are:

(1) Updating the minimum path tables of the network,

(2) A vehicle is entering the network,

(3) A vehicle is exiting a link to be transferred to another link, or exit the

network if it has reached its destination,
(4) Start a traffic incident,
(5) End a traffic incident.

Both vehicle types have to base their path selection process on some data base
containing travel time information for the links of the network categorized in
time intervals. While this data base for “smart” vehicles is created and
updated in real-time during the simulation run, for “non smart” vehicles such
information has to be known a-priori, to emulate the past experience concept.
In order to create such a data base, the simulation model is run twice. In the
first run, in which the data base is constructed, all vehicles are considered to
be “smart” and no traffic incidents are created. This concept is shown in Fig-
ure 4.1, where the first run is referred as the initialization run. The second
run is the regular run where vehicles can be from either category, and the pro-
cedure for creating traffic incidents is reactivated. For convenience, the initial
run can be skipped if data about average travel times are available (i.e. from
previous runs of the simulation model for the same network) to be used for the

travel time data base emulating the past experience information.

65
4.3.1 Event 1: Updating The Minimum Path Tables Of

The Network
As was mentioned, the travel time data base for smart vehicles is created and
updated while the regular run is taking place. This process has to be accom-
plished in regular time intervals, referred to as time steps, at which point spe-
cific tasks have to be executed for the proper operation of the prediction
models. Therefore, the basic function of this event is that in each time step the
RLS filter updates the parameter vectors and then performs a prediction of

travel times on the network links, based on the most recent parameter vector.

The first step of this event (Figure 4.2) is to schedule in the calendar the next
call of itself, which will be exactly one time step ahead. Following this, the
average travel times, T031) (k) , on all the links of the network (i j) for the time
step that has just ended (k) have to be computed, so they can be utilized for
the structure of the input vectors to the RLS filter. The travel time of a link is
estimated by the system each time the status of the link is changed. The sta-
tus of the link is considered to be changing whenever:

(1) one vehicle enters the link,

(2) one vehicle exits the link,

(3) a traffic incident starts,

(4) a traffic incident ends and

(5) if there is a queue formation on the link, when the length of the queue

is altered.

During one time step k the average travel time of a link ( i ,i ), 70.1) (k) is calcu-
lated as the weighted average of the values of the travel time that it assumes
due to changes in the link status, T031)“ - 1 +d,,,), where d,,, is the elapsed

time since the start of the last time step, when a new sample measurement

66

 

Schedule Next Call
Event 1

Calculate Average Travel Times

for All Links During
Last Time Step

1

Perform Predictions for a
Number of Time Steps
in the Future

l

Update Minimum Path Tables
from All Nodes of the Network
to All Destination Nodes
for Each Vehicle Category

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

®

Figure 4.2: Flow Chart of Event 1: Update the Minimum Path Tables

67
was acquired. The weights used for the weighted average are the time lengths

for which each sample measurement of the travel time of the link was valid. If
we have M-l changes in the status of the link, this is expressed in the follow-
ing equations:

M
2 T(ij)(k- l +dm) . (dm+l-dm)
m=0 ’ (4.23)

 

TUE/)(k) = M
z (dm+ l — dm)
m=0

where:

M .
2 (drrH-l-dm)
m=0

lTime Step d0 = O dM = lTimeStep (4.2.b)

and

dm+ 1' 2 dm dm S lTime Step Vdm, m e [0, ..., M] (4.2.0)
The next step is to call the filter routine so the parameter vector of the predic-
tion model of each link will be calculated, so predictions for a number of time
steps in the future can be performed. With this information the simulation
model calls the minimum path routine, and constructs the minimum path
tables. The minimum path routine finds the minimum path from every node
in the network to all destination nodes, by considering only time “costs” and
“savings” over alternative paths. This is based on the assumption that drivers

are only interested in minimizing their travel time toward their destination.

It is recognized that other factors affect the final choice of the actual path that
each individual driver is going to follow - like safety considerations, familiar-
ity with the road system, trip purpose and so forth. While it would be possible

to include some of these behavioral aspects in the cost function (instead of just

68
travel time), full account of the drivers decision making process would not be

completely modelled, due to the complexity of such a process. In addition to
this, and most important task in this analysis, the results of the simulation
regarding the performance of the RLS filter in predicting travel times with

adequate accuracy, would be clouded with possibly irrelevant information.

The minimum path routine examines all possible paths from a node i, to a
destination node in, ,. The travel time of each path is calculated by considering
the cost of each link for the entire downstream path, depending on the
expected time of arrival at the entrance of the link (starting node of link). For
example, for the path from node i , to destination node i“, as given in equation

(4.1), the cost of the path is calculated as:

C(‘l 4i...» = 2 T(ii’ii*l) (kj) (4.3.3)

I = 1
where:

k’l = O kIj+l = klj+T(i,.i,-.1) (k1) kj = [k2] +1 (4.3.b)

and 7(1), 5+1) (kj) is the expected travel time of link (ij,i,-,,) at kj time steps
ahead. The brackets in (4.3.b) denote the integer part of a real number. Equa-
tion (4.3.a) takes into account the dynamic nature of the traffic network. For
“non smart” vehicles the cost of a path is calculated in the same manner, but
instead of using the expected travel time of the links included in the path, the

travel times as calculated in the initial run are used:

n

(hm...) = int-1.1) (41') (4.4.a)
j=1

C

where:

69

, _ CurrentTime 1 _ 1 — _ 1
1 — Timelnterval qu - q1+T(‘r ‘11:) (q!) q} _ [q1l+l (4.4.b)

 

and T (1,. i,.,) (qj) is the average travel time on link (i,-,i,+,) at the q, time
interval. Here it should be noted that the time interval q has a different
length than the time step k used in equation (4.3.a). Thus, the value of q can
be large enough, so the classification of travel conditions on the links of the
network in the memory of the “non smart” driver would be reflected. Because
of the way path costs are calculated (equations (4.3.a) and (4.4.a)), static
shortest path algorithms (like Dijkstra’s or Dreyfus’ algorithms, the label cor-
rection method, the label reaching method or the recursive -fixing method)
could not be applied. This becomes obvious if we let YiJ be the minimum time
to travel from node i to j and T0,,” be the cost to travel link (kj). Note that Y,-,-,
and TM) are not dependent on the time that the vehicle starts the trip or it
enters the link, since in this case the network is considered to be static. In a
network with M nodes, the basic principal of such algorithms is (Romeijn and
Smith 1990, Hall 1986):

Y,- = min.

I j¢l{ylk+T(k,j)} for k = l,...,M (4,5)

The underlying meaning of this principal is that the optimum path towards a
node - for example node j - is also optimum for the nodes contained in it - for
example node k (Kaufinan, and Smith 1990). However, in a dynamic network,
such as the one that we have to model, the fastest path to reach a node (k) may
not be the fastest path if the ultimate destination is a subsequent node (1).
since the cost of link (kJ) may be significantly larger if we reach (k) early than
if we reach it a few time units later. This is illustrated in Figure 4.3, where we
can reach node 4 via paths {(1,2),(2,4)} and {(1,3),(3,2),(2,4)}. Although the
shortest path to reach node 2 is {(1,2)} with cost 10 time units, the total cost to

7O

 

 

1:0

10 10
1 10 2 3O .6)
1:10

10 10

 

 

t=20

 

 

10 2 10 ’6)

Figure 4.3: Violation of Principle of Optimality in Dynamic Networks

71
node 4 if we arrive at this point in time 10 is 40 while if we arrive 10 time

units later it will drop to 30.

In a more dynamic approach Cooke and Halsey (1966) tried to solve the prob-
lem by starting from the destination node and considering the shortest path to
reach it progressively towards the starting node. However, they still consid-
ered fixed travel time. Hall (1986) has suggested a method for networks with
time varying random travel times that are boundable from below, by combin-
ing a branch and bound technique with an M shortest paths algorithm (algo-
rithm that finds the M best paths between two nodes). This method would
only have advantages (in terms of computational effort) over an exhaustive
search if the computation of the expected travel times of paths is difficult. In
our model expected values of travel times are produced by the RLS filter any-

way.

Kaufman and Smith (1990) suggested a modification on Dreyfus’ algorithm so
it could be used in dynamic networks. This was achieved under the assump-
tion that each intermediate node of the optimum path has to be reached as
early as possible. In this algorithm costs are time variant, but they must sat-

isfy (under the assumption stated above) the following restriction:

where T,-,'(s) is the cost of link (iJ) at time s. This assumption is necessary to
avoid the case described in Figure 4.3. It is argued that it is not too restrictive

because driver behavior is not changing in such a dynamic pattern.

In order to avoid such assumptions which may not be valid in the case of non

72
recurrent congestion, and to cover cases like the one described in Figure 4.3,

the only feasible solution appears to be an exhaustive search of the cost of all
possible acyclic paths from a node towards a destination node. The term acy-
clic path is used to indicate that paths where vehicles circle in a loop waiting
for the cost of a subsequent link to drop are not allowed. This is accomplished
by using a depth-first algorithm for identifying the possible paths, and as soon
as a path is identified its cost is computed with equations (4.3.a) or (4.4.a).
This cost is compared with the cost of previously identified paths towards the
same destination and if it is found to be smaller it replaces the old value. This
process continuous until all possible paths are evaluated at which point the

minimum paths in the dynamic network are found (Paull 1988).

After the establishment of a better path the two first nodes of the path,
excluding the starting node, are kept in memory. This is done for all the nodes
of the network for both vehicle categories, so two sets of minimum path tables
are constructed, on for each category. Each set of tables consists of (i) the first
node matrix, denoted F c, with c=1,2 (for each vehicle category) and defined as:
(1) The rows of the matrix correspond to the nodes of the network, and the
columns correspond to the destination nodes,
(2) f},- with i 6 N and j e D, is the first node of the minimum path to be fol-
lowed if the trip starts at node i and has destination the node j,
and (ii) the second node matrix, denoted SC, and defined as:
(1) The rows of the matrix correspond to the nodes of the network, and the
columns correspond to the destination nodes,
(2) 3,,- with i e N and j e D, is the second node of the minimum path to be
followed if the trip starts at node i and has destination the node j.
These tables are used as reference during the following time step, and they

73
are updated in each time step. While the significance of the first node is obvi-

ous since it indicates the link to be followed immediately after arriving at the

end of a link, the importance of the second node will be discussed later.

4.3.2 Event 2: Entrance Of Vehicle In The Network

The logic describing event 2 is shown in Figure 4.4. As soon as a vehicle enters
the network from one of the generation nodes, the next vehicle generation at
the same node is scheduled. In this way, the model does not need to keep in
memory all the entities to be created until the end of the simulation run, but

only those that are on the network.

To capture the dynamic nature of traffic networks, in terms of traffic demand,
a dynamic generation rate (rate with which vehicles will be entering the net-
work) was utilized. Such dynamic behavior was reflected in the modelling pro-
cess by utilizing generation rates that are dependent on the time of the day.
Arrivals are created according to a Poisson distribution (exponentially distrib-
uted interarrival times), with parameter based on the demand level at the
current time of the simulation clock, while the demand curve of each genera-

tion node is assumed to be known apriori.

Following the scheduling of the forthcoming vehicle from the current genera-
tion node, the entering vehicle was assigned to a link, thus increasing the
number of vehicles currently traversing this link. The selection of this link is
done by referring to the minimum path tables created in event 1. Based on the
vehicle category c, the entering vehicle is assigned to the link defined by the

entering node and the node f,,- from the first node matrix F c, where i is the

74

 

Update Number of Vehicles
Generated from this Node

1

 

 

 

 

 

Find: Destination Node &
-Vehicle Type of Next Arrival

 

 

1

Schedule Next Arrival from
Current Generation Node

 

 

 

 

 

 

Find lst and 2nd Link of the
Minimum Path.

 

 

 

Enter from

k‘ k Event 3

Increase Volume of lst Link

1

Check if Vehicle Creates
Congestion on the Link.

 

 

 

 

 

 

 

 

 

 

 

 

Check if Vehicle Creates
Accident on the Link.

1

If There is a Queue (due to an
Accident) Check if Vehicle
will Join the Queue.

1

Calculate Exit Time of
Vehicle from the Link and
Schedule the Exit Event

1

Update Measurement of
Travel Time for Current Link

1

Update Plot of Current Link

®

Figure 4.4: Flow Chart of Event 2: Entrance of a Vehicle in the
Network

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

75
entering node and j is the destination node. In addition to this, the second

node of the current optimum path towards the destination j, 5,,- from the sec-

ond node matrix, is stored as an attribute of this vehicle.

As was mentioned earlier, the traversing of a link by a vehicle is simulated by
storing the vehicle on the link for a period of time equal to its travel time. The
remaining functions performed in this event have as a goal the computation of
travel time on the link. These functions are executed not only when a vehicle
enters the network but also each time it is transferred to a link from another
link. The calculation of the travel time is based on the Bureau of Public Roads

travel time function, shown in the following equation (TRB SR165):

 

T

-FFTT - 1+015- 11m) 4 (47)
(1.1) ‘ (1.1) - -

C (1, 1)
where TM) is the travel time of the link (i ,j), F F 77”,,- J) is the Free Flow Travel
Time of the link, and WC is the volume over the capacity ratio for the link. Free

flow travel time is defined as the time required by a vehicle to traverse the

link if this vehicle is the only one on the link.

To make the above equation usable for our purposes, we introduce two new
variables to replace v and c in equation (4.7). First the Occupancy (0CC(;J)(t))
of the link is defined as the number of vehicles traversing the link at a specific
point in time. Thus:

0CC(,-,,-)(t) = v0.1) (t) - dt (4.8)
The second variable is the Free Flow Maximum Occupancy (FFM0(,-J)) of the
link, which is defined as the maximum number of vehicles that can “fit” on the
link at any point in time, and have traffic still move freely. Since capacity (c) is

defined for a given time period, F F M0 can be regarded as the instantaneous

76
capacity or:

From (4.8) and (4.9) equation (4.7) can be written as:

 

OCC ,- (t) 4
"” N (4.10)

Equation (4.10) does not take into account delays due to queuing, and it is
operational until traffic flows with some minimal speed. As the occupancy on
the link increases so does the travel time, and when the link approaches the
congestion state small increases in the occupancy result in significant
increases in the travel time (Figure 4.5). In order to prevent excessive travel
times due to unrealistic occupancies, it was assumed that the maximum occu-
pancy that a link can handle is twice the free flow maximum occupancy. As
shown in Figure 4.5, this will result in a travel time at capacity that is 3.40
times greater than the free flow travel time, while when the occupancy is
equal to the free flow maximum occupancy the travel time is increased by 1.15
times the free flow travel time. The factor which sets the ceiling in the occu-
pancy of the link, denoted as fm, is a parameter of the model and can be

altered by the user.

When a link is in the congestion status, it can exit only when the occupancy on
the link drops back to 1.70 times the free flow mardmum occupancy. This fac-

tor, denoted as fine, is also a parameter that can be altered by the user.

Therefore, the first step after a vehicle is assigned to a link is to determine
whether or not this vehicle will congest the link that it just entered. Ifit does,

then the link is assumed to be closed and no other vehicle is allowed to enter

77

3.;

.532... 1m
1.:— 2: :e woman 353.590 ...—5 ...—a 251—. .389 3:5 5950: 3:28:23— "mé 95E 1“—

ap. «8:. Each. 30E 8E Co 3.38:.
61—..5 ch10 chum 01—h? OPHM GLEN 61—1 — Avg—HO

 

 

« A) —

sham

352W

 

 

 

O:

m.—

Wm

(Kouednooo umunx'eui mom 991:1)/(1(ouednooo)

78
until the link leaves the congestion status.

The next step is to consider if the entering vehicle is about to create a traffic
incident. A traffic incident can be caused only by a vehicle, and if there are no

entities traversing a link, the probability of having an incident is zero.

Two types of traffic incidents are assumed to occur in this model (although
more types could be included): traffic accidents which result in the complete
blockage of the link, and vehicle breakdowns which result in partial blockage
of one lane of the link. The probability of a vehicle causing a traffic accident
Pa, the probability of causing a vehicle break down 1%, or the probability of not
causing any incident P0, along with the average duration of each incident type
are assumed to be known for each link of the network. Obviously Pa+Pb+P0=1.
In this analysis the probability that a vehicle will create an incident is
assumed to be 0.00010/lane-mile, from which 80% of the incidents that occur
are vehicle breakdowns and 20% traffic accidents. This ratio of traffic inci-
dents is obtained from the result reported by Guiliano for high volume urban
freeways (Guiliano 1989). The probabilities used are higher than real accident
rates, but this was done intentionally, so there will be some incident occur-

rences on the network within a single simulation run.

After the entrance of the vehicle in a link, a multinomial random variable
(Pa,°Pb,'Po) is constructed to determine if the vehicle will indeed cause an inci-
dent, and the type of the incident. If an incident is about to be initialized, the
point at which the vehicle causes the incident on the link (RLOC) as a percent-
age of the length of the link is found. This is also a random variable, uniformly
distributed with U[0,1]. The starting time of the incident depends on the per-

79
centage of the length of the link that the vehicle has travelled before the inci-

dent. The average duration of each incident type is assumed to be different, as
vehicle breakdowns, although less serious in severity and capacity reduction,
may last longer due to lower priority for service by emergency units (Koutso-
poulos and Yabloski 1991). Due to the great variance in incident duration it
was thought reasonable to assume that the distribution of the duration of traf-
fic incidents is exponential, with parameter known. The start and the end of
the traffic incident are scheduled as separate events in the calendar of the
simulation. Because of the memory requirements, and the complexity of mul-
tiple queue formations on the same link, it was assumed that the occurrence
of two incidents of the same type on the same link simultaneously is not
allowed. This is not too restrictive, since the probabilities of having an inci-

dent is already very small.

If the occurrence of a traffic accident has been initialized on the link, the link
is assumed to be completely blocked, and a queue starts forming behind the
point where the accident occurred. Upon the entrance of a vehicle in the link,
in the case that a queue exists on the link, a check is made to determine
whether or not the vehicle will join the queue. If the vehicle is the one that
causes the accident then it will also be the one that initializes the formation of
the queue. After this vehicle, each vehicle that enters the link is checked to
determine if it will reach the end of the queue before the formed queue has

dissipated.

Ifthe vehicle entered the link at time t then the time required to reach the end
of the queue (TRQ) is calculated as a percentage of the free flow travel time of

the link, as if all vehicles entering before the one under consideration, have

80
already joined the queue:

(4.11)

 

QUJ) (I) J

TRQ (1) = FFTTUJ) ’ (RLOCU'I) - FFM0(1,-) 'fmax

where Q(,-J-)(t) is the length of the queue on link ( i ,j) at time t. This technique
produces somewhat shorter travel times for the vehicles to reach the end of
the queue, but the differences are considered to be insignificant and it simu-
lates the worse (fastest) case scenario for reaching the end of the queue. Con-
sidering the time that the accident will end, the current time of the
simulation, and the time to reach the end of the queue we can deterrrrine if the
queue have started to disperse when the vehicle reaches the last car in the
queue. If the queue has started dissipating, we need to examine if, at the point
in time that the vehicle reaches the queue, there is any queue left. The time
required for the formed queue to be dissipated at time t, is calculated simply
as:

rd'Q(;,j)(I)

L (4.12)

T44“) =

 

(i1!)

where rd is the queue dissipation rate. rd is a parameter defined by the user
and in this analysis is assumed to be equal to 4.8 sec/veh. By comparing the
time required to dissipate the queue with the time to reach the end of the
queue we can determine if the vehicle will join the queue or not. If the vehicle

is going to join the queue the queue length is increased by one.

In the situation of an accident on the link, the number of vehicles that occupy
the portion of the link behind the point where the accident occurred, is
checked to see whether it has reached the maximum capacity of this portion of

the link. If so, the link enters the congestion status and no other vehicle is

8 1
allowed to enter the link.

After completing these checks, the travel time of the vehicle is calculated. As
was mentioned, the travel time calculated by equation (4.10) does not take
into account delays due to queueing or delays due to accidents, so these delays
have to be added to the travel time calculated by equation (4.10). When a vehi-
cle breakdown occurs, it is assumed that the only effect that it has is to reduce
the free flow maximum occupancy of the link (or equivalently the capacity of
the link) for the duration of the incident. If at time t there is a vehicle break-
down half a lane will be closed, so the fi-ee flow maximum occupancy of the

link will be reduced by a factor a(t), where:

 

(Lij — 0'5 ) if there is a vehicle break down on link (ty)
0 (1) _ L11 ‘
. . . . . (4.13)
1 if there IS no vehicle break down on link (1,1)
Therefore, equation (4.10) takes the form:
T FFTT (1 015 OCC“) (I) 4)
+ Tacc([) + qu (t) (4.14)

where Tacc( t) is the remaining duration of the accident at time t, if there is an
accident occurrence on the link. Note that Tacc( t) will be added to the travel
time of an entering vehicle even if the accident has not started yet, but a vehi-
cle that has already entered the link is about to cause the accident. In this
case the full duration of the accident is added. Further more, in order to con-
trol the rate with which vehicles exit the link the exit time form the same link

of the previous vehicle is recorded, and if the difference between the scheduled

82
exit of this vehicle minus the scheduled exit time of the previous vehicle is

smaller than a threshold value w, the travel time is increased so this differ-
ence will be equal to w. Such a threshold value, which represents the headway,
is assumed to be fixed at one second per lane. Then the exit of the vehicle is
scheduled in the calendar of the simulation based on the current time of the

simulation clock and T(,-_ j)( t):

P
T - =
11.1 , (4.15)
Tprevious + W If Tprevious—T(i,j) (t) - t < W

where Tan, is the exit time of the vehicle from link (i ,l), and Tpmm, is the exit

time of the previous vehicle from the same link.

To simulate the way that the system control center is measuring the travel
time of the link, (so the average of the travel time in each time step utilized by
the prediction model can be calculated) equation (4.14) has to be modified.
Under the assumption that the network system is equipped with detectors
and counters, so current occupancies, length of queues and vehicle break-
downs are detectable immediately, the only variable that will still contain
some uncertainty in equation (4.14) is the remaining duration of the accident.
The remaining duration of the accident will be calculated as the conditional
expectation of the duration of the accident, given that it has not ended yet. .
Under the assumption that this duration is exponentially distributed the
expected remaining time is equal to the mean of the distribution. This is due
to the well known “memoryless property” of the exponential distribution (Ross
1985). Thus for the calculation made by the system control center, T4660) will
be replaced by its expected value, denoted with a tilde:

83

E [d ( ,1.) ] accident has started and has not ended yet

T 11.10) = . (4.16)
0 otherwrse

where E[d(,-J-)] is the expected duration of an accident for link (i,j). If the acci-
dent has not started yet then Ta“. is equal to zero (no effect before the start of

the accident).

4.3.3 Event 3: Exit Of A Vehicle From A Link

After the completion of the travel time of a vehicle on a link, the vehicle is
transferred to a subsequent link towards its destination node. When a vehicle
is about to exit its current link there are several functions to be executed to
check if the vehicle is able to leave this link, and to determine which link it

will be transferred to.

As was described in event 2, queues can be formed because of an accident.
Besides accidents, recurrent congestion can cause formation of queues on the
network, and this aspect has to be included in the model. Generally, when a
vehicle tries to exit from its current link to another one, and the new link is
blocked, then this vehicle will start the formation of a queue right at the exit
point of its link. Such a queue is discriminated from a queue created due to
accidents which can start at any point on the link, and thereafter will be

referred to as congestion queues.

The procedures followed in this event are depicted in Figure 4.6. Before the
vehicle exits the link a check is made to’determine if there is a congestion

queue on the link, and if the exiting vehicle belongs to this queue. If it does,

 
     
     
  
    
  
 
 

 
 
 

Congestion Queue
on the Current Link?

Vehicle is in the
Queue ?

 

 
 

Link is
Congested 7

 

Find the lst & 2nd Link of
the Minimum Path

New Link
Congested ?

  
 

  

Congestion
Queue on Old
Link ?

 
  

84

 

Reschedule Exit from
Current Link after End
of Congestion Queue

 

 

 

t

 

Increase Congestion Queue I

 

 

 

 

 

 

Update Measurement of
Travel Time of Exiting ‘
Link

 

 

Update Measurement of
Travel Time of Link

Goto Event 2
Step it 5

 

 

Reschedule Exit from
Old Link after End
of Congestion on New Link

 

 

 

Reschedule Exit from Congested

 

  

Destination
Node ?

     
   

Collect Statistics
Destroy Vehicle

     

 

Correct Volume of
Old Link

Update Measurement of
Travel Time of Old
Link

Figure 4.6: Flowchart of Event of Exit of a Vehicle from a Link.

Link for all the Vehicles in the Queue
after the End of the Congestion Queue

 

 

 

 

 

 

 

 

 

85
then the exit is rejected and the vehicle joins the end of the congestion queue.

In this case the exit time of the vehicle from the current link is reevaluated as:

I“
d

Tnewexit : Tprevious+ L(- _) (4.17)
1,}

where the second term takes into account delays due to dissipation of the vehi-
cles from the queue, and Tpmms is the exit time of the vehicle in front of it in
the congestion queue. If the vehicle belongs in the congestion queue then it
may be allowed to exit, if the new link that it will be assigned to is not in the

congestion status.

In the case that the vehicle exits the link, then the occupancy of the link is
reduced by one. If the link that the vehicle just left was congested and/or if
there was a congestion queue on this link, then these variables are also
reduced by one. In the case that the link is in the congestion status the
reduced occupancy is checked to see whether it is low enough to terminate the
congestion status on the link. Following the exit from the current link a check
is made to see if the vehicle has arrived at its destination node. If the current
node is not the destination of the vehicle then is assigned to a new link, and
the second part of event 2 is executed for this vehicle and the new link. On the
other hand, if the vehicle has arrived at its destination, statistics regarding its
travel time are collected and the vehicle is removed from the network and
deleted from the simulation calendar. Information on the path that the vehicle

followed is not collected because of the large requirements for memory.

If the new link that the vehicle is assigned to is already in the congestion sta-
tus then the vehicle cannot exit its current link, and it starts forming a con-

gestion queue. In such a case there are two possible situations: (1) The old link

86
does not currently have a congestion queue, and (2) The old link already has a

congestion queue. In the first case the exiting vehicle will start the formation
of a congestion queue and it will reschedule its exit, depending on the time
that the link to which it was assigned to, but could not enter, will exit the con-
gestion status. For example, if the vehicle was on link (ij) and it is assigned to
link (j,k) which is congested, then the new exit time of the vehicle from link

(i ,j) is calculated as:

rd

T = TU,k)free + L— (4.18)

newexit . .
(1.1)

where th1k)free is the time that link (j,k) will exit the congestion status. In the
second case the exiting vehicle will trigger the rescheduling not only of its_own
exit from the link, but the exit of all the vehicles from the current link as well.
Again the exit time of the first vehicle in the queue will be calculated by equa-
tion (4.18), while subsequent vehicles will be scheduled to exit based on equa-
tion (4.17).

Each time that a vehicle exits a link the status of the link is changed. There-
fore, the current travel time of the link has to be reevaluated so it can be uti-
lized in the calculations of the average travel times. Two additional terms
have to be added to equation (4.14), so delays due to congestion queues and
delays due to congestion on successor links will be taken into account. Delays
due to congestion queues are calculated in a similar fashion as in equation
(4.12). For the calculation of delays due to congestion in a subsequent link, the
time that the new link will exit the congestion status is utilized, as in equation
(4.18). Thus, for the calculation of the current travel time of a link (ij) as the
system control center perceives I“),- (t) , it will be given by the following

expression:

87

4

,, 0CC(,-’j)(t) ..
T(,-,,3(t) = FFTTWY 1+0'15(FFM0(,D-a(1)l +Tacc(t)+

 

+ qu(1)+ chdu) + TC (1'. k) (I) (4.19)

where 7144(1) is the delay due to congestion queues and de,k)( t) is the delay due

to congestion to the successor link (j,k) at time t. These variables have value if

there is a congestion queue on the link.

In the case that the vehicle is allowed to exit from its current link (there is no
congestion queue on the link or the vehicle is in the top of the queue if such a
queue exists) the model has to decide to which successor link the vehicle will
be assigned. The selection of the remaining path towards its destination node
is made in a time adaptive fashion. This means that, each time the vehicle
reaches a new node, new information is acquired, so its path towards its desti-
nation is reevaluated. The decision process of selecting the next link of the

path is depicted in Figure 4.7 .

A first indication of a possible next link is acquired from the first node matrix
F c for the appropriate vehicle category, from the minimum path tables of the
network. The link defined by the end node of the current link i and the node f,-,-
of the matrix F C, where j is the destination node of the vehicle, will be referred
to as the new link for simplicity. If the new link has entered the congestion -
status in the last time interval, then the minimum path from node i to node j
is reevaluated and the first and second nodes of the new minimum path
replace the corresponding elements of matrices F c and Sc. This step is applied
for both vehicle types, since it is assumed that even “non smart” vehicles are

able to detect if the next link of their path is blocked. This way vehicles will

88

      
   
   
    
 
     

Current Node =
Destination Node ?

 
 
 

Congestion on
lst Link of New
Path ?

 

Recalculate Minimum Path
from Current Node to Destination
& Set this as the New Path

 

 

 

 

 

 

Yes

  

1st Link of New Path =
= 2nd Link of Old Path ?

 

l

 

 

  
   

  

Are Travel Time

Savings Significant 1) . ISI Link=2nd Link Of Old Path

2nd Link=2nd Link of New Path

 

 

 

 

 

 

lst Link=1st Link of New Path
2nd Link=2nd Link of New Path

Figure 4.7: Flow Chart of Selection of Next Two Links of Path

 

 

 

 

89
not start forming congestion queues if there is an alternative path more

attractive than the one with the congested link.

Vehicles should not change paths for very small gains in their travel time. If
vehicles always followed their minimum path, then the new link would be the
one to which a vehicle would be assigned. But, the assumption that drivers are
willing to change paths along their way in pursuit of any gain, no matter how
insignificant, is too extreme, and as suggested by Mahmassani and Chen
(1991), the driver’s switching behavior exhibits a rather bounded rational
character anchored in his current path. In this model a relative indifference
band similar to the one developed by Mahmassani and Jayakrishan (1990)
will be utilized:

1 if Yom- Ynew>max{01' Yawn}
8 = (4.20)

0 otherwise

where Yold is the travel time from the old minimum path, I’m is the travel
time of the new minimum path, otis the relative indifference band as a per-
centage of its remaining travel time from the old path to its destination, and r
is the minimum gain over the old path travel time, required to change from
the old path to the new. The vehicle will switch to the new path if 8 is equal to
1, and it will not if 8 is equal to 0. Parameters or and r can be specified for each
vehicle category individually, but for simplicity in the application runs of the
model they were kept equal.

The prevailing requirement for rule (4.20) to be applicable is knowledge of the
old minimum path. Because of memory restrictions, the entire path selected

at each node for each vehicle in the network, could not be kept in memory.

90
Therefore it was assumed that if the first link of the new path is the same as

the second link of the old path, the two paths are equal. In the case where
these two links are not the same, it is obvious that the two paths are not the

same.

Thus, the new link will be compared with the link defined by the nodes 15,- and
3,,- which the vehicle had kept as attributes when it entered the link that it just
traversed. If these two links are the same then it is assumed that there is no
change in the path and the vehicle is assigned to the new link. If the two links
are different then rule (4.20) is utilized to define if the time saving from the

new path is significant.

4.3.4 Events 4 & 5: Start& End Of A Traffic Incident

A traffic incident is defined as any event that causes non recurrent congestion
or a reduction in the flow rate. The effects of traffic incidents may vary signifi-
cantly from complete blockage of a link to vehicle breakdowns blocking only a
portion of a lane. The duration of such incidents depends on the severity of the
incident, as well as the placement of emergency units. The importance of sim-
ulating traffic incidents is evident, if we consider that benefits of ADIS will be

greatest during the occurrence of such events.

As was described in event 2, when a vehicle enters a link it is examined to see
if it will cause the initialization of a traffic incident. In the case that it does
initialize an incident, the incident will not start immediately but after some
random portion of the vehicles’ travel time has elapsed. At the point in time

that the incident starts the parameters of the link on which the incident

91
occurs have to change. Depending on the type of the incident, the effect is

reflected in the travel time equation, as reductions in the free flow maximum
occupancy (by the factor a(t)) in the case of a vehicle break down, or as delays,
that are additive to the travel time of the link (delays due to queues qu(t)) in

the case of a traffic accident.

When the incident ends, the free flow maximum occupancy assumes its origi-
nal value in the case of a vehicle break down, or in the case of a traffic accident
the process for dissipating the queue formed behind the location of the acci-
dent is initialized. In the case that the queue formed behind the location at
which the accident had blocked the link, the link is in congestion status. In
this case the new length of the queue is examined to see whether it is short

enough for the link to exit the congestion status.

The basic modelling protocol of traffic incidents on the link of the network is
as random events. To be able to compare the results of two different runs of
the simulation model with different model parameters, it was necessary to be
able to create traffic incidents at exactly the same points in time in both runs.
Thus in addition to the random traffic incident occurrences, the model also
has the capability to preschedule traffic incidents from the beginning of the
run. In the case that the option of random traffic incidents is selected, the
characteristics of the incident (starting and ending time, link on which it
occurs, type of incident, and location of incident along the link) are written in
an output file. If the prescheduled incidents option is selected the random gen-
eration of incidents is disabled, and the start and end of the incidents are

scheduled in the model calendar from the beginning of the model.

92
4.4 Conclusions from the Development of the

Simulation Model

The development of the traffic simulation model for testing travel time predic-
tion models was presented. The model is a microscopic event oriented simula-
tion model, where individual vehicles are traced throughout their traverse on
the network. The model is developed in modular structure, so the various
model components can be accessed independently, and additional extensions
of the model will be relatively easy. This is especially true for the travel time
prediction component of the model, where different models can be tested by
simply supplying the appropriate routine that includes the prediction algo-

rithm.

Traffic enters the network through generation nodes, and is directed to move
toward a destination node, prespecified for each vehicle. Along their trip, vehi-
cles reevaluate their path at the nodes of the network, based on the most
recent information about traffic incidents, delays due to queues or congested
links. This way traffic is assigned on the network based on the most recent
minimum path toward their destination. By reevaluating the path of each
vehicle at each node based on updated travel time data, a continuous dynamic
equilibrium network is emulated. Currently all the nodes of the network are
regarded as decision nodes where vehicles can divert from the originally cho-

sen path toward their destination. An option that is reserved for future exten- I
sions of the model is to have only specific decision nodes (i.e. signalized
intersections where the installations of broadcasting devices for the predicted
travel times is more likely). This could be helpful, especially in the first steps
of implementation of IVHS technology, when the infrastructure will be more

scattered.

93
Each vehicle may be one of the two vehicle categories, “smart” and “non

smart”, that are currently modeled. Depending on the category that the vehi-
cle belongs to, it has access to a different data base of travel times on the net-
work. If the vehicle is “smart” then it has access to real time information
regarding travel conditions on the network. Otherwise the vehicle has access
to information built in an initial run of the simulation model, reflecting the
experience that such drivers acquire by using the network. “Non smart” vehi-

cles though are allowed to divert to better routes when links are blocked.

Currently drivers are assigned to paths by utilizing an indifference band for
shifting to a better path from their original path. The path that a vehicle fol-
lows is defined as a sequence of only two links, the one that is assigned to,’ and
the one right after. Instead of the indifference band, the two or three best
paths could be found with an M-shortest path algorithm, and a utility function

used to randomly assign vehicles to one of these paths.

Although the model is (considered to be adequate for this research effort, a
number of modelling aspects remain to be further validated and calibrated.
Such aspects include the factors for entering and/or exiting the congestion sta-

tus on a link and the queue dissipation rate.

Chapter 5

 

Application of the Prediction
Model

 

5.1 Introduction

As was mentioned previously, the purpose of this study is to examine the
potential of the recursive prediction model presented in Chapter 3 when
applied in a real time route guidance system. The performance of the predic-
tion algorithm will be measured by the error of the predictions for one as well
as many steps ahead, for a variety of traffic conditions. The simulation model
presented in Chapter 4 will be utilized where a portion of the simulated traffic
will be guided toward its destination based on the on-line predictions per-
formed by the travel time prediction routine. The rest of the traffic chooses

their routes based on past experience on travel through the network.

Because of the interrelations between traffic patterns in a traffic network and
availability of traffic information regarding future travel times, the prediction
algorithm will be tested for a variety of percentages of traffic with access to
the predicted travel times. In addition, different time intervals between

updates of forecasted travel times will be utilized, to examine the effect of the

94

95
frequency of updating information on travel times and the reliability of pre-

dicted travel times.

5.2 Test Network

The network that was utilized for testing the prediction algorithm is shown in
Figure 5.1 with the respective node and link labels. Table 5.1 presents the
adjacency list for the network. The network consists of three parallel arterials
representing an urban corridor consisting of a freeway and two major arteri-

als, connected with several crossing links.

Traffic arrives at the generation nodes 1, 2, and 3 and it is destined to nodes
19, 20, and 21. Therefore, according to the previous notation 0={1,2,3} and
D={19,20,21}. The crossing links provide a number of alternative routes from
the origin nodes and the intermediate nodes to the destination nodes. The
arrival pattern of traffic at the generation nodes is shown in Figure 5.2. This
pattern was based on examples from the 1985 TRB Highway Capacity Manual
(TRB SR209). Vehicles arriving at each generation node may have any desti-
nation from set D. The percentage of traffic from each generation node
towards each destination node, used for all the experiments conducted in this

study is given in Table 5.2.

The only difference among the three parallel arterials of the network is the
speed limit. The speed limit is 55 mph. for the freeway facility, and 45 mph.
and 35 mph for the two arterials, while the crossing links are assumed to
have a speed limit of 40 mph. The speed limit represents the maximum speed

with which vehicles can travel on the facilities, and is utilized for calculating

96

38

36

33

31

29

26

G
11
Q
.1
0
0
l 3
1
0

27 0 30
-
28
22
O O 23
- -
21
15
16
0-0
14
8
0 9
0 , 7
-=1 1 ‘3
cg. ‘ 0.-
(l’ E 1 2 g
m l
H V l m ‘

 

Figure 5.1: Test Network Layout

97

Table 5.1: Adjacency List of Test Network

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ann Tblflode

1 4 0 0
2 5 0 0
3 6 0 0
4 5 7 0
5 4 6 8
6 5 9 0
7 8 10 0
8 7 9 11
9 8 12

10 11 13

11 10 12 14
12 11 15

13 14 15 O
14 13 15 17
15 14 18

16 17 19

17 16 18 20
18 17 21 0
19 0 0 0
20 0 0
21 0 0 0

 

 

 

 

 

Volume (Vehicles / Hour)

5000

4500

4000

3500

3000

2500

2000

1500

1000

500

98

 

 

L l

 

S 10 15 20
Time of Day (Hours)

Figure 5.2: Traffic Generation Pattern at Nodes l, 2, and 3.

 

Table 5.2: Origin - Destination Matrix

 

 

 

 

 

To 19 To 20 To 21
From 1 50% 40% 10%
From 2 20% 70% 10%
From 3 10% 20% 70%

 

 

 

 

 

Table 5.3: Lengths, Free Flow Maximum occupancies and Free Flow travel Times

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

of Links of Network.
Length Max. Free Flow Travel Time (seconds)
Occup.
Link (miles) (vehicles) ggegglhl (4156:1ng $632113
1, 2, 3 0.50 66 30 40 50
5, 8, 10 1.50 198 100 120 155
12, 15, 17 2.00 264 130 160 205
19, 22, 24 1.80 244 120 150 185
26, 29, 31 2.00 264 130 160 205
33, 36, 38 0.50 66 30 40 50
Connectors 1.00 66 90

 

 

100
the free flow travel time. The free flow travel time, along with the length of

each link are given in Table 5.3.

All three arterials are two lane facilities, while the crossing links are one lane
(for each direction) facilities. Table 5.3 also shows the values of the free flow
maximum occupancies of each link utilized in the following experiments. The
free flow maximum occupancies were calculated based on the value of 66 vehi-
cles/mile/lane, given in the 1985 HCM for level of service D, which represents
the transient phase flom free flowing traffic to congested traffic (TRB
SR209).Therefore, according to the assumptions made in paragraph 4.3.2,
when the occupancy of a link is greater than double the free flow maximum

occupancy, thus 132 vehicles/mile/lane, the link is considered congested. ‘

The first step, prior to application of the prediction model to the route guid—
ance system, was to establish the experience data base, for use in routing the
non smart vehicles through the network. Because these data are to represent
the travel time experience of non equipped drivers, a rough classification of
link travel time is required. For this reason, in the initialization run of the
simulation model the five-minute mean link travel time was collected, which
was then smoothed by averaging each value with the previous and the next

five-minute mean value, i.e.:

I,(t— 1) +I,(t) +1‘,(t+1)

3 (5.1)

T1“) =

 

where T, (I) is the observed five-minute mean value of the link I travel time at
time t, and T10) is the smoothed five-minute mean value for the same time

interval. In Figure 5.3 are illustrated the smoothed five-minute mean travel

101
times of links 19 and 22, which are typical for all the links of the three arteri-

als.

5.3 Structure of the Prediction Model

The first step in the application of the model was to find the optimum struc-
ture of the prediction model given by equation (3.3). The procedure that was
followed was to experiment with different model structures on given
sequences of link travel times under two different scenarios of traffic condi-
tions: normal traffic conditions, where there was no congestion induced by a
traffic incident, and congested traffic conditions due to a traffic accident where
a link is completely blocked. The various model structures differed not only in
the number of components (time series) included but also in the order (the.

number of past values of a time series in the model) of each component.

Because predictions yielded from the RLS algorithm are not bounded, the pre-
diction model was applied in such a way that if the predictions obtained
exceeded some reasonable limits then the predictions assumed these limits. Of
course the lower limit of the predictions should be the free flow travel time of
the links, while the upper limit was set to be fifteen times the free flow travel

time of the link.

The measures of performance used were:
(1) the mean absolute relative error E which is a measure of the percent

expected error, and is defined as:

- 1 Inn-3d
e = [vi—fir (5.2)

l
(2) the square root of the mean square relative error E, which gives more

160

155

150

145

140

135

130

Link Travel Time (Seconds)

125

120

200
195
190
185
180
175
l70
165

Link Travel Time (Seconds)

160
155
150

Figure 5.3: Smoothed Five-Minute Average 'lt'avel Times of Links 19 and 22

102

 

Link 19

 

 

 

20

 

Link 22

 

 

5 10 15
Time of Day (Hours)

5 10 15
Time of Day (Hours)

20

 

 

103
weight to the larger errors, and is defined as:

1. 2
_ _ 1 T(t)-T(t)
6., - N - (El—7(1) ] (5.3)

I L

 

(3) the maximum absolute error em defined as:

IT(1) - 7(1)

em = max, { _—T(t)—} ' (5.4)

where T(t) is the predicted travel time and T (t) is the observed travel time for
the time interval t, and N is the number of observations in the time period that
the performance of the prediction model is examined. These error measures
were compared with the corresponding error measures for the case where no

predictions were performed, and the current travel times were used to obtain

the minimum paths.

For this phase of the study the traffic operations on the network were simu-
lated with 30% smart vehicles and the time interval between information
updates regarding traffic conditions was set at 60 seconds. The time series
consisted of 2880 observations (two days), with the first day free of any traffic
incidents. The occurrence of a traffic accident was simulated on link 19 that
started at time 08:34:10.2 and was cleared at time 08:50:21.5 in the second

day of the simulation run.

Shortly after the accident occurrence, the link is blocked by traffic that had
entered the link before the incident, and by traffic that does not know about
the traffic conditions of the link (i.e. non smart traffic). Meanwhile, smart
vehicles are diverted to link 18. After link .19 is completely blocked, all traffic
is diverted to link 18. Because of this diverted traffic link 18 becomes con-

104
gested and after a few minutes a queue is formed on link 12.

During the accident, the simulation model assumes that the observed travel
time of the link with the accident is equal to the expected duration of the acci-
dent plus the travel time of the link based on the current length of the queue
and the current volume of the link. The expected duration of an accident on
link 19 was set at 1000 seconds. After the accident ended, the queue from link
12 feeds link 19 with a steady rate, one vehicle from each lane every 2.8 sec-
onds. The queue formed on link 19 starts dissipating after the end of the acci-
dent at the same rate of 2.8 seconds per vehicle per lane. Because, the rate
with which the queue on link 19 dissipates is equal to the rate of incoming
traffic, the travel time on link 19 is almost constant until the demand is
decreased around 10:00 am. At that time the queue on link 12 is gradually
dissolved completely, and then, the queue on link 19 is also dissolved, and the

travel time on the link returns to normal levels.

5.3.1 Autoregressive Models
First the performance of a number of prediction models with just the autore-

gressive component in equation (3.3) were examined:

r,(1) = 2 a,(1— 1) - T,(1-1') +e(t) (5.5)

1': 1
so the relation of future travel times of a link with the past history of the
travel time of the same link were studied. The error measures were computed
for the one, five and ten step ahead predictions, which represent prediction of
the link travel time for one, five and ten minutes ahead. Models with different

autoregressive order (value of n) were tested with the order ranging from one

105
to fifty. Initially the forgetting factor 1 was set equal to 1.00.

5.3.1.1 Normal Traffic Conditions

For the situation of normal traffic operations (no traffic incident occurrence)
the travel time series for link 15 is illustrated. The error measures given by
equations (5.2), (5.3), and (5.4) were computed for two time periods of the sec-
ond simulated day, the morning period from 6:00 to 11:00 and the afternoon
period from 14:00 to 19:00. These two time periods were used because for the
rest of the time, link travel time, for almost all links, remains very close to the
free flow travel time of the link.

The mean relative error, the mean square error and the maximum error pro-
duced by a series of autoregressive models for the morning and evening peri-
ods are given in Table 5.4 and Table 5.5 respectively. In almost all cases the
resulting prediction errors from the models were smaller than the ones result-
ing if no predictions were performed. Only in the evening period and for the
models AR(3) and AR(5) the mean relative error and the mean square error of
the five and ten steps ahead are larger than those produced by the no predic-
tions case. As can be seen from the results of these experiments, the prediction
error is getting smaller for higher order models (order of 10 and higher) for

both the morning and evening time periods.

However, the large number of variables n used in the prediction model has the
adverse effect that the resulting parameter vector of the model is probably
overfitted to the data. The model, although it is large enough to include the
system describing the link travel time, is overparameterized and individual

106

 

R33 _ 883 _ 33:3 _ 2:3 _ $88 _ ”mad _ N885 _ 6385 _ ~38...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_ 8323.." oz
«$26 $566 3266 6826 6:666 emu—66 2.366 68666 66366 6m
2316 M3566 8656 2.6666 @2666 6956 3486 26666 8366 mm
«$36 2:86 2686 3866 6:666 3266 ©6366 3866 8366 2
$62 6 3566 3:266 5866 «:86 «$56 6586 ©8666 5366 S v.
_.
32:6 8866 «356 n KS6 “cm—86 $266 5366 68666 2366 n 1.
w _ w: 6 5866 6356 $2 _6 am ~ 666 wan—66 $686 $6666 6 _ 366 v M
c~o§6 8866 62:66 6326 .8566 9266 wmm~66 R866 2366 m
Ema—6 5866 6386 ”6626 62666 w-56 >386 $6666 2366 N
6526 8866 3266 $526 62666 «mm—66 $366 6386 N386 6
.e .w w ...... ..m M... 1... .m w 3.5
36536615 6622 63m 3 3633695 322 63m 6 6:68:35 6622 63m H a
86":

1 836 533?.360 83 6:336:60 055 .2:qu .33.: vote.— wEEeE 0.: .5.— m— 3:: «6 EELH swam—3.5 Sam 035,—.

 

107

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3:8 2:88 _ 88.8 _ 823 _ 58.8 _ $28.8 _ W888 _ 288.8 _ 588.8 _2o§8£ oz
28:. 88.8 328.8 88.8 58.8 822 838 358.8 888.8 8
383 588 288.8 $8.8 88.8 828.8 ”83.8 888.8 $8.: 3
52.8 :8... 888.8 88.8 28.8 828.8 :22. 38.8 3.88 2
883 0:88 885.8 888.8 58.8 328.8 E38 9588 088.8 2 Y
=
388 868.8 38.8 88:. 588 228.8 888.8 988.8 38.8 n w.
283 9:88 888.8 283 828.8 :23 :38 «88.8 :88 v m
9:8 88.8 028.8 886.8 58.8 823 33.8 958.8 588.8 m
883 888.8 0888 883 88.8 as... :82. 388... 9.8.8 N
3.2.8 2:88 888.8 223 58.8 «85.8 958.8 988.8 88.8 6
acoflomkum 93:4 63w 3 58302695 6922 305 n 2833695 652?. noem H m3.
865—

.8”: 52.233 89 952550 use? .332 3...... 8t».— uafié 2: .8 B ...5 ... flea 8832.. fin 2.5

 

 

108
parameters are not affecting the predictions. The effect of old observations

that most likely do not correlate as well as more recent ones with the current
and the near future travel times is carried for a long time (i.e. for as long as
these observations are in the model), and if sudden changes in the travel time
occur, the result would be a dramatic increase in the error. For the same rea-
son, the filter is not kept sufficiently alert to follow the most recent changes in
the tramc conditions on the link. The low correlation of the older observations
to the most recent ones can be seen by studying the parameters of the autore-
gressive models as n increases. From Table 5.6 we can see that observations
older than five time steps do not contribute significantly to the predictions (as
compared to the contribution of observations from one to four time steps old).

From the same results, we can observe that as expected, one step ahead pre-
dictions have less error than five step ahead predictions which are better than
the 10 step predictions. The one step and ten step ahead predictions with an

autoregressive model of order three, for the morning period are shown in Fig-

Table 5.6: Parameters for Autoregressive Models at the End of the Evening Period
(19:00) of the Second Simulated Day (A I: 1.00).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

AR 01 02 a3 a4 a5 a6
1 1.000 -- -- -- -- --
2 1.354 -0.355 -- -- -- --
3 1.340 -0.301 -0.041 -- .. --
4 1.347 -0.249 -0.267 0.169 -- --
5 1.346 0.249 -O.266 . 0.165 0.003 --
6 1.347 -0.249 -0.265 0.166 -0.004 0.004

 

 

109
ure 5.4 and Figure 5.5 respectively. Figure 5.6 and Figure 5.7 show the predic-

tions obtained with an autoregressive model of order five for the evening
period. In both cases it can be seen that while the one step ahead predictions
are very close to the observed data, the ten step ahead predictions almost rep-
licate a shift of the observations ten time steps ahead. This can also be
deduced by comparing the error measures of these models with the no predic-
tion case. In Table 5.7 and Table 5.8 the percent difference between the error
of each model and the no predictions case is given. Values in parentheses indi-
cate the relative ranldng of each error measure for the given prediction, while
in the column under the heading ‘Total Rank’ the sum of the ranks along with
the relative rank of these figures is given. From these results we can see that
the AR(l) model in both the morning and the evening periods score the lowest,
while the AR(2) and AR(4) models are the best. Nevertheless, improvements

over the no predictions case are too small to be considered significant.

In the following, the forgetting factor was set to values smaller than 1.00, so
the parameters of the models will be allowed to vary with time, and less
weight will be given to prediction errors encountered in the distant past. For
example, in the case where 70: 0.975, the weight attributed to the error of the
prediction made one time step before is 0.975 while the weight attributed to
the error of the prediction 20 time steps before is only 0.402. In Figure 5.8 and
Figure 5.9 the parameters of the model AR(3) for 10:1.000 and H.975 are ’
shown. As can be seen from these figures, in the case of hLOO the parameters
are converging to constant values, while in the case of H.975 the parameters
of the model are allowed to vary with time. i

The prediction errors for forgetting factor equal to 0.990, 0.975 and 0.90 are

110

205 I I l I l T I 1

 

200 -

195 _

§

185 ’ a

§

Link navel Time (Seconds)
5'}.

170

 

 

165

 

 

 

 

‘—v

13 1'5
Time of Day (Hours)

Figure 5.4: 1 Step Predictions of Travel Times of Link 15 with Autoregressive Model
of Order 3 - Normal Traffic Operations, Morning Period

7?

   

205

 

Observed Value a

195 Predicted Value ..

 

190

185

180

175

Link 'h'avel Time (Seconds)

 

170

165

 

 

160

 

- 11

 

8
Time of Day (Hours)

Figure 5.5: 10 Step Predictions of Ravel Times of Link 15 with Autoregressive
Model of Order 3 - Normal Traffic Operations, Morning Period

111
205 I I I I I I I I I

 

200 - ’, Obsa'ved Value ‘

195 - , Predicted Value -

 

 

185 - a

Link Travel Time (Seconds)

175 - 1. -. -
17o _ ~_ —

165- .1-

 

 

16014 14.3 13 15.3 T6 16.3 1‘7 17.3 113 18.3 19

Time of Day (Hours)

Figure 5.6: 1 Step Predictions of 'lt'avel Times of Link 15 with Autoregressive Model
of Order 5 - Normal Traffic Operations, Evening Period

 

205 I I I I f I I I I

 

. Obsaved Value ‘

195 h PredictedValue ‘

 

§

185 —

 

180 -

l

175 b

 

 

 

Link Travel Time (Seconds)

170 -

I

 

165 1-

 

 

 

14 h 14.5 15 15.5 16 16.3 1‘7 17.5 18 18.5 19
.Time of Day (Hours)

Figure 5.7: 10 Step Predictions of Travel Times of Link 15 with Autoregressive
Model of Order 5 - Normal Traffic Operations, Evening Period

112

Table 5.7: Percent Difference of Prediction Error of Autoregressive Models with No
Predictions case for Morning Period (06:00-11:00)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

AR 1 Step Ahead1 5 Step Ahead 10 Step Ahead Total
Predictions Predictions Predictions Rank2
62 62, 62,, 62 62, Ac", 62 62, 62,,

1 0.0 0.0 0.1 -1.1 0.0 +0.5 —0.5 -2.4 ~55 36
(5) (5) (5) (2) (4) (4) (5) (4) (2) (5)

2 -6.8 -7.5 -17.5 -l.6 ~3.9 -6.2 -1.3 -3.4 -3.2 18
(1) (2) (3) (1) (2) (3) (2) (1) (3) (1)

3 -S.7 -7.5 -26.7 +0.6 —4.7 -10.8 -0.9 -2.9 -1.7 25
(4) (2) (2) (5) ( 1) ( 1) (3) (3) (4) (3)

4 -5.9 -7.2 -16.7 -0.8 +0.4 2.1 -0.9 -3.3 -6.0 30
(3) (4) (4) (3) (5) (5) (3) (2) (1) (4)

5 -6.8 .100 -231 0.3 -3.9 -8.6 -1.1 -2.4 -1.4 ' 21
(1) (1) ( 1) (4) (2) (2) ( 1) (4) (5) (2)

 

 

1. Numbers in parentheses denote relative rank.
2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the
sums.

shown in Table 5.9 and Table 5.10 for the morning and evening periods respec-
tively. As can be seen from these tables, the error measures get worse as the
forgetting factor is set to smaller values. The smaller the value of the forget-
ting factor the better the tracking capability of the model which is trying to
find not only the optimum values of the parameters, but its optimum values at
each point in time (see Figure 5.8 and Figure 5.9). This is achieved though, at
the expense of the sensitivity of the model to the prediction errors. Obviously
and as it was discussed in paragraph 3.4.2 there is a trade off which has to be
made between the tracking ability of the model and its sensitivity to the pre-
diction errors. This is especially evident for the ten step ahead predictions

where the mean absolute relative error is almost double the corresponding

113

Table 5.8: Percent Difference of Prediction Error 01‘ Autoregressive Models with No
Predictions case for Evening Period 04:00-19:00)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

AR 1 Step Ahead 5 Step Ahead 10 Step Ahead Total
Predictionsl Predictions Predictions Rank2
62 62, 62,, 62 62, 62,, 62 62, 62,,

1 0.0 0.0 +0.2 -1.9 0.0 0.4 -2.3 -l .6 -5.1 31
(5) (5) (5) (2) (3) (5) (2) (2) (2) (4)

2 -3.9 -2.2 -13.1 0.0 -0.8 -4.6 -0.6 -0.5 -3.7 27
(4) (4) (2) (3) (2) (3) (3) (3) (3) (2)

3 -5.3 -4.4 -12.7 +1.9 0.0 -5.7 +1.3 0.5 -1.2 31
(3) (1) (3) (5) (3) ( 1) (4) (4) (5) (4)

4 -6.4 -4.2 -l4.0 -25 -1.1 -4.9 -3.3 -2.7 -5.9 12
(1) (3) (1) (1) (1) (2) (1) (1) (1) (1)

5 -5.6 -4.4 -12.7 +1.7 0.0 -4.6 +1.3 +0.5 -2.1 ' 28
(2) (1) (3) (4) (3) (3) (4) (4) (4) (3)

 

 

 

 

 

1. Numbers in parentheses denote relative rank.
2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the

sums.

error of the no prediction situation (i.e. for the morning period, 0.02288 and

0.01114 respectively). In the case of 1:0.990 and 1:0.975 the one and five step

predictions have not deteriorated too much, and the AR(3) model give the best

results, which still are only marginally better than the no predictions case (i.e.
for the morning period with l=0.975, 0.01227 and 0.01238 respectively).

114

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

‘ '

 

 

3 I I I I I I I I
01
0
:3
E i “3
E a 6w
0
a: 2 q
4
'3 o 5 10 13 20 23 30 33 40 43 48
Time (Hours)
Figure 5.8: Parameters of Autoregressive Model of Order 3 - Forgetting Factor
2:1.000
3 I I I I I I I I I
2 )- —
01
1 -
0
§ ‘ “3
.>.. o ' L
g 11".” 1
a
a“! -1 . 2
-2 . _
'3 o 5 10 13 20 23 30 33 40 43 48
Time (Hours)

Figure 5.9: Parameters of Autoregressive Model of Order 3 - Forgetting Factor
1:0.975 .

115

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

as; _ N88... _ 3:3. _ 2:8 _ 6.28... — was... _ N385 _ c385 _ N385 _§§Be oz
NNBN... 253 N38... £38 628... 3:2. 86ch _38.c 62.86 n
as? 88.3 883 «8:5 385 Named 6885 688... 586 N w.
838 6885 N385 8§d 585 8:2. N28... 688.: 58d N %
883 $83 NNNNod .923 385 82:. NNNch 9.ch $.85 _
«ENS RN85 2:85 SON; 385 $22. 438... N88... N985 n
ENS 28% 638.6 883 was... NNNSd £685 585 23.3 N M
8N8 £33 265... 823 6285 £33 £3; N885 833 N m
N6NNN.¢ eNNSd 63:3 3E3 386 E55 3.85 883 385 _
2:3 nNNSd 6885 :23 :53 62:; £83 585 £48.23 n
9.83 6386 33:3 :33 £53 62:3 882. 585 232. m mu.
$38 :83 :22. 528 58.: 68:3 66ch N886 2485 N m
583 :83 :23 ENE N285 $23 83:. 8955 N385 a

s» ..w e ...» 4w e ...» ..w s ~33
8:86:25 86.2 63m 2 685565 322 new ... mechanism 68.2 85 N 5.

 

 

 

 

 

sen—N33 68:35.5 89 .38... 3.3.5...
2.. .6 82.3 2.865: 23 23.8.50 cess. .9562 as... 8.5.. ”5562 .5. NN .3: .6 825 5:38... “an 2...:

 

116

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

555:5 _ 5555555 _ 55558.5 — 555N555 _ 55555.5 55555.5 _ 555555 — 55.5555 _ 5.55555 _ao5e55e.5 oz
585555 2855 5.5585 5855.5 85555 5555555 53555 55555.5 55555.5 5
555.35 5585.5 55585 555555 5.55555 5.55555 5.55555 55555.5 55555.5 5 w.
NNRN5 55855 55585 5555555 5555555 855555 555555 5555555 85555 N w
5285 5585.5 5885 55555.5 555555 5555555 55855 5555555 5555555 5
285.5 885.5 858.5 555N55 555555 555555 55558.5 55555.5 8555.5 5
5555N5 N5855 55.855 5.555555 555555 85555 55555.5 55555.5 55555.5 5 M
85555 885.5 55NN55 N55N55 5555555 58555 555555 3.5555 555555 N M
8555.5 5585.5 8585 558555 5555555 555555 55855 55.5555 55.5555 5
55:55 55555.5 555585 555.25 55555.5 55555.5 555585 3.5555 55555.5 5
555555555 85555 :585 5355.5 85555 555555 55585 545555 35555 5 M
N5855 555555 55585 8:55 55555.5 5.55555 8555 3.5555 555555 N W
55855 555555 55585 85555 5555555 55555.5 55555.5 55555.5 55555.5 5

..6 .5 N ..s .5 .... ...... ...... 5 .855.5
855565585 55855.55. 5535 55 5555555555855 5855.5. 88 5 555555555255 55855... .535 5 52

 

 

 

 

 

5555255 52:52 855... 55555555: 85555555283 5555 555555.. 55.555255 .555 N5 5555.5 55 8855 55555555525 555.5 55555

.5555... 855555.55... 255 55 8.5555 55.2525: 5.55 25555555550

 

117
5.3.1.2 Congested Conditions Due to Traffic Accident

For the situation of congested traffic operations due to a traffic accident the
series of travel time observations on link 19 were considered. A traffic accident
occurred on link 19 at time 08:34:10.2 and ended at time 08:50:21.5. Autore-
gressive models of order ranging from one to five were tested and the forget-
ting factor was set to four different values: 1.00, 0.99, 0.90 and 0.80. The error
measures obtained by these models for a time period that includes the inci-
dent and its aftermath (starting at 8:00 and ending at 10:30) are shown in
Table 5.11.

The performance of the autoregressive model is depicted in Figure 5.10 and
Figure 5.11 where the one step and the ten step ahead predictions respectively
obtained with an autoregressive model of order one and with 1:1.00 are
shown. As can be seen in these figures, like in the normal conditions situation,
predictions are almost only a shift of the observations. In Figure 5.12 and Fig-
ure 5.13 the same predictions with an autoregressive model of order one and
with 1:0.80 are shown. Due to the smaller forgetting factor in the later set of
figures, the model is in a more alert condition, and thus response to the
change of the travel time is more extreme. Obviously, the one step predictions
are worse, at least in the beginning of the accident, but the ten step predic-
tions are better than in the no predictions case. In the case where 1:0.80, the
model reacted to the large error at the beginning of the incident, and predic-
tions reached the ceiling of the allowable range of the travel time predictions
for one time step. After the end of the incident the model also responded to the
abrupt drop of the travel time of- the link, and especially close to the end of the
aftermath of the incident 10 step predictions return to observation values
more rapidly than in the case where 1:1.00.

118

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$56.— $9.66 $42.26 6336 «286 6326 $6666 2866 3366 . 555555555255 52
NM: 5.5 5886 8636 m~m6m6 6386 549436 namaw6 mom—66 33.66 m
3365 6886 3836 655636 2.586 362 6 3866 8:66 R536 4 v.
533.— 3686 m§w~6 mmmaw6 $4366 6236 namaw6 666566 @6586 a W
336.5 54886 $636 mama... 6286 $62 6 3866 «8666 5886 N m
36ch 6386 $4536 $636 8586 $52 6 ~§w6 8866 6386 a

ammo: 58566 56mwN6 $3556 6386 an»: 6 mmmow6 5266 8566 m

5.8—w; 5366 w— 5 5N6 Vn 566 2266 2%? 6 mmmow6 @8566 @6086 v v.
5 ~ Aug; 66:56 _ 386 $6666 NVNN66 mgm 5 6 N836 666666 66mm66 m .5...
$543.5 3636 $586 55856 3:86 3356 3636 5.5666 8686 N W
wnmvwg 8:66 mmmom6 65566 5386 $356 $636 66866 559.86 H

.... .5 N .... .5 ... ...... .5. N 855
5:555:5on 6555555 63m 6H 5555536555“ 65555.2 63m m meofiomvoum 655.5552 63m H m<

 

 

 

 

 

555555. 5555 5:555:83 555 5555855. 555525. 55 55 255 5555555555550 565855550
525:: .5355... ”£35355— .2: ..e 85.55» 5:25.555 6:: 5.5—52 5385.53.58.34 5m? 3 5.5,— ..e 22,—m 5586:525— 5=.m 535,—.

 

119

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R53 $36 38o e88... 383 8:3 88$ ES... «885 .280? 02
88mm 2:3 332 8%; 5955 2%... 382 822. 25:. m
33.: ~22 .c 2.83 383. @385 5:5 88$ as... @335 v v.
:33 SEE :83 8:3 :82. :28 282 8:2. was... a W
£33 386 $82 3354 823 $83 232 823 385 N m
5:3 :83 $83 88$ £23 £88 282 9:85 3.85 H

38% 3:85 $3.2 $80.6. 33... 823 282 332 3.8.9 m

233 . «$85 :93 35:. @885 88:. 282 ”8:3 883 v . M
was; 323 8&2 88$ 5.85 82:. 282 2:2 :33 m ..n_u
was; Eéd 288 832 823 3:5 £33 822. 833 N M
~88; :53 232 8.82 883 2:3 532 882 385 g

a» ..w w s» ..m m ...» ..w m 86.8
8828an 322 8a S 83888.” 222 .55 m 8855 822 9% fl 5

 

 

 

 

 

A3=:=:86 =.m 035,—.

 

120

 

 

 

 

 

 

 

 

 

1200 . . fl
1000 Observed Value
Predicted Value
a —4
E 800
9
E 600 _ -
i— #
0
E 400 ~ d
5..
'_1 200 . _
02: 3.3 6 93 lb 10.5
Time of Day (Hours)

Figure 5.10: 1 Step Ahead Predictions of Travel Times of Link 19 with
Autoregressive Model of Order 1 and 1.21.00 - Congested Traffic Conditions Due to

 

 

 

 

 

 

 

 

 

 

 

 

Accident
1200 r 1 T
1000 h Observed Value ..
Predicted Value
’5? 300 - _
'8
3
I: 600 r- "
.§ — M._.
[-
‘23
400 ~
E
32
:3 200 -
O ’ 1 L 1 4L
8. 8.5 9 9.5 10 10.5
Time of Day (Hours)

Figure 5.11: 10 Step Ahead Predictions of Travel Times of Link 19 with
Autoregressive Model of Order 1 and 1:1.00 - Congested Traffic Conditions Due to
Accident

121

 

 

 

 

 

 

 

 

 

1800 r
1600 ’ ObservedValue
1400 ’ PredictedValue 7
@1200 - a
2
§tuno _ —
9
E 800 - a
'5.
13 6a)- -
é -.—
E 4‘” " -‘
"J 2&3- -
0 1 1 L 1
8: 8.5 9 9.5 10 10.5

 

Time of Day (Hours)

Figure 5.12: 1 Step Ahead Predictions of Travel Times of Link 19 with
Autoregressive Model of Order 1 and 1:0.80 - Congested Traffic Conditions Due to
Accident

1800 . . r

 

E

Observed Value

Predicted Value

 

 

 

P M .1
b V; ‘

 

 

 

 

Link Travel Time (Seconds)
o § § § °8° § § §

 

 

s. 8.5 6 9.3 ’16 10.5
Time of Day (Hours)

Figure 5.13: 10 Step Ahead Predictions of Travel Times of Link 19 with
Autoregressive Model of Order 1 and H.80 - Congested Traffic Conditions Due to
Accident

122
This is shown more clearly in Table 5.11 where the error measures for these

traffic conditions and for different values of the forgetting factor are shown.
For larger order models and for small values of the forgetting factor the model
reacts too spasmodically as it can be deduced by the value of the maximum
error, which reaches a high of 13.85 for 1:0.80 and 11:4. Generally, for all the
values of the forgetting factor, models with smaller autoregressive order n (i.e.
n=1 or 2) gave better results than models of larger order, and this was espe-
cially apparent when fewer past prediction errors of the algorithm were con-
sidered in the computation of the parameters of the model with the forgetting
factor set at 0.90 and 0.80. For example, for n=1 the mean square relative
error of the five step ahead predictions is 0.02149 for k=1.00 and 0.02107 for
1:0.99, which represent a 3.5% and 5.4% reduction over the no prediction
case. On the other hand, the same error is 0.02007 for 1:09 and 0.01883 for
1:0.80, which represent a 9.9% and 15.5% reduction respectively.

While the mammum error is decreasing for larger order models, the mean rel-
ative error and the mean square error have their best values when n=1. For
the models with n=1, the five step and ten step ahead predictions obtained
with models with the forgetting factor equal to 0.90 are better by almost 5%
than those obtained by the models with a forgetting factor of 1.00, and the
same predictions obtained with models with a forgetting factor of 0.80 have
improved the error measures roughly by an additional 10%. However, the
error measures for the one step prediction becomes worse as the forgetting fac-

tor is set to smaller values.

123
5.3.2 Autoregressive Models Including the Average

Travel Time of the Link
The next set of models that tested were those that include both the autore-
gressive component and the average travel time of the link for the correspond-

ing time interval. Thus, the general form of these models was:

1,0) = z a,(:- 1) - T,(t - i) + d- 1m) + e(t) (5.6)

i: 1
Again the error measures are computed for the one, five and ten steps ahead
predictions for models of different autoregressive order, and they were com-
pared to the no prediction case. The average travel time of each link used in
this set of prediction models were the travel times used as a basis for routing

“non-smart” vehicles, defined by equation (5.1).

5.3.2.1 Normal traffic Conditions

For evaluating the performance of the prediction models defined by equation
(5.6), the travel time series of link 15 was used. The error measures were com-
puted for the same two time periods as in the previous section, the morning
(06:00 to 11:00) and evening (14:00 to 19:00) period. Table 5.12 and Table 5.13
show the values of the error measures obtained when the average travel time
of the link for the corresponding time step is included, along with the autore-
gressive component. The results are for models with order of the autoregres-
sive component ranging from one to ten, and for different values for the

forgetting factor: 1.00, 0.99, 0.975 and 0.90.

Similar to the models with just the autoregressive component, when the for-

getting factor }. is set to unity, and thus all previous prediction errors encoun-

124

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.5535 .5585 7.885 7325 75.85 75585 $3.85 _5..5555 V3555 _ 259.852
8555 52555 «$85 555555 5:85 55:55 «5.555 5.585 55.555 5.
8255 .2555 55355 $355 55855 $585 55585 3.585 53.85 5
555555 53555 «5585 8855 3855 $5.55 55585 8585 2.555 5 M
5555 $555 9.585 .885 .5855 5.585 53.555 5.5555 .3555 m m
.5255 5:555 8355 53.555 3855 2:55 .5585 8585 «5.555 5
3.5555 5.555 «SS5 535.5 55855 3:55 53.55 5885 55.555 .
9.5.5 8855 8:55 .5855 55855 5585 $555 $585 .5855 5.
535.5 52555 5.85 58.555 8855 £585 £555 $585 .5855 5
535.5 .2555 55585 $355 8855 55585 555555 555555 555555 ... m.
88.5 52555 3.255 55:55 .5855 2585 5.555 A.5555... 5.555 m m
55.5 55.555 5.585 55:55 .5855 8585 58555 5.585 55555 5
5555.5 5285 55585 55355 55855 5885 8.555 58555 5.355 .

...... .w m. .. ...... w. .. ..w w as.

855.58.. 58.2 86 5. 2.35.8... 58.2 53m 5 885.58.. 58.2 9% . .2

 

.55.:555 gauges... 80 8...... uses: . 2.3.550 9E5 ......32
3...... ......— 2: ... 0...: .25 «was... 2: 55522.. 2582 3.825233 ......» m. ......— 5 £8... 8:22... .25 2...?

 

125

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3525 55555.5 H.885 _5§.HH5 _5NH555 7.5585 «$.55 35555 «3.85 239.8... ..z
5535 H3555 .5855 5.525 8855 «5:55 55:55 3585 55585 S
$5.55 55555 55855 H5525 H5855 55:55 «55555 $585 $355 ...
55855 .5855 «.5555 825 5:85 H5255 5.5555 5.5555 53.85 H. M
5.5555 5.585 35555 $525 «5855 H5585 $5555 55555 55585 a m
53.55 555555 555555 355 8855 5555 5.555 5.585 55.555 5
555555 555555 3.5555 H5525 $855 $585 5555 3585 8355 H
«H5555 55555 2.255 $2.5 55855 55:55 58.85 5885 55.555 S
«8555 555555 H5355 55525 3855 8585 55585 5585 5:555 m
53:55 25555 8255 $55 5:85 H5585 «H.585 $5555 «H555 .. M
5385 55855 55:55 555555 55855 5.585 53.555 5.5555 55.555 5 M
$5.55 58555 5.255 5225 55855 5:55 8555 5.5555 «5.555 a
55555 555555 8585 35:5 55:55 5:55 53.55 5885 55.555 H

.... .m m .... .... .... .. .w m ......
2.5.8.585 58.2 53m 2 9.35.5.5 58.2 5.6 m 255.585 58.2 8% H 5.

 

€025.83 «fin «Bah.

 

 

126

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

T825 _5..855 _55H85 7.55:5 _H.m855 7385 T5855 T3585 :88... _ 280.352
8.555 55855 5885 55.5.5 «”855 8:55 «$.85 5885 «$555 5H
8:55 .5855 .5585 .5552. 8855 5.85 83.55 58555 8855 m
55.85 3855 8585 53:5 .5855 58.85 «$.85 «.8555 58555 .. .v..u.
£525 $855 «$85 58:5 .5855 $585 8585 58555 55855 5 m
.5585 55855 8585 85:5 8855 .5585 555.55 5885 55855 a
58555 .5855 55:55 8525 .5855 5......85 ..885 58555 8855 H
58.35 5.5.855 H885 3855 8855 5885 £585 H8555 58555 5H
8.55 8855 8585 $5.85 55855 8585 .5855 «8555 .8555 5
9.8.5 £855 8585 58.55 8855 ......85 8855 58555 2855 .. m.
8525 8855 5885 8585 .5855 8585 8355 «8555 8855 m m
.585 8855 $585 8585 .5855 $585 H385 58555 5885 N
.825 55855 55585 8585 2855 5885 8.85 .885 3855 H

...» ..w w ...» ..w w ...» .w w 8......

5:38:55 @522 amam 3 5:38:85 @522 n3m m maoflomvfim v8.2 nfim H m...

 

855.55.... 2.2.9.3.... 80 3...... 8.5... . 83.8.39 use... .252
5...... ...... .... ... as: .25 «was... 2.. ”5.5.2.. 22...... 558.522.... ...... m. ...... ... 2...... 8.8.5.... .25 2......

 

 

 

 

 

 

 

 

127

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7825 55855 .5855 82.5 8855 $885 _555555 F885 8855_ 2558852
$3.55 555555 55855 8.85 55855 5885 555555 5885 85555 5H
88.5 55.555 55.585 85:5 8855 8.85 55855 58555 85555 5
552.55 8.555 H885 558.5 8855 5.85 55855 85555 555555 .. M
58555 55855 5885 58.25 8855 8585 8.555 58555 85555 5 W
85555 55855 8585 89:5 55855 $585 5885 .885 55855 a
85.55 8855 5885 8525 8855 52.85 85.55 58555 58555 H
8855 55855 «885 $535 8855 5885 8.85 58555 $5555 5H
88.5 58555 55585 88.5 55855 .5585 8:55 5885 8855 ...
558.55 8855 8585 585.5 8855 5885 55585 58555 58555 ... M
5885 58555 8585 585.5 55855 5885 5885 85555 $855 5 m
555555 55855 5885 555:5 H5855 8.585 5885 58555 58555 ...
85555 8855 8585 58:5 8855 .5585 $5.55 5885 8585 H

.... .... w .. .w w .... .w m 85....

2.58.8... 58.... .....m 5. 8......55... 58.... .....m. 5 2.3.5.8.... 58.2 .....m . .2

 

25:52.8. 2% 035—.

 

128
tered are considered in the calculation of the parameters a,- and d, the

resulting errors are smaller than the ones obtained when l. is set to smaller
values. This is true for both time periods, for all predictions, the one, five and
ten steps ahead, and for all three error measures, the mean absolute relative
error, the mean relative square error and the maximum error. As A is set to
smaller values the error measures increase as we move further into the
future, i.e. for the ten step ahead predictions. In fact, for the cases that 7. is
equal to 0.975 and 0.90 the error measures became worse than the no predic-
tions case. For example in the case where n=1 and for the five step ahead pre-
dictions, the mean square error for 7L=1.00 is 0.00106 while for l=0.80 the
same error of the same model is 0.00143. This happens for the same reason as
explained in the case of the simple autoregressive models concerning the trade

off between the sensitivity to noise and the tracking ability of the model.

Ten step ahead predictions are approximately 20% worse than five step ahead
predictions which are approximately two to three times worse than the one
step predictions. The one step and ten step ahead predictions for the morning
period obtained with a model containing an autoregressive component of order
3 and the average link travel time are shown in figure 5.14 and Figure 5.15.
The same predictions for the evening period are shown in Figure 5.16 and Fig-
ure 5.17. As can be seen in these figures, the one step prediction is very close
to the observed travel time, while the ten step ahead prediction follows the
general pattern of the observed values, but they are more smoothed, since
they are more affected by the average values. For example, this can be seen if
we consider that for the model depicted in these figures, the two step ahead
prediction at time I, To + 2) is based on the one step ahead prediction which is

already based on the average travel time at time t+ 1, the average travel at

Link Travel Time (Seconds)

Link Travel Time (Seconds)
'55
O

o—a
\l
O

205

8

fl
\0
Lit

8

~
00
{It

p—a
\l
M

165

Autoregressive Model of Order 3, Including the Average Travel Time - 1:1.00 -
Normal Operating Conditions - Morning Period

205

195

190

185

180

175

170

165

160

129

 

 

  
 
 
  
   

 

l

8

8.3

L

9

Time of Day (Hours)
Figure 5.14: 1 Step Ahead Predictions of Travel Times of Link 15 with

I

T

Observed Value

Predicted Value

   

10.5

1

l

 

  
 

 

 

 

 

 

 

Figure 5.15: 10 Step Ahead Predictions of Dave] Times of Link 15 with

Autoregressive Model of Order 3, Including the Average Travel Time - 1:1.00 -
Normal Operating Condition - Morning Period

 

- Observed Value 5
- Predicted Value -
b g 1 A H
.. I' . -
'u 1 x ' ‘

“'1'!”

6 6.3 7‘ ’73 8 8.3 6 9.5 10 10.5 1i

Time of Day (Hours)

130

 

 

 

 

 

 

 

 

205 I T I F I T
200 - P ..
A195 r- . H
é I . Predrcted Value
8 190 r r
5
0185 - t -
E t '3
1’; 180 r 1"!
£175 1- 11
E
-‘ 17o - . ‘ p
165 - 3
1m 5 1 t 1 1 1 1 4__‘_—__‘_ 1
14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19
Time of Day (Hours)

Figure 5.16: 1 Step Ahead Predictions of Travel Times of Link 15 with
Autoregressive Model of Order 3, Including the Average Travel Time - 1.21.00 -
Normal Operating Conditions - Evening Period

8

 

§

Obeaved Value J

a—a

‘O

M
I

Predicted Value 1

l M" ‘
- ,v 1‘ ‘h
{A} V ‘3'“; e

.31
, ”t. 1"", V" ‘

1 1 1 I l — l L 1
14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19
Time of Day (Hours)

Figure 5.17: 10 Step Ahead Predictions of 'Ii‘avel Times of Link 15 with
Autoregressive Model of Order 3, Including the Average Ravel Time - 1:100 -
Normal Operating Conditions - Evening Period

 

...a

8
I
l

 

8

Link Travel Time (Seconds)
8. 5:

fl

\3

O
I

 

e—e
Ox
M
1

 

160

 

 

131
time t+2 and the observed values at times t and t-l:

10+ 2) = (1119+ 1) +02T(r) +a3T(r- 1) +d‘i‘(t+ 2) =
(of + a2) T(:) + (a3 + azal) T(r- 1) +ala3T(t- 2) +d7'(r+ 2) +da1T(t+ 1)
Since the average link travel times are given in five minute intervals, the
effect of the same value for the average travel time is magnified further into
the future predictions.

The relative improvement of these models over the no prediction case when 1.
is set to 1.00 and 0.99 is shown in Table 5.14, and Table 5.15 for the morning
and evening periods respectively. In the case where 1 is set to 1.00 the
improvement for both time periods are close to 20% and 35% for the mean rel-
ative error for the five and ten step predictions respectively, while the maxi-
mum error is reduced by approximately 30% and 44%. The one step
predictions do not show such dramatic improvements but the errors associ-
ated with the one step predictions are already very small. When 1. is set to val-
ues smaller than one, the maximum error deteriorates. Even when 1 is set to
0.99 there are instances, at least for the ten step ahead predictions, with a
larger error than in the no prediction counterpart. In the same table, the
ranking of the models is shown for values of 1. equal to 1.00 and 0.99. The
model with an autoregressive component of order three appears to give the
best results, for both time periods. The models with autoregression order 1 as
well as those of order 10 gave the worst results, which indicates that in the
first case the model was too “small” to include the system, while in the later

case the model is overparametrized.

132

Table 5.14: Percent Difference of Prediction Error of AR Models Including the
Average Link Ravel Time Term from the No Predictions Case - Morning Period

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(06:00-11:00)
1 Step Ahead 5 Step Ahead 10 Step Ahead
g Predictions1 Predictions Predictions is
A2 A2, Aem A}? A2, Aem A2 A2, Aem

l -5.4 -3.6 +0.1 -l7.8 ~18.2 -28.3 -36.2 -36.0 -45.8 40
(6) (6) (6) (3) (3) (3) (6) (6) (1) (5)
2 -11.7 -11.3 -18.1 -18.0 -l9.9 -30.2 -36.3 -37.8 -44.6 24
(1) ( 1) (5) (2) (2) (2) (5) (2) (4) (2)
3 -1 1.5 -11.4 ~21.4 -18.2 -20.5 -30.1 -36.5 -38.0 -44.6 16
§ (2) (1) (1) (1) (1) (1) (4) (1) (4) (1)
ll 4 -10.5 -11.0 -l9.l -17.2 -l6.9 -27.8 -36.9 -37.2 «44.7 38
T (5) (5) (4) (5) (5) (4) (3) (4) (3) _(4)
5 -10.7 -11.3 -19.9 -l7.8 -l7.4 -27.8 -37.4 -37.5 -44.8 25
(4) (1) (2) (3) (4) (4) (2) (3) (2) (3)
10 .10.9 -11.2 -19.7 -17.1 -153 -24.8 -37.8 -36.9 44.4 40
(3) (4) (3) - (6) (6) (6) ( 1) (5) (6) 1(5)
1 -2.9 -2.3 +1.4 -8.4 -5.0 -7.4 -20.5 -6.4 +205 51
(6) (6) (6) (5) (6) (6) (5) (6) (5) (6)
2 -8.9 -9.9 -22.2 -10.3 -11.9 -l9.5 -23.5 -14.5 +108 27
( 1) (2) (5) (4) (3) (3) (4) (3) (2) (3)
8 3 -7.1 -9.7 ~29.3 -l6.1 -19.5 -35.2 -29.2 -22.1 +1.2 16
a; (2) (4) (4) (1) (l) (1) (1) (1) (1) (1)
fi 4 6.6 -9.8 -42.6 -14.5 -ll.3 -16.7 -27.3 -l3.3 +16.1 29
K (4) (3) (2) (2) (4) (4) (2) (4) (4) (4)
5 -7.3 -ll.3 -47.8 -11.5 -15.4 -27.9 -25.8 -l7.9. +12.7 20
(3) (1) (1) (3) (2) (2) (3) (2) (3) (2)
10 -3.6 -5 .4 -37.0 -7.1 -8.4 - 16.4 - 19.5 -10.4 +25 .4 46
(5) (5) (3) (6) (5) (5) (6) (5) (6) (5)

 

 

 

 

 

 

 

 

 

 

 

 

1. Numbers in parentheses denote relative rank.

2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the

sums.

 

133

Table 5.15: Percent Difference of Prediction Error of AR Models Including the
Average Link Travel Time Term from the No Predictions Case - Evening Period

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(14:00-19:00)
1 Step Ahead 5 Step Ahead 10 Step Ahead
g Predictions1 Predictions Predictions (3%
:3
A2 A2, Ae,,, A2 A2, Aem A2 A2, Aem “
l -2.1 -2.2 -16.9 -l7.7 ~16.0 -30.2 -34.2 -32.3 -42.l 37
(6) (3) (5) (5) (6) (1) (5) (5) (1) (4)
2 -6.6 -6.6 -3l.7 -l9.2 -l9.7 -29.9 -35.8 -35.4 -39.6 28
(5) (2) (2) (4) (3) (3) (3) (2) (4) (3)
o 3 -7.1 -6.7 -31 .8 - 19.3 -20.6 -30.1 -36.2 -35 .9 -38.9 20
8 (4) (1) (1) (3) (1) (2) (2) (1) (5) (1)
7f 4 -8.8 45.7 -30.8 -19.6 -18.3 -28.3 -3s.7 -3s.1 -39.8 _28
‘< (3) ( 1) (3) (2) (5) (5) (4) (3) (2) (3)
5 -8.9 ~6.7 -30.8 -l9.2 -18.8 -28.5 -35.8 -34.9 -39.7 28
(2) (1) (3) (4) (4) (4) (3) (4) (3) (3)
10 — 10.1 -6.7 -28.8 -20.3 - 19.8 27.9 -36.4 -35 .4 -39.6 22
(1) (1) (4) ( 1) (2) (6) ( 1) (2) (4) (2)
l -1.8 0.0 -1. 1 -8.2 +2.4 +7.1 -17.9 +2.2 +27.l 43
(6) (2) (6) (5) (5) (4) (6) (5) (4) (6)
2 -6.6 -4.4 -5.9 -10.3 0.0 +5.9 -19.8 0.0 +26.8 29
(2) (1) (5) (3) (3) (3) (5) (4) (3) (3)
8 3 -5.0 -4.4 ~13.4 -12.0 -5.3 -2.0 -25.0 -8.9 +13.4 14
q (5) (1) (1) (2) (1) (1) (1) (1) (1) (1)
o
It 4 -5.7 -4.4 -ll.8 -13.1 -4.3 +2.4 -24.9 -5.9 +21.7 18
K (4) (1) (2) (1) (2) (2) (2) (2) (2) (2)
5 -7.0 -4.4 6.0 -8.1 +4.5 +13.7 -21.1 +3.7 +428 40
( 1) (1) (4) (6) (6) (6) (4) (6) (6) (5)
10 -6.1 -4.4 -6.2 -9.7 +0.8 +10.4 -21.4 -0.4 +34.9 31
(3) (1) (3) (4) (4) (5) (3) (3) (5) (4)

 

1. Numbers in parentheses denote relative rank.

2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the

sums.

 

134
5.3.2.2 Congested Conditions Due to a Traffic Accident

In the case where the prediction model was applied when a traffic accident
had occurred, predictions demonstrated similar behavior as those obtained
with models containing just the autoregressive component. This was expected
since the average link travel time does not contain much information related
to the trafic conditions governing the link in the case of a traffic accident. The
error measures for this set of models for the congested conditions for the time

period from 8:30 to 10:00 are shown in Table 5.16.

When 1 was set to one, the mean relative and mean square errors produced by
this set of models were almost the same as those obtained with the models
including the autoregressive component alone. The maximum errors' are
smaller due to the smoothing effect of the average link travel time term that is
included in the model. For smaller values of the forgetting factor, i.e. 0.90 and
0.80, the maximum error is increased up to 13.98 for the ten step predictions
when the autoregressive component of the model is of order higher than 2.
However, for larger values of the forgetting factor, the mean errors are similar
or even worse than those produced by the no predictions case, while for
smaller values of 1 both mean errors become smaller. When n=1 the mean rel-
ative error is decreased by 24% and 33% for the five step predictions and the
ten step prediction respectively, and the mean square error by 20% and 31%
respectively for the same predictions. This improvement of the mean predic- '
tion errors can partially be attributed to the fact that predictions during the
first 34 minutes (from 8:00 to 8:34 when the accident started) made with this
models are of better quality than those obtained with the autoregressive com-

ponent alone, as was shown in the previous paragraph.

135

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

$56.. $3.66 94.86 6336 6386 6mv~.6 606666 2866 56366 958.52.. oz
65666.. 53566 5.26 63.66 .5366 2526 3366 .6266 .6266 n
3666.. .3566 66986 5836 £3.66 6.66.6 3366 66266 $9.66 5 v.
6N666.~ 2.9.66 665mm... $366 3266 .6626 3866 $266 663.66 M W
53.66 2966 5.26 2.966 «$86 663.6 3366 «56666 66366 N m
2686 6~n566 3206 2.566 6.586 5.826 3366 3.6666 «6266 .
53.66.. 2686 mmnw~6 9366 $366 3.3:... «$666 3266 33.66 n
339. 63.86 635.6 .3866 6386 $6.26 3.1.36 2.6.6.6 «6686 v v.
$68.. 3686 «$36 F636 8366 8626 666666 _. 36.66 3966 m H...
6565.. 3.366 3536 $866 3.86 93.6 2.366 36666 66.86 N W
65666.. N386 $686 $6666 5.86 563.6 66636 6.866 2.866 .
.... .... w ...... .m ... .. .... m .8...
2.3.3.8.... 6.56.2 63m 6. 5536.695 6.3.2 63m m 5.833695 63.2. ..Sm fl m<

 

 

 

 

 

.36.... ....3 o... ..e 2...... .95; numb}. a... ”...—5.6.: £9.52 338.3335. 5.3 a. 3:... he fleece .8333... .36 «Ea...

$55.55... 2.558826 52. . .858... ... ...... 8355...... 55...... 8.8555

 

136

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

r323.— m6m36 nVEN6 6336 mNNN66 6m¢N _ .6 666666 m _ 866 v9.86 80636»:— oz
$63.2 6N6N—6 N236 oivofi 666666 ~NNNN6 nNmaw6 2366 2.866 m
336.2 €366 $656 chwn.N_ 28666 $6606 3366 63:66 ~VNNm66 v Y
3336 662.66 3636 "mo—m6 53666 Sow—6 3366 69266 5566 m We
Nwmwo; 66686 8866 Nvaoma N886 6326 3366 mun—~66 2686 N m
6696.— wooN66 6526 mNmaw6 3266 3866 mNmow6 $6666 $686 _
ENS; mmNB6 32mm6 $8666 $6666 3566 nNmow6 $266 8686 m
363.2 wNS; .6 $816 $6666 nan66 2 5N6. 3366 8&66 3636 v M.
nNNoNH 6N$66 :66N6 25ch N6mN66 66266 nNmow6 mwNS6 «6966 m .n__u
mmfi 5 N386 66— _N6 mNmow6 2.266 awng .6 nNmaw6 nN:66 66686 N M
£25.— VNmm66 $626 mNmaw6 36—66 36666 nNmmw6 68666 3636 —

...» “W w ..9 ..m m ...» m w .32..
£83368m 635w 99% 6H 3833605 6822 63m 6 3363695 6864 39% H m<

 

 

 

 

 

 

8:52.86 83 use.

 

137
5.3.3 Models Including the Convection Term

Based on the findings so far, models including an autoregressive component of
order up to four, and the average link travel time for the corresponding time
interval have given the best results, at least in the normal traffic operations
case. In the following models, including the convection term will be examined
to determine if further improvements can be made to the quality of the link
travel time predictions. According to equations (3.3) and (3.4.b), the general
form of these models will be:

T,(:) = Z a‘(t— 1)-T,(t-i)+ 2 zka— 1).T,‘(z— n+0 . 1",(:)+e(t) (5.7)
i=1 Ice lj=1

where I is the set of links k that end at the starting node of link 1. Because no
cycling is allowed in the network (vehicles looping in a sequence of links), set I
will have up to three elements, one link from one of the major arterials of the

test network and one or two connector links.

The number of variables in the autoregressive component will be held con-
stant and equal to three, since the combination of this AR component with the
average travel time gave the best results in the previous step. Furthermore,
for simplicity we will assume that the number of variables m,‘ used in the
model from each connector link It ending at the entrance of the link under con-
sideration I, will be the same and equal to me, unless it is otherwise specified.
The error measures given by equations (5.2), (5.3) and (5.4) will be computed
for a set of models with different values for ma, where a is the previous major

link, and the results will again be compared to the no prediction case.

138
5.3.3.1 Normal Traffic Conditions

For normal traffic conditions the series with travel time observations from
link 15 was used again. In this case, the set I consists of the links {8, 11, 16}.
The error measures for the morning and evening time periods, given by this
set of models are shown in Table 5.17 and Table 5.18. Since the results that
have been found so far indicate the performance of the prediction model dete-
riorates for values of the forgetting factor smaller than one, only the results
for k=1.00 and 1:0.99 are shown in these tables. Different values for the num-
ber of the past values of each link from set I included in the model, ranging

from one to five, were tested.

When the number of past link travel times included in the model from the 'con-
nector links, me, was greater than 2 the model became unstable and the error
increased rapidly. This happens because links 11 and 16 are empty most of the
time, and therefore their travel time remains equal to their free flow travel
time for long periods. When light volumes occur this creates a big shock to the
system, especially when 1:0.99. The RLS prediction algorithm tries to identify
the true values of the respective parameters, which should be close to zero.
When more than one such parameter exists in the model, the algorithm may
assign values to the parameters such that the total contribution made by the
connector links to the predictions of the travel time of link 15 is zero or close to
zero. This is illustrated in Figure 5.18, where the sum of the parameters
(b11,1+bu,2) and (b16.1+b16.2) are approximately equal so they cancel each other,
since the travel time on both links 11 and 16 is equal to their free flow travel
time, 100 seconds. At the end of the second simulated day, and for the case of
k=l.00, all parameters corresponding to the connector links converge to zero.

However, when l is set to values smaller than one, even though the sum of the

139

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5636 62.666 33 66 $536 $866 @366 «6366 63666 «3.666 95368.“ oz .
39:6 3566 3266 2.366 $6666 6386 2636 68666 5866 m
$126 $566 3266 $566 68666 $6666 8636 68666 5866 v v.
wm~26 9.2666 9.366 8866 2.6666 “$666 $366 56666 $866 m W
Emwfic $666 $266 6866 36666 ©5666 8566 68666 8866 N M
6v~6N6 1:666 3266 3366 36666 63366 6386 36666 2.866 _
66666 S 566 w— _ S6 N336 06686 2.866 $366 36666 66866 m
@6666 S :66 VS S6 3366 $6666 $866 3536 $6666 8866 v v.
$6666 2 666 R: 56 $9.66 . $6666 2 866 @386 68666 .2 M666 m ......
36666 3 866 66:66 2366 $6666 2866 $366 68666 3866 N W
3366 2 566 62 86 5966 86666 2 866 N386 «8666 $866 6

.... .w w .... ..m m. .... .m w ....

macaomvoum mama? 63m. 6H 3°32va 68:4 63m m 23886.5 «322 93m H

 

 

823.666: 2533.339 89 $3.5m

3:82 . 83:25 use? .332 . :5... 552:5 2.. ”53.2.. 2252 .5s 3 3:: ... 285 8:52.. 2.3 as“...

 

 

140

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

mans... 9:85 8&3 amaze 88.3 «88¢ 883 $255 $33 2538... oz
55 .o 9:55 32:. SEE «885 586 «$85 @885 ”386 n
«32 .o €85 «~22. 586 283 @385 £22. £83 883 e v.
85 .c :53 :23 835 @585 883 ”88c :83 $83 n W
awe .o E86 82% 8°35 ”885 585 833 88°... 38% N m
33.3 €86 323 was... ~88... 5:3 $33. 385 £33 _
585 : 53 5:3 ”28o 28o... $83 $83 383 3.83 n
385 t 53 £22. 22% 2955 ”885 £82. ”885 £82. a. v.
$53 2 52. 322. 385 $83 $85 888 $85 883 m "..l
283 8 5.3 3.55 585 3°85 58... 586 @886 $83 N m
$33 M: 53 323 335 383 383 W285 ”885 £33 _

...» ..w w as .m m ...» ..m w .5
2828.5 98.2 6am 2 8806.5 222 9% ... maosofifi 22¢ 93m a

 

366—663.— mguggc 669 63.5.—

usfié . 22:35 9&5. .332 . Eta 5.93:5 ...... ”5.5.95 225.2 ...? m. E: ... 2.5m 5:23... "2w «:5

 

141
parameters b11.j and bum still tend to zero, the individual parameters may

assume large values, and even very small differences in the travel time of the
connector links will introduce large errors to the predictions made by the alga.
rithm. As it is noted by Ljung and Sfiderstro'm (Ljung and Siiderstrfim 1983,
page 203) this is a natural result, since those parameters, or linear combina-
tion of parameters, which are not affecting the predictions, cannot be esti-
mated by input-output data, and in such instances the correlation matrix R(t)
becomes singular. Therefore, in all experiments described in the following the

variable me will be set at 0.

In Figure 5.19 the parameters bay j=1,2,3 are also shown. These parameters
correspond to the values of the travel time of link 8 that are used in the pre-
diction model. As can be seen, bu and b3; are close to zero, while bu has a
larger value. This time lag represents the time required for upstream traffic to
reach downstream links. The travel time of link 8 is 120 seconds, and thus the
effect of upstream traffic on downstream travel conditions is lagged by two to
three time steps. Actually the convection wave propagates to the downstream
link somewhat faster than the speed of the vehicles traversing links 8 to enter
link 15, which is indeed in accordance with the findings of Kyte et. al. (Kyte et.
a1. 1989).

As can be seen from the results in Table 5.19 and Table 5.20 the model with ma
equal to two gives the best results for the morning period for both 1:1.00 and
1:099. For the evening period the model with ma equal to three is slightly bet-
ter than the model with ma equal to two, while for both time periods including
a larger number of variables into the model increases the error. The ranking of

the models for the morning and evening time periods is shown in Table 5.19

 

 

b16.1 +b16.2

 

 

 

b11.1+b11.2 d

Parameter Value
0
'}

 

 

 

 

 

m _
414 _ -
06 - w? —
-08 r- -
'10 5 l l 26 24

10 Time (Hours) 15
Figure 5.18: Value of Parameters Corresponding to Connector Links (11 and 16) in

 

 

 

 

 

 

 

 

 

 

 

 

 

the Convection Term
0.4 . . r
1.x: W .4.» ,
0 3 - bag a
0.2 - _

0

g o l ' baa ‘

‘- fl

% 0 - W -‘

S '_‘.— __

E. -O l L- b8,3 -1
—0.2 - -
-0.3 ~ _
’0'4 o 5 16 13 26 24

Time (Hours)

Figure 5.19: Value of Parameters Corresponding to the Major Arterial Link (8) in
the Convection Term

143
and Table 5.20 respectively. In the same table the improvement of these mod-

els over the no predictions case is also shown. As can be seen, all models give
significant improvements over the no predictions case. In the morning period
error reductions reach up to 60% for the maximum error, when 1:1.00, while in
the evening period reductions of the same error exceed 70%. While for the one
step predictions, the maximum error is getting worse, the mean relative and
the mean square errors are up to 30% better. However this is not too serious
since prediction errors for the one step ahead predictions are already very
small. On the other hand, all the error measures for the five and ten step
ahead predictions for both time periods are significantly better than the no
predictions case. From all the models that were tried the ones with ma=1 gave
the worst results in both time periods, while the errors produced fi-om the 'rest
of the models were similar. This is explained by the fact that the one step back
travel time values of the upstream links do not contain any information for
the downstream tramc conditions, since it has not yet started affecting these

conditions.

Also in Table 5.21 are shown the relative improvement of the performance of

the model including the convection term with ma=2 over the no prediction
case, the simple autoregressive model and the model consisting of only the
autoregressive component and the average travel time of the link. As can be
seen, the improvement to the one step predictions are of the order of 20% for
the morning and 30% for the evening period. The five step ahead predictions
also show significant improvements over the models that include the average
travel time of the link: approximately 30% for both the morning and the
evening time periods for the mean relative absolute error, 36% for the mean

square error and above 40% for the maximum error. The ten step ahead pre-

144

Table 5.19: Percent Difference of Prediction Error of Models Including the
Convection Term from the Case of No Predictions - Morning Period (6:00-11:00)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Step Ahead 5 Step Ahead 10 Step Ahead
so Predictions1 Predictions Predictions fig
A2 A2, Ae, A2: A2, Ae, A2 A2, Ae, °‘
1 43.1 -200 34.1 41.9 43.3 -60.8 41.0 -575 49.7 34
(5) (4) (1) (3) (5) (1) (5) (5) (5) (5)
2 -237 27.5 +3.1 42.1 -512 -60.5 42.2 -58.6 -52.1 15
(3) (1) (3) (1) (1) (2) (1) (1) (2) (1)
g 3 -233 25.0 +2.7 42.1 -512 -60.1 42.2 -58.6 -52.1 17
u (4) (2) (2) (1) (1) (3) (1) (1) (2) (2)
K 4 -31.4 -225 +33.4 -36.9 47.3 -55.7 41.3 53.2 -52.1 32
(1) (3) (4) (5) (4) (5) (4) (4) (2) (4)
5 -30.1 -20.0 +41.0 -37.3 43.3 -57.3 41.6 -58.6 -52.3 23
(2) (4) (5) ~ (4) (3) (4) (3) ( 1) (2) (3)
1 -143 -15.0 -333 -32.1 -395 42.6 -233 42.5 +6.3 36
(5) (5) (1) (4) (4) (3) (5) (4) (5) (5)
2 -314 -300 -19.3 -34.1 43.4 49.4 -36.4 45.4 -3.9 15
8 (4) (2) (2) (1) (2) (1) (1) (1) (1) (1)
g 3 -357 -325 -12 -329 42.6 42.9 -30.4 44.3 +1.6 22
u (3) (1) (3) (2) (1) (2) (3) (3) (4) (2)
‘< 4 -36.4 -27.5 +16.3 -32.4 41.1 42.4 -30.6 -44.6 +1.0 26
( 1) (3) (5) (3) (3) (4) (2) (2) (3) (3)
5 -36.4 .27.5 +16.0 -31.3 -36.4 -37.9 -29.1 42.5 -2.1 29
(1) (3) (4) (1) (5) (5) (4) (4) (2) (4)

 

1. Numbers in parentheses denote relative rank.

2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the

sums.

 

145

Table 5.20: Percent Difference of Prediction Error of Models Including the
Convection Term from the Case of No Predictions - Evening Period (14:00-19:00)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Step Ahead 5 Step Ahead 10 Step Ahead
Eu Predictions1 Predictions Predictions (154
- -- — — -- -- M
Ac Ac, Ac", Ae Ae, Aem Ae ' Ae, Ac,
1 -l4.6 -15.6 -37.3 44.4 -51.1 -60.5 -35.3 -37.6 43.0 33
(5) (5) (5) (2) (1) (5) (5) (5) (5) (5)
2 -37.7 -35.6 -53.2 43.3 -504 -72.3 -36.5 -38.6 43.6 24
(4) (3) (4) (3) (3) (1) (3) (1) (2) (4)
g 3 -333 -35.6 -54.3 43.9 -51.1 -72.1 -36.5 -38.6 43.7 19
.. (3) <3) (3) (1) <1) <3) (3) <1) (1) (1)
‘< 4 41.1 -37.3 -55.2 -33.3 46.6 63.3 -36.6 -33.1 43.4 22
(1) (1) (1) (4) (4) (4) (1) (3) (3) (2)
5 40.2 -37.3 -55.0 -33.1 46.6 -72.2 -36.6 -33.1 43.4 23
(2) (1) (2) (5) (4) (2) (1) (3) (3) (3)
1 -13.9 -11.1 47.7 -353 -374 -352 -270 -233 -27.6 37
(5) (5) (5) (5) (5) (4) (4) (2) (2) (5)
2 -38.4 -35.6 49.2 43.9 43.1 -559 -235 -243 -274 20
(4) (4) (3) (1) (1) (2) (1) (1) (3) (1)
g 3 42.0 40.0 -59.5 42.6 ' 47.3 -61.9 -274 -22.2 -20.5 23
.. (3) (3) (1) <5) (2) (1) (3) (5) (5) (4)
“ 4 46.0 42.2 -50.0 42.3 46.6 47.9 -27.5 -23.3 -24.3 23
(2) (1) (2) (4) (3) (3) (2) (2) (4) (2)
5 47.4 42.2 42.6 42.9 45.0 -30.3 -26.8 -233 -293 26
(1) (1) (4) (3) (4) (5) (5) (2) (1) (3)

 

 

 

 

 

 

 

l. Numbas in parentheses denote relative rank.

2. Cell numbers indicate the sum of ranks, and numbers in parentheses indicate relative rank of the

sums.

 

146

Table 5.21: Percent Difference of Prediction Errors of Models Including the
Convection Component Over the No Predictions Case, Autoregressive Models and
Models Including the Average have! Time

 

 

 

 

 

 

 

 

1 Step Ahead 5 Step Ahead 10 Step Ahead
Predictions Predictions Predictions
Model
A? AZ, Ae, A? A3, Ae, A2 A2, Ae,
No Predic- -23.7 -27.5 +3.1 42.1 -512 -60.5 42.2 -58.6 -52.1
E tions
a AR(Z) -235 -21.6 -201 41.0 46.3 -53.2 40.2 40.3 43.0
a
'g AR(3)& -19.2 -194 -19.5 —29.2 -35.9 43.3 -7.4 -7.3 -9.2
g Diurnal
Term
N0 Pnedic- -37.7 -35.6 -53.2 43.3 -50.4 -72.3 -36.5 -33.6 43.6
E tions
a AR(Z) -33.5 -32.6 45.6 41.3 49.6 -70.3 -34.3 -36.6 40.1
g AR(3)& -33.0 -31.0 -31.3 -297 -37.5 -60.3 -0.4 4.1 -7.7
If; Diurnal
Term

 

 

 

 

 

 

 

 

 

 

 

 

 

dictions, although better, are not significantly improved. The maximum error
shows improvement of approximately 8% for both periods. However the mean
relative error, at least for the evening period does not show any significant
improvements over the later model. The poorer performance of this set of mod-
els for predictions further into the future can be explained because such pre-
dictions are based not only on previous predictions of the travel time of the
link that is under consideration, but also on predictions of the main arterial
link(s) that ends at the entrance node of the link, i.e. link 8. The improve-
ments over the no predictions case and the simple autoregressive models are

significant and always greater than 20% for the one step predictions, 40% for

147

 

205 1 j 1 Y I T

l

200 Observed Value

195 Predicwd Value -1

 

53'

185

180

 

Link Travel Time (Seconds)

 

 

 

 

 

6 6.5 7 7.5 3 8.5 9 9.5 10 10.5 11
Time of Day (Hours)
Figure 5.20: 1 Step Predictions and Observed Values of Travel Times of Link 15 -
Model Including the Convection Component - Normal 'Ihflic Conditions - Morning
Period - 1:1.00, m,=2

205 , . . . I . . 7 1

 

1

§

Observed Value

p—e
‘0
M

53'

y—s
on
(It

5

 

Link Travel Time (Seconds)

 

     

 

 

6 6.5 7 7.5 3 3.5 9 9.5 10 ' 10.5 11
Time of Day (Hours)
Figure 5.21: 10 Step Predictions and Observed Values of Travel Times of Link 15 -
Model Including the Convection Component - Normal 'Ii‘affic Conditions - Morning
Period - 1:1.00, ma=2

148

205 . r

 

N
8
1

Observed Value ~

—e
c

M
l

Predicted Value —

 

H
8
l
l

 

185 -

5

175 r-

Link Travel Time (Seconds)

170 -

 

165 -

 

 

lw r 1 1 1 1 L _L_
14 14.5 15 15.5 16 16.5 17 17.5 18 18.5 19

Time of Day (Hours)
Figure 5.22: 1 Step Predictions and Observed Values of Travel Times of Link 15 -
Model Including the Convection Component - Normal Traffic Conditions - Evening

 

 

 

Period - 1:1.00, ma=2
205 1 I l' T f T 1
200 1- Observed Value <
195 - PredictedValue ‘
190 L ‘ .1

§

u—a
\I
U.

L A 1"» d

A ‘11:" '
a g ’5‘ .r‘
Mn" ’ .

it:
17

Link Travel Time (Seconds)
92°
‘42...
¥
1

:3
O
1

 

s—s

Q

U
l

 

16014 14.5 15 15.5 16 163 17.5 is 13.5 19

Time of Day (Hours)
Figure 5.23: 10 Step Predictions and Observed Values of Travel Times of Link 15 -
Model Including the Convection Component - Normal Traffic Conditions - Evening
Period - 71:1.00, ma=2

149
the five step predictions and 35% for the ten step predictions.

The one and ten step ahead predictions for the morning period obtained with
these models are shown in Figure 5.20 and Figure 5.21. Also in Figure 5.22
and Figure 5.23 are shown the same predictions obtained for the evening
period for the case with 121.00. As can be seen in the figures corresponding to
the 10 step ahead predictions, the effect of‘ the average travel time is lessened,
and predictions follow future travel times more closely than when the model

with just the autoregressive component and the average travel time is used.

This is shown more clearly in Figure 5.24 where the five step predictions
obtained with a model including the average travel time (o) and those
obtained by a model that in addition includes the convection term (+) are plot-
ted. This is explained also by examining the value of the parameter corre-
sponding to the average value of the travel time of the link. While in the
former model the parameter stays above 0.08 for the entire second simulated
day of the simulation run, for the model that includes the convection term it
stays very close to zero for the entire day. At the beginning of the simulated
day these two parameters are 0.0929 and 0.0021 respectively, whileat the end
they become 0.0855 and 0.0072. This means the contribution of the average
link travel time is less in the models that contain the convection term, at least
by one order of magnitude. However, when the average travel time is excluded '
from the model, the five step and ten step ahead predictions became worse
than when this term is included in the model. The behavior of these two
parameters is shown in Figure 5.25 where d", is the parameter corresponding

to the model without the convection term, and dc to the one with it.

 

205 l T— I 1 l I I l I

200

195

190

185

180

175

Link Travel Time (Seconds)

 

 

 

170

165

 

 

160

 

 

Time of Day (Hours)

Figure 5.24: 5 Step Predictions with Model Including the Convection Term («1) and
with Model Including the Average Travel Time Only (0)

 

0.1 I I I I

 

0.06 r- -

0.04 - ~

 

 

Parameter Value
.6 .5 .<'>
8 i 8
O
l l l

.6
8
l

 

 

0 5 10 15 20
Time of Day (Hours)

Figure 5.25: Parameter Corresponding to the Average havel Time Term from
Model Including the Convection Term (dc) and from Model Including the Average
Travel Time Only (dm)

5‘:

 

151
5.3.3.2 Congested Conditions Due to 'h'affic Accident

In the case where the link under consideration is experiencing a traffic acci-
dent, demand originating from upstream links will determine the level of con-
gestion in terms of the duration of the aftermath of the accident. The travel
time data from link 19 were used in this experiment, and thus links {12,20}
comprise set I. The speed with which the queue of link 12 is dissolved will
directly affect the speed with which the queue of link 19, which has started
dissipating after the end of the accident, will dissolve. Therefore, the travel
time of link 19 should be related to the traffic demand on link 12. Again the
error measures are calculated for the time period starting at 8:00 and ending
at 10:30.

The results obtained in the case when the congested link (link 19) was the one
for which the predictions are performed, are shown in Table 5.22. As can be
inferred from these figures, there is no improvement in the quality of the pre-
dictions made with this model configuration. In all cases, predictions made
with the models including just the autoregressive component along with the
average link travel time give better quality predictions.

This was expected during the first minutes of the accident, since trafic condi-
tions of upstream tramc do not affect the occurrence of the incident. The one
and ten step ahead predictions obtained with these models are shown in Fig-
ure 5.26 and Figure 5.27, for the case where A=1.00 and in Figure 5.28 and
Figure 5.29 for the case where 1:080. The predictions shown are obtained
with a model with ma=1 including an autoregressive component of order n=2

and the link average travel time.

152 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

T33. N83... SEN... _ 688... ..NNNo... as... .89.... 38... 348... 333.3... oz—
..nNSN .28... N54... ..aN... 38... ...NSN... was... :22. 88.... n
8.2: was... 3.52. 8N8. 58... N432. 28.... Es... 8.3... 4 v.
$53 5.3... 48:... 583... 3.68... 83:. 88.... No.5... 53... N w
NESN 53... 3.32. 8.8... 38... was... was... .85... 3.3... N m
NasN 2.5.2. 3.5.... 2.32. 3.48... N22... 88.... 685... .83... .
8N8. N83... 822 N48... 3.8... 32... New... 38... 58... n
Smut... 2636 66:06 3.636 6286 83.6 N336 35.666 3266 v v.
38%.. N88... ”N82. .83.... ENG... N32. .83... N88... 388... m "....
9.8: .53... 588 N53... N.NN...o N492. 9.8.... 382. 2.8... N m
EN: 683... .833 28.... .88... 32...... 68%... N38... .438... .

.... .w m .... ..m m .... ..w w ....
935.69... .522 .....m S 835.62.. .592 63m 6 2.3.6.66... 22.4 63m .

 

ens—.85.. Sausage cm: . .5284 ... 25 26......50 68...; 8.8.50 5...... ......— 6... ... 2.2.2.55
5:82.60 2.. ...... 2...... .23.; 382.4 2.. ”.55....— 582 353.322.... ...... a ....5 .6 28.... 8.6.8... ANNA 63a.

 

153

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

in”... $9.... SEN... 638... ..NNN..... 83.... 8.5.... 28.... 348... _ 36.3.32. ..z
5%.... 88.... .....N... 88.... 33.... N83... 28.... 68...... N28... n
:5... 848... 68:... 38.... RS... 3s... 88.... 43...... 85.... .. v.
3N5. NNNN..... 2.8... 88.... N..NN..... NN..N.... 88.... 22.... 2N2... N w
84%.. 3.8... $5.... 28.... 628... :2... 33.... 3N5... 68...... N m
68%.. .88... 38.... N83... ”3...... 5...... 38.... 8...... .548... .
83... $48... ..6N.N... 88.... NS... 432... 38.... 82.... 88.... n
N48: 248... ......N... 88.... 6:8... :8... 38.... 84...... 23.... .. v.
882 33...... ..N...N... .88.... N. .8... SN... 28.... 9.2.... 48...... m M.
£2: .98... :8... 83.... ......N..... 63:... 38.... 2.2.... 68...... N M
2wa 22.... .48.... N22... 48...... .58.... 38.... 68...... $2.... .
... .N N .. .N N .... .N N ....
2532695 6626... 33m 3 $553695 63.2 33m 6 3385655 6.85.4 53m a

 

.82....8. New 2...:

 

154
The erratic behavior of the model during these first minutes is due to the

inclusion of the convection term into the model, which creates a delayed
response to the rapid increase of the travel time by a few time steps, as com-
pared with the response of the models without the convection component. This
occurs because the relationship of the travel times of links ending at the start-
ing node of the link under consideration has been established by the model,
and when the incident occurs the parameters associated with the convection
term still have large values, thus greatly affecting the predictions. This is also
the reason the maximum error, even when ma is larger than 2 and the forget-
ting factor is set to small values, does not get such high values as it did in the
previous models. During the incident though, this relationship is reduced and
the prediction model behaves much like the models without the convection

term.

When 151.00, and after the incident has ended the model underestimates the
predictions for the five and ten steps ahead, because of the strong shock to the
system during the accident (travel time increased almost by a factor of 10) and
because of the long memory of the model, due to which the parameters associ-
ated with the convection term diminishes much slower. In the case of 2:0.80
the shock is overcome fast and predictions during the period of the dissipation
of the queue are close to the real values. Also, immediately after the queue is
dissipated, ten step predictions return to normal values.

155
120)

 

5

§

Link Travel Time (Seconds)
§ §

 

§

 

 

 

P

 

0

 

 

a. 8.5 6 9.3 10 10.5
Time of Day (Hours)

Figure 5.26: 1 Step Predictions of Travel Times of Link 19 with Model Including the
Convection Term - Congested flame Conditions - 1:1.00

 

 

 

 

 

 

 

 

 

 

 

 

 

14m r T r I
12m _ Observed Value _
,3 ’ Predicted Value
E1000 - -
:5; 800 L ‘
7; 600 - _ .q
5 fi ...
E 400 - -
..l
200 - ’ -
0 1 1 1 1
E. 8.5 9 9.5 10 105
Time of Day (Hours)

Figure 5.27: 10 Step Predictions of have! Times of Link 19 with Model Including the
Convection Term - Congested Traffic Conditions - 2:1.00

156

 

 

 

 

 

 

 

 

 

 

 

12w 1 T at I
10“) _ F Observed Value _
.3 Predicted Value
2 800 _ _
8
Q.
E 600 + _
F .... -
T)
>
g 400 - 1
g
200 - —
...—r T .A _ , r
o 1 1 L 1 ~
8 8.5 9 9.5 10 10.5
Time of Day (Hours)

Figure 5.28: 1 Step Predictions of Travel Times of Link 19 with Model Including the
Convection Term - Congested Traffic Conditions - 1:0.80

 

 

 

 

1200 . , r .
r
10“) _ ObsavedValue _
. Ll ‘ PredictedValue
800 - _

 

 

 

Link Travel Time (Seconds)

 

 

 

 

 

 

 

 

 

 

400 - ,
200 + _
0 ' J 1 1 i
8. 8.5 9 9.5 10 10.5
Time of Day (Hours)

Figure 5.29: 10 Step Predictions of Travel Times of Link 19 with Model Including the
Convection Term - Congested Traffic Conditions - 1:0.80

157
5.3.4 Models Including the Congestion Term

In the last part of this portion of the study we examine the effect on the link
travel time predictions of the information from downstream links. For this
reason, the congestion term was included in the model, which will have the

form:

1,0) = 2a,.(t—1)-T,(z-i)+ 2 ZkaU- l)-Tk(t-j)+

i=1 kelj=l

+ 2 2' cp,(:- 1) - rpa — h) + d- m + e(t) (5.8)
peOh=l

where 0 is the set of links p that start at the exit node of link 1. Again, due to
the geometry of the network that is examined, set 0 will consist of one or' two
connector links and one link of one of the major arterials. As was discussed in
paragraph 3.3.2, the congestion term is included in the model in order to cap-
ture the efl‘ect of traffic shock waves travelling in the opposite direction of the
traffic. Such shock waves may be produced either due to excessive demand or

due to a traflic incident.

In the following experiments, the number of variables from each link in the
congestion term that will be used into the prediction model is examined. Again
for reasons of simplicity, the number of variables used from the connector
links rc will be equal to the number of variables used from the link belonging
to the arterial rd. The order of the autoregressive term is kept constant and
equal to three, and the diurnal term is also included in all models.

158
5.3.4.1 Normal Traffic Conditions

In the case of normal traffic conditions the travel time series of link 15 was
considered, and set 0 consisted of the links {20, 21, 22}. The mean relative
error, the mean square relative error and the maximum relative error for the
predictions obtained by these models are shown in Table 5.23 and Table 5.24

for the morning and the evening periods respectively.

The models examined included the convection term with ma=2 (for link 8),
along with the autoregressive and the diurnal terms. In all cases the resulting
errors are slightly worse than those obtained with the respective model con-
sisting only by the autoregressive, the convection and the diurnal terms. This
was expected since there was no traflic wave traveling backwards (i.e. from
link 22 towards link 15). Therefore, current travel times of the link under con-
sideration should not be correlated to the current or past values of the travel
times of downstream links. Indeed the parameters associated with the conges-
tion term, in the case of normal tramc operations are converging to zero. This
is illustrated in Figure 5.30 where the parameters associated with link 22 are
plotted for the second simulated day. After each peak period the parameters
are decreased in a stepwise manner. This happens because the rest of the time
travel times of both the link for which the predictions are performed and the
downstream link are inactive and no change on their relationship can be

detected. The contribution of the congestion term:

2 z cP,(:- 1) . Tpa- h)

p 6 011 = l
to the one step ahead predicted travel times of link 15 is shown in Figure 5.31
where as it can be seen it converges to zero with the same stepwise manner as

the corresponding parameters.

159

 

 

5...... _........... 78...... 7...... _.......... _......... _.......... 7.38... 73.8.; 2828... oz .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3...... 8.8... 8...... 8...... 8.8.. ...8... 2...... ....8... 2.8... n
.5... 2...... 2...... ......o 8.8... 38.... .88... .....8... 8.8.. v v.
...... 8.8... 8...... 2...... 8.8... .88... 8...... 88.... ....8... m ._n_.
2...... ....8... .85... 2...... 8.8... .88... 5...... .....8... ...9... . m
8...... 8.8... .32... .5... .88.. ....8... .38... ....8... ...8... .
.32.... .... ....... ... ...... 8...... .88... ....8... 2...... .88... $8.... .
83.... .......... 8...... 38.... .88... ...8... ....No... ....8... 3.8.. v v.
83.... .. ........ ... ...... 9...... .88... . ...8... 5...... .....8... ...9... ... .....
5...... .28... .... ...... .38... .88... 38.... .....o... .....8... ...8... . m
.38... a. .8... .25... can... .88... 38.... 8...... ....8... ...9... .

.. .. . ... .. . ... .. m ..

22.0.8... .52... as. ... 2.3.2.5... .52... as. m 828...»... .322 mam .

 

 

 

 

 

.8............. 22.28.... ...... 3......
.55.... .8225 as... .55.: . 5...... 8.8.5.. 2.. .525... 288,. ....e m. ...... ... 22.... 8.8.8... a... 2......

 

160

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3.... 3.8.8 8.8... $2.... .28... $28... _ n88... 9.8... $98... 826.3... oz
.32... $.86- .85... 3.8... 2.8... :8... N28... 38... 9&8... m
. .Nm. .8 .38... 865... 253... $8... 8.8... 3.8... «88... utm8d v Y.
3.3... $.86 365... 358... $8... 88... ~38... .88... .386 m P
8%.... 3.8... 265... 88... 2.8a... v38... ammo... 38¢... a~m8d N W
Rom—... 638... .85... .386 $8... v88... $.86 58... nmm8d .
898... ~28... 83¢... 83.... .58... 8.8... News... R8... 88... m
8.8... 2.8... :30... 3%.... .886 88... omens... mmoood 538... v v.
28.... 8.8... $2.... ~38... E8... v38... 868... .88... .38... m .....
$8.... 8.8... «3.5... 658... 28... 3.8... .88... R8... 058... N W
.38... .28... SEC... 2.68... 2.8... $83. ammo... 88o... mhm8d .
...... .w . ... .m . ...... .. . ..
9.3.3695 6.5.3. 93m 3 2.38.695 6.8.6... gnaw m 2.33.605 6.8.2 93m H

 

 

 

 

 

Sena—.83.— mceuatvmnc 89 63.5

.55»... ...........=5 9.22... ...:ch . as... 5.5.80 2.. 9.622.. 2.8.2 ....B m. ...... ... 28.... 8.8.8... ...... 2......

 

161

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0.5 . r ,
0.4 _ -
0.3 _ _
g 0.2 '- c-
E 0 1 C223 _‘ _ _
a ’— \ __
A. \
u— — _.. _M.
g 0 _ C22,] __ ,r- 2
.g -o.1 _ c *J _
> 22.2
-O.2 — _
-0.3 - -
'0.4 >— —4
’0'5 o 5 16 13 2E)
Time of Day (Hours)
Figure 5.30: Convergence of Parameters of Congestion Term to Zero Under Normal
Traffic Conditions.
4 I I
3 - _

 

 

 

Value Of Congestion Term
I

 

 

l l l

lo 15 20
Tune of Day (Hours)

Figure 5.31: Contribution of the Congestion Term to the l-Step Ahead Predictions
Under Normal Traffic Conditions.

 

'20 5

162
5.3.4.2 Congested Conditions Due to Traffic Accident

In the case of congested traffic conditions, the travel time observations of link
12 will be examined. In this case set 0 consists of the links {18, 19} and the
way that the shock wave produced on link 19 due to the accident affects the
travel times of link 12 will be investigated.

First the results obtained with a model consisting of the autoregressive com-
ponent only, the one consisting of the autoregressive term and the diurnal
term, and the one including the convection term are shown in Table 5.25. As is
shown from these results, analogously to the case of link 19 on which the acci-
dent occurred, the simple autoregressive models produces errors similar to the
no predictions case when the forgetting factor is equal to 1.00 or 0.99.‘ For
smaller values of A, the model is exited more easily which result in large val-
ues of the maximum error. This also results in a large mean square error
value although the mean average error is improved slightly. When the diurnal
term is added into the model, the results are similar to the ones obtained with
only the autoregressive term. When A was set to 1.00 or 0.99 the resulting
errors were worse than the no predictions case while for smaller values of A
the errors are smaller for the ten step ahead predictions but worse for the rest
of the predictions. This occurs because at the beginning in the creation of the
queue the model reacts too erratically to the sudden increase in the travel
time, and it reaches the allowable ceiling value, and then goes back to the
allowable floor value once or twice until it stabilizes close to the observed
travel times. The result is a few gross errors at the beginning of the creation of
the queue which deteriorate the values of the error measures. However, in the
ten step predictions this “bang-bang" effect is not so obvious due to the
smoothing effect of the average value. The same is also true for the predictions

163

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.83.. SS... 83.... 2.3... 8...... 3.... ... 3.2... .28... 8.8... _ ease»... oz
. . . . . . . . . .25 e
.....8. $2.... .22 .. 88.. N .88.. m2... .. $8.. $2.... 3.8.. bus. ..9...
V»
. . . . . . . . . 2E. .25 w
.....8. 3.8.. .82 .. 88.. N 2.8.. ...9. .. 83.. 8...... 33”.... .2 is”... w
.33.. .88... 9.2... .83... 8...... ... S. ... $3.... :28... 8.8... ....2
.>8
...9... .38... 9.8.... 83:. 8...... .3. . . ... 3.2.... 88.... “2.8... tus. WNW...
. . V»
2...... .26.... .F
...9... .. .88... .52... 8.3... .82.... 8.... ... .82... 82...... 3.8... .2 e .92 .m
.8... 8.8... 88.... .83... $2.... 3.8... .82... $8.... .88... 5.2
830...»... .32... .....m ... 830.62.. .52.... .....m m 8352.. .322 ..3m .

 

.8568... ”Seats... 8.. ... ...... .... 2.8.8.. .22... 9.6.... fl. ...... ... 28.... 5.8.3... "m3 2......

 

164

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.83.. N88... SEN... .22.... 82.... 82...... 2.8.... .28... 88.... 25.28.. oz
. . . . . . . . 2.8 ...
82... N 5.8.. «...... .. 88.. N .22.... 2.... .. .8... N .88.. $8.... :22 .62..
V»
. . . . . . . . . 2E .25 F
3.8.. . .88 .. .8... .. 8...... N .22.. .. at... .. .88 N 88 .. 8...... .. 22 a .25. .m
88.: .88... 88: ... 22.2 888... 28.... SE... 38.... 8.8... .9...
$8
3.8... 88.... ..NN... ... 8......N 2.8... 2.8.... 82.2 N88... 82...... 2526.“...
. . V»
. . . . . . . . . 2E .25 ....
.28 N 8.8 .. .82 .. 8.5.. N 22.. .. ....8. .. .88 N ......8 .. .8... .. .3. a 6.... m
..SSN .88... m2... ... 83.... 2.2.... 3.8... 22:... $8.... .88... 6.2
2.80.8... .8... 2% ... 8°88“... .32... 2% m 862.2... .32... 2% .

 

 

 

 

 

...9—.5250. mud 035.

 

165
obtained with the model including the convection term.

The results of the prediction models including the congestion term are shown
in Table 5.26. When the forgetting factor is set at 1.00 or 0.99 the resulting
errors for all the models that were tested were greater than the errors result-
ing from the no predictions situation. However, the errors of the model with
ra=10 gave the smallest errors for both 7L=1.00 and 1:099 and for all the pre-
dictions, the one, five and ten step ahead. In the case when l is set to the
smaller values of 0.90 and 0.80 the prediction errors of all models was worse
except the model with ra=10, for which the error is smaller. In the case of
1:090 the resulting error from this model was smaller than that obtained
without any predictions performed or those obtained by any other model. -

This was expected because there is a delay of approximately 8 time steps (8
minutes) between the time the incident occurs on link 19 and the start of the
queue on link 12. Therefore there is a time lag before travel time on link 19
starts affecting the travel time of link 12. This time lag represents the time
required for the shock wave to be transferred from link 19 to link 12. Thus
models with ra smaller than 8, i.e. 1,2 and 5, fail to capture the relationship
between the travel times of links 19 and 12, and the contribution of the con-
gestion term to the predictions” is relatively small most of the time (Figure
5.32). On the other hand, when rd is equal to 10 the contribution of the conges-
tion term to the prediction of the travel time of link 12 is more significant, as
is depicted in Figure 5.33. When ra=10 the total contribution of the congestion
term gains not when the accident starts, but when the queue on link 12 starts
building up, and draps to a lower value atthe end of the incident and decays

as the queue generated by the incident is dissolved.

166

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_ .82.. N..N.... SEN... 3...... 82.... 3...... ......2. .28... 8.8... _ 332.3... oz
.22... 2%.... ....N... «.5... $2.... ...... ... 3...... .88... 38.... ...
......o. .83... .82... 2.2... 5...... N2... ... ENE... 2.8... 2...... n _v_.
0
...... 08...... .83.... .32.. 2...... E2 ... ..NE... .28.... ONE... N mm
3.2.... .83... .28... 8...... 8.8... ...... ... 5.3... .....o... .23.... .
5.2... 9...... 2...... ..E... 23...... ..N... ... 5...... 88.... N...N.... ...
.85.. .88.. 38.... 8...... _ 3.8... :3... 2.8:. 28.... .58.. m a.
....8... 22...... .....N... N...... 3:8... ..N... .. 2...... .28... 3...... N .m
.35.... N......... .....N... 8...... ....N.... E2 ... 8.2... ...8... .88... .
EN mm. W EN ”W W Ks” hm W RQEO
82.2.3... .32... 8.. .. 2.2.2.2.. .32... as. m 2.32.3... .32... .3. . ....
............... 2.23:3...

..2. 2.2.380 2.3.... 8.3.80 . 53.. 5.33.80 2.. 2.3.2.. 223:. 5.2 N. ...... 3 3.2.... 8.3.3... ...... 2.3...

 

167

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

...... ....o... 8...... _ 3...... .38... 3...... 3...... .38... 8...... 322.3... 9..
...... .38... .82... ...... 8...... 3...... ...... 33...... .38... ...
...... 3...... .....3... 3.3.. ......o... ....2... ........ 38...... 2...... 3 a.
...... 33...... 8...... ...3... .....o... 3...... ...... 3...... 3.8... . m
.38... 32...... 3...... .....3 .....o... .23.... 3...... 3...... 3...... .
3...... ....o... .33.... ......o 5...... 3...... ....o... .38... 3...... ....
3...... 3.3.... 2...... 2...... 32.... 3.2.... 3...... ......5... ....c... 3 m.
3...... 2...... 2.2... 8...... .38... 3...... 3...... 3...... 2...... N m
...... 8...... 2...... 3...... 3...... 3...... 2...... .22.... 3...... .

.. .. .. .. .. .. .. .. .. ..

3°33... .32... 3.. ... 2.23.3... .32... .3. m .5332... .32... .3. .

 

 

 

 

 

.32....8. .... 2......

 

 

168
300 'r r

 

250 - _
200 L .
150 — _
100 r- .

 

Value of Congestion Tenn (Seconds)
1]!
CD CD
I

 

 

 

 

-50 _ -
-100 _ -
'150 r 1 !
'200 a: 8.3 9‘ 9.3 16 10.5
Time of Day (Hours)

Figure 5.32: Value of the Congestion Term from Link 19 for the 1 Step Travel Time
Predictions of Link 12 - ra=2

§
i
i

 

‘3

8

I
1

 

 

 

 

Value of Congestion Tenn (Seconds)
5 § § § §
1

CD

J

a: 8.3 6 9.3 10 10.5
Time of Day (Hours)

Figure 5.33: Value of the Congestion Term from Link 19 for the 1 Step 'IYavel Time
Predictions of Link 12 - ra=10

 

 

 

169
The one and ten step ahead predictions obtained with the model including the

congestion term with rd: 10 and for 1:1.00 are shown in Figure 5.34 and Fig-
ure 5.35. As can be seen in these figures, the effect of the long travel time of
link 19 due to the queue that is formed on it is carried for a long time on the
ten step ahead predictions, thus increasing the error. On the other hand when
1:0.90 (Figure 5.36 and Figure 5.37) the predicted values are not affected too

much by the queue on link 19, and remain closer to the observed travel times.

170

g
1
.J

 

§

Observed Value

00

8
I
1

Predicted Value

 

Link Travel Time (Seconds)
w A UI \l
s s 8 § 8
L l l L l

N
8
I
l

 

 

 

 

 

'—

8 8.5 6 93 lb 10.5
Time of Day (Hours)

Figure 5.34: 1 Step Predictions of 'h'avel Times of Link 12 with Models Including the
Congestion Term - “=10, 1:1.00

 

100

 

1000 I f . r
900 - Observed Value .
800 — Predicted Value -

700.

 

Link Travel Time (Seconds)

 

 

 

 

 

 

soo -
400 L
300 -
200 -
10° 8. 8.5 5 9.3 16 10.5

Time of Day (Hours)

Figure 5.35: 10 Step Predictions of Travel Times of Link 12 with Models Including
the Congestion Term - ra=10, 1:1.00

171

 

10(1) r 1
900 ~ -
Observed Value

800 - -«
Predicted Value

700- —

 

600 - -

500. -

400- _

Link Travel Time (Seconds)

300» -

200- -

AA .A—
A

 

 

 

" ww— v T

a: 8.5 a 9.3 16 10.5
Time of Day (Hours)

Figure 5.36: 1 Step Predictions of Travel Times of Link 12 with Models Including the

Congestion Term - re: 10, 1:0.90

 

 

100

1000 . r r r

 

I

900 P Obsaved Value

800 - Predicted Value

I

 

700.

Link Travel Time (Seconds)

 

 

 

  

 

 

 

 

 

500 i- -
400 - -
300 - ~
200 - 4

.._ - 1‘“ J, 4"»
10° 8. 8.5 9 9.5 10 10.5

Time of Day (Hours)

Figure 5.37: 10 Step Predictions of Travel Times of Link 12 with Models Including
the Congestion Term - 5:10, 1.20.90

172
5.3.5 Discussion of the Results and Further

Developments
From the previous analysis it can be concluded that the models including the
autoregressive, the diurnal and the convection terms are the most appropriate
for the prediction of the link travel times. Models including the convection
term did not give acceptable results. A probable reason for this is due to the
low influence for long time periods of the input data from the downstream link
on the travel times of the link under consideration. For the same reason model
that included information from connector links in the convection term pro-
duced larger errors when a small change occured on the travel time of the con-
nector link. Therefore, in the following analysis the models that will be used
will include the autoregressive, the diurnal and the convection terms with

order mc=0 and ma depending on the length of the upstream link.

It is obvious that the prediction model works best under normal traffic Opera-
tion with the forgetting factor set at one. The fact that the results are better in
the case of the normal operation than in the case of the trafic accident are not
a surprise, since when the accident occurs there is a strong shock to the sys-
tem and the RLS algorithm operates efficiently only while the parameters of
the model are not changing too fast.

Because the environment in which the filter operates is not stationary, even
during normal Operations - since the stochastic process of the link travel times
which is followed by the filter has variations which are time dependent - it
was expected that the model would give better results when the forgetting fac-
tor, l was set to values less than one. When such values are assigned to the
forgetting factor, the adaptation of the model to the prevailing trafic condi-

173
tions is fast, but at the expense of an increase in the mean relative error. This

is obviously a trade off that has to be made between the tracking ability of the
model and its sensitivity to the prediction errors. When the forgetting factor is
set to values smaller but very close or equal to 1.00, the result is smaller
errors due to the large amount of data that are used for the computation of the
parameter vector, since old and recent prediction errors contribute equally to

the loss function (3.21).

An important feature of the prediction model that includes the diurnal term,
can be used for the justification of the usage of a large value for the forgetting
factor under normal traffic condition. The inclusion of the average travel time
into the model has as an effect that the link travel time process approximates
a stationary one. Of course, the difference [T, (t) -T, (t)] is not really station-
ary, since during non peak periods the value approaches zero since both vari-
ables T, ( t) and T, (t) are very close to the free flow travel time, while during
peak periods where there is much higher variation in T, (t) the difference
[T, ( t) -T, (t)] oscillates around zero. Note that this would be true even if we
would apply differencing of one day on T, (t) , i.e. if the process that was mod-
eled was

2 (t) = 7,“) (z) —T,“" 1’ (t) _ (5.9)
where 1,“) (t) is the observation at time t of the day d. Without attempting to
prove this here, we can assume that for given time periods, smaller than a
peak period, the above difference becomes asymptotically stationary. For this
reason and when the diurnal term is included in the model it is suitable to use

a forgetting factor k=1.00.

However, when traffic conditions suddenly change from normal to congested,

174
then the model needs to employ its tracking characteristic. The results

obtained with small values of A such as 0.90 and 0.80 under such conditions
demonstrate this need. Of course, such small values for the forgetting factor
would have an adverse effect on the prediction errors for the periods when the
system is not excited as much due to the increased sensitivity to even small
errors. Furthermore, the best results in the case of congested conditions due to
the traffic accident were obtained with a model of different structure than the
one which gave the best results for the normal operations situation. Since the
prediction model will have to be implemented so it will operate automatically,
a trade off will have to be made, so the model will operate satisfactory while
either normal or congested conditions are in effect.

Therefore, we need to device a mechanism that would employ small values to
the forgetting factor only when appropriate, while for the rest of the time the
model should operate in a close to stationary environment. Until now we have
assumed a constant value for 2.. However, there is nothing to prohibit a time
varying value. Such a time varying function for 1, Mt) should assume small
values when there is a strong excitation to the system, and return to values
close to one when conditions are reinstated to normal. An appropriate trigger
to induce the reduction of the value of Mt) would be the prediction error e(t),
defined in equation (3.12). Such a function could be defined as:

A. if |é(t)|2§,l(t—1) <9.

0

t s _ _ (5.10)
Mt): 10+21,M.t 1) if t>s,A(t-1)<l_

i=1

2. otherwise

where sis the time at which a large prediction error is observed, § is the pre-

17 5
diction error threshold, to is a small initial value for the forgetting factor such

as 0.80. The function defined in (5.10) allows the usage of a general value for
the forgetting factor 0. S 1.00),while when prediction errors occur that exceed
g, Mt) is set to a small initial value 10, and afterwards it approaches 1.00
asymptotically, until it reaches the value of the forgetting factor, 1. With
proper selection of the threshold 5, equation (5.10) will net affect the predic-
tions performed by the RLS algorithm in the case of normal traffic conditions.
Such a value is selected to be double of free flow travel time of the link,
(i = 2 xFFTT,). In the case of the congested traffic conditions the modified
fimction for Mt) was examined on link 19.

The model that was used consisted of the autoregressive term with n=3', the
diurnal term and the convection term with ma=2, since this is the model that
gave the best results for the normal traffic conditions. The initial value 10 was
set at 0.80. Smaller values were examined but they gave worse results. The
error measures obtained with this prediction model and with the forgetting
factor as defined in equation (5.10) are shown in Table 5.27, while in Figure
5.38 and Figure 5.39 the one and the ten step ahead predictions obtained with

the same model are shown.

In the sar'ne table the percent differences of these errors from the no predic-
tions case, and the errors obtained from the same model in the case that the
forgetting factor, is constant and equal to 1.00 and 0.80 are shown. The errors
of the one step predictions of the model with the varying forgetting factor are
still worse than the no predictions, but better than those obtained by the
model with 1:0.80. On the other hand, five and ten step ahead predictions are
of better quality than the no predictions case and the case with k=1.00. The

 

176

 

 

 

 

 

 

 

 

 

 

 

 

 

Que; .... . ._ T $3.2 - .32. .3 .m §o.~ send «$.N. gem. : Owdfl.‘
....m... 9.3.2 $65 ...—6. .32.... «3.3 use... «2.3. ......m- 8.7.x
«$.0— «mNNN .3. .N cams «3.3 .5. .3 .86 ......vm- $06” .8550... oz
38... 3.8... 9.3.... .25.... _ 8.8... $3.... .89.... .38... 5.8... c...
s. ..w w 3. aw w e. .w w 55
...... ...... ......<
2.3862... “.322 93m 3 .5333... 2.2.4 q3m m 3.3062... v8.2 ..Sm . ".032

 

 

 

 

25.5.5.0 989:. 3.8».50 . a ...—5 ...... 3.3% 3:895.— u:..~._a> 2.5. 5.3 ...—52 be ...9—.....— =etu=§£ .uflm 035.

......8... 23.3.32... .... . .528... .. 2...

 

177

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12w I I f I
10“) _ Observed Value
Predicted Value
’3 800 *- -1
'O
i
g 600 1. _
.§ ~
E-
g 400 - a
E
i-
E 200 - —
o ' 1 1 L 1
8. 8.5 9 9.5 10 10.5
Time of Day (Hours)
Figure 5.38: 1 Step Ahead Predictions of Travel Time of Link 19 with Time Varying
Forgetting Factor
1400 . fl , r
Observed Value
1200 - _— _
’ Predicted Value
1;, 1000 - ~
2
g 800 - -
.E
E- 600 - .4
g V {5‘1 “-
E" 400 _ d
.3
200 - _
o ’ 1 4 1 1
8. 8.5 9 9.5 10 10.5
Time of Day (Hours)

Figure 5.39: 10 Step Ahead Predictions of 'n'avel Time of Link 19 with Time Varying
Forgetting Factor

178
mean square error for the five step predictions is 14.9% and 13.8% smaller

than same errors obtained from the no predictions case and the case with
1:1.00. Compared to the model with 1:0.80 five step predictions are almost
the same (slightly better with the mean square error just 3.1% lower) while
ten step predictions are worse by as much as 12.8% for the mean relative
error. It should be noted though, that the most crucial predictions are the one
step ahead, since errors to further predictions will affect vehicles which are
not at the entrance of the congested link, and thus, such vehicles may still

have the opportunity to divert to alternative paths.

179
5.4 Effect of Time Step Length on Predictions

In the following we will examine the effect of the length of the time interval
between sampling the link travel times of the network. To that end, the mod-
els that suggested good performance under normal and/or congested traflic
conditions will be utilized for examining the different time intervals. From the
previous paragraph we have seen that the RLS algorithm works efficiently
when traffic conditions are not disturbed by incidents which produce large and
abrupt anomalies to the system. In the situation where the system is dis-
turbed by a traffic accident, the algorithm gives acceptable results when the
forgetting factor is set to small values, so the large errors which occur at the
start and at the end of the incident will not affect the travel time predictions
of the links for a long time.

Four different sampling intervals will be examined: sampling every 1, 2, 5,
and 10 minutes. For evaluating the effect of the length of the time interval,
the simulation program was utilized in four separate runs where the time step
between updates of the link travel times and the evaluation of the minimum
paths in each run was set respectively to 1, 2, 5 and 10 minutes. Of course,
predictions of s time steps ahead are not comparable among the different runs,
since 3 represents a different length of time in each run. For this reason, and
in addition to the average travel time of the link in every time interval, the
one minute average travel time of each link was recorded so the results of the '
prediction model can be compared with the “real” travel time which will be
approximated by the one minute discrete observations. The performance of
the prediction model under the different time intervals h, will be based on the
error of the estimation of the travel time of the link under consideration k min-

utes into the future where k=1,2,...15, which is defined as:

180

ek(t) = T1(t+ k) - 7),“, r) (5.11)
where T1(t + k) is the one minute sample of the travel time of the link at time
(t + k) and 7,,(5, r) is the r-step ahead prediction of the travel time of the link,
obtained at time (s-h), and with a model utilizing a sampling time step 1:,
where s is given as s = [é] , and r is given as r = [’3‘] , where the brackets
denote the integer part of the fraction. It must be brought to the attention that
the results of each different run cannot be compared with the results obtained
by the run with the one minute time interval, because the routing of the traffic
is different due to the more sparse updates of the traffic conditions on the net-

work, as the time step h increases.

Based on the errors defined by (5.11), and parallel to the measures defined in
paragraph 5.3, the measures of comparison among the models with different
time steps will be:
(1) the mean absolute error given as:
-(k) _ 1
e - W - Z|ek(t)| (5.12)

(2) the mean square error:

2,“) = %- /;[ek(t)]2 (5.13)
and
(3) the maximum error:
ejf’ = max,{|ek(t)|} (5.14)

where N is the number of one minute observations in the period that the above
errors are evaluated. The effect of the different time intervals will be tested
under the two different traffic conditions: the normal traffic operations and
the congested ones due to the traffic accident. All simulation runs were made
with 10% smart vehicles in the network and the simulation program was run

for two simulated days.

181
5.4.1 Effect of Time Interval under Normal Traffic

Conditions

The effect of the length of the time between sampling the travel time of the
link on the predictions performed with the RLS algorithm was tested with the
results from link 15. The model that was used in all cases consists of the
autoregressive term with n=3, the diurnal term and the convection term with
ma depending on the length of the upstream link and mc=0, and with the for-
getting factor set to 1.00. The errors defined by equations (5.12) to (5.14) are
calculated for the time period starting at 06:00 and ending at 19:00 of the sec-
ond simulated day.

The mean absolute errors and the mean square errors calculated for this time
period are shown in Figure 5.40 and Figure 5.41 respectively. Also their values
for k minutes into the future with k=1,2,...,15 are shown in Table 5.28. As can
be seen from Figure 5.40 and Figure 5.41 the algorithm gives consistently bet-
ter results when sampling on the travel times of the link is most frequent. For
the predictions of the travel times for one to four minutes ahead the shorter
the time interval the better they appear to be in terms of the mean square
error. Only in the case where the time step h was five minutes, predictions of
three minutes or further ahead appear to be worse than those obtained in the
case of h=10 minutes. Nevertheless, predictions for one and two minutes

ahead get consistently worse as h increases.

The quality of the predictions obtained with small time steps deteriorates
faster than those obtained with large time steps, at least for the first 8 to 10
minutes, while after this point the quality of the predictions is tempered. This
is due to the increasing effect of the diurnal term on predictions k time steps

 

182

 

.33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

wF.m~ v26 new; Sada «:6 SEN «3.0 gm..— vwn.m_ >26 85; n—
wF.m~ 0:6 mam; imam 3:. ”Zn— amfihu «:6 Gm.— o»—.«— 8:. map; 3
«Emu ”:6 v3; Smdu >26 m2..— amfihm ~26 «a; 20.: 8:. a2..— 2
azumm ofld wood Rhea cfld 0:: ZEN 2 mo 0;; 3:.— 3_.c cg.— S
w :umm «Q 6 a2: Rhea «S .c 2.”.— 815 M: me New; 8:; as .c 99— :
«no.2 Rod SN..— 8m.m~ 8. .o 2k..— SEN S 2. n2..— Nawfi Sod N3; 2
Nmo.c_ mood m3..— Smdm R: .o «Q..— EbHN S _.c so».— 0%.: 8a.: a3.— a
«8.2 256 awn; 302 X: .o 89— 03.5 R: 6 SK.— won.: mood wan; w
3:.— cwod 82 30mm 5. .6 new; 82h X: 6 9K..— NOQS 256 m— m._ 5
$5.— 356 59.— awodm 36d Sc.— meHN 390 Sn; ”8.: god 8v. _ o
$5.3 med 55..— owodm oo— 6 mg; «3.5 256 Fe." emf: wood S: ._ m
35.3 :56 mom; 23.2 macd mmmg ENSN _ Pod cmmg 30: v36 mead .. v
$5.— 806 mom; cwfimm 956 mm»...— ZNSN Sod n36 2%.: n36 ”2.6 m
35.3 Ebd 3m.— ewa.~N weed SN.— mENm need «8.— wmoi ”mad Sod N
$5.3 god N3”.— Vnodm 2.06 Sb.— nFNN mnod 5.2.6 82. aged 09.6 _
...... new am ...e. .3.” 2w set ...m 3w .3... ...m em. Amps
552": scans sewn: 581 can.

 

 

 

 

 

: asm 2:? 228.5 .5. 2 ...5 .... seam 5:22... £3 «.3...

 

Value of Mean Error (Seconds)

Value of Mean Square Error (Seconds)

.0999
82889.3

2.5

183

 

p...
M
I

...
l

p
u.

 

1

1 l

v

 

1

 

 

2

A

6 8 16
Time of Prediction (Minutes)

1'2

14

Figure 5.40: Behavior of Mean Absolute Error for Different Time Steps under

0.2
0.18
0.16
0.14
0.12

0

Normal Traffic Conditions

 

 

)—

"p._

1 l

‘-—"

 

 

 

m

6 8 10
Time of Prediction (Minutes)

12

Figure 5.41: Behavior of Mean Square Error for Different Time Steps under Normal

Traffic Conditions

 

184
ahead as k increases, as was explained previously. On the other hand, the

mean error of the predictions obtained in the case of h=10 minutes is almost
constant for the first ten minutes, and increases after this point. This consis-
tency in the quality of the predictions when large time steps are used is due to
the fact that such predictions are obtained with one or two time steps ahead
predictions, while for the case of h=1 this would require ten successive predic-

tions, with the obvious results of the propagation of the errors.

The errors produced in the case of h=10 and h=5 are remarkably small, espe—
cially for predictions around the ten minutes ahead (one or two step ahead
predictions). In fact, predictions for eight to ten minutes ahead obtained with
h=5 appear to be slightly better than those obtained in the case of h=1, while
they are clearly better than the case of h=2. In addition, predictions beyond
ten minutes appear to have some reduction in their error, instead of an
increase. Figure 5.42 illustrates the quality of the two step ahead predictions
obtained in the case of h=10, and as it can be seen, predicted values are close

to the one minute observations.

This behavior is understood when we examine the parameters of , the model
when such large time steps are utilized. The total gains of each term in the
case of h=10 are shown in Figure 5.43. The importance of the autoregressive
term is minimized, while the importance of the other two components of the '
prediction model is magnified. This is especially true for the diurnal term
which throughout the simulated day retains a value close to 0.5, and at the
end of the simulated day assumes a value of 0.4981, thus affecting greatly the
one and even more the two step ahead (10 and 20 minutes ahead) predictions.
This occurs due to the limited sampling of the travel time of the link itself

 

205

200

195

190

185

180

Link Travel Time (Seconds)

185

 

T

 

 
 

L l I

s 83 9
Time of Day (Hours)

~11—

I’ \\
I \
v
1‘
l \
t~
‘1‘»

Observations every 10 min.‘

Observations every 1 min. -
2 Step Predictions

 

 

—l

v‘.

9.3

 

Figure 5.42: 2 Step Predictions of Travel Times of Link 15 with Time Step h=10

0.8
0.6

0.4
0.2

-0.2

Value of the Term

41.4
-0.6
-0.8

minutes

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- f M: Convection Term -
' Diurnal Term ‘
x A “.7;

F 1
_ Autoregressive Term 4
_WW V’v/M
)— —1
o 5 lb 13 26 24
Time of Day (Hours)

Figure 5.43: Value of Components of Prediction Model for Link 15 with Time Step

h=10 minutes

 

186
which changes values more rapidly than in the case of h=1, and thus the RLS

algorithm cannot eficiently track the states of the autoregressive component.
Instead, it identifies the relationship of the link travel time with the diurnal
term, and therefore, it attributes large values to parameter d. The same gen-
eral trends of the mean error are observed for the mean square error as well,

indicating that many of the prediction errors are smaller than one second.

Overall, from the above results it can be concluded that short term predictions
in the time range of one to five minutes ahead are of very good quality when
they are obtained with smaller time steps. For predictions further into the
future, all time steps that were examined appear to give comparable results,
although the smaller time step tested was consistently better. However, longer
time steps are translated to lower operational cost, since information will have
to be predicted and broadcasted fewer times than in the case of small time
steps. When the results of the cases h=10 and h=5 are compared with those for
h=2 it is more obvious that for longer term predictions, long time steps give
better results. First because they depend more heavily on the average travel
time of the link and second because they are obtained with fewer step ahead

predictions.

5.42 Efl'ect of the Time Interval under Congested
Traffic Conditions

For the situation of the congested traffic conditions the performance of the

RLS algorithm under different time steps was evaluated based on the results

of link 19, on which the accident occurred. The model that was used for the

prediction of the travel times of this link consisted of the autoregressive term

 

187
with order n=1 and the diurnal term and the forgetting factor that was set at

1:090. The errors were computed for the period of time starting at 8:00 and
ending at 12:00.

The results are summarized in Figure 5.44 and Figure 5.45 where the sensi-
tivity of the prediction algorithm to the length of the time step in terms of the
mean absolute error and the mean square error is shown. As was expected,
the shorter the time step, the smaller the resulting error, since the estimation
of the travel time of the link at the beginning and at the end of the incident
which contain large errors, were in effect for longer times. This was true for
predictions of the travel time of the link for all times that were tested. In con-
trast to the case of normal operations where errors of the predicted values
were tempered after the first few minutes, here it was clear that predictions
further into the future contain more error, with almost a linear relationship.
As is revealed from Figure 5.44, the mean error of the predictions are consis-

tently worse as the time step increases by almost a constant amount.

When a large time step is used the adaptation of the model to the sudden
increase of the travel time is hampered even more due to the limited number
of observations, and thus the resulting errors are worse. On the contrary, in
the case of small time steps, changes of travel time are perceived by the algo-
rithm as being more gradual and thus adaptation is more successful, and pre-
dictions even further into the future are of better quality than those obtained

in the case of longer time steps.

 

 

188

 

200

180

Value of Mean Error (Seco s)
3 8 8 8 8 3 8

N
O

 

 

 

l l

2 4 6 8 16 12 14
Time of Prediction (Minutes)

 

0 l l l 1

Figure 5.44: Behavior of Mean Absolute Error for Different Time Steps under
Congested Traffic Conditions

 

   

 

 

 

25 r fi . . . I
l-
8
1.1.1
i
U)
2
a—
O
8
'3
>

S 1 1 1 1 1 1 1

2 4 6 8 10 12 14

Time of Prediction (Minutes)

Figure 5.45: Behavior of Mean Square Error for Different Time Steps under
Congested Traffic Conditions

 

Chapter 6

 

Effectiveness of Route Guidance
System

 

6.1 Introduction .

In this section of the study we assess the impact that the route guidance sys-
tem utilizing the prediction algdrithm has on the throughput of the network.
Of course, poor predictions may have a negative impact on the performance of
smart vehicles, with possibly negative effects on the rest of the traflic as well.
On the other hand, good predictions should improve the travel times of smart
vehicles more than if smart vehicles had information only on current traffic
conditions and not on predicted ones. The performance of the system was
examined at different levels of market penetration of smart vehicles. In all
instances of market penetration and route guidance schemes, the same tramc
demand patterns were used. Also in all runs an accident was simulated on .

link 19 starting at time 08:34:10.2 and lasted till time 08:50:21.5.

189

 

190
6.2 Effectiveness of Route Guidance System at

Different Levels of Market Penetration
The hourly average travel time for smart and non smart vehicles for the route
guidance schemes utilizing the prediction model and at five different levels of
market penetration are illustrated in Figure 6.1 through Figure 6.5. As can be
seen from these figures, for time periods other than the one where operations
are affected by the traffic accident, travel times of smart vehicles and non
smart vehicles are almost identical. They differ only by a few seconds, and
smart vehicles do not always have shorter average travel time than non smart

 

vehicles.

The above observation is explained if we consider the definition of the non

1050 . . . .
moo . NmSmmVWI“ _
3 a. Smart Vehicles
950 . '1 -
900 - 3, -
850 _ ,5 -
800 — 5' _
60° 5 . 16 1'5 2b

 

"‘0

Average Travel Time (Seconds)

 

 

 

 

Time of Day (Hours)
Figure 6.1: Hourly Average Travel Time - Market Penetration 10%

 

191

 

 

 

 

 

1050 I r T V
1000 _ ”Meeker?
Smart Vehicles
’3 950 - P <
.8
§ 9(X) " 1
Z), : '.
” 850 - .3 ‘-. -
é : :
E‘ 0 n
"‘3
E
E-
o
on
i!
0
>
<
6G) ' ‘

lb 15 20
Time of Day (Hours)

Figure 6.2: Hourly Average Travel Time - Market Penetration 30%

L)“-

 

 

 

 

 

1050 Y I U ‘
1000 _ ”msmv‘mfl“ A
Smart Vehicles

9 950 - ' _
.8 9
§ 9(1) ' 5". ‘
9 : '.
0 :' '1 -
g 850 r-
E‘ 0 u
T)
>
E.
[—
%
E
O
>
<

600 5 lb 13 2?)

Time of Day (Hours)

Figure 6.3: Hourly Average Travel Time - Market Penetration 50%

192

 

1050

1000 _ "09.3..mehisls
Smart Vehicles

950 - —— _

900 - u

Average Travel Time (Seconds)

   

 

 

 

lb 13 20
Time of Day (Hours)
Figure 6.4: Hourly Average Travel Time - Market Penetration 70%

Ml-

 

1050 . , 1 ,

1000 - ”WSmdeucl“ r
Smart Vehicles

950 - — ,

 

Average Travel Time (Seconds)

 

 

 

 

LIN-
p—o
O
u-o
M
N
C

Time of Day (Hours)
Figure 6.5: Hourly Average Travel Time - Market Penetration 90%

193
smart vehicles. Actually, in the case of normal operations, non smart vehicles

do not differ from smart vehicles. This is true for two reasons: first, the infor-
mation on which they base their route choice, the smoothed average travel
time of the link for the current five minute interval, is a relatively good
approximation of the actual travel time. Second, the actual travel time of any
given path (under normal traffic conditions) is not that much worse than non
smart drivers perceive it to be, so no alternative route would be suggested to
smart vehicles. This is further reinforced by the fact that vehicles do not
change routes for very small gains in their travel time, but only if the gains of
the new path exceed a minimum threshold value. Therefore, when there is no
congestion due to an unexpected event, smart and non smart vehicles chose
the same route toward their destination, even if the perception of the travel
time is more accurate for smart vehicles. In this case any differences in the
average travel time between the two vehicle categories is random and not due
to any intelligent routing strategy. Of course this behavior of smart and non
smart vehicles is very much dependent on the layout of the network, and the
threshold (in terms of time) applied to vehicles shifin'ng from one route to an
other. For example, if drivers could alter their route with very small penalty in
the travel time, which would results from shifting from the original path, it is
believed that the savings of the smart vehicles would be evident.

On the other hand in the case of the traffic accident smart vehicles know of the
occurrence of the incident when the incident occurs. In addition they have
information regarding the expected time of duration of the incident, and as
soon as the incident ends they receive this information as well. Due to this
information, smart vehicles are guided to alternative paths and thus are able

to improve their travel times, when such alternative routes exist. Therefore,

194
the actual time savings (in the case of the given network) for smart vehicle

accrue from their route choices during the period that operations on the net-
work are affected by the accident on link 19. However, even in the case of the
incident, non smart vehicles employ a quite intelligent routing strategy: they
enter the link till the link is filled, and after this point they reevaluate their
route toward their destination based on the fact that link 19 is congested.

A prominent difference though is observed among the average travel times of
both smart and non smart vehicles for the different market penetration levels
during the incident. Figure 6.6 illustrates the profiles of the average travel
time of smart and non smart vehicles during the incident for the different pen-
etration levels. For low penetration levels the average travel time of the smart
vehicles is much lower than the one for non smart vehicles (from 26.3% to
16.1% lower average travel times for smart vehicles at levels of market pene-
tration of 10% and 30% respectively - Table 6.1). However this difi‘erence is
diminished for higher percentages of market penetration and for a penetra-

tion level as high as 90% it is even inverted in favor of the non smart vehicles.

The total throughput of the network is also shown in Figure 6.6. As can be
seen in this figure, for low levels of market penetration the overall perfor-
mance of the network improves until the 59% level, while after this point, it
starts a slow decline. Thus, the route guidance system appears to reduce the -
effect of the incident on the overall performance of the network at all levels of

market penetration.

The accident on link 19 is triggered by a vehicle which has traveled almost
75% of the link before it createsthe incident. Therefore, a large portion of the

Average Travel Time (Seconds)

1050

1000

950

850

800

750

195

 

    
    

—

 

Non Smart Vehicles

Weighted Average

 

 

 

10 2b

32)

4b 56

ab

Market Penetration Level (96)
Figure 6.6: Travel Time Profile for Different Levels of Market Penetration '

76 ab

Table 6.1: Travel Times and Percent Differences of Smart and Non Smart
Vehicles for Different Market Penetration Levels.

 

 

 

 

 

 

 

 

 

 

Market Smart Non Smart Difference Weighted
Penetration (seconds) (seconds) % Average
10% 767.09 1041.26 26.3 1013.9
30% 791.23 943.01 16.1 897.5
50% 797.28 913. 13 12.7 855.2
70% 851.22 868.38 1.9 856.4
90% 881.76 867.52 -1.6 880.4

 

 

 

 

196
high travel time of both smart and non smart traffic, is due to the vehicles

from each category that are traversing link 19 before the start of the incident
and have entered the link after the entrance of the vehicle that will cause the
incident (such vehicles that join the queue in link 19 will have to wait until
the end of the incident and thus their travel time is increased by approxi-
mately 950 seconds, the duration of the incident). Since smart vehicles will
stop entering link 19 right after the start of the incident, while non smart
vehicles will enter until the link is completely congested, their average travel
time never reaches the high levels of the travel time of the non smart vehicles
in the cases of market penetration of 10% and 30%.

However, at high levels of market penetration, and due to the long duration of
the incident, smart traffic which is aware of the congestion, in order to bypass
the congested link, starts diverting to alternative routes which soon become
congested because of the large number of vehicles that divert to these paths.
Thus, equipped vehicles which still have the opportunity start diverting to
new alternative paths from further upstream. On the other hand, non smart
vehicles improve their average travel time as the market penetration
increases, since at higher levels of market penetration the formed queues are
shorter. This results in faster dissipation of the formed queues on the links
that become congested, with the subsequent result of shorter waiting times in

such queues.

In the case where there was no incident in the network the average travel
time of smart vehicles at the same time period (from 9:00 to 10:00) was almost
the same for all levels of market penetration ranging form 665.6 to 667.4 sec-

onds. The same was true for non smart vehicles with average travel times for

197
the same period ranging from 665.8 to 667.5 seconds. Smart vehicles have

higher travel times as compared with the travel times at the no incident case
for two reasons. First traffic that is diverted to alternative routes is forced to
follow longer paths than what it would follow if the incident had not occurred.
Second, some smart vehicles are trapped in the queues created due to the inci-

dent as explained above.

Due to the time lag between the inspection of the congestion, and the time this
information is broadcast to the traffic, equipped vehicles will start diverting to
alternative routes only after the system updates the information regarding
the current travel conditions on the links. Until then, even smart vehicles will
follow the directions of the system from the last time step. However, such
directions may lead them to routes which already are becoming congested dur-
ing the last time step. Of course, the shorter the time between updates of
information regarding link trafic conditions during congestion periods, the

less severe the effects of the congestion.

This is demonstrated in Figure 6.7 where the average travel time for smart
and non smart vehicles are plotted in the case that the link travel time infor-
mation is updated and broadcast every 30 seconds. From these results it
becomes obvious that higher frequency of information update improves the
performance of smart vehicles significantly for all levels of market penetra-
tion. Of course this is also associated with the fact that predictions of link
travel times are also of better quality for smaller time steps, as was discussed
in paragraph 5.4.2. The percent gains of the average travel times for the
period after the accident of each vehicle category, as well as of the throughput
of the network are listed in Table 6.2. The effectiveness of the shorter time

198

 

1050 t t
' Update every 60 sec.

 

Update every 30 sec. q

i

 

0

Ln

O
r

.. Non Smart Vehicles

0.

E§

...
‘e.
...
.
.
.
.
.
O.
.
.
.
.
.
.
.
.
.
.,
.
.
O.
u
.
.
-.
.
.
.,
._

......
........
....

850 - - .

Average Travel Time (Seconds)

r
A
1

Smart Vehicles

,0
.-
a"
e-'
eI'
n"
.0'
nnnnnn
n
,-
ov‘
oI’
‘0‘
o"
u"

 

 

 

75010 zb 3b 4b 52) 60 7b 80 90
Market Penetration Level (96)
Figure 6.7: Comparative Ravel Time Profiles for Information Updates Every 60 and
Every 30 Seconds

Table 6.2: Travel Times of Smart and Non Smart Vehicles for Different Market
Penetration Levels when Information is Updated Every 30 Seconds

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Market Smart Non Smart Weighted % Reduction 0f Delay 1
Penetration (seconds) (seconds) Average Smart Non Smart Overall
10% 762.54 1038.55 1010.9 4.6 0.7 0.8
30% 783.04 917.22 877.0 6.6 9.3 8.9
50% 792.12 896.68 844.4 4.0 6.7 5.7
70% 803.34 847.36 816.5 26.0 10.5 21.0
90% 825.99 820.83 825.5 26.0 23.3 25.7

 

l. Delays are calculated as the difference of the average travel times between the case of prediction
update every 30 seconds and every 60 seconds reduced by 667 seconds which is approximately the
travel time of both smart and non smart traffic in the case of no incident for all market penetration
levels.

 

 

199
interval increases with the level of market penetration. This indicates that the

importance of having the correct information as soon as possible, is more cru-
cial when a large percentage of the traffic has access to this information, so
congestion to the alternative paths which are suggested by the system (or cal-
culated by the on board computers based on the information provided by the
system) will be avoided. At penetration levels of 90% smart vehicles still have
longer average travel time than the non smart vehicles. However, the differ-
ence between their travel time is reduced almost to one third the value in the
case of 60 second updates, while at 70% penetration, this difference is much

larger, from 17.2 to 44.0 seconds.

When the penetration level is only 10% frequent update of information about
link conditions does not appear to have a strong impact on the average travel
time of the non smart vehicles and the overall performance of the network,
while for smart vehicles there are moderate improvements. On the other
hand, when broadcast information is affecting a large percentage of traffic,
this tramc moves more eficiently with more frequent information updates. In
addition the overall performance of the network is greatly improved (Table
6.2).

 

Chapter 7

 

Summary and Conclusions

 

From the literature review it become apparent that models designed to esti-
mate future travel conditions based on current ones all have limitations. How-
ever, models of this type are needed in the development and application of
IVHS technologies, and more specifically in ADIS. A significant level of
research is concentrated on extending equilibrium models for this purpose,
but such models are only applicable when the market penetration is rather

high.

In this study we examined the use of a recursive identification model for pre-
dicting travel time on the links of a tramc network in real time, when the
input signal to the model is comprised of current and past information regard-
ing traffic condition on the network. The main reason for using a recursive
algorithm is to provide the adaptive characteristics required, to respond to
evolving traffic conditions. The proposed prediction algorithm is not new, but
is an existing methodology applied to the specific problem of predicting travel
times on the links of a network. Similar algorithms have been successfully

used in the past, mostly for predicting tramc volumes. However, the use of

200

201
these models in route guidance systems, where the availability of real time

information to drivers may affect the traffic patterns on the network, has not

been tested until now.

Due to the lack of real world data from a system where drivers (or a portion of
drivers) have access to real time information regarding traffic conditions, it
was decided that the prediction model would be tested on simulated data. Fur-
thermore, due to lack of access to the source code of simulation programs that
could be modified for simulating such a network-driver system it was neces-
sary to construct such a traffic simulation program. The simulation program
is microscopic at the vehicle level, and was developed so any shape of network
could be simulated. A certain percentage of the traffic has access to real and
predicted information, and routing of traffic is performed under the properties

of dynamic networks.

The prediction algorithm was tested under normal traffic conditions where
traffic operations were not afl‘ected by any unexpected event such as a traffic
accident, and under congested traffic conditions where the operating condi-
tions were greatly influenced by the occurrence of a traffic accident on a link of
the network. The input data to the link travel time prediction model consid-
ered in this study included the time series of the travel times of the link that
is under consideration, as well as information from those links ending at the
entrance node of this link and the ones emanating from the exit node of the
link. In addition the time dependent average travel time on the link observed
during previous days, was included as well. The measures of efi'ectiveness
used were based on the errors produced by each model. The magnitude of the

error was compared with the errors produced when the only information avail-

202
able to equipped drivers was the current travel time on the link.

When the model includes only the autoregressive term, the predictions were
only marginally better than the no predictions case. When a large order model
was used, the performance of the algorithm improved, but it is recognized that
such models overparametrize the system, with the result that many of the
parameters do not afi'ect the predictions. When the model was modified to uti-
lize different weights for the prediction errors, by means of a forgetting factor
k, to discount errors in the distant past, the model performance was expected
to improve. However, when the forgetting factor was set to values smaller
than 1.00, so the tracking capability of the model would be used, the predic-

tion errors increased.

When a diurnal term was included in the model, predictions were better than
those obtained with the autoregressive term alone. This improvement
increases for predictions further in the future, mainly because such predic-
tions are smoothed by the increasing effect of the diurnal component. For
example one, five and ten step ahead predictions have approximately 10%
20% and 35% less error than the no prediction case. By comparison, when only
the autoregressive term was used, the one step predictions were approxi-
mately 7% better and five and ten step ahead predictions were only margin-
ally better.

The inclusion of information from upstream links in the model enhanced the
performance of the model even more. The expected errors of these prediction
models were reduced up 31% and 37% for the one and five step ahead predic-
tions respectively, while ten step ahead predictions gained only an additional

 

203
8%. In this model, the effect of a forgetting factor set at 0.99 was positive, and

one step ahead predictions were better when 1:1.00, and five step ahead pre-
dictions where almost equal. These results were obtained when information
from links that were rarely used was excluded. This was necessary since such
information does not affect the predictions, and very small changes in the

travel time of such links resulted in large prediction errors.

Using the same model, it was detrmined that the number of past observations
in the convection term represents the time lag required for the tramc wave to
travel downstream. For example, in the case examined two parameters (b8.1
and bag) were included when using a 60 seconds time step since traffic waves
needed approximately 120 seconds to reach from the upstream link to the link
under consideration. The parameter b“ was approaching zero, and exclusion

of it fiom the model may have improved the results.

While these results were obtained for the normal traffic conditions, when a
traffic accident occurs , the model performed worse than the case of no predic-
tion when the forgetting factor A was set to one. However, when the parame-
ters of the model were not assumed to be fixed, and the forgetting factor was
set to relatively small values such as 0.80, the model gave predictions that
were better for five and ten steps ahead. The one step ahead predictions still
contained more error than the no prediction case. When information fi'om
downstream links was included in the model, predictions under normal trafic
conditions deteriorated, while for the link that is upstream from the one
where the accident occurred, predictions were improved when the congestion
term with a large order was included. It was expected that such input would

improve the predictions for this link since it contains information about the

 

204
shock wave which is traveling backwards. However, due to the alternative

paths available, this relationship was not manifested as early as the shock
wave reached the exit of the link with the accident, and thus the large order

congestion term had to be used.

Since information regarding the time and location of a traffic accident is not
predictable, since traffic accidents are random events with very small proba-
bility, it is not possible to operate the prediction model with the structure and
the forgetting factor that would give good predictions only under congested
conditions. Therefore, to obtain good results it was neccesary to develop a time
varying weighting function to replace the forgetting factor. While further
development is required for such a function, a function was designed for this
study which would assume small values when large prediction errors occur,
while the rest of the time A would remain close to one. The results obtained
were not as good as those obtained during the congestion period by the models
with a small forgetting factor, but they were better than those obtained with
the forgetting factor set at 1.00 or 0.99.

With the model containing the autoregressive the diurnal and the convection
terms, the sensitivity of the prediction algorithm to the size of the interval
between recursions of the algorithm was examined. It appears that the
smaller the interval, the better the predictions of the travel time on the link in ‘
the immediate future. For predictions further in the future it was observed
that the algorithm is relatively insensitive to the length of the interval, and
predictions obtained with large intervals were surprisingly good. This result
means that in the selection of the time step, the length of the links in the net-
work should be taken into account. If very short term (i.e. 1 minute) predic-

 

205
tions are not needed, a larger time step may be used, which would result in

less operational cost. However, in the case of a traffic accident, it was clear

that the larger the time step the greater the error in the predictions.

The effectiveness of the route guidance system with the prediction model was
examined at different levels of market penetration. From the result of this
part of the study, it is obvious that benefits of such systems will accrue mostly
during unexpected congestion (such as congestion induced by traffic incidents)
when non equipped vehicles are not aware of the downstream congestion.
Benefits during recurrent congestion are greatly dependent on the network
layout, as well as the behavior of non equipped vehicles. Nevertheless during
accident induced congestion, equipped vehicles do significantly better than
non equipped vehicles, at least at market penetration levels lower than 50%.
At higher levels of market penetration equipped traffic appears to congest the
alternative routes, and at levels as high as 90% their travel time is even
higher than the travel time of non equipped vehicles. This is tempered when
the time step is decreased from 60 to 30 seconds.

Along with the performance of the equipped traffic the performance of the
entire system also appears to improve as market penetration increaSes until it
reaches 50% for the 60 second time step, and until it reaches 70% for the 30
second time step. At lower levels of market penetration the performance of the
model appears to be insensitive to the length of the time step while for higher
levels the benefits are significant. This result indicates that during congested
periods accurate information regarding traffic conditions is essential when

such information affects the routing decisions of a large portion of the traflic.

 

206
Although the effectiveness results are dependent on the network used, the

principles underlying the prediction model will be applicable to more general
networks as well. While further research is necessary to improve the predic-
tion model, particularly during incident induced congestion, the proposed
model appears to perform very well especially during normal trafic condi-
tions. Improvement of the performance of the model may be achieved by filter-
ing the input data and/or the predictions, so gross errors that may occur
during the first time steps of an incident, which are also the most critical, are

minimized.

 

BIBLIOGRAPHY

 

 

Bibliography

 

Al-Deek Haitham and Kanafani Adib, 1991. Incident Management with
Advanced Traveller Information System. Paper presented at the VNIS’91
Conference, Dearbom, Michigan.

Ahmed Mohamed and Cook Allen, 1982. Analysis of Freeway Trafiic Time
Series Data by Using Box-Jenkins Techniques. Transportation Research
Record 722, pp 1-9, TRB, National Research Council Washington, DC.

Ahmed Mohamed and Cook Allen, 1980. lime Series Models for Freeway
Incident Detection. 'h’ansportation Engineering Journal of ASCE, Vol 106,
No TE6, American Society of Civil Engineers, New York, New York.

Astrom Karl Johan and Wittenmark ijm, 1989. Adaptive Control. Addi-
son Wesley Publishing Company.

Boyce David, 1984. Route Guidance Systems for Improving Urban Travel
and Location Choices. Transportation Research A, Vol 22A, No 4, pp 275-
288.

Boyce David, 1989. Route Guidance Systems for Managing Urban Transpor—
tation Networks: Review and Prospects. Paper presented at 10th Italian
Regional Conference, Rome, Italy.

Brockwell Peter and Davis Richard, 1987. Time Series: Theory and Meth-
ods. Springer Verlag Book Company, New York.

Carey M., 1987. Optimal Time Varying F lows on C ongested Networks. Oper-
ations Research, Vol 35, No 1, pp 58-69, Operation Research Society of
America.

Chen Kan and Underwood Steven, 1991. Research on Anticipaton Route
Guidance. Paper presented at the VNIS’91 Conference, Dearbom, Michi-

207

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

208
gan.

Chen Peter She-Te and Mahmassani Hani,1991. Reliability of Real-Time
Information Systems for Route Choice Decisions in a Congested Trafi‘ic Net-
work: Some Simulation Experiments. Paper presented at the VNIS’91 Con-
ference, Dearbom, Michigan.

Cook, K. L. and Hasley E., 1966. The Shortest Route Through a Network
with Time Dependent Intermodal Transit Times. Journal of Mathematical
Analysis and Applications, Vol 14, pp 493-498.

Davis Gary and Nihan Nancy, 1984. Using Time Series Designs to Estimate
Changes in Freeway Level of Service, Despite Missing Data. Transportation
Research A, Vol 18A, No 5/6, pp 431-438.

Ervin Robert and Chen Kan, 1990. Providing Radical Functionality to
Serve Highway Transportation: A 20 Year Vision for IVHS. University of
Michigan Transportation Research Institute, Ann Arbor, Michigan.

Euler Gary, 1990. Intelligent Vehicle/Highway Systems: Definitions and
Applications. ITE Journal, Vol 60, No 11, pp 2331, Institute of Transpor-
tation Engineers, Washington, DC.

French Robert, 1990. Intelligent Vehicle/Highway Systems in Action. ITE
Journal, Vol 60, No 11, pp 23-31, Institute of 'h'ansportation Engineers,
Washington, DC.

Friesz Terry, Luque F., Tobin Roger and Wie Byung-Wook, 1989. Dynamic
Network Trafiic Assignment Considered as a Continuous Time Optimal Con-
trol Problem. Operations Research, Vol 37, No 6, pp 893-901, (Operation
Research Society of America

Gazis Denos and Knapp Charles, 1971. On Line Estimation of Traffic Den-
sities from Time Series of Traflic and Speed Data. Transportation Science, .
Vol. 5, No 3.

Grenzeback Lance and Woodle Clyde, 1992. The True Costs of Highway
Congestion. ITE Journal, Vol 62, No 3, pp 16-20, Institute of Transporta-
tion Engineers, Washington, D. C.

Guiliano Genevieve, 1989. Incident Characteristics, Frequency and Dura-
tion on a High Volume Urban Freeway. Transportation Research A, Vol
23A, N0 5, pp 387'396.

 

 

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

209
Hamerslag Rudi and van Berkum Eric, 1991. Effectiveness of Information
Systems in Networks With and Without Congestion. Paper presented at the
70th TRB meeting, Washington, DC.

Halati Abolhassan and Boyce David, 1991. Effectiveness of In- Vehicle Nav-
igation Systems in Alleviating Non-Recurring Congestion. Paper presented
at the VNIS’91 Conference, Dearbom, Michigan.

Hall Randolph, 1986. The fastest Path through a Network with Random Time
Dependent Travel times. Transportation Science Vol 20, No 3.

Haykin Simon, 1984. Introduction to Adaptive Filters. Macmillan Publish-
ing Company, New York.

Kaufman David, Lee James and Smith Robert, 1990. Anticipatory Trafi‘ic
Modeling and Route Guidance in Intelligent Vehicle Highway Systems. IVHS
'Ibchnical Report 90-2, University of Michigan Transportation Research
Institute, Ann Arbor, Michigan.

Kaufman David and Smith Robert, 1990. Fastest Paths in Dynamic Net-
works with Application to Intelligent Vehicle Highway Systems. IVHS 'lbchni-
cal Report 90-4, University of Michigan Transportation Research
Institute, Ann Arbor, Michigan.

Kaufman David, Smith Robert and Wunderlich Karl, 1991. An Alternative
Routing/Assignment Method for Anticipatory Real Time Route Guidance.
Paper presented at the VNIS’91 Conference, Dearbom, Michigan.

Koutsopoulos Haris and Lotan Tsippy, 1990. Motorist Information Systems
and Recurrent Trafi‘ic Congestion: A Sensitivity Analysis of Expected Benefits.
Paper presented at the 69th TRB meeting, Washington, DC.

Koutsopoulos Haris and Yablonski Ann, 1991. Design Parameters of
Advanced Driver Information Systems: The case of Incident Congestion and
Small Market Penetration. Paper presented at the VNIS’91 Conference,
Dearborn, Michigan.

Kyte Michael, Marek Joseph, Frith Douglas 1989. Using Multivariate Time
Series Analysis to Model Freeway Trafi‘ic Flow. Paper presented at the 68th
TRB meeting, Washington, DC.

Lafortune Stephane, 1990. Anticipatory Trafi‘ic Modeling and Route Guid-
ance: A General Mathematical Formulation. IVHS Technical Report 90-6,

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

41.

210
University of Michigan Transportation Research Institute, Ann Arbor,
Michigan.

Lafortune Stephane, Sengupta Raja, Kaufman David and Smith Robert
1991. A Dynamic System Model for Trafiic Assignment in Networks. Paper
presented at the VNIS’91 Conference, Dearborn, Michigan.

Ljung Lennart and Sederstrom Torsten 1983. Theory and Practice of
Recursive Identification. MIT Press, Cambridge, Massachusetts.

Lu Jian, 1990. Prediction of Trafiic Flow by an Adaptive Prediction System.
Transportation Research Record 1287, pp 54-61, TRB, National Research
Council, Washington, DC.

Mahmassani Hani and Chen Peter Shen-Te, 1991. Comparative Assess-
ment of Origin—Based and E n-Route Real-Time Information Under Alternative
User Behavioral Rules. Paper presented at the 70th TRB meeting, Wash-
ington, D.C.

Mahmassani Hani and R. J ayakrishan, 1990. System Performance and
User Response under Real Time Information in a Congested Traflic Corridor.
Paper presented at the 69th TRB meeting, Washington, DC.

Mauro Vito, 1991. Evaluation of Dynamic Network Control: Simulation
Results Using NEMIS Urban M icrosimulator: Paper presented at the 70th
TRB meeting, Washington, DC.

Merchant Deepak and Nemhauser George, 1978a. A Model and an Algo-
rithm for the Dynamic Trafiic Assignment Problems. Transportation Science,
Vol 12, No 3. pp 183-199.

Merchant Deepak and Nemhauser George, 1978b. Optimality Conditions
for a Dynamic Trafi'ic Assignment Model. Transportation Science, Vol 12,
No 3. PP 200—207.

Mulgrew Bernard and Cowan Colin, 1988. Adaptive Filters and Equalizers.
Kluwer Academic Publishers, Boston, Massachusetts.

Newell Gordon, 1980. T rafiic Flow on Transportation Networks. MIT Press,
Cambridge, Massachusetts.

Nihan Nancy and Davis Gary, 1989. Application of Prediction-Error Mini-
mization and Maximum Likelihood to Estimate Intersection O-D matrices

42.

43.

44.

45.

46.

47.

48.

49.

50.

51.

52.

53.

211
from Traffic Counts. Transportation Science, Vol 23, No 2, pp 77-90.

Nihan Nancy and Davis Gary, 1987. Recursive Estimation of Origin Desti-
nation Matrices from Input/Output Counts. Transportation Research B, Vol
21B, No 2, pp 149-163.

Okutani Iwao and Stephanedes Yorgos, 1984. Dynamic Prediction of Traf-
fic Volume through Kalman Filtering Theory. Transportation Research B,
Vol 183, No 1, pp 1-11.

Papageorgiou Markos, 1983. Applications of Automatic Control Concepts to
Trafiic Flow Modelling and Control. Springer-Verlang Book Company, Lec-
ture Notes in Control and Information Sciences, No 50, Berlin, Germany.

Papageorgiou Markos, 1990. Dynamic Modeling, Assignment, and Route
Guidance in Trafiic Networks. Transportation Research B, Vol 24B, No 6.

Papageorgiou Markos and Messmer Albert, 1991. Dynamic Network traffic
Assignment and Route Guidance via Feedback Regulation. Paper presented
at the 70th TRB meeting, Washington, DC.

Papoulis Athanasios, 1984. Probability, Random Variables and Stochastic
Processes. McGraw Hill Book Company, New York.

Paull Marvin, 1988. Algorithm Design: A Recursion Transformation F rame-
work. VVrley, New York.

Pritsker Alan, 1986. Introduction to Simulation and SLAM II. Halsted
Press, Wiley, New York.

Ran Bin, Boyce David and LeBlanc Larry, 1992. Some Basic Constraints
for a Dynamic Trafi‘ic Assignment Model. Paper presented at the 71st TRB
meeting, Washington, DC.

Ross Sheldon, 1985. Introduction to Probability Models. Academic Press,
New York.

Romeijin Edwin, Smith Robert, 1990. Notes on Parallel Algorithms and
Aggregation for Solving Shortest Path Problems. Class notes, Ann Arbor,
Michigan.

Rosen Dan, Mammano Frank and Favout Rinaldo, 1970. An Electronic
Route Guidance System for Highway Vehicles. IEEE Transactions on Vehic-

 

 

54.

55.

56.

57.

58.

59.

60.

61.

62.

63.

64.

2 12
ular Technology, Vol VT-19, N o 1.

Sen Ashish, 1991. Short Term Forecasting of Link Travel Times: A Prelimi-
nary Proposal. Class notes, Ann Arbor, Michigan.

Shefii Yossef, 1985. Urban transportation Networks: Equilibrium Analysis
with Mathematical Programming Methods. Prenctice Hall, New York.

Stephanedes Yorgos, Kwon Eil, Michalopoulos Panes, 1990. On Line
Diversion Prediction for Dynamic Control and Vehicle Guidance in Freeway
Corridors. Transportation Research Record 1287, pp 11-19, TRB,
National Research Council, Washington, DC.

TRB, 1975. Trafiic Flow Theory. Special Report 165, Transportation
Research Board, National Research Council, Washington, DC.

TRB, 1985. Highway Capacity Manual. Special Report 209, Transportation
Research Board, National Research Council, Washington, DC.

Underwood Steven, 1990. Review of Traffic Simulations for Intelligent Vehi-
cle-Highway System Evaluation. IVHS 'lbchnical Report 90-10, University
of Michigan Transportation Research Institute, Ann Arbor, Michigan.

US. General Accounting Ofice, 1991. Smart Highways: An Assessment of
Their Potential to Improve Travel.

Van Aerde Michel and Yagar Sam, 1988a. Dynamic Integrated Freeway /
Traffic Signal Networks: Problems and Proposed Solutions. Transportation
Research A, Vol 22A, N o 6, pp 435-443.

Van Aerde Michel and Yagar Sam, 1988b. Dynamic Integrated Freeway /
Trafiic Signal Networks: A Routing Based Modelling Approach. Transporta-
tion Research A, Vol 22A, N o 6, pp 445-453.

Wie Byung-Wook, 1991. Dynamic Analysis of User Optimized Network
Flows with Elastic Travel Demand. Paper presented at the 70th TRB meet-
ing, Washington, DC.

Wie Byung-Wook, Friesz Terry and Tobin Roger, 1990. Dynamic User
Optimal Trafiic Assignment on C ongested M ulti Destination Networks. Trans-
portation Research B, Vol 24B, No 6, pp 431-442.

 

 

"Illl'lllllllllllllf