##### Document Text Contents

Page 1

DEGREE PROJECT, IN , SECOND LEVELCOMPUTER SCIENCE

STOCKHOLM, SWEDEN 2015

Multiple-objective optimization of

traffic lights using a genetic algorithm

and a microscopic traffic simulator

NICOLAS DAMAY

KTH ROYAL INSTITUTE OF TECHNOLOGY

SCHOOL OF COMPUTER SCIENCE AND COMMUNICATION (CSC)

i

Page 2

Nicolas Damay, [email protected]

Multiple-objective optimization of tra�c lights

using a genetic algorithm and a microscopic tra�c simulator

KTH Royal Institute of Technology,

School of Computer Science and Communication (CSC)

Supervisor: Orjan Ekeberg

Examiner: Anders Lansner

May 4, 2015

Page 53

• The description of the features of the cars: Width, length, acceleration/breaking

parameters, oil consumption etc..

• The drivers behavior: Reaction-time, impatience, infractions etc...

Considering all of those sources of modeling errors, this thesis investigates the

way the demand is modeled in SUMO in order to reduce the spread between the

simulated behavior and the real one.

3.1.1 Problem Definition

A common way of describing the demand is to use an ODM. Cascetta, Ennio and

Nguyen, Sang (1988) [43] Yang et al (1992) [44], Cascetta et al (1993) [45]. An ODM

is a matrix where each cell represents the number of vehicle going from a specific

origin to a given destination. See figure 3.1 for more detailed description.

(a) Origin - Destinations (b) Corresponding ODM

Figure 3.1: Origin Destination Matrix description.

In the ODM, figure 3.1b, the term γ(B,A) describes the number of cars willing to

go from A to B. The variable B and A being defined as in figure 3.1a

Creating this ODM is a challenging task in itself. With n origins/destinations

there are n2 unknowns. Collecting ODM information directly by conducting surveys

or interviews is a very long, uncertain, and costly process. Other methods are

model-based estimations, models are used to relate social, geographic and economics

features to the ODM. Yet, those models usually require advanced data. Furthermore,

those models need to be calibrated for the considered network.

Recently, a large number of studies have been devoted to indirect estimation of the

ODM parameters using traffic counts. Those studies have mostly been motivated by

the the relative ease of obtaining traffic counts compared with other more advanced

data.

46

Page 54

The notations used in this paper are described below:

The network is modeled by a directed graph G(C,L) where C is a set of nodes

and L is a set of links. L′ ⊆ L is the subset of monitored links. We are interested

in finding the ODM X = {xn} which describes the travel demand for each OD pair

n ∈ N , with N the number of OD pairs.

We use field traffic-counts observed on the real network Ỹ = {ỹl,t} where ỹl,t is

the number of car going through link l at time t. Finally we also use an evaluation

function Y that computes the simulated flow counts for a corresponding ODM:

Y : X −→ Y (X) = {yl,t}. Where yl,t is the number of car traveling on link l at time

t for the current estimation of the ODM X.

X =

x1

x2

...

xN

(a) Origin Destination Matrix

Ỹ =

ỹ1,1

...

ỹL′,1

...

ỹl,t

...

ỹ1,T

...

ỹL′,T

(b) Traffic Counts

The optimization problem can be stated as:

X∗ = argmin

X

Z(X) = argmin

X

F (Y (X)− Ỹ )

Where F measures the distance between the desired and observed flow counts Y

and Ỹ .

The ODM estimation problem is composed of two sub-problems:

• Traffic assignment. The purpose is to map OD flows described in X to link

counts Y (X).

• Computation of a new ODM X∗ using available traffic counts in the network,

Y (X) in order to reduce the distance between the simulated counts and the

real one.

47

Page 106

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

300

I

n

d

ic

a

to

r

Gradient method :Rand --> Light

(a) Initial ODM: Random ODM

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

I

n

d

ic

a

to

r

Gradient method :Uni --> Light

(b) Initial ODM: Uniform ODM

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

300

350

400

I

n

d

ic

a

to

r

Gradient method :M0 --> Light

(c) Initial ODM: Heuristic-based

ODM

0 2 4 6 8 10

Iteration

0

100

200

300

400

500

I

n

d

ic

a

to

r

Gradient method :Opt --> Light

(d) Initial ODM: Optimized ODM

Figure C.2: GSA - Simple case - three flows.

Evolution of the indicator as a function of the iteration of the GSA for a scenario

with a low demand for different initial ODM. The indicator is the mean over the streets

of the absolute error in the traffic counts. In this scenario the demand is set to 0 except

for three (randomly chosen) path.

99

Page 107

www.kth.se

100

DEGREE PROJECT, IN , SECOND LEVELCOMPUTER SCIENCE

STOCKHOLM, SWEDEN 2015

Multiple-objective optimization of

traffic lights using a genetic algorithm

and a microscopic traffic simulator

NICOLAS DAMAY

KTH ROYAL INSTITUTE OF TECHNOLOGY

SCHOOL OF COMPUTER SCIENCE AND COMMUNICATION (CSC)

i

Page 2

Nicolas Damay, [email protected]

Multiple-objective optimization of tra�c lights

using a genetic algorithm and a microscopic tra�c simulator

KTH Royal Institute of Technology,

School of Computer Science and Communication (CSC)

Supervisor: Orjan Ekeberg

Examiner: Anders Lansner

May 4, 2015

Page 53

• The description of the features of the cars: Width, length, acceleration/breaking

parameters, oil consumption etc..

• The drivers behavior: Reaction-time, impatience, infractions etc...

Considering all of those sources of modeling errors, this thesis investigates the

way the demand is modeled in SUMO in order to reduce the spread between the

simulated behavior and the real one.

3.1.1 Problem Definition

A common way of describing the demand is to use an ODM. Cascetta, Ennio and

Nguyen, Sang (1988) [43] Yang et al (1992) [44], Cascetta et al (1993) [45]. An ODM

is a matrix where each cell represents the number of vehicle going from a specific

origin to a given destination. See figure 3.1 for more detailed description.

(a) Origin - Destinations (b) Corresponding ODM

Figure 3.1: Origin Destination Matrix description.

In the ODM, figure 3.1b, the term γ(B,A) describes the number of cars willing to

go from A to B. The variable B and A being defined as in figure 3.1a

Creating this ODM is a challenging task in itself. With n origins/destinations

there are n2 unknowns. Collecting ODM information directly by conducting surveys

or interviews is a very long, uncertain, and costly process. Other methods are

model-based estimations, models are used to relate social, geographic and economics

features to the ODM. Yet, those models usually require advanced data. Furthermore,

those models need to be calibrated for the considered network.

Recently, a large number of studies have been devoted to indirect estimation of the

ODM parameters using traffic counts. Those studies have mostly been motivated by

the the relative ease of obtaining traffic counts compared with other more advanced

data.

46

Page 54

The notations used in this paper are described below:

The network is modeled by a directed graph G(C,L) where C is a set of nodes

and L is a set of links. L′ ⊆ L is the subset of monitored links. We are interested

in finding the ODM X = {xn} which describes the travel demand for each OD pair

n ∈ N , with N the number of OD pairs.

We use field traffic-counts observed on the real network Ỹ = {ỹl,t} where ỹl,t is

the number of car going through link l at time t. Finally we also use an evaluation

function Y that computes the simulated flow counts for a corresponding ODM:

Y : X −→ Y (X) = {yl,t}. Where yl,t is the number of car traveling on link l at time

t for the current estimation of the ODM X.

X =

x1

x2

...

xN

(a) Origin Destination Matrix

Ỹ =

ỹ1,1

...

ỹL′,1

...

ỹl,t

...

ỹ1,T

...

ỹL′,T

(b) Traffic Counts

The optimization problem can be stated as:

X∗ = argmin

X

Z(X) = argmin

X

F (Y (X)− Ỹ )

Where F measures the distance between the desired and observed flow counts Y

and Ỹ .

The ODM estimation problem is composed of two sub-problems:

• Traffic assignment. The purpose is to map OD flows described in X to link

counts Y (X).

• Computation of a new ODM X∗ using available traffic counts in the network,

Y (X) in order to reduce the distance between the simulated counts and the

real one.

47

Page 106

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

300

I

n

d

ic

a

to

r

Gradient method :Rand --> Light

(a) Initial ODM: Random ODM

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

I

n

d

ic

a

to

r

Gradient method :Uni --> Light

(b) Initial ODM: Uniform ODM

0 2 4 6 8 10

Iteration

0

50

100

150

200

250

300

350

400

I

n

d

ic

a

to

r

Gradient method :M0 --> Light

(c) Initial ODM: Heuristic-based

ODM

0 2 4 6 8 10

Iteration

0

100

200

300

400

500

I

n

d

ic

a

to

r

Gradient method :Opt --> Light

(d) Initial ODM: Optimized ODM

Figure C.2: GSA - Simple case - three flows.

Evolution of the indicator as a function of the iteration of the GSA for a scenario

with a low demand for different initial ODM. The indicator is the mean over the streets

of the absolute error in the traffic counts. In this scenario the demand is set to 0 except

for three (randomly chosen) path.

99

Page 107

www.kth.se

100