This is an implementation of the algorithm proposed in the paper: Road Traffic Optimisation Using an Evolutionary Game written by Syed Md. Galib and Irene Moser.
Programmed by Anderson Rocha Tavares
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Sun's Java site. Apparently, it does not work on Linux anymore. Anyway, you can copy the .nlogo code and run in NetLogo 4.1.3.
powered by NetLogo
view/download model file: MG_TA.nlogo
If you download the model file, get the file which describes the road network here.
This model is an implementation of the modified Minority Game algorithm for traffic assignment proposed in the paper: Road Traffic Optimisation Using an Evolutionary Game written by Syed Md. Galib and Irene Moser.
Agents predict occupancy on the roads they can use on their trip. They have a set of predictors for each link and "believe" the prediction made by the best scored predictor. Then they choose the next link of their trip as the one with the least predicted occupancy. This is repeated until they reach their destinations. Then travel times are calculated and the predictors' score are updated.
Click 'setup' to load the road network and place the drivers on their origins (uniformely distributed on the nodes 1, 2 and 3). Click 'go' to simulate one iteration. The 'go 50' button simulates 50 iterations, and the looped 'go' repeats iterations forever.
If one of the parameters is changed, the setup button must be pressed again to create the simulation environment with the updated values. Parameters are:
- num-drivers: the number of drivers on the network
- history-size: drivers store road occupation from 'history-size' iterations from the past
- alpha and beta: these are parameters of the travel time calculation formula:
fftt * (1 + alpha * (num-drv / capacity) ^ beta)
- learning-factor: it weights the score to be updated on the predictors (lower makes previous scores more important than the current)
The networks tends to self-organise. Drivers distribute themselves almost proportionally to the capacity of the roads. On average, actual travel times are lower than the expected.
It is interesting to see how the parameters affect the simulation.
It is possible to force drivers to have only one origin-destination pair by changing the code.
This implementation was built to the Advanced Artificial Intelligence course at UFRGS.
Author: Anderson Rocha Tavares
Advisor: Ana L. C. Bazzan
Paper: Road Traffic Optimisation Using an Evolutionary Game
Authors: Syed Md. Galib and Irene Moser
globals [
num-intersections
num-roads
ideal-segment-length
]
breed [ intersections intersection ]
breed [ drivers driver ]
directed-link-breed [ roads road ]
intersections-own [
x y
id
]
roads-own [
road-id ;identificador da via
capacity ;capacidade [130:250]
num-drv ;numero de motoristas
opt-num-drv ;numero proporcional de motoristas
avg-num-drv ;ocupacao real media
avg-opt-drv ;ocupacao proporcional media
fftt ;free-flow travel time
travel-time ;tempo de viagem
history ;historico de ocupacao
]
drivers-own [
current-route ;lista de road-id descrevendo a rota atual
route-weight ;peso da rota a ser calculado na chegada
actual-tt ;tempo de viagem real do motorista
optimal-route ;rota otima (menor #nos ate o destino)
expected-tt ;tempo de viagem esperado (considera os motoristas no mesmo par OD
roads-weight ;lista com o peso das rotas TODO: sera' necessario?
origin ;ID do no' de origem
destination ;ID do no' de destino
current-node ;ID do no' atual
current-road ;via atual (a via mesmo, nao o ID)
predictors ;lista com 'num-roads' conjuntos de 'num-predictors' preditores
predictors-score ;lista com 'num-roads' conjuntos de 'num-predictors' pontos p. preditores
best-predictors ;lista com o indice do melhor preditor por via (?)
]
to setup
clear-all
build-network
setup-drivers
ask intersections [ set label id ]
end
to go
reset-road-network
while [drivers-not-arrived] [
step
]
experience-travel-times
update-predictors-score
update-history
update-roads-visual
do-plots
tick
end
to step
distribute-drivers-proportionally
choose-next-road
advance
end
to setup-drivers
create-drivers num-drivers [
set origin 1 + random 3 ;origem em nos 1, 2 ou 3
set destination 8 + random 3 ;destino em 8, 9 ou 10
set current-node origin
set current-route []
set optimal-route calculate-opt-route origin destination
set predictors n-values num-roads [random-predictors]
set predictors-score n-values num-roads [initial-scores]
set best-predictors n-values num-roads [random num-predictors]
set roads-weight n-values num-roads [1]
let myorig origin
let mydest destination
move-to one-of intersections with [id = myorig]
face-nowrap one-of intersections with [id = mydest]
]
calculate-ett
end
to distribute-drivers-proportionally
ask intersections [
let drv-at-intersection count drivers-here with [current-node != destination];desconta os motoristas que ja chegaram
let total-capacity sum [capacity] of my-out-links
ask my-out-links [
let proportion capacity / total-capacity
set opt-num-drv opt-num-drv + (proportion * drv-at-intersection)
]
]
end
; atualiza o historico de ocupacao das vias, inserindo a ocupacao da rodada atual
to update-history
ask roads [
;show history
let occupation (num-drv / capacity) * 100
if occupation < 60 [set occupation 60]
if occupation > 140 [set occupation 140]
set history remove-item (length history - 1) history
set history fput occupation history
if length history = 1 [show (word "error " history)]
]
end
;calcula o tempo de viagem esperado para cada motorista
to calculate-ett
ask drivers [
let drv-same-od 0
let exp-drv 0
let ett 0
let myorig origin
let mydest destination
set drv-same-od count drivers with [origin = myorig and destination = mydest]
set exp-drv drv-same-od ; - 50 + random 101 ;adiciona ruido +-50
foreach optimal-route [
ask ? [set ett ett + fftt * (1 + exp-drv / capacity) ^ 2]
]
set expected-tt ett
]
end
; reinicia a rede de trafego: coloca os motoristas na origem, reseta as rotas
; reseta os tempos de viagem das vias e a ocupacao
to reset-road-network
reset-drivers
reset-roads
end
;reinicia o estado dos motoristas, posicionando-os na origem e resetando as rotas
to reset-drivers
ask drivers [
set current-node origin
set current-route []
;TODO atualizar os pesos das rotas
;set roads-weight n-values num-roads [1]
let myorig origin
let mydest destination
move-to one-of intersections with [id = myorig]
face-nowrap one-of intersections with [id = mydest]
]
end
;reinicia o estado das vias (num-motoristas; num-proporcional; tempo-de-viagem)
to reset-roads
ask roads [
set num-drv 0
set opt-num-drv 0
set travel-time 0
]
end
;faz cada motorista escolher a proxima via a ser usada
to choose-next-road
ask drivers[
if current-node = destination [stop] ;nao faz escolhas se ja tiver chegado
;configura variaveis para serem usadas dentro dos asks
let node-id current-node
let the-predictors predictors
let the-scores predictors-score
let the-roads-weight roads-weight
let myorig origin
let mydest destination
;inicializa melhor via e menor ocupacao encontrada
let best-road-id -1
let lowest-prediction 100000 ;inicializa menor ocupacao com valor grande
;a partir da intersecao atual...
ask intersections with [id = node-id] [
let will-reach-dest false
;...analisa todos os links de saida para achar o melhor
ask my-out-links [
; ifelse [id] of end2 = mydest
; [
; set best-road-id road-id
; set will-reach-dest true
; ]
;[
;se ja encontrou aresta que leva ao destino, nao procura mais
if will-reach-dest [stop]
if (not in-route myorig mydest) [stop]
let scores sublist the-scores (road-id - 1) road-id
let hiscore max (item 0 scores)
let best-pred-index position hiscore (item 0 scores)
let curr-predictors sublist the-predictors (road-id - 1) road-id ;OK - obtem os preditores desta via
;set best-pred-index 0
let best-predictor (item best-pred-index (item 0 curr-predictors))
let predicted-occ predict-occupation best-predictor history
let weighted-prev predicted-occ * item (road-id - 1) the-roads-weight
;COMPARAR COM MELHOR PREDICAO E AJUSTAR MELHOR VIA
if weighted-prev < lowest-prediction [
set lowest-prediction predicted-occ
set best-road-id road-id
]
;];ifelse
] ;ask my-out-links
] ;ask intersections
set current-road one-of roads with [road-id = best-road-id]
;face-nowrap [end1] of current-road
;fd 1
ask current-road [set num-drv num-drv + 1]
]
end
to-report in-route [orig dest]
let forbidden []
if dest = 8 [ set forbidden [18 20 21 22 23 24] ]
if dest = 9 [ set forbidden [21 23 24] ]
report not member? road-id forbidden
; int rid = r.getId();
; int[] forbidden = null;
;
; if(destination.getId() == 8) {
; int[] fbd = {18, 20, 21, 22, 23, 24};
; forbidden = fbd;
; }
; if(destination.getId() == 9){
; int[] fbd = {21,23, 24};
; forbidden = fbd;
; }
; if(forbidden == null) return true;
;
; for(int badlink : forbidden) if(rid == badlink) return false;
;
; return true;
end
;faz o motorista chegar ao destino da via escolhida e experimentar o tempo de viagem
to advance
ask drivers [
if current-node = destination [stop]
;adiciona a via atual 'a rota
set current-route lput current-road current-route
;avanca para a proxima intersecao
set current-node [id] of [end2] of current-road
let nid current-node
move-to one-of intersections with [id = nid]
]
show "advanced"
end
;calcula o tempo de viagem gasto pelos motoristas
to experience-travel-times
ask roads [
set travel-time fftt * (1 + alpha * (num-drv / capacity) ^ beta)
;show num-drv
;show opt-num-drv
if num-drv > 0 [
set avg-num-drv ((num-drv - avg-num-drv) / (ticks + 1)) + avg-num-drv
set avg-opt-drv ((opt-num-drv - avg-opt-drv) / (ticks + 1)) + avg-opt-drv
]
;show avg-opt-drv
; avgNumDrivers = ((getNumDrivers() - getAvgNumDrivers()) / (Experiment.getInstance().getTimestep() + 1)) + getAvgNumDrivers();
]
ask drivers [
let attR 0 ;inicializa o tempo de viagem do motorista
;calcula o custo da rota
foreach current-route [
ask ? [set attR attR + travel-time]
]
set actual-tt attR
set route-weight actual-tt / expected-tt
;atualiza o vetor de pesos de rota por aresta
foreach current-route [
let rw roads-weight
let att actual-tt
let w route-weight
ask ? [
let rid road-id
set rw replace-item (rid - 1) rw w
;replace-item 0 [1 3 3] 3
]
set roads-weight rw
]
]
end
;atualiza a pontuacao dos preditores de cada motorista
;somente sao atualizados os preditores que foram usados na ultima viagem
;SC = (1-u)SC + u[(Ca / Xa) -1]*ATTR
to update-predictors-score
;para cada via...
ask roads [
if num-drv = 0 [stop]
let rid road-id
let rhist history
let rocc capacity / num-drv
;para cada motorista
ask drivers [
let curr-predictors sublist predictors (rid - 1) rid ;OK - obtem os preditores desta via
let scores sublist predictors-score (rid - 1) rid
let bpindex item (rid - 1) best-predictors ;obtem o indice do melhor preditor desta via
;obtem o score e o recalcula
let score item bpindex (item 0 scores)
set score (1 - learning-factor) * score + learning-factor * (rocc - 1) * actual-tt
;coloca o novo score na sub-lista das pontuacoes dos preditores daquela via
let new-scores replace-item bpindex (item 0 scores) score
;atualiza em qual indice esta o melhor preditor
let bpidx position (max new-scores) new-scores ;OK
set best-predictors replace-item (rid - 1) best-predictors bpidx
;show (word new-scores " " bpidx)
;coloca a sub-lista na lista de pontuacoes geral
set predictors-score replace-item (rid - 1) predictors-score new-scores
;show predictors-score
;atualiza os indices dos melhores preditores
; foreach predictors-score [
; set bpidx position max
; ]
; let curr-predictors sublist predictors (rid - 1) rid ;OK - obtem os preditores desta via
;set best-pred-index 0
;let best-predictor (item best-pred-index (item 0 curr-predictors))
;let predicted-occ predict-occupation best-predictor rhist
]
]
end
;retorna a rota otima entre nos origem-destino
to-report calculate-opt-route [org dest]
let rid-list []
if org = 1 and dest = 8 [ set rid-list [1 6 15] ]
if org = 1 and dest = 9 [ set rid-list [3 12 20] ]
if org = 1 and dest = 10 [ set rid-list [3 12 21] ]
if org = 2 and dest = 8 [ set rid-list [6 15] ]
if org = 2 and dest = 9 [ set rid-list [6 13 18] ]
if org = 2 and dest = 10 [ set rid-list [6 15 23] ]
if org = 3 and dest = 8 [ set rid-list [9 17] ]
if org = 3 and dest = 9 [ set rid-list [9 18] ]
if org = 3 and dest = 10 [ set rid-list [9 18 24] ]
let opt-route []
foreach rid-list [
set opt-route lput one-of roads with [road-id = ?] opt-route
]
report opt-route
end
; Prediz a ocupacao na via dado uma estrategia (o preditor) e o historico.
; A previsao e' dada pela formula:
; p(t) = x(t - 1) * a(t - 1) + x(t - 2) * a(t -2) +..
; ... + x(t - MEMORY-SIZE) * a(t - MEMORY-SIZE)
; onde p(t) e' a previsao no tempo t, x(t) e a ocupacao da via no tempo t,
; a(t) e' o peso para o tempo t e MEMORY-SIZE e' o tamanho do historico
to-report predict-occupation [predictor occ-history]
let prediction sum (map [?1 * ?2] predictor occ-history)
if prediction < 60 [set prediction 60]
if prediction > 140 [set prediction 140]
report prediction
end
;diz se todos os motoristas ja chegaram nos seus destinos
to-report drivers-not-arrived
let all-arrived true
ask drivers [
if current-node != destination [ set all-arrived false ]
]
report not all-arrived
end
;gera uma lista de zeros como score inicial dos preditores
to-report initial-scores
report n-values num-predictors [0] ;score inicial dos preditores e' zero
end
;gera uma lista com 'num-predictors' preditores aleatorios
to-report random-predictors
report n-values num-predictors [random-predictor]
end
;gera um vetor de pesos entre [-1:1] do tamanho do historico
to-report random-predictor
report n-values (history-size) [1.0 - random-float 2.0]
end
to build-network
clear-turtles
file-open "mgta2" ;user-file
set num-intersections file-read
set num-roads file-read
set ideal-segment-length file-read
repeat num-intersections [
create-intersections 1 [
set id file-read ;id-counter
set xcor file-read / 1.1
set ycor file-read / 1.1
update-node-visual
]
]
repeat num-roads [
let r-id file-read
let id1 file-read
let id2 file-read
let primary? file-read
ask intersections with [ id = id1 ] [
create-roads-to intersections with [id = id2] [
set road-id r-id
set num-drv 0
set opt-num-drv 0
set avg-num-drv 0
set avg-opt-drv 0
set fftt 5
set capacity 130 + random 121
;set capacity num-drivers / 7.5 ;TODO REMOVER ISSO APOS TESTAR
set label road-id
set label-color red
set history n-values history-size [60 + random 81] ;historico de valores entre 60 e 140
]
]
]
file-close
ask roads [
set shape "default"
set thickness .2
]
end
to update-node-visual
set shape "circle 2"
set size ideal-segment-length / 3
set color 5
end
to do-plots
plot-travel-times
plot-roads-occupation
plot-tt-per-od
end
to plot-travel-times
let total-att 0
let total-ett 0
ask drivers [
set total-att total-att + actual-tt
set total-ett total-ett + expected-tt
]
let avg-att total-att / num-drivers
let avg-ett total-ett / num-drivers
set-current-plot "avg-travel-time"
set-current-plot-pen "actual"
plot avg-att
set-current-plot-pen "expected"
plot avg-ett
end
to plot-tt-per-od
let counter 1
let origins [1 2 3]
let dests [8 9 10]
set-current-plot "travel-time-per-od"
clear-plot
foreach origins [
let orig ?
foreach dests [
let dest ?
set-current-plot-pen "actual"
plotxy counter (att-per-od orig dest)
set-current-plot-pen "expected"
plotxy (counter) (ett-per-od orig dest)
set counter counter + 1
]
]
end
to-report att-per-od [orig dest]
let total-tt 0
ask drivers with [origin = orig and destination = dest] [
set total-tt total-tt + actual-tt
]
if total-tt = 0 [report 0]
report total-tt / count drivers with [origin = orig and destination = dest]
end
to-report ett-per-od [orig dest]
let total-tt 0
ask drivers with [origin = orig and destination = dest] [
set total-tt total-tt + expected-tt
]
if total-tt = 0 [report 0]
report total-tt / count drivers with [origin = orig and destination = dest]
end
to plot-roads-occupation
set-current-plot "drivers-per-road"
clear-plot
set-current-plot-pen "actual"
ask roads [
plotxy road-id avg-num-drv
]
set-current-plot-pen "proportional"
ask roads [
plotxy road-id avg-opt-drv
; if road-id = 24 [show (word "error " road-id " " avg-opt-drv)]
]
if plot-capacity? [
set-current-plot-pen "capacity"
ask roads [
plotxy (road-id + .5) capacity
]
]
set-current-plot "inst-drv-per-road"
clear-plot
set-current-plot-pen "actual"
ask roads [
plotxy road-id num-drv
]
set-current-plot-pen "proportional"
ask roads [
plotxy road-id opt-num-drv
]
end
to update-roads-visual
ask roads [
let occ avg-num-drv / capacity
if inst-road-view?
[set occ num-drv / capacity]
set color green
if occ > 0.80 [set color yellow]
if occ > 1.00 [set color orange]
if occ > 1.20 [set color red]
; show occ
]
end