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.

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 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.

Table of Contents

Chapter Page

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

Chapter Page

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

Table of Figures

Figure Page

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

Table of Tables

Table Page

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

List of Acronyms and Abbreviations

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

Chapter 1
Introduction

1.1 Background

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.

1.2 Problem Statement

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.

1.3 Research Objectives and Methodology

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).

1.4 Scope of Study

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.

1.5 Organization of This Report

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.

Chapter 2

Literature Review

2.1 Introduction

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.

2.2 Dynamic O-D Matirx Estimation

2.2.1 Static O-D Estimation

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.

2.2.2 Dynamic O-D Estimation

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.

2.2.3 Estimation of Temporal Route Choice for Dynamic O-D Estimation

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.

2.3 Genetic Algorithm

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).

2.3.1 Introduction

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.

2.3.2 Mechanisms of Genetic Algorithm

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 2^r 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

2.3.3 Genetic Algorithms in O-D Estimation

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:

X_n[m][ij] = choice proportion of m^th chromosome between i and destination j in n

generation, where m=1, 2, …, M, M is the number of population, and

Y_n[m][ij] = proportion of m^th 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.

2.4 Traffic Simulation Model in ITS Evaluation

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.

2.5 Summary

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.

Chapter 3

a Development of Large Scale Case Study Simulation Network

3.1 Introduction

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

3.2 Microscopic Simulation Model Selection

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.

3.3 Microscopic Simulation Model, PARAMICS

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.

3.3.1 User Interface

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.

3.3.2 Network Structure

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.

3.3.3 Traffic Generation and Assignment

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.

3.3.4 Signal Control in PARAMICS

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.

3.3.5 API in PARAMICS

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).

3.3.6 Model Weaknesses

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.

3.4 PARAMICS Network

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.

3.4.1 Network Building

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

3.4.2 Signal Control Logics

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].

3.4.3 Parameter Setting

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.

3.4.4 Simulation

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.

3.4.5 Visualization

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”.

3.5 Development of an API for Coordinated Actuated Signals

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.

3.5.1 Geometry of Intersection and Detectors

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.

3.5.2 Yellow Change Interval

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.

3.5.3 New Phase Sequence for API

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).

3.5.4 Input Data Structure

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.

3.5.5 Control Logic

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.

3.5.6 Fully Actuated Signal Control and T-intersection

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.

3.6 Summary

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.

Chapter 4

Building Dynamic O-D Estimation Mmodels Using GA and QUEENSOD Model

4.1 Introduction

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.

4.2 Use of Assignment Matrix

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.

4.3 QUEENSOD Model

4.3.1 Mechanism of QUEENSOD Model

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

4.3.2 Using Existing Traffic Information

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.

4.3.3 QUEENSOD-based O-D Estimation Process

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.

4.4 GA-based O-D Estimation Model

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 Determination of GA Selection Method, GA Parameters and GA Operators

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_Fitness^t = fitness of the best solution at

generation t,

Mean_Fitness^t = average fitness of entire solutions at

generation t, and

t = generation number, t > 10.

4.4.2 Selection of Solution Representation, GA model and Evaluation Function

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.

Solution Representation 1

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