R2 - Webnode

Transcrição

R2 - Webnode

DISTRIBUTED AND ECOLOGICAL
VEHICLE ROUTING
Flávio A. R. de Faria
PESC/COPPE/Universidade Federal do Rio de Janeiro
Felipe M. G. França
PESC/COPPE/Universidade Federal do Rio de Janeiro
Antonio A. F. Loureiro
DCC/Universidade Federal de Minas Gerais
Paulo C. M. Ribeiro
PET/COPPE/Universidade Federal do Rio de Janeiro
Priscila M. V. Lima
PPGI/Universidade Federal do Rio de Janeiro
Motivation
• Road saturation
Brazilian vehicle fleet quadrupled in the the last 30 years
Rise in fuel consumption and polluent emissions
• Urban mobility losses
24% of Brazilian population waste more than one (1) hour to
reach job or school
São Paulo average travel time: 52 min
• Participative sensoring networks
Brazilian Computing Chalenges: sensoring as a service
Goals
• Travel time reduction
• Comfortable acceleration/stop reduction
• Fuel consumption reduction
• CO, HC and NOx minimization
Proposed solutions
•  Vehicle routing as a function of semaphores timing
•  Velocity/acceleration planning
as a function of semaphores timing
•  Evaluation via a traffic microsimulator:
distributed timing control of semaphores
Intelligent SMER-based routing
•  Semaphores timing prediction:
fixed and dynamic timing
•  Routing based on Dijkstra’s algorithm
as a function of semaphores timing
(SMER – Scheduling by Multiple Edge Reversal)
•  SMER-based intersecting Green Waves:
booking places inside green waves
•  ReSATyrus for intersecting Green Waves:
Automatic Generation of Constraints graphs
(Alves, Lima and França, IFORS 2014)
7
Colective Robotics
ReSATyrus Simplified notation:
R0: 15 xor 16 xor 17 xor 10 xor 9 xor 16 xor 23 xor 22
Neighborhood Constrained Systems
The DINING Philosophers Problem(Dijkstra 65)
Constraints graph: neighborhood..
.. sharing resources.
R1
A
A
R3
R2
B
C
R4
D
R5
E
R3
R1,R2
B
R2,R3
R2
C
R3
R4
R5
E
D
Sharing styles: AND (greedy)
A:= R1.R2"
B:= R1.R2"
R1
A
B
R2
A
R1,R2
B
Sharing styles: OR (relaxed)
A:= R1 + R2"
B:= R1 + R2"
B
R2
R1
a1
R1
A
A
B
b1
R2
a2
b2
Sharing styles: XOR (restrained)
A:= R1
B:= R1
R2 = R1R2 + R1R2"
R2"
A
a1
R1
A
B
R2
B
R1
b1
R1 R2
R1 R2
a2
b2
R2
SER – Scheduling by Edge Reversal
(Gafni&Bertsekas 81)(Chandy&Misra 84)(Barbosa&Gafni 89)
r1
r3
r2
r4
r5
Initial acyclic orientation
r1,r2
r2
r4
r2,r3
r3
r3
r5
(Gafni&Bertsekas 81)(Chandy&Misra 84)(Barbosa&Gafni 89)
r1
r3
r2
r4
r1,r2
r2
r4
r5
r2,r3
r3
r3
r5
m=1, p=3 (Barbosa 86, Barbosa&Gafni 89)
m=1, p=3 (Barbosa 86, Barbosa&Gafni 89)
m=1, p=5
•  Concurrency:
γ o (ω ) = m / p
1 / 2 ≤ γ o (ω ) ≤ 1 / n
(Barbosa 86)(Barbosa and Gafni 89)
€
m=1, p=3
•  max γ is NP-complete
(Barbosa 86)(Barbosa and Gafni 89)
•  min γ is NP-complete
(Arantes Jr, Faria, and França 06)
m=1, p=5
A
E
B
C
D
m=2, p=5 , γ* =2/5
Asynchronous view: consistent global states
A
B
C
A
E
B
D
C
D
E
21
SER: Distributed control of traffic intersections
(Carvalho, Protti, DeGregorio and França 05)
G
F
F2
G
F
E
F1
R5
A
F1
B
E
R4
R3
R1
R2
C
F2
A
B
C
D
D
F1:= R1.R2.R3.R4 + R1.R2 (A + B)
F2:= R2.R3.R4.R5 + R4.R5 (G + F)
22
SER: Distributed control of traffic intersections
G
F
G
F
E
E
A
A
B
B
G
F
C
C
D
E
A
m=1, p=3
B
C
D
D
The ZEN Philosophers Problem
(França 93, 94)
SMER — Scheduling by Multiple Edge Reversal
T
h
e
mzen =1, mnormal =2, p=4
(ri –...1)
(r...
j -1)
i
r...
i
i
rj
j
eij > (ri – 1) + (rj -1) (deadlock)
j
eij < ri + rj (mutual exclusion)
eij = ri + rj – mdc(ri , rj) (nec&suff)
eij = ri + rj - 1
2. The period between two nodes
i
j
ri = 3, rj = 2
ri + rj
pij =
gcd(ri, rj )
•  SMER-based intersecting Green Waves:
booking spots inside green waves
•  Acceleration&velocity as F(Green Waves):
SMER-based semaphore timing
•  Improvements via microsimulation:
Less fuel consumption
Less CO/HC/NOx emissions
Less stops/acceleration
•  Routing policies:
Shortest in distance
Shortest in time
Intelligent/intersecting green waves
•  MicroLAM microsimulator:
Extended IDM & SMER-based semaphore timing
•  Closed 10 X 10 network:
Alternated fluxes
4 arteries
2h duration
Shortest in distance
Shortest in time
Intelligent/intersecting green waves
634
Contagem de veículos
1249
Espacialmente mais curta
Temporalmente mais curta
Orientada a ondas verdes
1000
6
900
5
Velocidade média (m/s)
Tempo (s)
800
700
600
500
400
4
3
2
1
300
200
Viagem
Atraso
0
Velocidade média
Results for dynamic/intelligent Semaphores: (5 min reconf.) 338-‐450 vph (arteries) e 225-‐300 vph (other roads).
0.3
3
0.25
2.5
Níveis de emissão (g/km)
Consumo de combustível (L/km)
0.2
0.15
0.1
0.05
2
1.5
1
0.5
0
0
Combustível
CO
HC
NOx
Results for dynamic/intelligent Semaphores: (5 min reconf.) 338-‐450 vph (arteries) e 225-‐300 vph (other roads).
Collaborative planning + dynamic routing
Sem reserva de espaço nas fases
Com reserva de espaço nas fases
6
600
5
Velocidade média (m/s)
700
500
Tempo (s)
400
300
200
4
3
2
1
100
0
Viagem
Atraso
Results for ﬁxed >me Semaphores: Velocidade média
450 vph (arteries) e 300 vph (other roads).
Collaborative planning + dynamic routing
2.5
0.25
2
Níveis de emissão (g/km)
Consumo de combustível (L/km)
0.3
0.2
0.15
0.1
1.5
1
0.5
0.05
0
Combustível
0
CO
Results for ﬁxed >me Semaphores: HC
NOx
450 vph (arteries) e 300 vph (other roads).
Conclusion, ongoing and future work
•  Noticeable gains obtained
•  Realistic urban traffic scenarios
fixed, seasonal and dynamic semaphore timing
inclusion of intermediate stop/go
heterogeneous traffic, including driverless cars
•  Collaborative sensoring
semaphore and vehicles considering online information about traffic
Thank you, Gracias, Obrigado!
[email protected]

R2 - Webnode

Transcrição

Documentos relacionados

IMPULSOR PARA MOTORES DE PARTIDA CBT, CASE, Clark

Evaluation Data