

Development of ITS Evaluation Test-Bed Using
Microscopic Simulation – City
of Hampton Case Study
By:
Ilsoo Yun
Byungkyu “Brian”
Park
A Research Project Report
For the Center for ITS Implementation
Research (ITS)
A U.S. DOT University Transportation
Center
Ilsoo Yun
Email: iy6m@virginia.edu
Dr. Byungkyu “Brain” Park
Department of Civil Engineering
Email: bpark@virginia.edu
Center for Transportation Studies at the University of Virginia produces outstanding transportation professionals, innovative research results and provides important public service. The Center for Transportation Studies is committed to academic excellence, multi-disciplinary research and to developing state-of-the-art facilities. Through a partnership with the Virginia Department of Transportation’s (VDOT) Research Council (VTRC), CTS faculty hold joint appointments, VTRC research scientists teach specialized courses, and graduate student work is supported through a Graduate Research Assistantship Program. CTS receives substantial financial support from two federal University Transportation Center Grants: the Mid-Atlantic Universities Transportation Center (MAUTC), and through the National ITS Implementation Research Center (ITS Center). Other related research activities of the faculty include funding through FHWA, NSF, US Department of Transportation, VDOT, other governmental agencies and private companies.
Disclaimer: The contents of this report
reflect the views of the authors, who are responsible for the facts and the
accuracy of the information presented herein.
This document is disseminated under the sponsorship of the Department of
Transportation, University Transportation Centers Program, in the interest
of information exchange. The U.S.
Government assumes no liability for the contents or use thereof.

1. Report No. |
2. Government Accession No. |
3. Recipient’s Catalog No. |
||
|
VACTS-15-0-45 |
|
|
||
|
4. Title and Subtitle |
5. Report Date |
|||
|
Development
of ITS Evaluation Test-Bed Using
Microscopic Simulation - City of
Hampton Case Study |
August, 2003 |
|||
|
|
6. Performing Organization
Code |
|||
|
|
|
|||
|
7. Author(s) Ilsoo Yun and Byungkyu
“Brian” Park |
8. Performing Organization
Report No. |
|||
|
|
|
|||
|
9. Performing Organization
and Address |
10. Work Unit No. (TRAIS) |
|||
|
Center for Transportation
Studies |
|
|||
|
University of Virginia |
11. Contract or Grant No. |
|||
|
PO Box 400742 Charlottesville, VA
22904-7472 |
|
|||
|
12. Sponsoring Agencies'
Name and Address |
13. Type of Report and
Period Covered |
|||
|
Office of University
Programs, Research and Special Programs Administration US Department of
Transportation 400 Seventh Street, SW Washington DC 20590-0001 |
|
Final Report |
||
|
|
|
14. Sponsoring Agency Code |
||
|
|
|
|
||
|
15. Supplementary Notes |
||||
|
|
||||
|
16. Abstract |
||||
|
Microscopic traffic
simulation models are very powerful tools as they provide inexpensive, fast,
and risk-free evaluation environment. They not only provide the simulation of
scenarios that cannot be practically tested in real world conditions, but
also allow various network wide performance measures including travel times,
delay and emissions. In addition, traffic simulation models are also being
used extensively in Intelligent Transportation Systems (ITS) researches.
However, there is a need to develop appropriate methodology and gain
experience in practical usage of traffic simulation models to evaluate ITS
deployments. In this study, the
procedure relevant to building a microscopic traffic simulation-based
test-bed for ITS applications is presented. This thesis describes the
entire process for building a microscopic traffic simulation-based test-bed
for ITS using a case study. The process consists of building a basic traffic
simulation network, the API development for coordinated actuated signal
control and, the dynamic O-D matrix estimation for the network. In order to
estimate the dynamic O-D matrix, an approach using GA and QUEENSOD method
coupled with traffic simulation model is introduced. Some findings during
making the simulation test-bed are also presented. The findings are very
useful for developing a simulation-based test-bed because the lessons learned
from this study can reduce trial-and-errors and efforts needed. |
||||
|
17 Key Words |
18. Distribution Statement |
|||
|
Intelligent Transportation
Systems (ITS), evaluation, microscopic traffic simulation |
No restrictions. This
document is available to the public. |
|||
Microscopic traffic simulation models are very powerful tools as they provide inexpensive, fast, and risk-free evaluation environment. They not only provide the simulation of scenarios that cannot be practically tested in real world conditions, but also allow various network wide performance measures including travel times, delay and emissions. In addition, traffic simulation models are also being used extensively in Intelligent Transportation Systems (ITS) researches. However, there is a need to develop appropriate methodology and gain experience in practical usage of traffic simulation models to evaluate ITS deployments. In this study, the procedure relevant to building a microscopic traffic simulation-based test-bed for ITS applications is presented.
This thesis describes the entire process for building a microscopic traffic simulation-based test-bed for ITS using a case study. The process consists of building a basic traffic simulation network, the API development for coordinated actuated signal control and, the dynamic O-D matrix estimation for the network. In order to estimate the dynamic O-D matrix, an approach using GA and traffic simulation model is introduced in Chapter 5. Some findings during making the simulation test-bed are presented in Chapter 3, 4 and 5. The findings are very useful for developing a simulation-based test-bed because the lessons learned from this study can reduce trial-and-errors and efforts needed.
1 Introduction 1
1.1
BACKGROUND 1
1.2 PROBLEM STATEMENT
2
1.3
RESEARCH OBJECTIVES AND METHODOLOGY 4
1.4
SCOPE OF STUDY 5
1.5
ORGANIZATION OF THIS THESIS 5
2 Literature Review 6
2.1
INTRODUCTION 6
2.2
DYNAMIC O-D MATRIX ESTIMATION2.2.1 STATIC O-D 6
ESTIMATION
2.2.1 Static O-D
Estimation 6
2.2.2 Dynamic O-D Estimation 8
2.2.3 Estimation of
Temporal Route Choice for Dynamic O-D 16
Estimation
2.3
GENETIC ALGORITHM 17
2.3.1 Introduction 18
2.3.2 Mechanisms of Genetic Algorithm
18
2.3.3 Genetic Algorithms
in O-D Estimation 24
2.4 TRAFFIC SIMULATION MODEL
IN ITS EVALUATION 27
2.5 SUMMARY 28
3 a development of large scale case study 29
simulation network
3.1 INTRODUCTION 29
3.2
MICROSCOPIC SIMULATION MODEL SELECTION 30
3.3
MICROSCOPIC SIMULATION MODEL, PARAMICS 33
3.3.1 User Interface 33
3.3.2 Network Structure 33
3.3.3 Traffic Generation and Assignment
33
3.3.4 Signal Control in PARAMICS
34
3.3.5 API in PARAMICS 34
3.3.6 Model Weaknesses 35
3.4 PARAMICS NETWORK 35
3.4.1 Network Building 35
3.4.2 Signal Control Logics 39
3.4.3 Parameter Setting 39
3.4.4 Simulation 39
3.4.5 Visualization 40
3.5 DEVELOPMENT OF AN API FOR
COORDINATED 42
ACTUATED
SIGNALS
3.5.1 Geometry of
Intersection and Detectors 42
3.5.2 Yellow Change Interval
44
3.5.3 New Phase Sequence for API
45
3.5.4 Input Data Structure 47
3.5.5 Control Logic 49
3.5.6 Fully Actuated Signal Control and T-intersection 50
3.6 SUMMARY 51
4 BUILDING Dynamic O-D Estimation Models 53
Using GA and QueensOD model
4.1 INTRODUCTION 53
4.2 USE OF ASSIGNMENT MATRIX 55
4.3 QUEENSOD MODEL 57
4.3.1 Mechanism of
QUEENSOD Model 57
4.3.2 Using Existing Traffic Information
59
4.3.3 QUEENSOD-based O-D
Estimation Process 60
4.4 GA-BASED O-D ESTIMATION MODEL 61
4.4.1 Determination of
GA Selection Method, GA Parameters 62
and GA Operators
4.4.2 Selection of Solution Representation, GA model and 65
Evaluation Function
4.4.3 Evaluation Function 72
4.4.4 GA-based O-D
Estimation Process 77
4.5 SUMMARY 79
5 Implementation of Dynamic O-D matrix
80
Estimation MODELs
5.1 INTRODUCTION 80
5.1.1 Data Collection 80
5.1.2 Peak Period
Selection 81
5.2 QUEENSOD-BASED DYNAMIC O-D
ESTIMATION 82
5.2.1 Finding Better
Assignment Matrix (Step #1) 82
5.2.2 Finding the Best O-D
Matrix (Step #2) 84
5.3 GA-BASED DYNAMIC O-D
ESTIMATION 91
5.3.1 Finding Better
Assignment Matrix (Step #1) 92
5.3.2 Finding Appropriate Total O-D Demand (Step #2) 94
5.3.3 Finding Best Sum of
O-D Demands and O-D Matrix 95
(Step #3)
5.4 SUMMARY 98
Chapter
Page
6 Conclusions and Recommendations 100
6.1 CONCLUSIONS 100
6.2 RECOMMENDATIONS 102
REFERENCES 104
APPENDIX A PHASE SEQUENCE OF 25 ORDERS IN API 108
APPENDIX B INPUT FILES OF API FOR COORDINATED
110
ACTUATED CONTROLLER
APPENDIX C SOLUTION DECODING CONCEPTS IN THE GA
116
APPENDIX D MATALAB CODES FOR QUEENSOD-BASED 119
MODEL AND GA-BASED MODEL
1 Example of Chromosome-like Data Structure Using Binary Digits 19
2 City of Hampton, Virginia 30
3 GIS Map Used as Reference for Network Coding 37
4 Images in Lizard Tech’s MrSID Format 38
5 PARAMICS Network for the Case Study 38
6 Example of inappropriate “next lane” 41
7 Impact of Insufficient Distance for “signposting” 41
8 An Example Intersection in PARAMICS Network 43
9 Splits and Phasing Diagram Based on a Dual Ring, 45
Eight-Phase Controller
10 Splits and Phasing Diagram Based on a Single Ring Controller 45
in PARAMICS
11 Seven External Zones of Case Study Network 60
12 Selection Probability Comparison of Two GA Selection Methods 64
13 Three Stages of Making O-D Matrix Using Solution Representation 1 68
14 Three Stages of Making O-D Matrix Using Solution Representation 2 69
15 Three Stages of Making O-D Matrix Using Solution Representation 3 70
16 Estimated and Observed Link Flows Comparison 74
17 Correlation of Estimated Link Flows from GA Using SSE and MAPE 74
18 15-minute Interval Link Flows 81
19 Convergence of the QUEENSOD Model in Step 1 82
20 Change of Total O-D Demand in Iterations 83
21 Box Plot of O-D Matrix Estimates Evaluation Using PARAMICS 84
22 Convergence of the QUEENSOD Model In Step 2 85
23 Change of Total O-D Demand in Iterations 85
24 Box Plot of O-D Matrix Estimates Evaluation Using PARAMICS 88
25 O-D Demands Adjustment by the QUEENSOD Model 90
26 Comparison of Estimated Link Flows vs. Observed Link Flows 91
27 Box Plot of O-D Matrix Estimates Evaluation Using PARAMICS 93
28 Box Plot of O-D Matrix Estimates Evaluation Using PARAMICS 94
29 Convergence of GA Iterations 95
30 Box Plot of O-D Matrix Estimates Evaluation Using PARAMICS 96
31 Comparison of Estimated Link Flows vs. Observed Link Flows 99
1 Summary of Simulation Run Times Comparison 32
2 Proposed Phase Sequence for API in PARAMICS 46
3 Example of an Assignment Matrix 56
4 Summary of Initial Populations From Three Solution Representations 71
5 Summary of Examination 72
6 Error Measures in Divided Groups 76
7 Results of the QUEENSOD Iterations 86
8 Results of O-D Matrix Estimates Evaluation Using PARAMICS 87
9 Results of the GA Runs 96
10 Evaluation Results of Estimated O-D Matrix Using PARAMICS 97
API - Application Programming Interface
DTA – Dynamic
Traffic Assignment
GA – Genetic
Algorithm
GLS – Generalized
Least Squares
ITS – Intelligent
Transporation Systems
LRE – Least
Relative Error
LSE – Least
Squate Error
MAPE – Mean
Absolute Percent Error
MLE – Maximum
Likelihood Estimation
MOE - Measures of Effectiveness
O-D –
Origin-Destination
SSE – Sum of
Squared Error
Microscopic traffic simulation models are very powerful tools as they provide inexpensive, fast, and risk-free evaluation environment. They have been widely used for evaluating traffic operation and traffic management studies. They not only allow to run simulation scenarios that may not be practically tested in a real world condition, but also provide various network wide performance measures including travel times, emissions, etc (1). It appears that microscopic traffic simulation is slowly becoming an accepted tool in the traditional transportation engineering applications, such as signal timing plan development and capacity studies (2, 3). In addition, traffic simulation models are also being used extensively in the Intelligent Transportation Systems (ITS) researches. When a microscopic traffic simulation model is used to evaluate ITS projects, it is necessary to ensure that the model reflects real world conditions. Hence high fidelity stochastic and microscopic simulation models are used and the models are calibrated using field traffic data.
However, there is a need to
develop appropriate methodology for building the simulation models and to gain
experience in practical usage of traffic simulation models to evaluate various
ITS deployments. In this research, the
procedure relevant to developing a microscopic traffic simulation-based ITS
evaluation test-bed is presented. The procedure includes building a traffic
simulation network and estimating a dynamic Origin-Destination (O-D) matrix.
As transportation system networks to be analyzed become more and more complex, tools that are much better than traditional planning models are required to perform such analyses. Microscopic traffic simulation models used for traffic studies can realistically replicate the movement of traffic to match existing observed conditions and produce network-level performance measures. Thus, traffic simulation models offer several advantages over traditional planning models. The benefits include more detailed results, fancier graphics, capability to model ITS applications, and over saturated facilities. This is why microscopic simulation models have been widely used as test-beds with increasing attention to ITS (1).
However, users should be
careful with the development of the network. It is necessary for the network to
replicate real word situations to the highest degree possible in order to
establish the functionality of simulation model. In particular, when the
network is big, the user might receive abnormal results during simulation
because a large-scale simulation network causes more complex dynamics in
interactions of vehicle-to-vehicle and vehicle-to-traffic control as well as
efforts for data surveying and entering.
This thesis builds a large network and presents the efforts to make the
traffic simulation network to be more realistic.
Another issue for traffic simulation models when they are used in large networks is gathering an appropriate Origin-Destination (O-D) trip matrix. Conventional methods for collecting O-D matrix tend to be costly, labor intensive and time consuming. Therefore, the estimation of O-D matrices from traffic counts is of great interest as traffic counts are easily available, inexpensive to collect and they do not disrupt traffic (4). Moreover, obtaining more accurate and complete traffic information can be expected through good surveillance systems such as vehicle detection sensors, automatic vehicle location (AVL) systems, automatic vehicle identification (AVI) systems, and toll collection systems (TCS). Because of these reasons the process of O-D estimation from traffic counts is gaining interests.
For several decades, many
researchers have proposed and introduced various techniques to estimate static
O-D demands. In conventional planning applications, the static O-D matrix is very
valuable. However, applications based on static O-D matrices can not explain
several issues like the dynamics of congestions, departure time selection, and
time-varying link usage and its spatial change over time. These limitations
become more severe when the estimated O-D matrix is used for short-term
planning studies or traffic operational studies. And with the introduction of
ITS in traditional transportation domain, there has been more need for the
dynamic O-D matrices to consider the temporal and spatial change in congestion
and behaviors of drivers.
Recent researches in the
dynamic O-D matrix estimation based on observed traffic counts provided
promising results on simple networks, long freeway sections and complex
corridors. However, only a few researchers tried to apply the dynamic O-D
matrix estimation techniques to a large city. This thesis proposes a new
approach for the dynamic O-D matrix estimation in a large-scale network.
The objectives of this thesis are: 1) to build a large-scale traffic simulation network using PARAMICS, 2) to develop an coordinated actuated signal control logics for the network, and 3) to estimate a dynamic O-D matrix for the network. The specific tasks are as follows:
1. Review relevant literature and assess the state-of-the-art in the dynamic O-D estimation;
2.
Build a traffic
simulation test-bed (base network) using PARAMICS;
3.
Develop coordinated actuated signal control
logic for the test-bed; and
4.
Estimate a dynamic O-D matrix using QUEENSOD and Genetic Algorithm (GA).
The traffic simulation test-bed consists of the traffic simulation network for the entire City of Hampton and estimates of the dynamic O-D matrix for the network. As a microscopic traffic simulation model, PARAMICS was selected.
This report is organized into six chapters. Chapter 1 is an introductory chapter. Chapter 2 reviews the state-of-the-art related to the dynamic O-D matrix estimations. It includes the introduction of various techniques for the dynamic O-D matrix estimation and their applications and also discusses genetic algorithm (GA) and its applications in the O-D matrix estimation. The developments of the basic simulation network for the case study and the API for a coordinated actuated signal controller are explained in Chapter 3. Chapter 4 and 5 detail the process of estimating a dynamic O-D demand matrix for traffic simulation model based on counted link flows. Finally, Chapter 6 describes the conclusions and recommendations of this project.
This chapter performs a review of literature relevant to dynamic O-D matrix estimations, a genetic algorithm (GA) and use of microscopic traffic simulation model in ITS evaluation. Dynamic O-D matrix estimation methods are summarized and then, the introduction of GA and its applications on the static O-D matrix estimation are followed.
An O-D matrix estimation by using traffic information can be static or dynamic (i.e., time independent or time dependent). The both static and dynamic estimations generally calculate O-D matrices based on the relationship between traffic information (i.e., traffic counts) and O-D information. Ortuza and Willumsen (4) mathematically expressed the relationship as follow:
(1)
where,
= observed
traffic count in link a,
= trips
generated from zone i to zone j,
= proportion
of trips from zone i to zone j traveling through link a,
i = origin,
j = destination, and
a = link identifier.
The assignment parameter (
) is used to define the proportion of trips from zone i
to zone j traveling through link a. Thus, the observed traffic
count (
) in a particular link a is the summation of the
contributions of all trips between zones to that link. The
can be obtained using
various trip assignment techniques ranging from a simple all-or-nothing to a
more complicated equilibrium assignment. Using the calculated
and the observed traffic counts (
), the unknown
is estimated.
For several decades
researchers have proposed various models and their solution techniques to
estimate static O-D matrices. Based on theory used in the OD estimation, the
models can be divided into gravity-based models, entropy models, equilibrium models, statistical models, neural network models, fuzzy
weight models (5), and GA models (6, 7). The gravity-based models utilize
multiple linear regression or non-linear regression (4, 5). Some equilibrium
models use a modified Frank-Wolf algorithm (5). The maximum entropy models
generally have their own specific computer programs (4). The statistical models
utilize the generalized least square estimation methods, Bayesian inference
methods, maximum likelihood estimation or bilevel programming method (8).
In conventional planning
applications, the static O-D matrix is sufficient. However, the applications based on these static O-D matrices do not capture
departure time selections, dynamics of congestions, and time-varying link usage
and its spatial change over time. With the introduction of ITS in traditional
transportation area, there has been an increasing need for the dynamic O-D
matrix to consider the temporal and spatial change in congestion and drivers’
behaviors.
Dynamic O-D matrix estimation involves finding not
only trips from zone i to zone j but also the departure times of
the trips. In other words, dynamic O-D matrix estimation searches the trips (
) leaving zone i to zone j during time interval
dt so as to match the estimated traffic counts to surveyed traffic
counts using assignment parameters (
). The variable
is used to define the
proportion of trips leaving from zone i to zone j during time
interval dt and traveling through link a during time interval t.
Thus, the observed traffic count (
) in a particular link a during time interval t
is the summation of the temporal and spatial contributions of all trips between
zones to that link. Mathematically, the relationship between traffic
information (i.e., traffic counts) and O-D information can be expanded from
Equation (1) as follow:
(2)
where,
= observed traffic count in link a
during time interval t,
= trips leaving zone i to zone j
during time interval dt,
= proportion of trips leaving zone i
to zone j during time interval
dt
and traveling through link a during time interval t,
i = origin,
j = destination,
a = link identifier,
dt = time interval for departure time, and
t = time interval.
Ashok (9) categorized the
dynamic O-D estimation into closed network and open network. A closed network
implies that complete traffic information of the network is available at all points in time. In real world, obtaining that kind
of complete information can be rarely. On the contrary, an open network is
common but it provides only partial information. The following section
discusses several dynamic O-D estimation models for the open network found in
literature. The models are categorized by solution techniques used in the
dynamic O-D estimations in this section.
2.2.2.1 Generalized Least Squares (GLS) Estimator
Cascetta et al. (10) generalized and extended general statistical frameworks proposed for the static O-D estimations to the dynamic O-D estimation case. In their study, two approaches were proposed. The first approach, referred to as simultaneous, looks for an estimator which gives, in one step, the whole O-D matrices for all time intervals by using traffic counts simultaneously as shown in Equation (3). The second approach, referred to as sequential, produces, at each step, estimates a O-D matrix for one time interval using two information: 1) traffic counts relating to the same time interval and to the previous time intervals and 2) O-D estimates relative to previous time intervals as shown in Equation (4). The sequential estimator has two merits over the simultaneous estimator: 1) the use of estimated O-D demands obtained from current time interval as a seed value for the next time interval and 2) the obvious computational advantage. The following equations are the general forms of the simultaneous estimator [Equation (3)] and the sequential estimator [Equation (4)].
(3)
(4)
where,
= vector of the estimated trips for all
O-D pairs leaving the origin
during time interval t,
= vector of the initial true trips for
all O-D pairs leaving the origin
during time interval t,
= vector of observed link flows at time
interval t,
= current value of the trips vector, and
t
= time interval, t = 1,….
.
Cascetta et al. (10)
applied the above two Generalized Least Squares (GLS) estimators and tested the performances of their methods on the
Brescia-Verona-Vicenza-Padua motorway in Italy (linear 140 km long network
including 19 zones, 19 nodes and 54 links).
The accuracy of OD matrices
obtained from these approaches heavily relied on the amount of available
observed link flows (9). Furthermore, no normal procedure was developed for assigning dynamic demands onto the network to obtain
the dynamic assignment parameters mentioned in the section [2.2.2]. However,
the Cascetta et al.’s approach is a good initiative in that it provided
explicit equations for modeling the dynamic O-D estimations using observed link
flows (9).
Hellianga and Aerde (11) compared a least square error (LSE) model and a least relative error (LRE) model. In the LSE model, the best O-D estimate is the one that minimizes the sum of the squared absolute deviations between estimated and observed link flows [Equation (5)]. On the contrary, the LRE model determines the best O-D estimate as the one that minimizes the relative link error [Equation (6)].
(5)
(6)
where,
= link identifier,
= estimated flow on link
, and
= observed flow on link
.
Their study described the application of the above two models for a 35-km section of Highway 401
in Toronto, Canada. In their application, many field conditions including the
true O-D matrix, the true routes, and the true route weights were unknown. Furthermore, loop detector data covered only 45% of the
35-km section of the freeway. The study results showed that the LRE
model estimates showed a much higher correlation (r = 0.95) between observed
and estimated link flows than that of the LSE model (r = 0.75). The study also
argued that the LSE model tends to overestimate the link flows, particularly at
low flows because the it tends to place higher weight on links with large
observed flows (11).
2.2.2.2 QUEENSOD
Van Aerde et al. (12) introduced the QUEENSOD model for generating dynamic synthetic O-D matrices and applied the QUEENSOD model to a 35-km section of Highway 401 in Toronto (12), Canada and Scottdale/Rural Rd. and Hayden Rd. (an alternate parallel rout to Scottdale/Rural Rd.) network in Phoenix, Arizona consisting of 499 nodes and 1,021 links (36) and Salt Lake metropolitan region, Utah (3,365 nodes, 7,926 links and 565 zones) (37). The QUEENSOD model, which is based on an iterative approach, starts the first iteration from a seed O-D matrix, which can be a uniform or historic O-D matrix. The seed O-D matrix is utilized to generate estimates of link flow based on an estimate of drivers’ expected route choices. The adjustment on the seed O-D matrix is conducted based on the quantitative comparisons between observed and estimated link flows. In this manner, the seed O-D matrix is systematically modified to produce a new O-D matrix. Detailed process will be explained in Chapter 4.
The QUEENSOD model is a
computer program specifically orientied to satisfy practical traffic
engineering as opposed to mathematical needs, while still providing a solution that is rooted in the state-of-the-art in a mathematical
theory.
2.2.2.3 Kalman Filtering
Kalman filter algorithms (13) have been widely
proposed to accommodate the real-time requirements (9, 14, 15). These algorithms
solve least-square problems in an incremental fashion and allowing an update on
the solution using measurement equation and transition equation when additional
data is available (16). Okutani (14)
presented a Kalman filtering-based model that estimates or predicts unobserved
link traffic flows from observed link flows. The model includes an
autoregressive formulation in which the state vector for a period is related by
correlation factors to state vectors for prior periods [refer to Equation (7)]. Let us assume that
stands for an unobserved traffic flow on link 1 at time
interval t, which is to be estimated from the observed flows on other
links,
(i = 2,3, ….,
n). According to Okutani (14), the following relationship (transition equation)
holds between
and
:
(7)
where,
= state vector of all link flows at time
interval t,
= n´n transition matrix,
= n dimensional noise vector with ![]()
,
R = matrix of size n´n, and
= Kronecker’s delta.
The measurement (or observation) equation associated with the state vector
is given by:
(8)
where,
= n-1 dimensional observation vector,
= measurement error vector of size n-1
with
,
= (n-1)´(n-1) covariance matrix of
,
= (n-1)´n transfer matrix of
measurement system defined as
,
O = zero vector of size n´1, and
I = n´n identity matrix.
The above Equation (8) states that the link flows except the flow on link 1
is observed. From Equations (7) and (8), we can obtain the estimate of
denoted by
in accordance with the Kalman filter theory as:
(9)
where,
= n´(n-1) Kalman gain matrix.
In Equation (9), the estimate
is given by the first
element of
.
Ashok (9) and Ashok and Ben-Akiva
(15) formulated a Kalman filter based approach for real-time estimation and
prediction. In order to overcome the inadequacy of Okutani (14)’s
autoregressive specification for link flows, they introduced the notion of
deviations of O-D demands form historical estimations. The state vector is
hence defined in terms of O-D deviations that conform to an autoregressive
process. The measurement equation is the same as Okutani’s. The assignment
factions are obtained either by using the equations derived by Cascetta et
al. (10) or by using a Dynamic Traffic Assignment (DTA) approach. The model
was evaluated using actual traffic data from Massachusetts Turnpike,
Massachusetts (120 miles, 15 entry/exit ramps, and 210 O-D pairs), a stretch of
I-880 near Hayward, California (5.2 miles, 4 on-ramps, 5 off ramps and 20 O-D
pairs) and a freeway encircling the city of Amsterdam, Netherlands (32 km, 20 entrance and exit
ramps (9).
Hu (35) also introduced
Kalman filtering algorithm in dynamic O-D estimation and prediction problem in
which a similar autoregressive process to Ashok and Ben-Akiva (15) was used in
the transition equation. The approach was evaluated at a hypothetical freeway
network, which consisted of 8 zones, 32 nodes and 70 links, and historic O-D
matrix. All entrance, exit and mainline traffic counts for the approach were
obtained from DYNASMART simulation results. In the approach, Hu included a
control equation within the Kalman filtering algorithm to consider drivers’
dynamic responses to traffic conditions (i.e., their route change according to
traffic information or congestions). For the equation, a discrete choice model
was included to calculate time-varying route switching probabilities of each
driver for given travel time and different routes (35).
The advantage of Kalman
filter algorithm is its ability of accommodation for estimation and on-line prediction of dynamic O-D matrix (15, 35). The
main drawback of the Kalman filter algorithm appears to be its inability to
handle large-scale O-D estimation problems. The analytical computation of the
normal equations and the variance propagation require intensive linear algebra
computations. Moreover, the sparsity of the least-square problem (the amount of
available observed traffic counts) is not exploited by the algorithm and a lot
of fill-in has to be performed (16). However, when traffic conditions are
normal, or when the time intervals are short, the auto-regressive process can
provide a good estimate of the O-D matrix (16).
2.2.2.4 Maximum Likelihood Estimation (MLE)
He et al. (17) proposed a Maximum Likelihood Estimation (MLE) approach to estimate the parameters of dynamic O-D demand and route choice simultaneously. In order to derive a full likelihood functions for dynamic O-D and route choice, they presented approximate joint probability distribution function of the temporal link flows on a network. This algorithm was tested in two simple and ideal networks: i) a network including 4 nodes and 5 links and ii) a network consisting of 9 nodes and 12 links.
The proposed model could incorporate prior information. It can estimate the parameters with measurement errors and incomplete data.
The most important input in the dynamic O-D matrix estimation is the calculation of temporal route choices of individual drivers. In static O-D matrix estimation, this route choice (assignment) is broadly classified into two main groups: proportional and non-proportional assignments. Proportional assignment method makes the proportion of drivers choosing each route independent from flow levels. The all-or-nothing assignment is an example of this kind of assignments. Non-proportional assignment explicitly considers congestion effects such that the proportion of travelers using each link does depend on link flows. Equilibrium or stochastic assignments are used in the non-proportional assignment method.
However, to estimate
dynamic O-D matrix, the assignment has to consider temporal variation of
congestions. Hence the traditional assignment method is not sufficient for this kind of estimation. In order to obtain temporal route
choices, DTA or traffic simulation models are usually used (9, 12, 15, 18). For
example, QUEENSOD model is linked with INTEGRATION, a microscopic traffic
simulation model.
In this section, genetic algorithms are investigated. Genetic algorithms (GA) were developed by John Holland in the early 1970s at the University of Michigan (19). GA is a family of computational models inspired by evolution and natural selection (20). These algorithms encode a potential solution to a specific problem on a simple chromosome-like data structure and apply recombination operators to these structures so as to preserve critical information. It can be classified as a guided random search algorithm to optimize any form of objective function (21).
Genetic algorithms have been used to solve problems
with objective functions that are difficult to work out with mathematical
approaches (19, 22, 23). In particular, lots of transportation systems are
based on stochastic systems, which are difficult to be represented in
mathematical formulations. Dynamic O-D matrix estimation is a good example. In
Equation (1), the observed traffic count (
) in a particular link a is the summation of the
contributions of all trips between zones using that link. The trips are
determined according to the dynamics of vehicle-to-vehicle, vehicle-to-control
system, congestions and resulting route choices. Thus, it is not easy to
represent the resulting trips with a mathematical formulation.
Genetic algorithms maintain
and manipulate a population of potential solutions and implement a “survival of
fittest” concept to search better solutions. The GA also provides an implicit
as well as explicit parallelism (24).
Explicit parallelism allows the exploitation of several promising areas
of the solution space at the same time through generations. The implicit
parallelism is due to the schema theory developed by Holland. Schema theory is
explained in the Sections 2.3.2.5.
The genetic algorithm is a population-based model that uses selection and recombination operators to generate new sample points in a search space. In general, the fittest individuals in the population tend to reproduce and survive to the next generation, thus improving the quality of successive generations. Genetic algorithms have been shown to solve linear and nonlinear problems by exploring all regions of search space and exponentially exploiting promising areas through selection, crossover and mutation operations (25).
2.3.2.1 Solution Representation
In GA, each individual solution should be systemically described by a chromosome-like data structure. The chromosome-like data structure is made up of a sequence of genes from a certain alphabet. An alphabet could consist of binary digits (0 and 1), floating point numbers, integers or symbols (24).
![]()
Figure 1. Example of Chromosome-like Data Structure Using Binary Digits
The Figure 1 illustrates an example of chromosome-like data structure using binary digits. This solution representation consists of three parameters (or genes). The first parameter (the first four binary digits) means ‘12’ in integer value.
The representation scheme
determines how the problem is structured in the GA and also selects the genetic
operators that are used. Problem representation (or solution representation)
has been the subject of much investigation. It has been shown that more natural
representations are more efficient and produce better solutions (25).
2.3.2.2 Selection Function
The selection function of
individuals to produce successive generations plays an extremely important role
in the genetic algorithm. A probabilistic selection is performed based on the
individual’s fitness such that the better individuals have an increased chance
of being selected. An individual in the population can be selected more than
once. There are several schemes for the
selection process: roulette wheel selection and its extensions, scaling
techniques, tournament, and ranking methods (23, 25).
Roulette wheel method,
developed by Holland (19), works as follow: The probability of selection for
each individual i,
, is defined by:
(10)
where,
= probability
where individual i is chosen, and
= fitness of individual i.
The use of roulette wheel
selection limits the genetic algorithm to maximize the evaluation function.
Extensions, such as windowing and scaling, have been proposed to allow for
minimization (24). Ranking method is also used and it requires the evaluation
function to map the solutions to a partially ordered set to allow for
minimization. Ranking method assigns
based on the rank of solution i when all solutions are
sorted. Normalized geometric ranking (24) defines
by:
(11)
where,
q = the probability of selecting the best individual,
r = the rank of the individual i,
N = population size, and
q’
= ![]()
Tournament selection also
requires the evaluation function to map solutions to a partially ordered set.
However, it does not assign probabilities. Tournament selection works by
selecting j individuals randomly, with replacement, from the population, and
inserts the best of the j into the new population. This procedure is repeated
until N individuals have been selected.
The elitist selection
method keeps the best individual from generation to generation. If the best
individual has not been transferred to the next generation during the
reproduction, crossover and mutation processes, the elitist method copies the
best individual from the current population to the next population to ensure
its survival (24). This elitist selection method is usually used with other
selection methods.
2.3.2.3 Genetic Operators
Genetic operators provide the basic search mechanism of the genetic algorithm. The operators are used to create new solutions based on existing solutions in the population. There are two basic types of operators: crossover and mutation (24). The crossover takes two individuals and produces two new individuals while the mutation alters one individual to produce a single new solution.
The application of these
two basic types of operators and their derivatives depends on the solution
representations (binary, real-valued number or symbol). In this section, simple
mutation and simple crossover processes for binary solution representation are
explained.
Let
and
be two m-dimensional
row vectors denoting individuals (parents). Simple binary mutation generates a
random number r from a uniform distribution and flips each bit in every
individual in the population with probability
according to the
Equation (12).
(12)
Simple crossover generates
a random number r from a uniform distribution and creates two new
individual (
and
) according to the Equation (13).

(13)

2.3.2.4 Initialization and Termination
The genetic algorithm must start with an initial population. The most common method is to use randomly generated solutions for the entire population. However, since GAs can iteratively improve existing solutions, the beginning population can be seeded with one potentially good solution with the remainder of the population being randomly generated.
The GA moves from
generation to generation by selecting and reproducing individuals until a
termination criterion is met. The most common stopping criterion is a maximum
number of generations. Another termination strategy involves population
convergence criteria. In general, GAs will force much of the entire population
to converge to a single solution. When the sum of the deviations among
individuals becomes smaller than some specified threshold, the algorithm can be
terminated. The algorithm can also be terminated due to a lack of improvement
in the best solution over a specific number of generations. Several strategies
can be used in conjunction with each other.
2.3.2.5 Schema Theorem
Even though there exists no established general theory that explains exactly why genetic algorithm works, several hypotheses have been proposed which can partially explain the mechanism of genetic algorithms (27).
The basic theory of genetic
algorithms is based on a binary string representing a solution, and on the
notion of schemata (25). A schema is a string of total length l, taken
from the symbols {0, 1, *}, where, ‘*’ is a ‘do not care’ symbol.
A schema represents the set of all binary strings of length l, which
match with all positions other than ‘*’.
For example, consider the schema, * 1 0 *. It matches with four strings,
{0100, 0101, 1100, 1101}. It is noted that every schema matches exactly 2r
stings, where r is the number of ‘ * ’ in a schema.
Two important properties of
schema are their order and defining length. The schema theorem is built from
these properties. Order is the number of fixed bit-positions (i.e., 0 and 1 position)
in a schema. Defining length is the distance between the first and last fixed
bit positions.
The schema theorem (19) was
the first rigorous explanation of how genetic algorithms work. It says that
“short, low-order, above-average schemata receive exponentially increasing
trials in subsequent generations of a genetics algorithm.” Michealewicz (25)
explained the schema theorem in more detail with the calculation of survival
probabilities
A few studies in the area of the static O-D matrix estimation have been successfully conducted with GAs. Kim et al. (6) proposed the GA to estimate static O-D matrices. In the study, the sensitivity analysis based (SAB) algorithm and the GA as solution algorithms based on a bilevel programming approach were compared using a simple network consisting of nine nodes and fourteen links. The objective function is formulated as minimization of square errors based on the bilevel program approach proposed by Yang (28). The objective function consists of traffic counts and historic O-D matrix as shown in the Equation (14).
(14)
where,
= estimated trips between zone i
and zone j, ij Î W,
= historical trips between zone i
and zone j, ij Î W,
= estimated link flows on link a, a
Î
A,
= observed link flows on link a, a Î A,
a = link identifier,
W = vector for all zone pairs, and
A = vector for all link.
Here,
is a parameter reflecting the reliability of the
historical O-D matrix. If the O-D matrix structure
is altered by changes in land uses, a new traffic facility or etc.,
should have lower
value since there is no significant dependence between the historical O-D and
the current O-D patterns. In order to obtain the assignment parameter (or
driver’s route choices and its weight), equilibrium assignment was used. The
individual solutions were represented with two chromosomes:
Xn[m][ij] = choice proportion of mth chromosome between i and destination j in n
generation, where m=1, 2, …, M, M is the number of population, and
Yn[m][ij] = proportion of mth chromosome from origin i in n generation.
Using the two chromosomes, the GA calculates the estimates of trips as follow:
(15)
where,
= historical trips generated from origin i.
Using the calculated trips
and resulting link flows from equilibrium assignment, the fitness values of
individual solutions are calculated from the Equation (14). Real-valued GA was
used with arithmetic crossover and uniform mutation (24). The maximum
generation number was used as a stopping condition.
Yin (7) also used GA-based
approach to solve a bilevel programming model for static O-D estimation with
two simple networks. The basic idea of the GA approach is to code the decision
variable (trips between zone-pairs) of the upper-level problem (minimizing the
difference between historical O-D matrix and estimated O-D matrix) and
calculate the fitness of each chromosome by solving lower-level problem
(minimizing the difference between observed link flows and estimated link
flows). In order to solve the bilevel problems, Binary GA was used with
single-crossover and single-bit point mutation (simple mutation) and tournament
selection. The maximum generation number was used as a stopping condition.
From the numerical tests,
the GA-based approach based on the global perspective and implicit parallelism
was founded to be more efficient than to SAB algorithms for the static O-D
estimation. Therefore, the GA-based approach could estimate the current O-D
matrix correctly by using the historic O-D matrix, which was surveyed before
changes in trips patterns because the GA decreases the dependency on initial
values. However, the GA-based approach required more computation efforts than
the SAB algorithms but avoids the complex computation.
In this section, researches that used microscopic traffic simulation models in evaluation on ITS applications are summarized.
Nelson and Bullock (39) examined the impact of emergency vehicle preemption on closely spaced arterial traffic signals on State Route 26, Indianan. In their study, CORSIM was used to gain the quantitative data according to control and preemption logic from three traffic signal controllers linked to CORSIM for the SR-26 arterial.
Hansen et al. (40) connected the adaptive signal control system SCOOT to CORSIM to evaluate the performance of the adaptive signal control system in a 6 nodes network. In their approach, CORSIM provides the necessary traffic detector data for SCOOT optimization such that SCOOT can be evaluated under various traffic conditions generated by the traffic simulation model.
Lucas et al. (41) evaluated the performance of the RHODES (real-time hierarchical optimized distributed effective system) under various traffic environment generated by CORSIM. Here, CORSIM produced second-by-second traffic detector information and evaluated the function of the traffic control of the RHODES via communication using a dynamically linked library (DLL).
Chu et al. (43) presented a micro-simulation method to evaluate potential ATMIS applications using PARAMICS. In the study, PARAMICS provided control of traffic operations and realized several functionalities of ATMIS strategies using APIs under incident scenarios in a corridor network located in Irvine, California.
The above review has summarized the various approaches for dynamic O-D matrix estimations from traffic information and it certainly illustrates the complexity of the problem. Several techniques including generalized least squares (GLS) estimation, QUEENSOD model, maximum likelihood estimation (MLE) and Kalman filtering have been used for finding solutions for the dynamic O-D estimation problem in previous studies. Each technique has its own strength and weakness related to i) the amount of available traffic information, ii) capability for a large-scale network and iii) finding reasonable drivers’ route choice and its weight.
With the advances in the computation technology and needs for better evaluation tools in the design and analysis of transportation network, the use of microscopic simulation programs has been widely practiced. This is, in part, because the microscopic simulation tools provide inexpensive, fast, and risk-free evaluation environment.
However, when researchers and practitioners are to use a microscopic simulation program in their studies, they often face that certain features are not provided with the original program or not sufficient in achieving desired evaluations. For example, the implementation of coordinated actuated signal timing control logic in the PARAMICS program is very limited. One solution to these is adding a user-specified module into the program using an application programming interface (API). This has been well exercised by researchers but very limited to practitioners.
The purpose of this chapter is to develop a large-scale case study simulation network. This chapter expresses the detailed process related to building a basic network and developing an API for coordinated actuated control logic in PARAMICS.
As a case study, this study develops a simulation-based large-scale test-bed for the City of Hampton, Virginia, in the U.S.A. using a microscopic simulation package, PARAMICS. Figure 2 shows the location of City of Hampton in Hampton Roads, VA.

Figure 2. City of Hampton, Virginia
According to Rakha et al. (37), a large network is defined as a network with more than 1,000 links. They described the requirements of a validated microscopic model for large-scale modeling as followings:
“ i) the model must be capable
of modeling origin-destination demand
tables, ii) the model must be
capable of modeling dynamic traffic routing,
and iii) the model must be capable of modeling the dynamic
interaction
of freeway/arterial
facilities.”
In order to search appropriate microscopic traffic simulation model, we compared CORSIM, SYMTRAFFIC, VISSIM and PARAMICS in terms of capability of large-scale network and the above three requirements (3). As a result of that, we selected PARAMICS for this study. In PARAMICS, there are no logical limitations on the number of links, nodes and vehicles whereas CORSIM and SYMTREAFFIC cannot support any large-scale network due to limitation on network size. VISSIM and PARAMICS can support O-D matrix-based assignments. In particular, PARAMICS provides various assignment methods including all-or-nothing, stochastic assignment, dynamic feedback assignment and their combinations whereas VISSIM allows one dynamic assignment method. These various assignments of PARAMICS can support to investigate various route choice behaviors of individual drivers. In addition, PARAMICS showed faster computational ability than VISSIM as shown in Table 1.
Table 1. Summary of Simulation Run Times Comparison
|
Programs |
Simulation Conditions |
Average (Second) |
Median (Second) |
Standard Deviation |
|
VISSIM |
With animation, with VAP |
300.8 |
298.0 |
6.76 |
|
Without animation, with VAP |
203.2 |
202.0 |
4.6 |
|
|
With animation, without VAP |
242.7 |
244.0 |
4.16 |
|
|
Without animation, without VAP |
145.2 |
145.0 |
0.84 |
|
|
PARAMICS |
With animation, with API |
296.3 |
295.5 |
4.13 |
|
Without animation, with API |
42.3 |
40.0 |
6.31 |
|
|
With animation, without API |
298.0 |
298.0 |
1.87 |
|
|
Without animation, without API |
41.6 |
40.0 |
6.19 |
1) These comparisons of simulation run time were conducted in the network including
four intersections that is operated in coordinated actuated signal control, and
2) These comparisons of simulation run time were conducted in the computer with Intel
Pentium III (933MHz) and 128MB memory.
PARAMICS, developed by QuadStone Ltd., in U.K., is a suite of high performance software tools that provides microscopic, time-stepping, and scalable traffic simulation (29). The complete suite of the PARAMICS software comprises five modules: i) Modeler, ii) Processor, iii) Programmer, iv) Analyzer and v) Monitor. Among these, the Modeller is a core simulation and visualization tool and the Programmer is an API to PARAMICS (30). PARAMICS has been chosen by traffic researchers and practitioners in the US for their traffic studies.
The PARAMICS model provides a graphical user interface to build networks and to watch the simulation results (Analyzer) and animation (Modeller). User can build the layout of network using background images in DXF, BMP, and OS/NTF Strategi format.
The network in PARAMICS is based on node-link structure. Node usually represents the intersection or the point where attributes of link connecting the node to other nodes change. Link means a road street. PARAMICS defines the route of each vehicle through assignment. Thus, PARAMICS has zones and zone connector. Each vehicle starts its trip from origin zone to destination zone. Zone connector links a zone and a link in a network. The zone connector has zero impedance and is not considered in calculation of MOEs such as travel time.
Travel demand in PARAMICS is defined as an origin-destination matrix of origin. The trips are proportioned into vehicle type and are profiled by 5 minute time period for a maximum of 24 hours. Based on this time period and demand, vehicles are randomly released.
The choice of time period is governed not only by the fluctuation in time dependent traffic demand but also network changes such as different traffic signal settings by time of day. This gives the user a lot of flexibility in the design. The three main assignment techniques used in PARAMICS are all-or-nothing, stochastic and dynamic feedback assignments. Stochastic assignment method accounts for variability in travel cost (or driver’s perception of those costs). This method assumes that the link costs perceived by drivers can be different depending on their characteristics. Dynamic feedback assignment assumes that drivers who are familiar with the road network will re-route if information on the present state of traffic condition is fed back to them.
The built-in traffic signal control logic in PARAMICS is designed for pretimed signals under single ring structure. Thus, the advanced signal control logics such as actuated signal control need to be developed. This can be achieved in two ways: an API and a plan language. The API has to be coded in a C++ language, while a built-in plan language can be written as a script.
The PARAMICS Programmer is a framework that allows advanced users to customize existing control logics in the simulation model using APIs. The user customized logics are implemented through a dynamic link library (DLL), which is generated from a C++ file containing the customized logic. A few examples of such API applications have been already exercised. These include signal control logic (3, 31) and parameter calibration (32).
Although PARAMICS allows the API and the plan language to develop coordinated actuated signal control logic, it is not easy for practitioner end users to build one. In addition, PARAMICS does not allow the dual-ring concept or NEMA control concept. Furthermore, PARAMICS doesn’t have an automatic diffusion function. For example, in PARAMICS if a vehicle were unable to make lane change it would stop and block other vehicles. This leads to discrepancies in performance when compared to real world condition and causes higher variability in simulation output. With a diffusion feature, a vehicle would not wait more than user-defined diffusion time. The vehicle would be removed from the simulation after diffusion time.
The PARAMICS network, as shown in Figure 5, consists of 50 zones, 3,364 links, 1,464 nodes, and 154 signals. The 97 intersections out of the total 154 signals are being operated under a coordinated and actuated mode.
Network building for this study was conducted as the following process (29):
1) Preparing Data.
- Background image of the City of Hampton
- Distance between two specific points within the desired network
- Categories of link types in terms of number of lanes, speed limits, arterial or freeway, major or minor, and width of median
- Detailed geometries of intersections and ramps
- Control types of intersections and their signal timing plans
- O-D matrices
2) Importing background image and adjusting scale parameters for the imported
image using the distance measured in advance.
3) Adding nodes for intersections and ramps using the Network Editor.
4) Adding links between nodes using the Network Editor.
5) Making network layout to be realistic through adding dummy nodes and links or
using Curve Editing function in the Network Editor.
6) Installing zones using the Network Editor.
7) Entering link attributes using Link Attribute Window in the Network Editor.
8) Fine-tune geometries of intersections using the Network Editor
- Installing left turning bay, right turning bay, and detectors
- Changing location of curbs and stop bars
9) Entering signal timing plans to each intersection suing Edit Junction Window in
the Network Editor.
10) Entering O-D matrix.
11) Setting simulation parameters.
12) Watching animations.
13) Repeat the above steps if necessary.
The layout of the PARAMICS
network is coded based on a bitmap image from a Geographic Information Systems (GIS) map (Figure 3). Using the GIS map of the
City of Hampton, the distances between intersections were determined.

Figure 3. GIS Map Used as Reference for Network Coding
The link attributes (number of lanes, geometry, link type – major, minor and freeway, etc.) and the node attributes (intersection geometry, intersection shape, number of lanes, lengths of left turning and right turning bays, etc.) were gathered from images in Lizard Tech’s MrSID format as shown in Figure 4.

(a) Zoomed-out Image (b) Zoomed-in Image
Figure 4. Images in Lizard Tech’s MrSID Format
Through the process mentioned in the above, the following traffic simulation network including 50 zones, 3,364 links, 1,464 nodes and 154 signals was finally built.

Figure 5. PARAMICS Network for the Case Study
An API for the actuated and coordinated signal control logic was developed. The API code consists of Visual C++ code of about 3,700 lines. The signal control logic can realize actuated control features including gap-out, force off and phase skip. An API code can control all intersections in the network. The development of this process is detailed in section [3.4].
The network started with default parameter values. Default values of 1 second each were used for the most important network wide calibration parameters: mean headway and mean reaction time. It is noted that in order to avoid unrealistic simulation the lengths of the entire links were used as signposting distances (i.e., the distance from the intersection that drivers become aware of the intersection). In PARAMICS, if a proper signposting distance is not provided, a vehicle that needs to make lane change occasionally blocks the traveling lane until it finds acceptable gap to make lane change. Even with the maximum signposting distance, extremely large queues and network gridlocks were observed. In order to reduce such unrealistic behaviors, the dynamic feedback time is reduced to 120 seconds from default of 350 seconds.
Since microscopic simulation programs start from empty network, they need initialization period. This basically fills the network such that the network condition and the simulation output become more realistic. It is decided to use 60 minutes of network warm-up time and 60 minutes of simulation time. Default time step of 0.5 seconds is used such that each vehicle’s position is updated every 0.5 seconds. There exist multiple paths among O-D zones in the test network. Thus, a dynamic assignment method in PARAMICS was used so that the variability in travel costs (or driver’s perception of those costs) plays the primary role in finding optimal routes.
The visualization involves the observation of the simulation runs and its purpose is to ensure that the traffic is moving through the network in a realistic manner. Some corrections were made to adjust specific behaviors at links, on lanes or at intersections via this visualization. These corrections include moving curb locations, stop line control points, forced lane change positions, etc (29). In particular, “next lane” for nodes and “signpost distance” for links are used for forced lane change by replacing default PARAMICS lane changing values. Setting “next lane” in a node and adjusting the parameters for “signposting” were critical in achieving realistic simulation. Parameters such as “moving curb” and “stop line control points” were used for smooth and realistic movements of individual vehicles at specific locations. These four parameters were changed after observing the visuals from the simulation.
Figures 6 and 7 show the impacts of inappropriate “next lane” setting and parameters for “signposting.”

Figure 6. Example of inappropriate “next lane”
As seen in Figure 6, all vehicles moving from the upstream link to the downstream link use only the third lane. This abnormal behavior could occur in a regular network if the “next lane” parameter is not set properly.

Figure 7. Impact of Insufficient Distance for “signposting”
Figure 7 shows some vehicles blocking the through lanes. These vehicles need to make left turns but are unable to make appropriate lane changes due to lack of acceptable gaps. This situation may lead to distortion in simulation results as the vehicles that are not on their proper lanes can lead to huge unrealistic congestion. This can be avoided by increasing the distance of “signposting”.
A major disadvantage in a pretimed signal is that its phase times do not respond to fluctuating traffic volume conditions. Unlike the pretimed signal, an actuated signal can adjust the phase times according to the prevailing traffic conditions (33). Furthermore, coordinated actuated signals can provide progression by maintaining coordinated phase times and allow phase skip and gap-out on non-coordinated phases. Thus, unused phase green times are added to the coordinated phases (34).
The API developed in this paper realizes coordinated
actuated signals with 25 possible types of phase sequences (refer to the
Appendix A). In the process of the API development, this research used PARAMICS
Modeler v.3, Programmer v.3., and Microsoft Visual C++ v.6.
Figure 8 illustrates the layout of a four-leg intersection being operated under coordinated actuated control logic. The eastbound and westbound approaches are coordinated phases.
N

(a) Layout of Intersection (b) Signpost
Figure 8. An Example Intersection in the PARAMICS Network
Detectors are essential components in the operation of coordinated and actuated signals. A detector in PARAMICS can cover entire lanes on an approach link where detector is installed (29). The proposed API is designed to utilize up to three detectors on each approach. The specific usage of detectors is explained as follow.
One detector case: One stop bar detector determines both the presence of through and left turn vehicles during red interval and the extension of the through movement during green interval.
Two detectors case: One stop bar detector determine only the presence of through and left turn vehicles during red interval, while the other upstream detector (second one) determines the green extension of through movement during green interval.
Three detectors case: Two stop bar detectors determine the presence of each of through and left turn vehicles during red interval, while the upstream detector (third one) determines the extension of the through movement during green interval.
The functionality of detectors may be changed according to the hierarchy of approach (coordinated approach or uncoordinated approach) or traffic controller type (fully actuated or semi actuated). A recent study (31) suggested that the use of multiple detectors instead of a long loop on left turning lanes. The study also noted that simulation time would increase with the use of multiple detectors as PARAMICS calculates the status of entire detectors in every time step.
In PARAMICS, yellow change interval time is a global variable such that only one value is used for the entire phases in the network. Furthermore, yellow change interval is not recalled for the phase once a phase skip occurs. Thus, the yellow change interval and the actual green interval are combined such that only effective green interval (1) is used.
PARAMICS does not provide any functions that can control yellow change interval. Only green time and all red time are controllable by “signal_action” call back function (31). Because of this limitation, yellow change intervals are added to the green intervals in this study as shown in Table 2.
PARAMICS uses a phase representation that is different from a dual ring, eight-phase controller. Figure 9 shows the splits and phasing diagram of Synchro (i.e., traffic signal coordination software) for the phase sequence number 1 (refer to Appendix A). The splits and phasing diagram of SYNCHRO are a graphical representation of the current splits and phasing based on a dual ring, eight-phase controller (34).

Figure 9. Splits and Phasing Diagram Based on a Dual Ring, Eight-Phase Controller
A phase symbol ‘f’ and the NEMA phase number is shown next to the movement symbol (arrows in Figure 9), while green split time in seconds is shown in the bar chart right below the movement diagram. The green split time includes green interval and intergreen times (yellow plus all red interval). However, PARAMICS uses a phase representation based on a single ring controller for its built-in pretimed controller. The single ring controller has the phases to operate one at a time sequentially as shown in Figure 10.

Figure 10. Splits and Phasing Diagram Based on a Single Ring Controller in PARAMICS
A phase number in PARAMICS is identified with the phase symbol # as shown in Figure 10. The phase number identifies a group of non-conflicting movements arranged in an established order of preferred sequence. For the dual ring controller (see Figure 9), the phase f1 identifies the westbound left turn movement. For the PARAMICS single ring controller (see Figure 10), phase #1 means the movement of the westbound and eastbound left turns. The phase #2 is an overlap phase here. If an overlap phase exists, PARAMICS gives no intergreen (yellow and all red time) time between consecutive movements. For example, when PARAMICS changes green time from phase #1 to phase #2, it assigns intergreen time only between the westbound left turn and eastbound through as shown in Figure 10. This is because the eastbound left turn on phase #1 and #2 is consecutive phase. Each phase in Figure 10 can be individually skipped and gapped-out if no demand is present except for the coordinated phases. In order to implement phase skip and gap-outs in PARAMICS, this study uses a few dummy phases as shown in Table 2.
Table 2. Proposed Phase Sequence for API in PARAMICS
|
Times (second) |
Phases |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#1 |
#2 |
#3 |
#4 |
#5 |
#6 |
#7 |
#8 |
#9 |
#10 |
#11 |
#12 |
#13 |
|
|
Green |
75 |
11 |
- |
- |
5 |
- |
47 |
15 |
- |
- |
9 |
- |
- |
|
Yellow**** |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
All Red |
3 |
3 |
- |
- |
3 |
- |
3 |
3 |
- |
- |
3 |
- |
- |
|
Marks* |
A |
A |
D |
D |
O** |
D |
A |
A |
D |
D |
O** |
D |
D |
*“A” means an actual phase, “D” means a dummy phase, and “O” means an overlap phase.
** These overlap phase is specified as a dummy phase if there exists no overlap phase.
*** The Phase #1 for these through movements is assumed as a coordinated phase.
**** Yellow times are included into Green interval as mentioned in the above
In Table 2, these dummy phases are used to realize the revised phase sequence due to gap-out, phase skip or extension on coordinated phase. For example, if no demand were present for phase #2 (both northbound and southbound left turns), the proposed API would skip the phase #2 and serve phase #7. If no demand for only northbound left turns were present for phase #2, the API would skip the phase #2 and serve phase #3 followed by phases #4 and #7. Here, the phase #4 works as an intergreen time for the southbound left turn movement and it serves between new phase #3 and actual phase #7. The phase sequence starts from the coordinated through movements (eastbound and westbound through movements) in order to keep the offset reference points. This is because it appears that the offset reference point in PARAMICS is always the start of the first phase (phase #1).
Two input data files are required to implement the proposed API. One is the “priorities” file – a standard input file in PARAMICS. The “priorities” file includes information like green interval, maximal allowed green interval, all red time and movement categorizations (i.e., major, medium and minor) for each phase. The other required input file contains the “intersection layout and signal timing” data. It includes detailed information about intersection layout, NEMA phase numbering, signal timing plan and etc. Detail descriptions are shown below.
3.5.4.1 “priorities” file
The “priorities” file defines green and red time interval and the hierarchy of movements. The following is an example of the first phase in the API (through movements on major approaches):
actions 1 (node
ID for this intersection)
phase offset 0.00 sec (offset)
phase 1 (phase number)
70.00 (green
interval)
max 135.00 (maximal
allowed green interval)
red phase 3.00 (all red
time)
fill (no use of
yellow time)
all barred except (priority of
movements)
from 2 to 5 minor (setting turning
movement of 2à1à5 as minor)
from 3 to 2 minor (setting turning
movement of 3à1à2 as minor)
from 3 to 5 major (setting turning
movement of 3à1à5 as major)
from 4 to 3 minor
from 5 to 3 major
from 5 to 4 minor
The hierarchy of priorities follows the order of “major”, ”medium”, “minor”, and “barred.” “Major” priority movements are free flow and not restricted by other streams of traffic. “Medium” priority gives way (yields) to “major” streams of traffic but has priority over “minor” traffic movements. “Minor” priority yields its right of way to both “major” and “medium” traffic flows while “barred” indicates the turn is banned to all vehicle movements (1). In this study, “major”, ”medium” and “minor” priorities are used for protected through or left movement, permissive left movement and right turn respectively. For dummy phase, no green interval and no all red time is assigned in the priorities file.
3.5.4.2 Intersection layout and signal timing data
Information like the intersection layout, NEMA
numbering, detailed signal timing plan for each intersection is embedded in
“plugin.c”, which is a standard file to make the “dll” file for actuated
control. The following is the structure
used in the “plugin.c” file. Data structure of “approach_layout” contains
detector ID, the number of lanes for the left turn and through movements, left
and through movement lane numbers. This information is required to check calls
for right of way during red intervals and for gap times during green intervals.
Data structure of “approach_layout” is embedded in the data structure of
“intersections”. The data structure of
“intersections” includes node (intersection in the PARAMICS Zoom window) name
and ID, the order of phase sequence, major and minor approaches ID and their
directions, the NEMA phase numbering and signal timing plan for each PARAMICS
phase. For offset values, the value in the PARAMICS standard input file
(priorities file) was used in the API. More
detailed description is available in Appendix B.
The objectives of developing an API for coordinated and actuated signal control are two folds. One objective is to develop an API that can consider various phase sequences as shown in Appendix A. It is noted that phase sequences at the traffic signals differ due to characteristics in vehicle arrivals, geometry (turn bay length) and others. The other objective is to develop an API that can control entire intersections in the simulation network. An API for each intersection would be easy to develop but would result in less efficiency.
To maintain a background cycle length and offsets, all coordinated and actuated intersections use the same reference phase – phase for the main street. For an eight-phase controller the reference phase is usually phases (f2 + f6) in NEMA phase numbering (10). In order to provide the right of way to the coordinated phase at the yield point within the cycle, the non-synchronized phases are terminated after a certain length of time and these are called force off points. The API calculates all force off points and permissive periods before starting simulation using the “api_setup” control function of the PARAMCIS Programmer.
In the API, coordinated phases (phase f2
+ f6
in NEMA phase numbering) are set to “maximum recall” (10). These phases utilize
their maximum green times plus any unused times from the preceding phases.
All the phases except for coordinated phases could be gapped-out or skipped depending on the demand calls and extension times. This process is established in the “net_action” control function of the Programmer. In order to check demand calls, the “loop_gap” callback function with “APILOOP_INCOMPLETE” option is used in every time step. Depending on the demand call status, the API finds proper path of phase sequence and allocates appropriate interval to the phases on the path using “signal_action” and “signal _inquiry” callback functions.
The API developed for this study can implement fully actuated signal logic. A significant part of the fully actuated signal logic is similar to that of the actuated-coordinated signal logic in the priorities file and data structure. However, fully actuated signal control is operated with slightly different control logic. The main difference of fully actuated signal from actuated-coordinated signal is that the fully actuated signal does not need to maintain the background cycle length. The fully actuated signal uses minimum recall on major approaches and no recall on minor approaches. In the fully actuated signal, the dummy phases used in the actuated-coordinated signals are not necessary. Instead, green and red intervals of every phase are operated in a “variable mode”. The green and red interval operated in the “variable mode” can be changed at any time.
T-intersection is a little simpler than 4-leg intersection. The API for T-intersections uses the same input files. However, the control logic inherits most parts of the coordinated actuated signals and fully actuated signals.
Building a network for microscopic simulation is not an easy task. The most efficient method of making realistic and acceptable network is to watch the simulation animations. Through visualization, one can identify the locations showing abnormal behavior of individual vehicles and could easily identify the reason for such abnormality.
A procedure of the proposed API for coordinated actuated signal control in PARMICS is presented in this chapter. A few technical challenges encountered during the API development are as follows: i) PARAMICS uses its own fixed phase sequence such that it does not implement NEMA dual-ring type control and ii) yellow change interval was not recalled for the phase once a phase skip occurs. The proposed approach introduced a few dummy phases to model dual-ring type controller and combined yellow change interval and green times such that only effective green time is utilized. The experience during the development on the API for coordinated actuated signal indicated that the development of an API may not be suitable for practitioners due to complications and efforts required to do so.
As has been mentioned in Chapter 2, several methods including generalized least squares (GLS) model, QUEENSOD model, maximum likelihood estimation (MLE) and Kalman filtering have been used for dynamic O-D estimation.
This study introduces a GA and microscopic traffic simulation based model as a new approach for the dynamic O-D estimation. Even though GA-based models have already been used for O-D estimations (6, 7), those only applied for static O-D estimations on simple networks using a traditional assignment method. However, this study involves a large network and updates assignment matrix (or assignment parameter) using a traffic simulation model (PARAMICS) during the dynamic O-D estimation. The microscopic traffic simulation model finds the preferred routes and calculates the weights between zone pairs.
One of the practical OD estimation models is selected to produce a benchmark performance such that the performance of the proposed GA-based model is evaluated. QUEENSOD model is selected because it is considered to be the practical OD estimation tool available in the literature. In other words, the QUEENSOD method is simple and is well explained in the literature (12) so that it can be easily implemented in real transportation field. In addition, the QUEENSOD method has been used in a large-scale network consisting of 3,365 nodes, 7,926 links and 565 zones (37).
Both of the GA-based model and the QUEENSOD model find a dynamic O-D matrix which minimizes the discrepancies between estimated and observed link flows. The approach can be mathematically expressed as follow:
(16)
subject to
where,
= function of the general error
measurement between
and
,
= observed link flow in link a
during time interval t,
= estimated link flow in link a
during time interval t,
= estimated trips leaving zone i
to zone j during time
interval dt,
= proportion of trips leaving zone i
to zone j during
time interval dt and traveling through link a during
time
interval t,
i = origin,
j = destination,
a = link identifier,
dt = time interval for departure time, and
t = time interval.
The implementations of both GA and QUEENSOD models are presented in this chapter. Firstly, the use of assignment matrix is discussed and followed by the procedure of QUEENSOD method. The selection of GA parameters and settings for the Dynamic O-D estimation model is examined and the procedures are presented.
The QUEENSOD model and the proposed GA-based dynamic
O-D estimation model use link flows as criteria to match existing traffic
conditions. In other words, the models try to reduce the discrepancies between
estimates of link flows and observed field link flows. In order to obtain such
link volume discrepancies during O-D estimation, an assignment matrix (
, shown in Equation 16) is generally required. A dynamic and
multi-path assignment matrix is selected to calculate the estimates of link
flows. This reduces computational time compared to running a microscopic
simulation model. However, the assignment matrix is developed from microscopic
traffic simulation model. It is also noted that the microscopic simulation
program is used in the evaluation of the O-D matrices developed from both GA
and QUEENSOD models.
The assignment matrix includes the origin zone, destination zone, departure time (e.g., 15-minute interval), and time-varying link usage probabilities such that the assignment matrix determines preferred paths between zone pairs and usage probabilities of links on the paths. The assignment matrix is designed to consider the uses of multiple paths and temporal links. Table 3 provides an example of a dynamic and multi-path assignment matrix:
Table 3. Example of an Assignment Matrix
|
Origin |
Destin- ation |
Departure Time Interval* |
Link ID |
Link Usage Probability (by Time)** |
|||||||
|
5:00 ~ 5:15 |
5:15 ~ 5:30 |
5:30 ~ 5:45 |
5:45 ~ 6:00 |
6:00 ~ 6:15 |
6:15 ~ 6:30 |
6:30 ~ 6:45 |
6:45 ~ 7:00 |
||||
|
1 |
2 |
1 |
1914 |
0.75 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1915 |
0.75 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1918 |
0.75 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1923 |
0.75 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1921 |
0.67 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
2007 |
0.67 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
1 |
2 |
1 |
2025 |
0.58 |
0.25 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
2026 |
0.58 |
0.25 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1914 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1915 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1918 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1923 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
1921 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
2007 |
0.17 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
. . . |
|
|
|
|
|
|
|
1 |
2 |
1 |
3100 |
0.08 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
2 |
1 |
2032 |
0.08 |
0.08 |
0 |
0 |
0 |
0 |
0 |
0 |
* Departure time of 1 means 5:00 pm ~ 5:15 pm.
** All floating values are rounded from the third decimal point.
As can be seen in Table 3, vehicles traveling from zone 1 (origin) to zone 2 (destination) during time interval 1 (5:00 pm ~ 5:15 pm) use two paths:
1) Path 1: 1914à1915à1918à1923à1921à2007à …. à 2025 à 2026
2) Path 2: 1914à1915à1918à1923à1921à2007à …. à 3100 à 2032
It can be also seen from Table 3 that 83% of the vehicles use path 1 and 17% use path 2. These percentages represent the sums of link usage probabilities for each link in Path 1 (0.75 +0.08 or 0.67 + 0.17 or 0.58 + 0.25) and 2 (0.17 or 0.08 + 0.08). It can also be observed that among the 83% of the vehicles following path 1, 75% use link 1914 during the period 5:00 pm ~ 5:15 pm and 8% use the link during the period 5:15 pm ~ 5:30 pm. In addition 17% of vehicles following the path 2 also use link 1914 during the period 5:00 pm ~ 5:15 pm.
QUEENSOD, introduced by Van Aerde et al. (12), is a model for generating static and dynamic synthetic O-D matrices. The QUEENSOD model initiates the first iteration from a seed O-D matrix. The seed O-D can be either a uniform or historic O-D matrix. The seed O-D matrix is utilized to generate estimates of link flows based on the estimates of drivers’ expected route choices. The seed O-D matrix is adjusted on the basis of the quantitative comparisons between observed and estimated link flows. Through the multiple iterations of these processes, the seed O-D matrix is systematically modified to produce a new and better O-D matrix. The following procedure explains the process of QUEENSOD model:
1) Step 1: Determining dynamic drivers’ expected route choices (a dynamic and multi-paths assignment matrix)
2) Step 2: Determining an appropriate dynamic seed O-D matrix (uniform O-D matrix or historic O-D matrix)
3) Step 3: Conducting assignment using dynamic seed O-D matrix (assignment of dynamic seed O-D matrix to the network based on the assignment matrix)
4) Step 4: Estimating link error correction factors
(17)
where,
= correction factor for link a
and time interval t,
= actual link volume at link a
and time interval t,
= estimated link volume at link a
and time interval t,
= link identifier, and
= time interval.
5) Step 5: Estimating O-D error correction factors
(18)
where,
= correction factors summed between
origin i and
destination
j,
= probability that vehicles leaving i
to j during dt use
link a during time interval t,
= probabilities of link use summed for
all links used for
traveling
from i to j during time interval t,
= correction factors finalized for
between origin i and
destination
j at time interval t,
i = origin,
j = destination, and
dt = departure time interval.
6) Step 6: Estimating a new O-D matrix
(19)
where,
= dynamic O-D matrix at iteration n+1,
and
n = iteration identifier.
7) Step 7: Repeating above steps until convergence criterion is met
The traffic simulation network built in Chapter 3 (Figure 11) has seven external zones that connect the City of Hampton to other areas. Data of 15-minute interval flows are available for the links connected to the external zones. Thus, it is assumed that the 15-minute interval link flows at external zones represent the total of O-D demands generated from the external zones during each of 15-minute departure time interval.
![]()
![]()
![]()
![]()
![]()

![]()

Figure 11. Seven External Zones of Case Study Network
Thus, the estimates of dynamic O-D demands generated from external zones are fixed by matching to the counted field link volumes (15-minute interval) after estimating a new O-D matrix (step 6 in Section [4.3.1]) in every iteration.
The QUEENSOD model is evaluated according to the following procedure:
(Step #1): Finding better assignment matrix
(1) Determine uniform O-D matrix as a seed O-D matrix
(2) Make assignment matrix based on the uniform O-D using simulation
model
(3) Run QUEENSOD model
(4) Evaluate iterations using simulation model
(5) Find the best O-D pattern
(Step #2) Finding the best O-D matrix
(1) Making a new assignment matrix from the selected O-D in Step #1
(2) Run QUEENSOD model
(3) Evaluate iterations using simulation model
(4) Find the best O-D pattern
However, if any historical O-D matrix were available, the first step of QUEENSOD-based dynamic O-D estimation process could be skipped because the assignment matrix can be directly calculated from the historical O-D matrix. In addition, the historical O-D matrix can be used as a seed O-D matrix for QUEENSOD-based dynamic O-D estimation.
As explained in Chapter 2, the GA model has a capability of finding a good solution within a reasonable time and works reasonably well with a complicated large scale optimization. The proposed GA-based O-D estimation model works with a population that is consisted of a large number of randomly generated potential O-D matrices. Through the GA selection based on the extent of discrepancy between actual observed link flows and estimated link flows calculated from the product of the O-D matrix and assignment matrix, better O-D matrices are selected for crossover and mutation operations. According to schema theorem (add reference), the number of better O-D matrices (i.e., the O-D matrices with less discrepancies between observed link flows and estimated link flows) increases through generations.
The GA-based O-D estimation model is designed to overcome some problems identified in the QUEENSOD-based model, which will be explained in detail later in this chapter and Chapter 5. For example, the GA model generates O-D matrices for a given total O-D demand. Note that the QUEENSOD model could not constrain total O-D demand volume during OD estimation. This section describes the process of estimating an appropriate total O-D demand and an O-D matrix, and it also explains the procedure of developing the proposed GA-based model. The reason for using an assignment matrix instead of a simulation model in the estimation of link volumes during GA generations is explained at the beginning of this section. This section also provides the selection of solution representation, parameters and settings for the GA-based OD estimation model.
4.4.1.1 GA Selection Method
Selection of individuals (or parents) plays an extremely important role in GA. The selection of individuals in GA is based on the individual’s fitness such that better individuals have higher probability of being selected. An individual in the population can be selected more than once.
This study compared two selection methods, roulette wheel selection and normalized geometric ranking method (24), using a binary GA with a population size of 200, a maximum number of generation of 50, a simple crossover, and a simple mutation. The comparison between roulette wheel selection and normalized geometric ranking method showed that normalized geometric ranking selection performed better. Figure 12 shows the selection probabilities of randomly generated 200 solutions for dynamic O-D estimation using Equation (10) (roulette wheel selection) and Equation (11) (normalized geometric ranking selection). The x-axis gives the ranking of chromosomes from 1 to 200 (chromosome of rank 1 is better than chromosome of rank 2 and so on) and the y-axis the selection probability. It can be observed that the selection probabilities of the better chromosomes under ranking method are significantly higher than those of roulette wheel selection.
In the normalized geometric ranking method better solutions (i.e., those with smaller error measure values) are given higher rankings, while in the roulette wheel method better solutions are given higher probabilities according to the proportions. One of the shortcomings in the roulette wheel method is that the selection probabilities of individuals become not much distinguishable when fitness values of individuals are similar. However, the ranking method selects individuals based on the rankings such that it can always selects better solutions regardless of the characteristics fitness values as shown Figure 12. The elitist method is combined with the normalized geometric selection method in order to keep the best solution over generations.

Figure 12. Selection Probability Comparison of Two GA Selection Methods
4.4.1.2 GA Operators
This section examines two types of GA models (binary and real-valued GA). A total of nine combinations of operators: three cross over operator (arithmetic crossover, heuristic crossover, and simple crossover) and three mutations (multi non-uniform mutation, non-uniform mutation and uniform mutation) were tested for the real-valued GA. Among these, simple crossover and multi non-uniform mutation combination is selected as it provided better results than other combinations. However, the results of other combinations were very similar to the best combination. For the binary GA model, simple mutation with a probability of 0.05 and simple crossover with a probability of 0.5 are selected.
4.4.1.3 Number of Generation and Stop condition
The most frequently used stopping criterion of the GA model is to have a specific maximum number of generations (24). A maximum number of generation of 50 was selected as the improvement in the best solution was found to be insignificant after 50 generations. Two other stopping criteria were used in conjunction with the maximum number of generations: 1) lack of improvement in the fitness of the best solution over 10 generations, 2) no differences between the fitness of best solution and the average fitness of the entire solutions over 10 generations.
(20)
where,
Best_Fitnesst = fitness of the best solution at
generation
t,
Mean_Fitnesst = average fitness of entire solutions at
generation t, and
t = generation
number, t > 10.
In GA, each individual solution is systemically represented by a chromosome-like data structure. The representation scheme determines how the problem is structured in GA. Evaluation function in GA generates the fitness values of individuals in a population. Based on the fitness values, GA conducts a selection of “parents” for GA operations. Thus, GA representation scheme and evaluation function have to be well designed. A total of 12 combinations including three proposed solution representation schemes, two GA models (binary and real-valued GA) and two evaluation functions are tested in this section.
The selection of solution representation and GA model (binary or real-valued GA) is explained and followed by the selection of evaluation function.
4.4.2.1 Solution Representation Scheme
More efficient and natural solution representation schemes produce faster convergence and better solutions (25). Major focuses on the design of solution representation in this study are twofold: i) the utilization of the existing flow patterns for external zones and ii) natural representation of dynamic O-D matrix.
In order to utilize existing flow patterns, as mentioned in the QUEENSOD model (refer to Section [4.3.2]), the proposed solution representations use 15-minute interval link flows. The natural representation is related to the structure of genes (or parameters) in the solution. The proposed GA-based dynamic OD estimation method is designed to maintain the total O-D demand (i.e., fixed during optimization) as an exogenously given value such that the total O-D demand does not change over GA generations. This ensures GA convergence. It is noted that total O-D demand in the QUEENSOD model could not be constrained during iterations. Thus, the increase in the total O-D demand might result in unrealistic values after a large number of iterations. In order to maintain the total O-D demand, the proposed solution representations utilize proportional allocation approaches. The following three solution representation schemes are proposed:
1) Solution representation 1: proportional allocation approach without utilizing link flows connected to external zones,
2) Solution representation 2: proportional allocation approach utilizing 1-hour interval link flows connected to external zones, and
3) Solution representation 3: proportional allocation approach utilizing 15-minute interval link flows connected to external zones.
This solution representation simply uses the proportional allocation approach through three sequent stages (i.e., the parameters of one solution representation can be grouped into three sequential parts and the parameters in each group have different roles in the dynamic O-D estimation) to make an O-D matrix. The four parameters in the first group are used to divide a given total O-D demand into four O-D demand pairs that depart in each of four 15-minute time intervals. Based on the four O-D demand pairs, the parameters in the second group make sums of O-D demands that depart in 15-minute intervals from each zone. Finally, the parameters in the third group determine the values of the O-D demands that depart from every origin to every destination. One solution (or chromosome) consists of 10,004 parameters (or genes). The detailed decoding equation is expressed in Append