USING EVOLUTIONARY COMPUTING FOR RAMP METERING DESIGN IN
AN INTEGRATED FREEWAYURBAN ROADS NETWORK
by
Poon Thiengburanathum
B.Eng., ChiangMai University, 1995
M.S., University of Colorado at Boulder, 1999
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Civil Engineering
2003
This thesis for the Masters of Science
degree by
Poon Thiengburanathum
has been approved
by
Sarosh Khan
Date
Poon Thiengburanathum (M.S., Civil Engineering)
Using Evolutionary Computing for Ramp Metering Design in An Integrated
FreewayUrban Roads Network
Thesis directed by Professor Sarosh Khan
ABSTRACT
Using evolutionary computing with microscopic simulation is an alternative method
to design a traffic signal operation system that has capability to consider a complete
picture an integrated system (i.e. freeway and urban road network). This study
employs this approach for a rampmetering signalizationdesign problem of a section
in highway 125, Denver, Colorado. The evolutionary computing with microscopic
simulation provides ability to analyze a problem in a broad scale.
Designers/engineers can easily monitor a system from several perspectives, such as
overall, freeway, and local network systems. As the results, not only does this study
give better design solutions than the existed condition, but also insight
understandings and conjectures, such as the relationship between system capacity and
efficiency of ramp metering policies which lead engineers/designers into another step
of ramp metering design.
This abstract accurately represents the content of the candidates thesis. I recommend
its publication
Signed
m
Sarosh Khan
DEDICATION
I dedicate this thesis to my family and all of my friends for their unfaltering
understanding and support while I was writing this.
ACKNOWLEDGEMENT
My thanks to my advisor, Sarosh Khan, my advisor, for her patience and support
with me during these past two years. I also wish to thanks Professor Bruce Janson,
and Professor James Diekmann for their support and understanding.
TABLE OF CONTENTS
Figures......................................................................ix
Tables.......................................................................xi
Chapter
1. Introduction...............................................................1
1.1 Background................................................................1
1.2 Requirements of an Integrated Approach...................................2
1.3 Review of Literature on the Integrated FreewayUrban Approach...........2
1.3.1 OptimalControl Approach................................................3
1.3.2 Intelligent Search Approach.............................................4
1.4 Methodology............................................................ 4
1.5 Objective, Focus Area, and Hypothesis....................................5
2. Background.................................................................6
2.1 Integration of Traffic Control and System................................6
2.1.1 System Viewpoint of System Integration..................................7
2.1.2 Proper Level of Integration.............................................8
2.1.3 Traffic System Characteristics of Semiintegration Model...............10
2.2 Traditional Practices of Traffic Control.................................11
2.2.1 Road Traffic Control...................................................13
2.2.2 Freeway Traffic Control................................................14
2.3 Available Optimization Techniques for Simulation........................15
2.3.1 Generic Algorithm......................................................16
vi
2.3.2 Tabu Search..........................................................17
2.3.3 Simulation Annealing.................................................18
2.3.4 Scatter Search.......................................................20
2.3.5 Comparison among MetaHeuristic Methods..............................21
2.4 Evolutionary Computing Techniques in Traffic Control System Design....23
3. Problem Conditions and Methodology......................................25
3.1 Network Description....................................................25
3.2 Objective Functions...................................................26
3.3. Design Variables/Constraints..........................................27
3.4 Mathematical Formulation..............................................28
3.4.1 General Model........................................................28
3.4.2 A Specific Model for 125, Belleview, and Orchard Network............31
3.5 Feasible Solutions Approximation......................................33
3.6 Methodology...........................................................33
3.6.1 Basic Methodology Scheme.............................................33
3.6.2 Overall Process......................................................34
4. Tools and Techniques....................................................37
4.1 Optimization Platform..................................................37
4.2 MultiRun Platform....................................................39
5. Results and Analysis....................................................41
5.1 Case 1, 2, and 3: Minimize Average Delay for Overall Network...........44
5.2 Case 4: Minimize Average Delay for Freeway Section....................45
5.3 Case 5: Minimize Average Delay for Freeway Section without Queue Length
Constraints............................................................46
vii
5.4 Case 6: Minimize Product of Freeway Average Delay and Summation of On
Ramp Queue Length..................................................47
5.5 Case 7: Minimize Overall Delay Mean (Green Time = 2 Seconds).......48
5.6 Case 8: Minimize Freeway Delay Mean (Green Time = 2 Seconds).......49
5.7 Case 9: Minimize Product of Freeway Average Delay and Summation of On
Ramp Queue Length (Green Time = 2 Seconds).........................50
5.8 Case 10: Minimize Overall Delay Mean (Green Time =1,1.5, or 2 Seconds).... 51
5.9 Case 11: Minimize Freeway Delay Mean (Green Time = 1,1.5, or 2 Seconds).. 52
5.10 Case 12: Minimize Product of Freeway Average Delay and Summation of On
Ramp Queue Length (Green Time = 1, 1.5, or 2 Seconds)..............53
5.11 Design Results....................................................54
5.12 Urban RoadFreeway TradeOff Relationship.........................60
6 Summary and Future Works.............................................65
viii
FIGURES
Figure
21 Completed independent (left), semiintegration (middle), and
total integration (right).....................................................7
22 System view of freewayurban roads system......................................11
23 Different traffic control strategies with levels of integration and automation.12
24 Flowchart of a simple generic algorithm (after Pham and Karaboga, 2000)........17
25 Flowchart of a standard Tabu Search algorithm
(after Pham and Karaboga, 2000)...........................................18
26 Flowchart of a standard simulated annealing algorithm (after Pham and
Karaboga, 2000)...........................................................19
27 Flowchart of a basic scatter search procedure (after Laguna, 1997).........21
2 8 Different branches of traffic engineering tools/applications.............24
3 1 Conceptual model of the integrated network...............................26
32 Network model links and intersections....................................30
33 Network model: approaches and individuals..................................30
34 Network model: links.......................................................31
35 A methodology scheme.......................................................34
3 6 A flowchart of the overall process.......................................35
4 1 A standard platform for simulation optimization........i.....................37
42 Simulation optimization platform of this study.............................38
4 3 Multiruns platform......................................................40
5 1 Comparison between the traditional and this studys feasible
design solution areas.....................................................41
IX
52 An example of Opquests search progression during optimization process.....45
53 Selection of a candidate list process.......................................55
54 Percentage improvement of each case from the base case
(without ramp metering) (all cases)...........,............................57
55 Improvement of overall delay (case 2,10, and 11) of 30 runs data
(bold line = mean value, dots = 5th / 95th percentile).....................58
56. In case #5, queue overflow of onramp #1 (approach #7) causes
fatal grid lock in the system..............................................59
57. Relationships of average delay between freeway and urban road sections
(all cases)......................'.a.......................................61
58 Tradeoff relationships of average delay between freeway and urban road
sections with a fitted polynomial equation.................................61
59. Relationships between average ramp metering flowrate and
average delay of overall, freeway, and urban road system...................63
510. Linear relationships between average ramp metering flowrate and
average delay of overall, freeway, and urban road system (omitting case 5).63
x
TABLES
Table
21 Suggested integration levels for different traffic characteristics........9
22 Metaheuristic classification...............................................22
51 Characteristics of each case................................................42
52 Tenbest solutions of minimizing average delay for overall network
(cases 1, 2, and 3)........................................................44
53 Tenbest solutions of minimizing average delay for freeway section (case 4).46
54 Tenbest solutions of minimizing average delay for freeway section (case 5).47
55 Tenbest solutions of minimizing average delay average ramp queues for
freeway section (case 6)................................................. 48
56 Tenbest solutions of minimizing average overall delay (case 7).............49
57 Tenbest solutions of minimize freeway delay mean (case 8)..................50
58 Tenbest solutions of minimizing average delay average ramp queues for
freeway section (case 9)...................................................51
59 Tenbest solutions of minimizing average overall delay (case 10).........52
510 Tenbest solutions of minimizing average delay for freeway section
(case 11)..................................................................53
511 Tenbest solutions of minimizing average delay average ramp queues
for freeway section (case 12)..............................................54
512 Average delay time (seconds per vehicle) (30 runs) of different areas......55
513 Average and maximal queue length (30 runs) of onramp sections........... 56
514 A summary of improved design solutions.....................................60
515: Average ramp metering flow rate and average delay......................62
xi
61 Suggested ramp metering policy for different system condition
66
xii
1. Introduction
1.1 Background
Owing to the increase in road traffic volume, signal operation and design for
integrated networks are becoming more and more important. This is particularly true
for freeway and urban road networks. Traditionally, traffic signal designs and
operations focus mainly on isolated intersections and coordination within a corridor
(HCM, 2002). Concentrating on only some parts of the network may result in
suboptimal conditions in a system, especially when the system approaches its
capacity. An integrated approach can prevent suboptimal situation from occurring.
However, implementing this approach may require extensive computational
resources.
During the past decade, computer hardware function has become faster. Concurrently,
several important algorithms in the Evolutionary Computing (EC) domain has been
invented, for example, Genetic Algorithms, Tabu Search, Simulated Annealing, and
Scatter Search algorithms. These developments make the integrated approach
plausible.
This study is an attempt to implement evolutionary computation with microscopic
simulation for the design of an integrated freewayurban road network.
1
1.2 Requirements of an Integrated Approach
Modem metropolitan traffic networks, including both urban road and freeway
networks, employ a variety of control measures (e.g. signal control, ramp metering,
signs, and route guidance), which differ in type and location. Control strategies are
traditionally designed and implemented independently. This may result in suboptimal
conditions and lack of synergy among different control strategies (Papageorgious,
1999).
Papageorgious (1999) supports the aspect of the integrated approach that control
strategies should consider all control measures simultaneously towards a common
control objective. However, there are several ways of integrating networks:
independent, total integrated, and semiintegrated. These topics will be discussed in
the later sections.
1.3 Review of Literature on the Integrated
FreewayUrban Approach
There are many published works on the subject of integrated freewayurban networks,
including Capelle (1979), Van Aerde and Yagar (1988), Mahmassani and
Jayakrishnan, (1991), Reiss, et al. (1991), Kim and Bell (1992), Papageorgiou (1994),
Elloumi et al. (1996), and Papageorgiou (1999). The traffic integrated network
problem is still difficult (Papageorgious, 1999) in terms of its size and the number of
feasible solutions. There are two main approaches to this problem. The first is using
2
an optimalcontrol approach which has an optimal control solution. The second is
using search technique as the main key to find an optimal answer.
1.3.1 OptimalControl Approach
Papageorgiou (1995) presents an approach to the design of integrated control
strategies for traffic corridors of arbitrary topology, including both freeways and
signalcontrolled urban roads. His approach models the system as a linear optimal
control problem.
HajSalem and Papageorgiou (1995) use this concept for the design of an urban
corridor network in Paris. They compare the effects of with ramp metering control
and without ramp metering control policies. They report improvements in traffic
conditions not only on the freeway but also on the parallel arterials and throughout
the whole corridor network.
Diakakia, Papageorgiou, and McLean (1997) extend this idea to an integrated
network in Glasgow. Their study presents the effects of different scenarios (e.g. fixed
routing without control, fixed route with ramp metering, and user optimum dynamic
assignment with ramp metering and signal control modification, etc.).
Kotsialos et al. (2002) introduce an optimal control for a coordinated and integrated
control network. They model a traffic system in a format of a discretetime optimal
control problem whose numerical solution is achieved by use of a feasibledirection
algorithm. There are two main design variables in their study: independent splitting
rate and ramp metering rate.
3
1.3.2 Intelligent Search Approach
Stephanedes and Chang (1993) suggested an optimal rampmetering control method
to alleviate congestion in the interacting corridor components, including freeway,
parallel arterials, and connecting streets. They model a traffic system in a format of a
continuous trafficflow model, and use gradient method to search for optimal ramp
metering rates according to the total travel time in the corridor.
1.4 Methodology
This study uses simulation optimization as a main methodology for solving a traffic
signal design problem, particularly in ramp metering rate. It models a traffic system
by microscopic simulation, which can give a quality and flexible model.
Evolutionary computing technique is used as an optimization method.
In general, this approach can be more straightforward and easier than the methods
shown in the literature review. Furthermore, this method affords greater flexibility to
adjust their objective functions, design variables, and systems constraints. The
number of design variables and the size of the model are limited only by the
computers capacity and the available time frame.
4
1.5 Objective, Focus Area, and Hypothesis
As mentioned above, this study aims applies evolutionary computing to determining
the optimum signal timing and ramp metering by using an integrated traffic network,
125 network with Bellview Orchard interchanges and Bellview Orchard arterials,
south of Denver as a main case study.
This study examines the performance of the optimization by comparing the results of
the application of the evolutionary computing technique with two traditional
techniques (i.e. without metering and with reactive ramp metering algorithm that is
current employed at 125, Denver). In this case, a main measurement of efficiency
(MOE) is average delay time per vehicle. Besides, the major design variables are
ramp metering rates.
The first hypothesis of this study is that using evolutionary computing with
microscopic simulation can used to provide an improved solution of the 125 traffic
system in term of overall delay. Results from each case (e.g. without metering,
existing reactive ramp metering algorithm, and the new approach) are compared by
statistic methods (e.g. ttest). The second hypothesis is proved by showing a
relationship between freeways MOE and urban roads MOE. Nonetheless, this
model is based on an assumption that traffic assignment and users route choices are
fixed.
5
2. Background
This chapter presents fundamental concepts of traffic system integration, traditional
traffic control practices, available optimization methods for simulation, and available
simulationoptimization packages for traffic systems.
2.1 Integration of Traffic Control and System
Integration is a major issue for worldwide Advance Traffic Management Systems
(ATMS). Integration can be addressed in several aspects including:
Integrated modeling of traffic process,
Integrated design of control strategies,
Integrated of software components,
Integrated of communication and hardware facilities,
Intergraded of control centers, and
Administrative aspects of system integration (Diakaki and Papageorgiou,
1997).
With respect to control strategies design, Diakaki and Papageorgiou (1997) note
levels integration as the followings:
6
Level 0: completely independent design of control application
Level 1: independent design of control application taking into account
existence and requirements of other applications in the network
Level 2: decentralized design of control application applications based on
realtime mutual exchange of measurement of decisions.
Level 3: coordination of individual control applications by an independent,
hierarchically superior unit.
Level 4: fully integrated design of control application
2.1.1 System Viewpoint of System Integration
When looking a traffic network from system view, levels of integration consist of
three levels: completed independent, semiintegration, and total integration, as shown
in the following figure.
Fig. 21 Completed independent (left), semiintegration (middle), and total
integration (right)
7
The independent approach is the classical, and easiest, approach to traffic signal
design and operation. This approach focuses on optimizing systems elements, or
subsystems, separately. Some examples are isolated traffic signalize intersection,
isolated freeway ramp metering, coordinated traffic signal, and coordinated freeway
ramp metering. It can be fitted into Level 0, 1, 2 of Diakaki and Papageorgiou
(1997) scheme. From practical perspective, this approach works very well in
unsaturated conditions (i.e. having a lot of surplus capacity). However, when the
traffic system reaches or nears its capacity, considering traffic systems independently
is not adequate. Each element affects each other directly or indirectly.
The semiintegrated approach aims to optimize elements/subsystems independently.
It belong to Level 3. However, it concerns the way in which elements/subsystems
join together. The details for this type is shown in section 2.1.2.
The third method is an integrated approach, which is level 4. This approach considers
a system as a whole. However as mentioned above, this approach is not practical if
the system is very complex and large.
2.1.2 Proper Level of Integration
Although some advance methodologies have been suggested for Level 4 (total
integration), practical applications are faced with many barriers, such as technical,
and administrative delays (Papageorgiou, 1995; Diakaki and Papageorgiou, 1997).
8
This study suggests selecting a type of integration according to traffic characteristics
such as level of congestion (level of surplus capability) and existence of control
devices. The strategy of selection is shown in the following table.
The more traffic congestion in a system, the more demand for an integration
approach. However, it is not necessary to implement total integration, which is very
costly and impractical. Semiintegration can be a compromised way of design and
operation today traffic system.
Table 21 Suggested integration levels for different traffic characteristics
Type of Integration Level of congestion of a system Traffic Condition Cost of Implementation
Total independent Low Traffic congestion in some areas Low
Semiintegration Medium Traffic congestion in some area and each area affecting others LowMedium
Total integration High Traffic congestion throughout the system High
9
2.1.3 Traffic System Characteristics of Semiintegration
Model
A traffic network can consist of two types of subsystems: studied and unstudied areas.
The studied area is a focused zone that usually requires traffic design and operation.
This area usually has low to zero surplus capacity (i.e. congested condition). On the
other hand, the unstudied area is a traffic zone or links that has high surplus capacity.
The unstudied area is also called a bujfer. This area functions as a linage and traffic
flow regulator between two studied areas.
Figure 22 shows an example of a semiintegrated network a freewayurban road
system. They are connected to each other via on and offramp road sections, which
are buffer areas in this case. When the onramp link is equipped with ramp metering,
the link functions as a queue element. At this point, engineers have ability to design
strategies for controlling effects between two subsystems. For example, queue
overflow can reduce performance of downstream systems.
10
Onramp metering
section
unstudied area /
noncongested area
studied area
Offramp section
Fig. 22 System view of freewayurban roads system
In brief, this model is a way to see a traffic system in macro viewpoint (capacity
view). Not only does it offer an overall understanding of traffic systems, but also a
foundation for formulating a traffic model. The next section is a survey of traditional
traffic control methods.
2.2 Traditional Practices of Traffic Control
This study provides an overview of advance traffic control strategies in two areas:
urban road networks and freeways. Moreover, the traffic control strategies can be
grouped by level of integration and automation. In this case, levels of integration
consist of intersection, corridor/network, and semi /total integration. Levels of
automation include nonsignalize, pretime signalize, actuated signalize, and fully
online automated control from a traffic control center. This study introduces Figure
23 to illustrate different examples of each type of traffic control strategy. The top
11
right example indicates the most advantageous controlling technique. The bottomleft
shows the most fundamental traffic control (also the cheapest strategy).
Total integrated network/Semi integrating Integrated traffic control in an integrated network (freeway and urban road) Online automatic control for a integrated network
Corridor/ partial network n/a Coordinated traffic corridor/ Coordinated ramp metering in a freeway section Online automatic control for a urban road network/freeway
Insolated Intersection Stop sign/ Speed control Pretime signalized intersection/ Ramp metering Actuated signalized intersection/ Ramp metering n/a
Unslgnalize
Pretime
signalize
Actuated control
signalize/ local
detector
Real time/
Automatic control
Level of Automation
Fig. 23 Different traffic control strategies with levels of integration and automation
The facial point of this study is the topleft area, which is an integrated traffic control
strategy in an integrated network (freeway and urban road). The following sections
describe some control strategies, particularly in road network and freeway,
respectively. More details related to the following sections are shown in
Papageorgious (1999).
12
2.2.1 Road Traffic Control
Road traffic control consists of isolated intersection control, fixedtime coordinated
control, and coordinated trafficresponsive strategies. They are shown follows:
Insolated Intersection Control
o Fixedtime strategies
Stagebased strategies: SIGSET (Allsop, 1971; 1976), it
focuses on the optimal split and cycle time in undersaturated
traffic conditions
Phasebased strategies: SIGCAP (Webster, 1958) an
extension of the stagebased strategies by addition of optimal
phasing as a design variable.
o Trafficresponsive strategies
These strategies make use of realtime measurements provided
by loop detectors (located at the upstream traffic). Many
algorithms are developed for the responsive strategies such as
Millers strategy (Miller, 1963) and MOVA (Vincent and
Yong, 1986).
Corridor/Partial Traffic Network
o Fixedtime strategies
MAXBAND (Little, 1966; Little et al., 1981) attempts to
specify corresponding offsets to minimize stopping time.
TRANSYT (Robertson, 1969) is a popular application in a
design of road traffic control strategies. It uses the platoon
13
dispersion concept. This application is considered as a macro
traffic simulation model,
o Trafficresponsive strategies
SCOOT (Hunt et al., 1982) is a trafficresponsive version of
TRANSYT. It is fed with real time traffic measurement (on
line data).
Other advanced methods are OPAC (Gartner, 1983),
PRODYN (Farges et al., 1983), CRONOS (Boillot et al.,
1991), and COP (Sen and Head, 1997), which use pre
specified traffic phase for each optimization. However, they
are usually faced with exponentialcomplexity algorithm for
their global optimizations.
2.2.2 Freeway Traffic Control
Freeway traffic control consists of fixtime ramp metering strategies, reactive ramp
metering strategies, and nonlinear optimal ramp metering strategies
Local Ramp Metering
o FixTime Ramp Metering, (Wattleworth, 1965) is based on historic data
and aims to maximize throughput.
o Reactive Ramp Metering uses a concept of demandcapacity strategy,
ALINEA (Papageorgiou et al., 1991).
MultiRamp Metering
14
o Multivariable Regulator, METALINE (Diakaki and Papageorgious, 1994)
is an attempt to coordinate all control along a freeway, METALINE is an
extension of ALINEA.
o Nonlinear Optimal Strategies, This is a coordination of all control
variables and constraints along a freeway and nearby road network. Most
of them are based on reactive strategies rather than pretime. The
examples of constraints are queue length, queue capacity, freeway traffic,
ramp traffic, and nearby road traffic (Kotsialos et al., 2002).
2.3 Available Optimization Techniques for Simulation
Computer simulation is a powerful tool in evaluating complex systems. Traditional
simulation approach is oriented on what if questions. What if questions demand
answers on certain performance measures for a given set of values for the decision
variables of the system (Azadivar, 1999). However, practical questions are often of
how to, which seeks optimum values for the system, e.g. how to open the green
light for an intersection. Simulation optimization techniques which can make the
existed traffic simulation packages more useful.
However, simulation optimization still has many barriers, such as (Azadivar, 1999):
lacking of analytical expression of systems, objectives, and constraints.
the objective function or the constraints are usually stochastic functions
computer simulation program are expensive to run
no guarantee of the optimal solution
15
This section reviews mainly the singleobjective problem, particularly in the meta
heuristic method. There are several optimization techniques that can be applied to
simulation optimization problems such as gradientbased search, stochastic
approximation, response surface, simplepath optimization, and metaheuristic
methods (Evolutionary Computing) (Azadivar, 1999; Glover et al., 1999; Swisher et
al., 2000; Fu et al., 2000). Metaheuristic refers to a meter strategy that guides and
modifies other heuristics to produce solutions beyond those that are normally
generated in a quest for local optimality (Glover and Laguna, 1997). The meta
heuristic approach shows the most promise (efficiency and reliability) among these
methods, particularly in terms of contentindependent problem. The four main meta
heuristic methods are reviewed in the next sections.
2.3.1 Generic Algorithm
Generic Algorithm (GA) is a directed random search technique, introduced by
Holland (1975). It is inspired by the natural evolution process. Each problem will be
represented by chromosome (i.e. schema theorem) or string or binary number. Then,
it will be evolved according to generic algorithm process, which consists of
evaluation, selection, crossover, and mutation, as shown in the following figure
(Pham and Karaboga, 2000).
16
population
Fig. 24 Flowchart of a simple generic algorithm (after Pham and Karaboga, 2000).
Among these three algorithms, generic algorithm is the most popular, due to its
efficiency, reliability, and simplicity of implementation.
2.3.2 Tabu Search
Tabu Search algorithm was developed by Glover (1986). It is an iterative search that
is based on using adaptive memory and responsive exploration (Glover and Laguna,
1997). It also consists of several problemsolving techniques/strategies such as
forbidding strategy (systemic violation and restoration of feasibility), freeing strategy,
intermediate/longterm strategy, and shortterm (overall strategy) (Pham and
Karaboga, 2000). The overall strategy is shown in the following figure.
17
Yes
_L_
Final
solution
Fig. 25 Flowchart of a standard Tabu Search algorithm
(after Pham and Karaboga, 2000).
The ability to use adaptive memory and responsive exploration makes this method
very efficient and promising.
2.3.3 Simulation Annealing
Simulation annealing is adapted from statistical mechanics (Kirkpatrical et al., 1983).
It is based on the analogy between the annealing of a solid and the problem of
solving combinatorial optimization (Pham and Karaboga, 2000). There are four main
principles for this algorithm: Representation of solutions, Definition of the cost
18
function, Definition of the generation mechanism of the neighbors, and Designing a
cooling schedule. A basic flowchart of this algorithm is shown below.
Yes
Final
solution
Fig. 26 Flowchart of a standard simulated annealing algorithm
(after Pham and Karaboga, 2000).
19
2.3.4 Scatter Search
Scatter search is an evolutionary (populationbased) algorithm that constructs new
solutions by combining others (i.e. it can derive new solutions from combined
elements). Figure 36 shows a sketch of this algorithm. Scatter search contrasts with
other evolutionary procedures, such as genetic algorithms, by providing unifying
principles for joining solutions based on generalized path constructions in Euclidean
space and by utilizing strategic designs where other approaches resort to
randomization (Laguna, 1999).
Principles of scatter search methodology are summarized below.
Useful information about the form (or location) of optimal
solutions is typically contained in a suitably diverse collection of
elite solutions.
When solutions are combined as a strategy for exploiting such
information, it is important to provide mechanisms capable of
constructing combinations that extrapolate beyond the regions
spanned by the solutions considered. Similarly, it is also important
to incorporate heuristic processes to map combined solutions into
new solutions. The purpose of these combination mechanisms is to
incorporate both diversity and quality .
Taking account of multiple solutions simultaneously, as a
foundation for creating combinations, enhances the opportunity to
exploit information contained in the union of elite solutions
(Glover, Laguna, and Marti, 2002).
20
Yes
A
Final
solution
Fig. 27 Flowchart of a basic scatter search procedure (after Laguna, 1997)
2.3.5 Comparison among MetaHeuristic Methods
Glover and Laguna (1997) make a good comparison among the popular meta
heuristic methods (e.g. Generic Algorithm, Tabu Search, Simulated Annealing, and
Scatter Search) in the following table.
21
Table 22 Metaheuristic classification
Metaheuristic Popular conception/ original Future trend
Generic Algorithm M/S/P M/N/P
Tabu Search M/N/P A/N/P
Simulated Annealing M/S/l M/N/l
Scatter Search A/N/l A/N/P
Remark: Threedimensional classification, x/y/z
x = {A (adaptive memory), M (memoryless)}
y = {N (a method that employs some systematic neighborhood search either
to select the next move or to improve a given solution), S (a method those
relying on random sampling)}
z = {1 (if the method moves from one current solution to the next after every
iteration), P (populationbased)}
In term of efficiency, no method has dominated the others yet. Some methods can be
better than others for a particular problem. For example, Pham and Karaboga (2000)
use a traveling salesman problem as a benchmark, and report that Generic Algorithm
and Tabu Search are better than Simulated Annealing. However if we are concerned
about implementation effort per algorithms efficiency, Generic Algorithm is the best
for inhouse algorithm because it is generally effective and easy to use.
However, if users are looking for an outsourced algorithm, several commercial
optimization packages are available. Pro is very effective, mostly employing hybrid
methods. Con is a contentindependent type, of algorithm, but cannot be customized
to the problem content, which is normally slower than the independent type (Laguna,
22
1997). An example of the commercial optimization package is Opquest, which use
a combination of Scatter Search, Tabu Search, and Neural Network (Glover et al.,
1999).
2.4 Evolutionary Computing Techniques in Traffic
Control System Design
Although evolutionary computing techniques are widespread in many of engineering
areas, implementing them in traffic control is not yet popular. In 1991, CRONOS
employs a heuristic global method with polynomial complexity (Papageorgious,
1999). In 1992, Foy et al. used the genetic algorithm method in signal timing. Later
on in 1993, Hadi and Wallace use this approach to extend the ability of TRANSYT
to be able to design signal phase. In 2001, Lo et al. combined the ability of this
algorithm with a traffic network formulation, called Dynamic Intersection Signal
Control Optimization (DISCO) model. This effort achieved better results than
traditional TRANSYT approach.
However, both TRANSYT and DISCO still have limitations, particularly when
applied in an integrated level (e.g. freeway and urban road network). TRANSYT and
DISCO are designed specially for urban road network. However, they still lack
flexibility. Furthermore, both are deterministic models, which cannot represent the
stochastic behaviors of traffic.
Similar to TRANSYT and DISCO, this study employ an evolutionary computing
technique with a traffic simulation application. But this study specifies on a general
23
microscopic simulation (e.g. CORSIM and VISSIM). In another sense, it is an open
platform of a microscopic traffic simulation integration model. This bring us more
effective method of integration, stochastic representation, and optimization than the
traditional way.
Traffic Signal
Design w/
microscopic
simulation
Microscopic
simulation
Fig. 28 Different branches of traffic engineering tools/applications
24
3. Problem Conditions and Methodology
The potential of using evolutionary computing techniques and microscopic traffic
simulation model with traffic system design is here demonstrated with an actual case
study, the 125 network with Belleview and Orchard interchanges and Belleview
and Orchard arterials, South of Denver, Colorado. (see Details in Malm 2003). This
description of the network is shown in the next section.
3.1 Network Description
This network is an integration network, which consists of the 125 freeway
(represented in bold lines in Figure 31) and an urban road network Belleview and
Orchard interchanges and Belleview and Orchard arterials (represented by dot lines).
25
Fig. 31 Conceptual model of the integrated network
Both networks are linked together by freeway onramps and offramps. For the
current conditions, ramp metering devices are installed only at onramps numbers
one and three (see Figure 31).
3.2 Objective Functions
In general, the performance of the network is determined by the various satisfaction
of its users. These can be divided into quality of service measures (e.g. travel time,
delay time, travel cost, and their reliability) and other indirect measures (e.g. air and
26
noise quality, safety, and etc). These measurements of efficiency (MOEs) can be
interpreted on several levels individual, group of users, intersection, links, and
overall system.
The problem is simplified into a single objective optimization and is concerned only
with average delay time per vehicle, determined from data collected only on
freeways, main roads, onramps, and offramps. The accumulation of queues, which
is used as a system constraint, is detected on all onramp sections.
3.3. Design Variables/Constraints
There are several factors that affect the system traffic signals, traffic signs, system
geometries, transportation fees, etc. In general, the most responsive design variables
are traffic signals. They include:
Network traffic signal
o Cycle time
o Green time
o Off set time
o Phase plan
Ramp metering signal (periodic time strategy)
o Cycle time
o Green time
27
Only rampmetering rate, which consists of cycle time and green time, falls within
the scope of this study. Thus, the others are assumed as systems constraints. Queue
lengths are also considered as constraints. They have to be equal or less than 200
vehicles and 100 for east side ramps (i.e. onramp 1 and 3) and west side ramps (i.e.
onramps 2 and 4).
3.4 Mathematical Formulation
3.4.1 General Model
For a general model, most conditions can be formulated mathematically as the
following equations.
Minimize
m
n
Z = Y,WP, z = l]T,
(1)
m
z=iyp
(2)
Subject to
c
^min j
max
(3)
0^G; <1
(4)
max
(5)
28
L, < L,
(6)
When
/(CpGj.Pj.Oj)
(7)
i individual, i = 1,2,3 ... n
j approach, j = 1,2,3 ... m
k intersection, k = 1,2,3 ... o
l link, 1 = 1,2,3 ... p
r Number of ramps
Wj Priority weight of approach j
Lj Queue length of approach j, vehicles
Lmax,j Maximal queue length of approach j, vehicles
Dj Average delay time of approach j, minute
Ti Travel time of individual i
Cj Cycle time of approach j, minute
Cmin Minimal cycle time of this system, minute
Gj Splitting ratio of green time of approach j
Pj Phase plan of single timing of approach j
Oj Offset time of approach j, minute
Vj Approximate speed of approach j, mph
Sj Distance of approach j, miles
29
Intersection k
o ' T
G> 0
Fig. 32 Network model links and intersections
Fig. 33 Network model: approaches and individuals
30
3.4.2 A Specific Model for 125, Belleview,
and Orchard Network
The problem conditions are simplified into the following equations. Let assume that
there are 14 approaches (m = 14) for this network, as shown in Figure 32.
Control/design variables are reduced at only pretime ramp metering rate for
approach 7, 8, 9, and 10. This model is set to minimize average delay time for all
approaches and for freeway only.
Fig. 34 Network model: links
31
Minimize
Z =
lyp,
___
m
a
M
gj and rj are design variables
(8)
for j = 7, 8, 9, and 10
Subject to
D, = f(Cj,g,) (9)
3 II (10)
Cj=Sj+rj (11)
1 ^,.
1 < g < g (13)
1
Lj < 300 for y=7 and 8 (15)
Lj < 150 for7=9 and 10 (16)
Vj
When
gj Green time of approach j, sec
8min> gmax Minimal and maximum green time of approach
j respectively, sec
n Red time of approach j, sec
rmint f max Minimal and maximum red time of approach j
respectively, sec
Traffic volume of approach j, vehicles
32
3.5 Feasible Solutions Approximation
Feasible solution can be approximated as the following:
Let Cj,Gj ,and Ojt be integers, and the number of possible phase plans is p.
Then, the approximate number of the feasible solution is 1.44E6 (p(mr) + r).
Let Cj ,Gj, and Oj be integers; the number of possible phase plan is 1. So, the
approximate number of the feasible solution is 1.44E6 (m).
3.6 Methodology
3.6.1 Basic Methodology Scheme
The methodology of this study is microsimulation modeling with metaheuristic
search techniques (context independent). It uses VISSIM as a microsimulation
model and Optquest as an optimization engine because of their availability and
quality.
Figure 35 shows the basic methodological scheme of this study. VISSIM behaves as
a black box function for the optimization engine. The process will be repeated until a
criterion is satisfied. The criterion can be either the number of runs or total running
time. The optimization will also terminate if all feasible solutions are toured.
33
Initial Condition
(e.g. constants and
initial design
variables)
Objective Function
Constraints Functions
Fig. 35 A Methodology scheme.
3.6.2 Overall Process
This work has a validated simulation model as its main input, and produces a
suggested list of design solutions. Figure 36 shows a complete picture of the process.
First, objective function, constraint, and termination criteria have to be set up. Then,
the simulation optimization is run. This optimization can be set in either deterministic
or stochastic mode for this study, deterministic. The stochastic mode gives more
realistic optimal results, but is a very timeconsuming choice.
34
Yes
1
Final
Solution
Fig. 36 A flowchart of the overall process
The optimization process provides an ascending list of feasible solutions. Users have
to pick some of these solutions for a candidate list, in a compromise of practical and
effective standpoints. These candidates need to be evaluated again by microscopic
simulation generating multiple runs at different seed numbers. The minimal iteration
number in this study is approximately 30 runs. Ttest is used as a main statistical
35
method for testing the differences between candidates. If users are satisfied with the
solutions results, the process is at an end. Otherwise, the process can go either to the
Set up step (objective function, constraint, and termination criterion) or the Selecting
candidate step again.
36
4. Tools and Techniques
This study involves of two main sets of tools: Optimization and MultiRun packages.
An optimization package is a tool for answering howto questions. On the other
hand, MultiRuns package is designed for answering whatif questions. They are
explained in the following sections.
4.1 Optimization Platform
A classic platform for simulating optimization is shown in Figure 41. There are only
two modules: simulation and optimization engine. Visual Basic Application (VBA)
on Excel worksheet platform is selected as a main methodology for this system.
Microscopic Simulation Module,
Optimization Engine
' Â£
Fig. 41A standard platform for simulation optimization
This optimal application consists of four main modules: Core Interface (Excel with
Crystal), Microscopic Simulation, Shell Running, and Qpquest Optimization
Engine modules. These modules are connected to each others, as shown in Figure 42.
The detail of each module is shown bellows:
37
Fig. 42 Simulation optimization platform of this study
Main Interface Module: this module is based on Excel/Crystal Ball
application. Excel is a popular worksheet application that supports Visual
Basic Application (VBA). Crystal Ball is an addon application of Excel
from Decisioneering, Inc. This addon allows a nice interface between Excel
and Qpquest. It also includes the stochastic feature in the Excel worksheet.
Combination of Excel and Crystal Ball gives us enough flexibility to
develop this core interface.
Opquest Optimization Module: It is a contextindependent commercial
optimization engine from Optek company (Laguna, 1997). It is a reliable
and effective optimization engines in the market, particularly for simulating
optimization problems. As mentioned above, it uses a hybrid optimization
method, based on Scatter Search, Tabu Search, and Neural Network
Accelerator.
Shell Running Module: this is an inhouse application, which is used to
control the running of external applications, such as simulation application.
Microscopic Simulation Module: this study uses VIS SIM as its simulation
module. It is a sophisticate traffic system modeling tool that allows the
38
integrated simulation of freeway and urban road network in stochastic manner.
VISSIM can be control by other application via commandline. Thus, it is a
suisimulation package for this study.
This application works by controlling from an Excel worksheet module. It activates
the Shell Running module simultaneously with writing values of design variables to
VISSIMs input file (i.e. *.inp). The Shell Running module controls simulation
process and reports back to the core interface module when the simulation is finished
for each run. VISSIM also report results in file format (e.g. *.vlr). The results are
selected and read back to the main interface at the Excel worksheet. Next, the
optimization engine retrieves the selected simulation results and suggests the new
design variables to the model for the next run. These processes will be terminated if a
criteria is satisfied (e.g. number of runs, run time, etc.).
4.2 MultiRun Platform
This package consists of three modules: Core Interface (Excel with Crystal),
Microscopic Simulation, and MultiRuns Modules. The interrelationships among
these modules are shown in the following figure.
39
Microscopic x,
. Simulation '
Module
Fig. 43 Multiruns platform
It uses similar modules as the optimization platform except the core interface module,
which is concurred for multi runs mode. This platform provides results for all runs on
an Excel worksheet. This can be concurred for the different seed numbers of each
run.
40
5. Results and Analysis
This study compares the new designed cases with two main references. The first
reference is without a rampmetering case. The second reference is a present
condition case that uses reactive ramp metering at ramps 1 and 3 (approaches 7 and
9).
The new cases, which consist of twelve cases, come from the optimization process.
This process is finding the best possible pretime ramp metering. It is not only
search in the traditional feasible solution areas (e.g. green time is 2 seconds and cycle
time is 7 to 10 seconds), but also investigate the opportunity beyond the traditional
area, such as higher green time and cycle time (see Figure 51).
CD
Unrestricted
J_____
Restricted
T
Total
feasible
area
Fig. 51 Comparison between the traditional and this studys feasible design solution
areas
41
There are twelve cases in this study. They can be classified into two presuppose
conditions: 1) restricted throughput per cycle time (one vehicle per cycle time per
lane) and 2) unrestricted throughput per cycle time (more than one vehicle per cycle
time per lane). The first condition is shown in case 1 to 6. It is typical ramp metering
strategy, which has an aim to regulate the flow of onramp traffic (receiving the
fluctuating traffics from urban road networks and releases if at a uniform rate). The
second condition is illustrated in case 6 to 12. This condition is a compromise
situation between the typical rampmetering policy and the nonmetering case. It is
not necessary to release the ramp traffic at a uniform rate.
Improvement of this system can be determined by three objectives: 1) minimize
delay of entire network, 2) minimize delay only 125 freeway, and 3) minimize the
product of freeway delay and summation of average onramp queue. 51 shows
characteristics of each case (both reference and new case)
Table 51 Characteristics of each case
Case Number/Name Metering Policy Condition Objective Constraints
w/o metering No metering n/a n/a
Present condition Reactive n/a n/a
1,2,3 0/1 Pretime/ Unrestricted Overall delay Queue length* rmax and gmax = 70 sec. Cmax 120 sec.
4 F/l Pretime/ Unrestricted Freeway delay Queue length* rmwc and gmax = 70 sec. Cmax= 120 sec.
42
Table 51 Characteristics of each case (Cont.)
Case Number/Name Metering Policy Condition Objective Constraints
5 F/N Pretime/ Unrestricted Freeway delay rmax = 35 sec. gmax 70 sec.
6 P/l Pretime/ Unrestricted Product of Freeway delay and onramp queue * T"max = 35 See. * gmax ~ 70 SeC.
7 0/2 Pretime/ Restricted Overall delay Queue length* gi = 2 sec rmax 35 sec.
8 F/2 Pretime/ Restricted Freeway delay Queue length* gi = 2 sec fmax = 35 sec.
9 P/2 Pretime/ Restricted Product of freeway delay and onramp queue gi = 2 sec * fmax = 35 sec.
10 0/3 Pretime/ Restricted Overall delay Queue length* rmax = 40 sec. Green time = 1, 1.5, or 2 sec
11 F/3 Pretime/ Restricted Freeway delay Queue length* rmax ~ 40 sec. Green time =1, 1.5, or 2 sec
12 P/3 Pretime/ Restricted Product of freeway delay and onramp queue Queue length* rmax = 20 sec. Green time = 1, 1.5, or 2 sec
Remark: see equation 15 and 16
Each optimization case spends approximately 10 hours for searching time (about 200
solutions). Each solution is a simulation in VISSIM, for 1100 seconds which uses
43
the last 900 seconds (15 minutes) as a comparison period (using seed number 59).
The following sections show the optimal results of each new case.
5.1 Case 1,2, and 3: Minimize Average Delay
for Overall Network
In this case, the overall delay is minimized (see equation 8). The simulation
optimization suggests the optimal solution as shown in 52. Solutions 1, 2, and 6 are
selected as candidates numbers 1, 2 and 3, respectively. Figure 52 shows an example
of search progression of Opquest optimization engine.
Table 52 Tenbest solutions of minimizing average delay for overall network
(cases 1, 2, and 3)
Solution MOE Overall delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
HD 58.9 .24 70 V :719U;; :. .22 '' ; 1 10
2(2).. ;; 59*vS'v^ .4 r '10 >62^ Vl ' . 36, .* 1 V ' ;70
3 59.1 5 70 1 62 1 36 1 70
4 59.2 3 70 1 62 1 36 1 70
5 59.6 3 70 1 70 1 25 1 70
6 (3)' . 59.6 . .\13i*4 70' 1V 34f. 22 ^?704
7 59.9 6 70 1 61 1 36 i 70
8 60.4 18 70 1 64 1 39 i 70
9 61.7 27 39 3 27 1 19 i 50
10 62 10 56 2 50 1 27 i 66
Remark: (candidate number)
44
Fig. 52 An example of Opquests search progression during optimization process
5.2 Case 4: Minimize Average Delay for Freeway Section
In this case average delay is minimized for freeway section. It suggests an optimal
solution as shown in 53. The objective function (equation 8) is modified as the
equation 17. Solution 4 is designed as a candidate number 4.
m
M
for j = 1 and 2
(17)
45
Table 53 Tenbest solutions of minimizing average delay for freeway section (case 4)
MOE Pretime ramp metering rate (sec)
Solution Freeway delay Ramp 4 Ramp 3 Ramp 2 Ramp 1
(sec/veh.) Red Green Red Green Red Green Red Green
1 93.3 3 26 1 21 1 3 1 11
2 98.9 2 25 1 22 1 1 1 9
3 (4) . 99.5 : .1 1 V 1 TT"7 "1 T,t \bf. ;vT
4 99.5 4 28 1 23 1 4 1 11
5 100 3 26 1 21 1 3 1 10
6 101.6 11 57 1 15 1 26 1 36
7 101.7 1 2 1 2 1 1 1 1
8 102.1 3 4 1 4 1 2 1 1
9 102.7 3 24 1 18 1 3 1 10
10 103.4 7 70 1 61 1 7 1 31
Remark: (candidate number)
5.3 Case 5: Minimize Average Delay for
Freeway Section without Queue Length Constraints
This is similar to the above approach, but omits queue length constraints (equation 15
and 16). To prevent an extreme condition, the maximum red time is reduced from 70
seconds to 35, as shown in Equation 18. 54 shows the top ten optimal solutions.
Then, solution 1 is picked as candidate number 5.
1 < rj < 35
(18)
46
Table 54 Tenbest solutions of minimizing average delay for freeway section (case 5)
Solution MOE Freeway delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
K5) 40.5 35 . 1 35 35 ? 35 yi'..
2 46 1 1 35 1 35 l 35 l
3* 48.7 35 1 35 1 35 l 35 70
4 52.7 1 70 35 1 1 70 35 1
5 62 30 14 35 1 33 10 35 70
6* 68.6 14 52 35 1 27 35 35 70
7 69.5 1 70 35 1 1 70 35 70
8* 72.3 22 33 35 1 30 22 35 70
9 78.8 1 1 1 70 35 70 35 1
10* 85.9 35 70 1 70 1 1 35 1
Remark: (candidate number)
5.4 Case 6: Minimize Product of Freeway Average Delay
and Summation of OnRamp Queue Length
In this case, the objective function is an integrated aspect of average delay and
average queue lengths of all onramps. It is illustrated in equation 19. 55 shows the
top ten optimal solutions. Candidate number 6 is solution number 1.
2
;'=i
(19)
47
Table 55 Tenbest solutions of minimizing average delay average ramp queues for
freeway section (case 6)
Solution MOE Overall delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
1(6) 992 4 66 5 . 35 '. 10 27 2
2 997 2 66 3 35 4 23 2 68
3 1038 4 66 5 35 10 26 2 66
4* 1074.7 4 66 6 34 10 31 2 66
5 1121 2 67 4 35 3 25 2 68
6* 1264.8 4 66 5 35 9 27 2 66
7 1372 1 69 5 38 11 32 1 69
8* 1461.2 11 59 2 41 8 30 4 43
9 1584 2 67 3 36 4 25 1 69
10 1614 4 65 5 34 10 30 2 65
Remark: (candidate number)
5.5 Case 7: Minimize Overall Delay Mean
(Green Time = 2 Seconds)
This case is similar to case numbers 1, 2, and 3 (see equation 8) except it has a green
time constraint that equals to 2 seconds, as shown in the following equation. The
optimal results of this approach are shown in the following table. Solution number
one is selected as candidate number 7.
= 2
(20)
48
Table 56 Tenbest solutions of minimizing average overall delay (case 7)
Solution MOE Overall delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
7; 7igr7 7 59.2 12.6 "7 2: 6.4 ,72 77 19.6 )< Â£77 7'.27f;
2* 60.3 19.6 2 3 2 19.6 2 2.8 2
3* 60.9 12.6 2 5.6 2 19.6 2 2.2 2
4* 61.2 12.6 2 5.2 2 19.6 2 2.2 2
5 61.3 19.8 2 2 2 19.8 2 2 2
6* 61.6 19.6 2 3.6 2 19.6 2 3 2
7* 62.4 11.4 2 6.2 2 17.6 2 6.6 2
8* 62.6 19.6 2 3.6 2 19.6 2 2.6 2
9* 62.6 19.6 2 3.6 2 19.6 2 2.8 2
10 63 19.6 2 2.2 2 19.6 2 2 2
5.6 Case 8: Minimize Freeway Delay Mean
(Green Time = 2 Seconds)
In this case freeway delay is minimized (see equation 17) with a constraint that green
time is equal to 2 seconds (Equation 20). The optimal results of this approach are
shown in the following table. Solution number one is selected as candidate number 8.
49
Table 57 Tenbest solutions of minimize freeway delay mean (case 8)
Solution MOE Freeway delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
"i  7916 12.8 . '' 2 4 ';2(M !t4.2T f >;:T5';: ' T 2
2 82.9 18.4 2 17.4 2 8.4 2 18 2
3 87.4 12.6 2 11.4 2 5.2 2 12 2
4* 88.4 8.6 2 2 2 12.8 2 14.8 2
5 90.7 12.8 2 11.2 2 5.4 2 12.4 2
6* 90.9 11.6 2 19.6 2 16.6 2 2 2
7 91.8 13.2 2 10.8 2 5.6 2 12.8 2
8 93 19.6 2 18.6 2 2.8 2 18.4 2
9 93.5 4.8 2 2 2 19.8 2 17.4 2
10* 93.9 5.4 2 15.2 2 2.8 2 2 2
5.7 Case 9: Minimize Product of Freeway Average Delay
and Summation of OnRamp Queue Length
(Green Time = 2 Seconds)
This case is minimizing product of freeway average delay and summation of onramp
queue length (see Equation 19) with the constraint that green time equals to 2
seconds (Equation 20). The optimal results for this approach are shown in the
following table. Solution number one is selected as candidate number 9.
50
Table 58 Tenbest solutions of minimizing average delay average ramp queues for
freeway section (case 9)
MOE Pretime ramp metering rate (sec)
Solution Overall delay Ramp 4 Ramp 3 Ramp 2 Ramp 1
(sec/veh.) Red Green Red Green Red Green Red Green
1 1086 *2v \ 2 2 2 4.2 2 = "2 ,
2 1196.4 2 2 2 2 4.6 2 2 2
3* 1207.8 2 2 2 2 2.6 2 2 2
4* 1233.1 2 2 2 2 3.4 2 2 2
5* 1245.4 2 2 2 2 5.6 2 2 2
6 1299.6 2 2 2 2 2 2 2 2
7 1400 2 2 2 2 2.2 2 2 2
8* 1402.7 2 2 2 2 4.4 2 2 2
9 1668 2.8 2 2 2 5.2 2 2 2
10* 1705.1 2 2 2 2 2.8 2 2 2
5.8 Case 10: Minimize Overall Delay Mean
(Green Time = 1,1.5, or 2 Seconds)
This case is similar to case number 8 (minimize overall mean delay) but green time
can also be 1 and 1.5 seconds (as see in Equation 20). The optimal results of this
approach are shown in the following table. Solution number one is selected as a
candidate number 10.
gje {1.0,1.5,2.0} (20)
51
J
Table 59 Tenbest solutions of minimizing average overall delay (case 10)
Solution MOE Overall delay (sec/veh.) Pretime ramp metering rate (sec)
Ramp 4 Ramp 3 Ramp 2 Ramp 1
Red Green Red Green Red Green Red Green
1 58.4 'X5 * S 1 V' 1?V'4 rT ' 1.5 1.5 s
2* 59.1 1.5 i 1 4 1 1 1 1.5 1.5
3 59.2 1.5 i 2.5 1 1 1 1.5 1.5
4 60.8 1 i 1 1 1 1 1 1.5
5* 64.8 1 i 1.5 1 1 1 1 1.5
6* 64.9 2 i 2 1.5 40 1.5 40 1
7 66.6 1 i 1 1 1 1 1 1
8* 66.8 1 i 4 1 1 1 17.5 1
9 67 1 i 2 1 1 1 1 1.5
10* 67.1 1 i 3 1 1 1 8 1.5
5.9 Case 11: Minimize Freeway Delay Mean
(Green Time = 1,1.5, or 2 Seconds)
In this case, freeway mean delay is minimized (Equation 17) with a green time
constraint (Equation 20). The optimal results of this approach are shown in the
following table. Solution number one is selected as candidate number 11.
52
Table 510 Tenbest solutions of minimizing average delay for freeway section
________________________________(case 11)________________________________
MOE Pretime ramp metering rate (sec)
Solution Overall delay Ramp 4 Ramp 3 Ramp 2 Ramp 1
(sec/veh.) Red Green Red Green Red Green Red Green
I:. 68.2 _ 1 1.5 }. /.TV' Vf. ' 1.5 1.5
2 74.7 1.5 1 3 l i 1 1.5 1.5
3* 75.9 1.5 1 1.5 l i 1 1.5 1.5
4* 77.4 1 1 1 l i 1 24.5 2
5* 81.3 1 1 4 l i 1 34 1
6* 82.6 1.5 1 1 l i 1 1.5 1.5
7* 84.1 1 1 2 l i 1 1.5 1.5
8 85.5 1.5 1 4 l i 1 1.5 1
9* 86.8 1 1 .3 l i 1 12.5 1
10* 89.3 1 1 1 l 4 1 2.5 1
5.10 Case 12: Minimize Product of Freeway Average Delay
and Summation of OnRamp Queue Length
(Green Time = 1,1.5, or 2 Seconds)
In this case, product of freeway average delay and summation of onramp queue
length (Equation 19) is minimized with a green time constraint (Equation 20). The
optimal results for this approach are shown in the following table. Solution number
one is selected as candidate number 12.
53
Table 511 Tenbest solutions of minimizing average delay average ramp queues
________________________for freeway section (case 12)____________________
MOE Pretime ramp metering rate (sec)
Solution Overall delay Ramp 4 Ramp 3 Ramp 2 Ramp 1
(sec/veh.) Red Green Red Green Red Green Red Green
1 ' 954 : ";2 l. 1 / 1 1 f 1 1 , 2
2 1334.4 1 1 1 1 1 1 1 2
3* 1612.8 1 1 1 1 2 1 1 1.5
4* 1782.2 1 1 1 1 1 1 1 1.5
5* 1812.2 1 1 1 1 1 1 1 1
6* 2668.8 3 1 1 1 1 1 1 2
7* 3202.8 2 1 1 1 3 1 1 1.5
8* 3205.4 1.5 1 1 1 1 1 1 1.5
9 3800 1.5 1 1 1 1 1 1 2
10 3800 4 1 1 1 1 1 1 2
Each case shows the best possible solution that the search engine can find within the
limited time. This information helps engineers/modelers to select their design
solutions.
5.11 Design Results
Once the search engine finds a list of the best possible solution, engineers/modelers
can select the candidate solutions from that list rather than the whole feasible solution
area. When the candidate list is known, all candidates are rerun again for 30 iterations
to generate stochastic representation. After that, the best solution is selected by
statistic comparison method. Figure 53 shows the overall picture of this design
process.
54
Fig. 53 Selection of a candidate list process
512 shows average delay of overall system, urban road system, freeway, onramps ,
offramps, of these candidates. 513 shows average and maximum queue length of
onramps (ramps 1 to 4). Figure 52 shows improvement in percentage by comparing
the result of each case with the base case, without ramp metering condition.
Table 512 Average delay time (seconds per vehicle) (30 runs) of different areas
Cases Average Delay (sec/vehicle)
Overall Urban Freeway On Off
system road ramps ramps
w/o ramp metering 69.0 107.7 109.4 22.4 22.4
Present condition 71.3 136.2 109.9 27.3 25.2
Case 1 (0/1) 69.3 136.2 111.2 20.6 21.9
Case 2 (0/1) 67.3 135.4 108.7 20.6 20.2
Case 3 (0/1) 68.4 134.0 110.4 20.5 21.0
Case 4 (F/l) 68.3 133.7 109.5 21.5 21.2
Case 5 (F/N) 62.13 154.89 46.06 122.77 79.38
Case 6 (P/l) 67.0 134.9 106.2 21.4 21.0
Case 7 (0/2) 70.4 137.8 108.9 24.7 26.7
Case 8 (F/2) 75.6 147.4 86.3 92.1 37.1
Case 9 (P/2) 68.5 134.3 109.6 21.0 21.2
Case 10 (0/3) 64.1 144.5 85.7 25.8 26.9
Case 11 (F/3) 63.5 149.2 85.6 26.1 25.0
Case 12 (P/3) 68.5 134.3 109.6 21.0 21.2
55
Table 513 Average and maximal queue length (30 runs) of onramp sections
Cases Average queue length (vehicles) Maximum queue length (vehicles)
ramp 1 ramp2 ramp 3 ramp 4 ramp 1 ramp 2 ramp 3 ramp 4
w/o ramp metering 11 0 27 0 76 5 119 0
Present condition 21 0 35 0 100 6 128 0
Case 1 (0/1) 9 0 17 4 67 5 98 70
Case 2 (0/1) 9 0 23 0 66 5 107 6
Case 3 (0/1) 9 0 22 1 66 4 103 29
Case 4 (F/l) 7 0 19 0 69 13 104 3
Case 5 (F/N) 249 201 342 315 294 254 445 376
Case6 (P/l) 8 2 21 0 66 60 101 3
Case 7 (0/2) 6 13 37 8 62 99 117 82
Case 8 (F/2) 232 1 109 12 294 45 253 101
Case 9 (P/2) 7 6 14 0 65 36 90 28
Case 10 (0/3) 259 0 15 16 295 7 87 88
Case 11 (F/3) 258 0 31 0 294 5 118 3
Case 12 (P/3) 7 0 15 0 66 14 94 26
56
Fig. 54 Percentage improvement of each case from the base case (without ramp
metering) (all cases)
There are four main practical candidates that give improvement in the overall delay:
cases 2, 6, 10, and 11. Case number 2 and 6, which are unrestricted type (allow more
than one car per cycle time per lane), provides 2.5% and 2.9% improvement of
overall average delay from the base case (without ramp metering) at alpha level 0.1
and 0.5 (ttest at equal variance), respectively. Case number 10 and 11, which are
restricted type (allow only one car per cycle time per lane), give 7.1 and 8.0 percent
improvement at alpha level 0.05, respectively (see Figure 55).
57
85
80 
g 75 
70 
o
o
1c
>
W
u
c
o
o
0)
S 65
0
Q
1
g 60
o
55
50 H11111
w/o metering case 2 case 6 case 10 case 11
Fig. 55 Improvement of overall delay (case 2, 10, and 11) of 30 runs data (bold line
= mean value, dots = 5th / 95th percentile)
Although case 5 gives the lowest value of the overall delay, case 5 is not a practical.
Case number 5 shows an extreme condition of maximum freeway efficiency without
consideration other constraints or perspectives, such as decaying of urban road
systems performance. A result of total ignorance in urban street is occurring of fatal
grid lock in the system (see 513 and Figure 56).
58
Fig. 56. In case #5, queue overflow of onramp #1 (approach #7) causes fatal grid
lock in the system
In sum, pretime ramp metering provides improvement to the overall system, if the
average delay is the only main MOE, the best solution can be case 10 or 11. However,
if several MOE is considered such as average delay and ramp queue length, no
metering policy dominates the others. Although case number 10 and 11 shows show
significant improvement in overall and freeway performance, their queue lengths in
ramp 1 of these cases are very long (see 514). Case 8 has improvement only in
freeway but loses in overall. Since, it has long queue at both ramp 1 and 3. Case 2
and 6 has accepted queue length but it improves only 23 percent of overall delay.
Therefore, it is a challenging issue for engineers/modelers to decide a proper weight
of each MOE.
59
Table 514 A summary of improved design solutions
Cases Type Ramp 4 Ramp 3 Ramp 2 Ramp 1 Flow rate Over all delay Urban delay Free way delay Max Queue
R C R C R c R C
w/o ramp metering unrestricted n/a n/a n/a n/a n/a n/a n/a n/a 1 69 107.7 109.4 119
2 4 70 1 62 1 36 .1 . 70 0.97 67.3 135.4 108.7 107
6 4 66 35" 10: 27 2 66 0.88 67 134.9 106.2 101
10 restricted 1.5 iA'l 1 }h5 T.5 0.41 64.1 144.5 85.7 295
11 1 ' Ji, 1.5 1, l. 1 1.5. ;L5 0.48 63.5 149.2 85.6 294
5.12 Urban RoadFreeway TradeOff Relationship
The tradeoff relationship between urban road and freeway system is also observed
among these candidates, as shown in Figure 57 and 58. For metering cases, the
correlation of average freeway and urban street delay is 0.958. This tradeoff
relationship can be fitted by a polynomial equation as shown in Figure 58. For all
cases (with and without metering), the correlation value is 0.699.
60
Average delay, sec per vehicle
on freeway
+ w/o ramp metering case
Present condition case
ACase 1 (0/1)
Case 2 (0/1)
igCase 3 (0/1)
Case 4 (F/1)
Case 5 (F/N)
Case6 (P/1)
 Case 7 (0/2)
Case 8 (F/2)
SCase9(P/2)
ACase 10 (0/3)
gjCase 11 (F/3)
x, Case 12 (P/3)
Fig. 57. Relationships of average delay between freeway and urban road sections
(all cases)
Fig. 58 Tradeoff relationships of average delay between freeway and urban road
sections with a fitted polynomial equation
61
Another perspective that can use to analyze rampmetering policy is ramp flow rate
(r), which is green time divide by cycle time. 515 and Figure 59 show relationships
between flowrate and system delays which include overall, urban road, and free way
systems for every case. Figure 510 is similar to Figure 59 but omits case number 5
(i.e. an unpractical case), a relationship among these functions can be simplified into
linear equations.
Table 515: Average ramp metering flow rate and average delay
Cases Average flowrate of ramps Average Delay (sec/vehicle)
Overall system Urban road Freeway
Case 1 (0/1) 0.91 69.3 136.2 111.2
Case 2 (0/1) 0.97 67.3 135.4 108.7
Case 3 (0/1) 0.94 68.4 134.0 110.4
Case 4 (F/l) 0.50 68.3 133.7 109.5
Case 5 (F/N) 0.03 62.13 154.89 46.06
Case 6 (P/l) 0.88 67.0 134.9 106.2
Case 7 (0/2) 0.24 70.4 137.8 108.9
Case 8 (F/2) 0.18 75.6 147.4 86.3
Case 9 (P/2) 0.46 68.5 134.3 109.6
Case 10 (0/3) 0.41 64.1 144.5 85.7
Case 11 (F/3) 0.48 63.5 149.2 85.6
Case 12 (P/3) 0.50 68.5 134.3 109.6
w/o ramp metering case 1.00 69.0 107.7 109.4
62
Average flowrate of ramps metering, r
Overall system
Urban road
h Freeway
Linear (Overall system)
Log. (Urban road)
Log. (Freeway)
Fig. 59. Relationships between average ramp metering flowrate and average delay
of overall, freeway, and urban road system.
Average flowrate of ramps metering, r
Overall system
Urban road
. Freeway
Linear (Freeway)
Linear (Urban road)
Poly. (Overall system)
Fig. 510. Linear relationships between average ramp metering flowrate and
average delay of overall, freeway, and urban road system (omitting case 5)
63
This view also shows the tradeoff relationship. Increasing the flowrate makes the
freeway worse and urban roads better important deterioration in freeway (18.99%),
and significant improvement in urban road system (20.91%).
64
6. Summary and Future Works
In brief, the first hypothesis, using evolutionary computing with microscopic
simulation can used to provide an improved solution of the 125 traffic system in
term of overall delay, is accepted. This study gives better several solutions in term
of overall delay.
Using evolutionary computing with microscopic simulation can be an alternative
method to design a traffic signal operation system that has capability to consider a
complete picture an integrated system (i.e. freeway and urban road network).
However, it is too risky to use it as an automatic design tool. This method does not
guarantee of optimal solutions. Furthermore, if systems objective function and
constraints are not well defined, it is possible to have impractical solutions. Therefore,
it is necessary to use engineers experiences and traditional whatif analysis to
guarantee practicability and improvement.
However, fruitful future of this approach is expected because of positive trends in
computing power, efficiency of simulation model, and capability of search
algorithms. These allow engineers to increase the speed of search, size of feasible
solutions, and number of runs per solution (stochastic optimization simulation).
Thus, if a problem has practical size and reasonable complexity, the approach is
promising one for traffic engineering to design an integrated control for an integrated
network, particularly when computer technology is better and cheaper everyday.
65
Furthermore, from a macro perspective, ramp metering does not always guarantee the
overall improvement (Janson 1998) This study conjectures that if the system (both
freeway and urban roads) reaches its capacity, rampmetering cannot find significant
improvement in the overall delay. Furthermore, a tradeoff relationship between the
delay of freeway and urban roads is a basic phenomenal in this case. If the urban road
system does not reach its capacity but the freeway reaches, ramp metering can
improve in the overall delay. Moreover, if the free system does not reach its capacity,
noramp metering should be the best policy for the overall delay. 516 summarizes
this conjecture.
Table 61 Suggested ramp metering policy for different system condition
System Capacity Suggested Policy for overall performance
Freeway Urban roads
1 Reach/near Reach/near Balancing the tradeoff
2 below Reach/near Noramp metering
3 Reach/near below Using ramp metering
4 below below Noramp metering
66
REFERENCES
Allsop, R. B. (1971). SIGSET: A computer program for calculating traffic capacity
of signalcontrolled road junctions. Traffic Engineering & Control, Vol. 12, 58
60.
Allsop, R.B. (1976). SIGCAP: A computer program for calculating traffic capacity of
signalcontrolled road junctions. Traffic Engineering & Control, Vol. 17, 338
341.
Azadivar, F. (1999). Simulation optimization methodologies. Proceedings of the
1999 Winter Simulation Conference, 93100
Bolleli, A., Mauro, V. and Pemono, E. (1991). Models and strategies for dynamic
route guidance Part B: A decentralized, fully dyamic, infrastructure supported
route guidance. Proc. DRIVE Conference, Brussels, Belgium, 99105
Capelle, D.G. (1979). Freeway/corridor system. International Symposium on Traffic
Control Systems, Berkeley, California, Vol. 1, 3335.
Diakaki, C. and Papageogiou, M. (1995). Design and Simulation Test of Integrated
Corridor Control for M8 Eastbound Corridor in Glasgow, Internal Report No.
19953. Dynamic Systems and Simulation Laboratory, Technical University of
Crete, Chania, Greece.
Diakakia, C. Papageorgioua, M. and McLean, T. (1997). Simulation studies of
integrated corridor control in Glasgow. Transportation Research, Vol.SC, 211
224.
Elloumi, N., HajSalem, H. and Papageorgiou, M. (1996). Integrated control of
traffic corridors Application of LPmethodology. 4th Meeting of the EURO
Working Group on Transportation Systems, Newcastle, UK.
67
Farfes, J.L., Henrt, J.J. and Tufal, J. (1983). The PRODYNrealtime traffic
algorithm. 4th IF AC, Symposium on Transportation Systems, Baden Baden, W.
Germany, 307312.
Foy, M.D., Benekohal, R.F. and Goldberg, D.E. (1992). Signal timing determination
using genetic algorithms. Transportation Research Record, Vol.1365, 108115.
Fu, M.C., Andradottir, S.,Carson, J.S.,Glover, F.,Harrel, C.R.,Ho, Y.,Kelly, J.P. and
Robinson, S.M. (2000). Integrating optimization and simulation: research and
practice. Proceedings of the 2000 Winter Simulation Conference, 610616.
Gartner, N.H. (1983). OP AC: A demandresponsive strategy for traffic signal control.
Transportation Research Record, Vol.906, 7584.
Glover, F. (1986). Future path for integer programming and links to artificial
intelligence. Computers and Operation Research, Vol.13, 533549.
Glover, F. and Laguna, M. (1997). Tabu search. Boston: Kluwer Academic
Publishers.
Glover, F., Kelly, J.P. and Laguna, M. (1999). New advances for wedding
optimization and simulation. Proceedings of the 1999 Winter Simulation
Conference, 255260.
Glover, F.,Laguna, M. and Marti, R. (2002). Scatter search. In A Ghosh and S.
Tsutsui (Eds.), Theory and applications of evolutionary computation: recent
trends. SpringerVerlag (in Press).
Hadi, M.A. and Wallace, C.E. (1993). Hybrid genetic algorithm to optimize signal
phasing and timing. Transportation Research Record, Vol.421, 104112.
HajSalem, H. and Papageorgioua, M. (1995). Ramp metering impact on urban
corridor traffic: field results. Transportation Research, Vol.29A, 303319.
Hansen, P. (1986). The steepest ascent mildest descent heuristic for combinatorial
programming, Conference on Numerical Methods in Combinatorial
Optimization, Capri, Italy.
68
Holland, J. H. (1975). Adaptation in natural and artificial systems. Ann Arbor, MI:
University of Michigan Press.
Hunt, P. B., Robertson, D.K. and Bretheton, R. D. (1982). The SCOOT online
traffic signal optimisation technique. Traffic Engineering & Control, Vol. 23,
190192.
Janson, B.N. (1998). Modelling network travel time impacts of freeway ramp
metering. The 77th Annual Meeting of the Transportation Research Board,
Paper No. 980871.
Kim, K.J. and Bell, M.G.H. (1992). Development of integrated traffic control
strategy for both urban signalized and motorway networks. Processing 1st
Meeting of the EURO Working Group on Urban Traffic and Transportation,
Landshut, Germany.
Kirkpatrick, S. Gelatt, C.D. Jr. and Vecchi, M.P. (1983). Optimization by simulated
annealing. Science, Vol. 220, No.598, 671680.
Kotsialos, A., Papageorgiou, M., Mangeas, M. and HajSalem, H. (2002).
Coordinated and integrated control of motorway networks via nonlinear
optimal control. Transportation Research, Vol.30A, 221230.
Laguna, M. (1997). Optimization of complex systems with OptQuest
http://leeds.colorado.edu/faculty/laguna/publications.htm
Laguna, M. (1999). Scatter SEARCH. InP. M. Pardalos and M. G. C. Resende
(Eds.), Handbook of applied optimization, Oxford University Press, 183193.
Little, J.D.C. (1996). The synchronisation of traffic signals by mixedintegerlinear
programming. Operation Research, Vol.14, 568594.
Little, J.D.C., Kelson, M.D. and Gartner, N.H. (1981). MAXBAND: A program for
setting signals on arteries and triangular networks. Transportation Research
Record, Vol. 795, 268275.
Lo, H.K., Chang, E. and Chan, Y.C. (2001). Dynamic network traffic control.
Transportation Research, Vol.35A, 721744
69
Mahmassani, H. and Jayakrishnan, R. (1991). System performance and user response
under realtime information in a congested traffic corridor. Transportation
Research, Vol.25A, 293307.
Malm, J.F. (2003). Evaluation of rampmetering algorithms using traffic simulation
model, VISSIM. Masters report, University of Colorado at Denver.
Miller, A.J. (1963). A computer control system for traffic network. 2nd International
Symposium on Traffic Theory, London, UK, 200220
Papageogiou, M., Blosseville, J.M. and HadjSalem, H. (1990). Modeling and real
time control of traffic flow in the southern part of Boulevard Peripherique in
Paris Part II: Coordinated onramp metering. Transportation Research,
Vol.24A, 361370.
Papageogiou, M., HadjSalem, H. and Blosseville, J.M. (1991). ALINEA: A local
feedback control law for onramp metering. Transportation Research Record,
Vol.1320, 5864.
Papageorgiou, M. (1995). An integrated control approach for corridors.
Transportation Research, 3C, 1930.
Papageorgiou, M. (1999). Traffic control. In R. W. Hall (Ed.), Handbook of
transportation science. Boston: Kluwer Academic Publisher.
Park, P., Rouphail N.M., Hochannadel, J.P. and Sacks, J. (2001). Evaluating
reliability of TRANS YT7F optimization schemes. Journal of Transportation
Engineering, Vol. 127, No. 4, July/August 2001, 319326
Pham, D.T. and Karaboga, D. (2000). Intelligent optimisation techniques : genetic
algorithms, tabu search, simulated annealing and neural networks. London:
Springer.
Reiss, R. A., Gartner, N. H. and Cohen, S.L. (1991). Dynamic control and traffic
performance in a fieeway corridor: a simulation study. Transportation
Research, Vol. 25A, 276276.
70
Robertson, D. I. (1969). TRANSYT method for area traffic control. Traffic
Engineering & Control, Vol.10, 276281.
Sen, S. and Head, L. (1997). Controlled optimization of phases at an intersection.
Transportation Science, Vol.31, 517.
Stephanedes, Y. J. and Chang, K.K. (1993). Optimal control of freeway corridors.
Journal of Transportation Engineering, Vol. 119, No. 4, July/August 1993,
504514.
Swisher, J.R., Hyden, P.D., Jacobson, S.H. and Schruben, L.W. (2000). A survey of
simulation optimization techniques and procedure. Proceedings of the 2000
Winter Simulation Conference, 119128.
Transportation Research Board (2000). Highway capacity manual. Washington, D.C:
Transportation Research Board, National Research Council.
Van Aerde, M. and Yagar, S. (1998). Dynamic integrated freeway/traffic signal
networks: problem and proposed solutions. Transportation Research, Vol.22A,
435443.
Vincent, R. A. and Young, C.P. (1986). Selfoptimization traffic signal using
microprocessor: The TRRL MOVA strategy for isolated intersections. Traffic
Engineering & Control, Vol.27, 385387.
Wattleworth, J.A. (1965). Peakperiod analysis and control of a freeway system.
Highway Research Record, Vol. 157,121.
Webster, F.V. (1958). Traffic signal settings. Road research technical paper, No. 39.
London, UK: Road Research Laboratory.
71
