Notebook source code:
notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb
Run it yourself on binder
Optimization of Sao Paulo traffic#
Lead author: Jules Deschamps.
This notebook presents a simple use case of information geometry, in the context of traffic optimization in Sao Paulo. We rely on a dataset listing all traffic jams in Sao Paulo for the past two decades (their location, date, their size, their duration, i.e. how long the traffic was jammed) to propose a solution involving information geometry.
This analysis relies heavily on the geometry of the Gamma manifold, which is particularly adapted to addressing this situation, as seen later on.
Figure 1: Sao Paulo: A city with 180km traffic jams – BBC News
In [1]:
import matplotlib.pyplot as plt
import geomstats.backend as gs
import pandas as pd
INFO: Using autograd backend
1. Introduction and Motivation#
40% of São Paulo residents own a motor vehicle. While this is lower than cities in the United States, it is still higher than most other Latin American cities and São Paulo’s infrastructure was not built to accommodate such a large number of private vehicles. As The Urban Mobility Research Network of São Paulo found, some São Paulo residents spend one month per year in traffic, or 2.4 hours per day. As car ownership increases, and with it further congestion, this time spent in traffic will only grow. In that regard, considering the increase in car ownership and air pollution, even though widening roads only brings a temporary solution, it can alleviate Brazilians of the absurd amount of time they spend in traffic.
In the role of Sao Paulo’s city planners, we have been granted a certain amount of resources to solve the congestion problem of Sao Paulo. The issue at hand becomes that of choosing which roads to renovate. More formally, the goal is eventually to reduce the mean expected congestion time in traffic.
2. Dataset description#
We have at our disposal a dataset (accessible here) containing traffic jam size measurements by CET at several locations on São Paulo between 2001 and 2019, with more than 5M entries.
Available columns: - passage (str) - Name of the passage - direction (str) - type (str) - Indicates if the passage is an expressway (E) - region (str) - São Paulo region - timestamp (datetime) - When the traffic jam was measured (UTC-4) - jam_size (int) - Traffic jam in meters - segment (str) - Where the passage is located
Our modeling will not take into account the fact that many of the passages/roads must have been renovated between 2001 and 2019. Similarly, the dataset does not offer information on the width of given roads (even though we could base it off of the type of the road), and therefore on their flow rate: this is an obvious flaw in our analysis but it is easy to fix if the relevant data can be accessed.
Pre-processing the dataset#
In [2]:
from geomstats.datasets.utils import load_sao_paulo
df, jam_count = load_sao_paulo()
INFO: Data has already been downloaded... using cached file ('/home/luisfpereira/.geomstats_data/jam.zip').
Some of the columns of the dataset are not necessary for our study: let alone index, type and segment do not seem to add any value to the table in our case. In addition, the times (timestamp) at which jams are occurring are not relevant in that specific format: it would make much more sense to have the duration of given jam. We also decide to drop the jam_size column.
Additionally, we would want to transform the original dataset so as to access a more relevant table, with features: - name of the road (primary key = passage + direction for instance, segments are regrouped within same key) - date (day only) - duration of the traffic jam (in h)
In [3]:
df
Out [3]:
| name | date | duration | |
|---|---|---|---|
| 0 | Abraão Ribeiro, Av Dr (F) Bairro... | 2005-01-12 | 1.0 |
| 1 | Abraão Ribeiro, Av Dr (F) Bairro... | 2005-01-20 | 1.5 |
| 2 | Abraão Ribeiro, Av Dr (F) Bairro... | 2005-01-21 | 1.5 |
| 3 | Abraão Ribeiro, Av Dr (F) Bairro... | 2005-02-24 | 4.5 |
| 4 | Abraão Ribeiro, Av Dr (F) Bairro... | 2005-02-28 | 2.0 |
| ... | ... | ... | ... |
| 650519 | Xangai, Vd unico/... | 2004-01-16 | 3.5 |
| 650520 | Xangai, Vd unico/... | 2004-03-24 | 4.0 |
| 650521 | Xangai, Vd unico/... | 2004-03-26 | 2.0 |
| 650522 | Xangai, Vd unico/... | 2004-04-29 | 4.0 |
| 650523 | Xangai, Vd unico/... | 2004-06-01 | 3.0 |
650524 rows × 3 columns
Above is the table df of all traffic jams and their durations, for each day.
In [4]:
jam_count
Out [4]:
{'Abraão Ribeiro, Av Dr (F) Bairro/Centro ': 185,
'Abraão Ribeiro, Av Dr (F) Centro/Bairro ': 28,
'Abraão de Morais, Av Prof/Imig Santos/São Paulo ': 1870,
'Abraão de Morais, Av Prof/Imig São Paulo/Santos ': 852,
'Abraão de Morais, Av Prof/Imigrantes (F)Santos/São Paulo ': 396,
'Abraão de Morais, Av Prof/Imigrantes (F)São Paulo/Santos ': 107,
'Adolfo Pinheiro e Lgo 13/05 Bairro/Centro ': 391,
'Adolfo Pinheiro e Lgo 13/05 Centro/Bairro ': 657,
'Aliomar Baleeiro, Vd Min Anchieta/Imigrantes ': 3831,
'Aliomar Baleeiro, Vd Min Imigrantes/Anchieta ': 3191,
'Aliomar Baleeiro, Vd Min (F) Anchieta/Imigrantes ': 1,
'Alvarenga, R único// ': 1919,
'Amaro, Al Sto único// ': 1000,
'Amaro, Av Sto (F) Bairro/Centro ': 647,
'Amaro, Av Sto (F) Centro/Bairro ': 316,
'Amaro, Av Sto (Pavao/Nebraska) (F) Bairro/Centro ': 41,
'Amaro, Av Sto (Pavao/Nebraska) (F) Centro/Bairro ': 23,
'Amaro, Av Sto - DEC SA (F) Bairro/Centro ': 6,
'Amaro, Av Sto - DEC SA (F) Centro/Bairro ': 8,
'Amaro, Av Sto DEC IB Bairro/Centro ': 1814,
'Amaro, Av Sto DEC IB Centro/Bairro ': 1280,
'Amaro, Av Sto DEC SA Bairro/Centro ': 830,
'Amaro, Av Sto DEC SA Centro/Bairro ': 803,
'Anchieta, Via Santos/São Paulo ': 836,
'Anchieta, Via São Paulo/Santos ': 1293,
'Angélica, Av Bairro/Centro ': 19,
'Angélica, Av Centro/Bairro ': 29,
'Angélica, Av (F) Centro/Bairro ': 6,
'Antonio Nakashima, Vd único// ': 1432,
'Antártica, Vd Limão/Sumaré ': 1331,
'Antártica, Vd Sumaré/Limão ': 1308,
'Antônio Joaquim de Moura Andrade, Av Ibirapuera/Marginal ': 7071,
'Antônio Joaquim de Moura Andrade, Av Marginal/Ibirapuera ': 2428,
'Arcoverde, R Card //unico ': 238,
'Arcoverde, R Cardeal (F) único// ': 1270,
'Aricanduva, Av/Elev/Pt Itaquera/Marginal ': 4929,
'Aricanduva, Av/Elev/Pt Marginal/Itaquera ': 3891,
'Aricanduva/Elevado/Ponte( F) Itaquera/Marginal ': 2258,
'Aricanduva/Elevado/Ponte( F) Marginal/Itaquera ': 1315,
'Arnaldo, Av Dr Consolação/Sumare ': 2596,
'Arnaldo, Av Dr Sumare/Consolação ': 5998,
'Arthur da Costa e Silva, Elev Pres Lapa/Penha ': 4972,
'Arthur da Costa e Silva, Elev Pres Penha/Lapa ': 3743,
'Ary Torres, Eng. Pte único// ': 3517,
'Asc.Reis/R.Berta(Local) Bairro/Centro ': 2614,
'Asc.Reis/R.Berta(Local) Centro/Bairro ': 998,
'Ataliba Leonel, Av. Gal. Bairro/Centro ': 56,
'Ataliba Leonel, Av. Gal. Centro/Bairro ': 110,
'Atilio Fontana, Pte Capital/Interior ': 71,
'Atilio Fontana, Pte Interior/Capital ': 3640,
'Atlantica, AV Bairro/Centro ': 485,
'Atlantica, AV Centro/Bairro ': 24,
'Ayrton Senna I, Tn (NÃO USAR) Centro/Bairro ': 2,
'Ayrton Senna I, Túnel unico// ': 7159,
'Ayrton Senna II, Túnel unico// ': 3815,
'Bandeirantes, Av dos Imigrantes/Marginal ': 7714,
'Bandeirantes, Av dos Marginal/Imigrantes ': 6796,
'Bento, Lgo São //unico ': 9,
'Bernardino/Verg/Noe/Domingos/Jabaquara Bairro/Centro ': 2153,
'Bernardino/Verg/Noe/Domingos/Jabaquara Centro/Bairro ': 519,
'Bernardo Goldfarb, Pte Bairro/Centro ': 1079,
'Bernardo Goldfarb, Pte Centro/Bairro ': 174,
'Brasil, Av Ibirapuera/Pinheiros ': 246,
'Brasil, Av Pinheiros/Ibirapuera ': 537,
'Brás Leme, Av / Pte Casa Verde Bairro/Centro ': 2002,
'Brás Leme, Av / Pte Casa Verde Centro/Bairro ': 419,
'Butantã, R //unico ': 206,
'Butantã, R (F) unico// ': 2032,
'CJardim/Europa, Av/Colômbia, R (F) Bairro/Centro ': 1,
'Caetano Alvares, Av. Eng. Bairro/Centro ': 26,
'Caetano Alvares, Av. Eng. Centro/Bairro ': 85,
'Camargo, R único// ': 1430,
'Carlos Caldeira Filho, Av Bairro/Centro ': 1209,
'Carlos Caldeira Filho, Av Centro/Bairro ': 345,
'Carrão, Av Cons (F) Bairro/Centro ': 488,
'Carrão, Av Cons (F) Centro/Bairro ': 61,
'Carrão, Av Cons Bairro/Centro ': 264,
'Carrão, Av Cons Centro/Bairro ': 116,
'Casa Verde, Pte e Av Bras Leme (F) Bairro/Centro ': 874,
'Casa Verde, Pte e Av Bras Leme (F) Centro/Bairro ': 324,
'Catiguá, R / Melo Peixoto, R (F) Bairro/Centro ': 1339,
'Catiguá, R / Melo Peixoto, R (F) Centro/Bairro ': 21,
'Celso Garcia, Av Bairro/Centro ': 124,
'Celso Garcia, Av Centro/Bairro ': 549,
'Chucri Zaidan, Av Dr Bandeirantes/Morumbi ': 1706,
'Chucri Zaidan, Av Dr Morumbi/Bandeirantes ': 285,
'Chucri Zaidan, Av Dr (F) Bandeirantes/Morumbi ': 461,
'Chucri Zaidan, Av Dr (F) Morumbi/Bandeirantes ': 380,
'Cidade Jardim / Europa / Colômbia Bairro/Centro ': 6013,
'Cidade Jardim / Europa / Colômbia Centro/Bairro ': 5448,
'Cidade Universitária, Pt PanAmericana/USP ': 3050,
'Cidade Universitária, Pt USP/PanAmericana ': 179,
'Cidade Universitária, Pte (F) PanAmericana/USP ': 1744,
'Cidade Universitária, Pte (F) USP/PanAmericana ': 116,
'Clelia, R (F) único// ': 172,
'Clélia, R //unico ': 391,
'Consolação, R da Bairro/Centro ': 3618,
'Consolação, R da Centro/Bairro ': 3679,
'Consolação, R da (F) Bairro/Centro ': 2257,
'Consolação, R da (F) Centro/Bairro ': 2784,
'Copa-Afonso de S. Souza/Harry DannembergAricanduva/Itaquera ': 1,
'Copa-Aguia de Haia A Alvim/S Miguel ': 11,
'Copa-Aguia de Haia S Miguel/A Alvim ': 4,
'Copa-Aguia de Haia (F) S Miguel/A Alvim ': 1,
'Copa-Campanella Bairro/Centro ': 10,
'Copa-Campanella Centro/Bairro ': 11,
'Copa-Itaquera/Lider Itaquera/Vila Formosa ': 6,
'Copa-Itaquera/Lider Vila Formosa/Itaquera ': 14,
'Copa-Jacu Pessêgo-N. Trabalhadores A Senna/Maua ': 4,
'Copa-Jacu Pessêgo-N. Trabalhadores Maua/A Senna ': 8,
'Copa-Luiz Ayres Bairro/Centro ': 2,
'Copa-Luiz Ayres Centro/Bairro ': 11,
'Copa-Pires do Rio Bairro/Centro ': 7,
'Copa-Pires do Rio Centro/Bairro ': 8,
'Corifeu de A Marques, Av Bairro/Centro ': 663,
'Corifeu de A Marques, Av Centro/Bairro ': 141,
'Corifeu de Azevedo Marques, Av (F) Bairro/Centro ': 73,
'Corifeu de Azevedo Marques, Av (F) Centro/Bairro ': 4,
'Cruzeiro do Sul, Pt e Av Ipiranga/Santana ': 1377,
'Cruzeiro do Sul, Pt e Av Santana/Ipiranga ': 2409,
'Cruzeiro do Sul, Pte e Av (F) Ipiranga/Santana ': 397,
'Cruzeiro do Sul, Pte e Av (F) Santana/Ipiranga ': 421,
'Dianópolis, Av //unico ': 395,
'Dianópolis, Av (F) unico// ': 181,
'Diário Popular, Vd único// ': 189,
'Dom Pedro (Av Exterior) Pq //unico ': 15,
'Dom Pedro (Av do Exterior), Parque (F) unico// ': 43,
'Edgar Facó, Av. Bairro/Centro ': 1197,
'Edgar Facó, Av. Centro/Bairro ': 160,
'Eliseu de Almeida, Av Bairro/Centro ': 821,
'Eliseu de Almeida, Av Centro/Bairro ': 75,
'Ermano Marchetti, Av Barra Funda/Lapa ': 710,
'Ermano Marchetti, Av Lapa/Barra Funda ': 606,
'Escola Politécnica, Av Bairro/Centro ': 752,
'Escola Politécnica, Av Centro/Bairro ': 39,
'Estado, Av do - DEC CT Ipiranga/Santana ': 7017,
'Estado, Av do - DEC CT Santana/Ipiranga ': 4633,
'Estado, Av do - DEC VILA PRUDENTE Ipiranga/Santana ': 3409,
'Estado, Av do - DEC VILA PRUDENTE Santana/Ipiranga ': 3920,
'Estela, R unico// ': 41,
'Eusébio M/Francisco Morato, Av Prof Bairro/Centro ': 5021,
'Eusébio M/Francisco Morato, Av Prof Centro/Bairro ': 2887,
'Eusébio Stevaux, Vd único// ': 1445,
'F1 - Jacinto Júlio, Av Bairro/Centro ': 1,
'F1 - Jacinto Júlio, Av Centro/Bairro ': 3,
'F1 - Jangadeiro, Av Bairro/Centro ': 4,
'F1 - Jangadeiro, Av Centro/Bairro ': 2,
'F1 - João Paulo da Silva, Av Bairro/Centro ': 2,
'F1 - Miguel Yunes/Pte Vitorino Goulart Interlagos/Marginal ': 2,
'F1 - Papini, Av Prof Centro/Bairro ': 3,
'F1 - Rio Bonito, Av Bairro/Centro ': 2,
'F1 - Rio Bonito, Av Centro/Bairro ': 1,
'F1 - Rubens Montanaro de Borba, Av Bairro/Centro ': 1,
'F1 - Teotonio Vilela, Av Sen Bairro/Centro ': 3,
'F1 - Teotonio Vilela, Av Sen Centro/Bairro ': 3,
'Faria Lima, Av Brig Itaim/Pinheiros ': 3606,
'Faria Lima, Av Brig Pinheiros/Itaim ': 5154,
'Fernando Vieira de Mello Túnel(Reboucas)Bairro/Centro ': 5663,
'Fernando Vieira de Mello Túnel(Reboucas)Centro/Bairro ': 5516,
'Ferradura unico// ': 698,
'Figueira, R da unico// ': 802,
'Francisco Matarazzo, Av Bairro/Centro ': 1170,
'Francisco Matarazzo, Av Centro/Bairro ': 1316,
'Francisco Matarazzo, Av (F) Bairro/Centro ': 1895,
'Francisco Matarazzo, Av (F) Centro/Bairro ': 2070,
'Francisco Mesquita, Av Dr S. Caetano/Sao Paulo ': 2214,
'Francisco Mesquita, Av Dr Sao Paulo/S. Caetano ': 168,
'Francisco Morato, Av Prof Bairro/Centro ': 1751,
'Francisco Morato, Av Prof Centro/Bairro ': 1145,
'Frederico Eduardo Mayr, Vd unico// ': 861,
'Freguesia, Pte Freguesia/Lapa ': 775,
'Freguesia, Pte Lapa/Freguesia ': 323,
'Freguesia/Com Martinelli, Pte (F) Freguesia/Lapa ': 507,
'Freguesia/Com Martinelli, Pte (F) Lapa/Freguesia ': 110,
'Gabriel, Av São (F) Bairro/Centro ': 127,
'Gabriel, Av São (F) Centro/Bairro ': 271,
'Gabriel, Av São Bairro/Centro ': 114,
'Gabriel, Av São Centro/Bairro ': 428,
'Gastão Vidigal, Av Dr Marginal/Pinheiros ': 804,
'Gastão Vidigal, Av Dr Pinheiros/Marginal ': 670,
'Gastão Vidigal, Av Dr (F) Lapa/Pinheiros ': 163,
'Gastão Vidigal, Av Dr (F) Pinheiros/Lapa ': 132,
'Gasômetro, R e Vd único// ': 1324,
'Gazeta do Ipiranga, Vd unico// ': 301,
'Grande Sao Paulo, Vd Ipiranga/Vila Prudente ': 3851,
'Grande Sao Paulo, Vd Vila Prudente/Ipiranga ': 1965,
'Groenlandia, R unico// ': 2879,
'Guadalajara, Vd Belem/Mooca ': 50,
'Guadalajara, Vd Mooca/Belem ': 20,
'Guaicurus, R //unico ': 143,
'Guaicurus, R (F) unico// ': 111,
'Guarapiranga, Av Bairro/Centro ': 755,
'Guarapiranga, Av Centro/Bairro ': 751,
'Guido Caloi, Av Bairro/Centro ': 292,
'Guido Caloi, Av Centro/Bairro ': 423,
'Guilherme Dumont Vilares, Av Dr Campo Limpo/Morato ': 16,
'Guilherme Dumont Vilares, Av Dr Morato/Campo Limpo ': 7,
'Heitor Penteado, R Bairro/Centro ': 202,
'Heitor Penteado, R Centro/Bairro ': 179,
'Ibirapuera, Av Bairro/Centro ': 2225,
'Ibirapuera, Av Centro/Bairro ': 3705,
'Ibirapuera, Av (F) Bairro/Centro ': 2433,
'Ibirapuera, Av (F) Centro/Bairro ': 2911,
'Ibitirama, R unico// ': 171,
'Iguatemi, R //unico ': 336,
'Iguatemi, R (F) único// ': 437,
'Inajar de Souza, Av Freguesia/Lapa ': 794,
'Inajar de Souza, Av Lapa/Freguesia ': 34,
'Inajar de Souza, Av (F) Freguesia/Lapa ': 16,
'Interlagos, Av I Bairro/Centro ': 2008,
'Interlagos, Av I Centro/Bairro ': 1110,
'Ipiranga, Av unico// ': 1523,
'Itapecerica, Est de Bairro/Centro ': 871,
'Itapecerica, Est de Centro/Bairro ': 145,
'Itapecirica, Est de (F) Bairro/Centro ': 274,
'Itapecirica, Est de (F) Centro/Bairro ': 86,
'Itápolis, R //unico ': 6,
'Jacinto Júlio, Av Bairro/Centro ': 2,
'Jaguare, Av Bairro/Centro ': 353,
'Jaguare, Av Centro/Bairro ': 287,
'Jaguaré, Pte Jaguaré/Lapa ': 314,
'Jaguaré, Pte Lapa/Jaguaré ': 828,
'Jangadeiro, Av Bairro/Centro ': 1,
'Jangadeiro, Av Centro/Bairro ': 4,
'Jose Colassuono, Vd unico// ': 1534,
'Jose Felix, R Campo Limpo/Morato ': 6,
'Jose Felix, R Morato/Campo Limpo ': 2,
'José Diniz, Av Ver (F) Bairro/Centro ': 915,
'José Diniz, Av Ver (F) Centro/Bairro ': 1726,
'José Diniz, Av Ver Bairro/Centro ': 2743,
'José Diniz, Av Ver Centro/Bairro ': 3017,
'José Garzotti, Av. Pe Teotônio/Batista Botelho ': 1,
'José Maria, Av Pe Bairro/Centro ': 267,
'José Maria, Av Pe Centro/Bairro ': 18,
'João De Luca, Ver Diadema/Marginal ': 122,
'João De Luca, Ver Marginal/Diadema ': 68,
'João Dias, Av Bairro/Centro ': 2689,
'João Dias, Av Centro/Bairro ': 2667,
'João Dias, Av (F) Bairro/Centro ': 1580,
'João Dias, Av (F) Centro/Bairro ': 1350,
'João Goulart, Elev Pres Lapa/Penha ': 173,
'João Goulart, Elev Pres Penha/Lapa ': 95,
'João Jorge Saad,Vd (Cebolinha) Centro/Bairro ': 384,
'João Mendes, Pça //unico ': 642,
'João Paulo da Silva, Av Bairro/Centro ': 5,
'João Paulo da Silva, Av Centro/Bairro ': 2,
'João, Av São único// ': 185,
'Julio de Mesquita, Pte Lapa/Piqueri ': 29,
'Julio de Mesquita, Pte Limão/Pompéia ': 667,
'Julio de Mesquita, Pte Piqueri/Lapa ': 77,
'Julio de Mesquita, Pte Pompéia/Limão ': 55,
'Juntas Provisórias, R das Ipiranga/Vila Prudente ': 2782,
'Juntas Provisórias, R das Vila Prudente/Ipiranga ': 1425,
'Juscelino Kubitschek, Av Pres Ibirapuera/Pinheiros ': 7635,
'Juscelino Kubitschek, Av Pres Pinheiros/Ibirapuera ': 8411,
'Jânio Quadros, Pres. Pte (Vila Maria) Bairro/Centro ': 114,
'Jânio Quadros, Pres. Pte (Vila Maria) Centro/Bairro ': 68,
'Jânio Quadros, Túnel unico// ': 4050,
'Lapa, Vd Lapa/Piqueri ': 306,
'Lapa, Vd Piqueri/Lapa ': 684,
'Liberdade/ Vergueiro, Av Bairro/Centro ': 841,
'Liberdade/ Vergueiro, Av Centro/Bairro ': 735,
'Ligação - Dec HG (F) Lapa/Penha ': 2672,
'Ligação - Dec HG (F) Penha/Lapa ': 2958,
'Ligação Leste-Oeste Lapa/Penha ': 4424,
'Ligação Leste-Oeste Penha/Lapa ': 4357,
'Limão / Av. Ordem e Progresso, Pte Limão/Sumaré ': 3797,
'Limão / Av. Ordem e Progresso, Pte Sumaré/Limão ': 182,
'Limão, Pt/Ordem e Progresso, Av (N USAR)Limão/Sumaré ': 3,
'Lineu de Paula Machado, Av Bairro/Centro ': 1190,
'Lineu de Paula Machado, Av Butanta/Morumbi ': 849,
'Lineu de Paula Machado, Av Centro/Bairro ': 70,
'Lineu de Paula Machado, Av Joquei/USP ': 62,
'Lineu de Paula Machado, Av Morumbi/Butanta ': 79,
'Lineu de Paula Machado, Av USP/Joquei ': 597,
'Luis Antonio, Av Brig Bairro/Centro ': 433,
'Luis Antonio, Av Brig Centro/Bairro ': 171,
'Luis Antonio, Av Brig. Dec-PA (F) Bairro/Centro ': 357,
'Luis Antonio, Av Brig. Dec-PA (F) Centro/Bairro ': 20,
'Luis Carlos Berrini, Av Eng Bandeirantes/Morumbi ': 1593,
'Luis Carlos Berrini, Av Eng Morumbi/Bandeirantes ': 967,
'Luis Carlos Berrini,Eng Av (F) Bandeirantes/Morumbi ': 1514,
'Luis Carlos Berrini,Eng Av (F) Morumbi/Bandeirantes ': 906,
'Luis, Av. São //unico ': 195,
'Luiz Ignácio de Anhaia Mello, Av Prof Bairro/Centro ': 4055,
'Luiz Ignácio de Anhaia Mello, Av Prof Centro/Bairro ': 2964,
'Luiz Ignácio de Anhaia Mello, Av Prof Sapopem./Vila Prudente ': 706,
'Luiz Ignácio de Anhaia Mello, Av Prof Vila Prudente/Sapopem. ': 360,
'M Paula, R/Jacarei/n Julho, Vd (F) //unico ': 2,
'M.M.D.C, R único// ': 1597,
'Manuel de Teffé, R Bairro/Centro ': 7,
'Marginal Pinheiros Castelo/Interlagos ': 10332,
'Marginal Pinheiros Interlagos/Castelo ': 9675,
'Marginal Tietê A.Senna/Castelo Branco ': 10776,
'Marginal Tietê Castelo/A.Senna ': 9885,
'Marginal Tietê - Pista Central A.Senna/Castelo Branco ': 2883,
'Marginal Tietê - Pista Central Castelo/A.Senna ': 2974,
'Maria Coelho Aguiar, Av Bairro/Centro ': 746,
'Maria Coelho Aguiar, Av Centro/Bairro ': 2554,
'Maria Maluf, CV Anchieta/Imigrantes ': 4512,
'Maria Maluf, CV Imigrantes/Anchieta ': 5019,
'Maria Paula/Vd Jacareí/Vd 9 de Julho único// ': 2778,
'Matriz, R da unico// ': 14,
'Max Feffer Túnel (Cidade Jardim) Bairro/Centro ': 4793,
'Max Feffer Túnel (Cidade Jardim) Centro/Bairro ': 2667,
'Melo Peixoto, R Bairro/Centro ': 1244,
'Melo Peixoto, R Centro/Bairro ': 1352,
'Melo Peixoto, R (F) Bairro/Centro ': 286,
'Melo Peixoto, R (F) Centro/Bairro ': 126,
'Mercúrio, Av único// ': 3250,
'Miguel Estefano,VD Abraão de Morais/Cursino ': 26,
'Miguel Estefano,VD Cursino/Abraão de Morais ': 10,
'Miguel Yunes/Pte Vitorino Goulart Interlagos/Marginal ': 6,
'Miguel Yunes/Pte Vitorino Goulart Marginal/Interlagos ': 3,
'Morumbi, Av Campo Limpo/Santo Amaro ': 194,
'Morumbi, Av Morumbi/Santo Amaro ': 1134,
'Morumbi, Av Santo Amaro/Campo Limpo ': 196,
'Morumbi, Av Santo Amaro/Morumbi ': 358,
'Morumbi, Av. e Pte Aeroporto/Marginal ': 2175,
'Morumbi, Av. e Pte Marginal/Aeroporto ': 2632,
'M´Boi Mirim, Est Bairro/Centro ': 8,
'M´Boi Mirim, Est Centro/Bairro ': 1,
'Natanael, R Mj (F) Estadio/Jardins ': 279,
'Nova Morumbi, Pte (F) unico// ': 1026,
'Nove de Julho, Av Bairro/Centro ': 4115,
'Nove de Julho, Av Centro/Bairro ': 5088,
'Nove de Julho, Av (F) Bairro/Centro ': 2488,
'Nove de Julho, Av (F) Centro/Bairro ': 2439,
'Nove de Julho, Av - DEC PA (F) Bairro/Centro ': 297,
'Nove de Julho, Av - DEC PA (F) Centro/Bairro ': 719,
'Olivia Guedes Penteado, R Bairro/Centro ': 2,
'Oscar Americano, R Eng Bairro/Centro ': 2037,
'Oscar Americano, R Eng Centro/Bairro ': 1767,
'Oscar Americano, R Eng (F) Bairro/Centro ': 445,
'Oscar Americano, R Eng (F) Centro/Bairro ': 62,
'Outeiro, Av NSra do Batista Botelho/Teotônio ': 1,
'Pacaembu / Mj Natanael / Abraao Ribeiro Estádio/Marginal ': 1390,
'Pacaembu / Mj Natanael / Abraao Ribeiro Marginal/Estádio ': 4199,
'Pacaembu, Vd (F) Bairro/Centro ': 330,
'Pacaembu, Vd (F) Centro/Bairro ': 279,
'Pacheco e Chaves, Cap. Vd Ipiranga/Vila Prudente ': 188,
'Pacheco e Chaves, Cap. Vd Vila Prudente/Ipiranga ': 1791,
'Pacheco e Chaves, R Cap Bairro/Centro ': 310,
'Pacheco e Chaves, R Cap Centro/Bairro ': 36,
'Papini, Av Prof Bairro/Centro ': 5,
'Papini, Av Prof Centro/Bairro ': 20,
'Paulina, Vd Dona //unico ': 2644,
'Paulina, Vd Dona (F) único// ': 1935,
'Paulista, Av Consolação/Paraiso ': 6247,
'Paulista, Av Paraiso/Consolação ': 9888,
'Paulo Eiró, R único// ': 2,
'Paulo VI, Av Limão/Sumaré ': 72,
'Paulo VI, Av Sumaré/Limão ': 36,
'Pedro Alvares Cabral, Av Pinheiros/Vila Mariana ': 680,
'Pedro Alvares Cabral, Av Vila Mariana/Pinheiros ': 1231,
'Pedro Alvares Cabral, Av (F) Pinheiros/Vila Mariana ': 791,
'Pedro Alvares Cabral, Av (F) Vila Mariana/Pinheiros ': 1975,
'Pedro I, Av. Dom Bairro/Centro ': 13,
'Pedro I, Av. Dom Centro/Bairro ': 18,
'Pinedo, Av de unico// ': 1,
'Piqueri, Pt Lapa/Piqueri ': 579,
'Piqueri, Pt Piqueri/Lapa ': 903,
'Piqueri, Pte (F) Lapa/Piqueri ': 278,
'Piqueri, Pte (F) Piqueri/Lapa ': 1054,
'Pirajussara, Av Bairro/Centro ': 17,
'Pirajussara, Av Centro/Bairro ': 53,
'Pompeia, Vd Marginal/Pompeia ': 2452,
'Pompeia, Vd Pompeia/Marginal ': 384,
'Queiroz Filho /Jaguaré, Pte Bairro/Centro ': 554,
'Queiroz Filho /Jaguaré, Pte Centro/Bairro ': 1276,
'Queiroz, Av. Sen. //unico ': 956,
'Radial Leste - DEC BR Bairro/Centro ': 6210,
'Radial Leste - DEC BR Centro/Bairro ': 4474,
'Radial Leste - DEC MO Bairro/Centro ': 7150,
'Radial Leste - DEC MO Centro/Bairro ': 4722,
'Raimundo Pereira Magalhaes, Av Bairro/Centro ': 47,
'Raimundo Pereira Magalhaes, Av Centro/Bairro ': 5,
'Raimundo Pereira de Magalhães - Norte Bairro/Centro ': 12,
'Raimundo Pereira de Magalhães - Norte Centro/Bairro ': 3,
'Raimundo Pereira de Magalhães - Sul Bairro/Centro ': 4,
'Raimundo Pereira de Magalhães - Sul Centro/Bairro ': 5,
'Rangel Pestana, Av (F) unico// ': 163,
'Rangel Pestana, Av DEC BR //unico ': 1134,
'Rangel Pestana, Av DEC CT Bairro/Centro ': 548,
'Rangel Pestana, Av DEC CT Centro/Bairro ': 66,
'Raposo Tavares, Via Capital/Interior ': 632,
'Raposo Tavares, Via Interior/Capital ': 3652,
'Reação, R único// ': 1388,
'Rebouças/ Eusébio Matoso, Av Bairro/Centro ': 8167,
'Rebouças/ Eusébio Matoso, Av Centro/Bairro ': 8720,
'Remédios, Pte Lapa/Remédios ': 1471,
'Remédios, Pte Remédios/Lapa ': 1965,
'Republica da Armenia, Vd único// ': 4197,
'República do Líbano, Av Bairro/Centro ': 750,
'República do Líbano, Av Centro/Bairro ': 788,
'República do Líbano, Av (F) Bairro/Centro ': 248,
'República do Líbano, Av (F) Centro/Bairro ': 129,
'Ribeiro Lacerda, R Abraão de Morais/Cursino ': 2,
'Ribeiro Lacerda, R Cursino/Abraão de Morais ': 21,
'Ricardo Jafet, Av Bairro/Centro ': 159,
'Ricardo Jafet, Av Centro/Bairro ': 228,
'Rio Bonito, Av Centro/Bairro ': 1,
'Rio Branco, Br do unico// ': 122,
'Rio Branco, Av Bairro/Centro ': 195,
'Rio Branco, Av Centro/Bairro ': 342,
'Robert Kennedy, Av Bairro/Centro ': 164,
'Robert Kennedy, Av Centro/Bairro ': 37,
'Roberto Abreu Sodré, Vd Bairro/Centro ': 2243,
'Roberto Abreu Sodré, Vd Centro/Bairro ': 169,
'Roque Petroni Júnior, Av Diadema/Marginal ': 1253,
'Roque Petroni Júnior, Av Marginal/Diadema ': 683,
'Roque Petroni Júnior, Av (F) Diadema/Marginal ': 881,
'Roque Petroni Júnior, Av (F) Marginal/Diadema ': 496,
'Rudge, Av/Orlando Murgel, Vd Bairro/Centro ': 484,
'Rudge, Av/Orlando Murgel, Vd Centro/Bairro ': 541,
'Rudge, Av/Orlando Murgel, Vd (F) Bairro/Centro ': 233,
'Rudge, Av/Orlando Murgel, Vd (F) Centro/Bairro ': 232,
'S.Vicente, Av Marques de (F) Barra Funda/Lapa ': 90,
'S.Vicente, Av Marques de (F) Lapa/Barra Funda ': 526,
'Sabará, Av NSra do Bairro/Centro ': 6,
'Sabará, Av NSra do Centro/Bairro ': 1,
'Salim F Maluf, Av/Tatuapé, Pt (N USAR) Marginal/Vila Prudente ': 1,
'Salim Farah Maluf, Av/Tatuapé, Pte Marginal/Vila Prudente ': 5335,
'Salim Farah Maluf, Av/Tatuapé, Pte Vila Prudente/Marginal ': 3669,
'Sapetuba, R único// ': 1637,
'Sebastião Camargo, Túnel unico// ': 4718,
'Socorro, Pte Bairro/Centro ': 1365,
'Socorro, Pte Centro/Bairro ': 1640,
'Sumaré, Av Limão/Sumaré ': 149,
'Sumaré, Av Sumaré/Limão ': 255,
'Susana Rodrigues, R unico// ': 444,
'São Vicente, Av Marq de Barra Funda/Lapa ': 856,
'São Vicente, Av Marq de Lapa/Barra Funda ': 1933,
'Sé, Pça da //unico ': 205,
'Tabapua,R (F) unico// ': 196,
'Tabapuã, R //unico ': 39,
'Tabapuã, R único// ': 482,
'Tajurás, Av dos Bairro/Centro ': 2201,
'Tajurás, Av dos Centro/Bairro ': 297,
'Tancredo Neves, Av Anchieta/Imigrantes ': 395,
'Tancredo Neves, Av Imigrantes/Anchieta ': 336,
'Teodoro Sampaio, R unico// ': 1651,
'Teotonio Vilela, Av Sen Bairro/Centro ': 41,
'Teotonio Vilela, Av Sen Centro/Bairro ': 7,
'Transamérica, Pte unico// ': 1208,
'Trib de Justiça, Túnel Ibirapuera/Marginal ': 6386,
'Trib de Justiça, Túnel Marginal/Ibirapuera ': 3397,
'Trinta e Um de Março, Vd unico// ': 1540,
'Vale/P.Maia/Tirad/S.Dumont Aeroporto/Santana ': 5988,
'Vale/P.Maia/Tirad/S.Dumont Santana/Aeroporto ': 9089,
'Vale/P.Maia/Tirad/S.Dumont (NÃO USAR) Santana/Aeroporto ': 1,
'Valerio, Av São Bairro/Centro ': 1471,
'Valerio, Av São Centro/Bairro ': 24,
'Vicente Rao, Av Prof Diadema/Marginal ': 362,
'Vicente Rao, Av Prof Marginal/Diadema ': 245,
'Vicente Rao, Av Prof (F) Diadema/Marginal ': 5,
'Vicente Rao, Av Prof (F) Marginal/Diadema ': 2,
'Vila Guilherme, Pte Bairro/Centro ': 211,
'Vila Guilherme, Pte Centro/Bairro ': 92,
'Vila Matilde, Vd Penha/Vl Matilde ': 19,
'Vila Matilde, Vd Vl Matilde/Penha ': 32,
'Vinte Três/R Berta/M Guim (NÃO USAR) Aeroporto/Santana ': 2,
'Vinte Três/R Berta/M Guimarães Aeroporto/Santana ': 9678,
'Vinte Três/R Berta/M Guimarães Santana/Aeroporto ': 10112,
'Vinte e Cinco de Março, Vd único// ': 140,
'Vital Brasil, Av Bairro/Centro ': 2983,
'Vital Brasil, Av Centro/Bairro ': 459,
'Vitor Manzini, Av Bairro/Centro ': 199,
'Vitor Manzini, Av Centro/Bairro ': 806,
'Washington Luis, Av Bairro/Centro ': 3511,
'Washington Luis, Av Centro/Bairro ': 2900,
'XXX Campo Limpo/Morato ': 7,
'XXX Morato/Campo Limpo ': 5,
'Xangai, Vd unico// ': 84}
jam_count is the dictionary listing all counts of traffic jams for each road.
The following graph plots the distribution of traffic jam counts between 2001 and 2019 for each and every road. It might seem more adapted to focus our renovations on the roads more likely to be impacted by traffic jams, and for that we may drop the roads with a small jam count.
In [5]:
sorted_jam_count = sorted(jam_count, key=jam_count.get)
In [6]:
fig = plt.figure(figsize=(12, 8))
plt.plot(gs.sort(list(jam_count.values())))
plt.xlabel("road n°")
plt.ylabel("number of traffic jams between 2001 and 2019")
plt.title(
"Number of traffic jams between 2001 and 2019 for each road in increasing order"
)
plt.show()
In [7]:
list_jam_count = gs.sort(list(jam_count.values()))
cdf = [list_jam_count[0]]
for i in range(len(list_jam_count)):
cdf.append(cdf[i] + list_jam_count[i])
cdf = gs.stack(cdf) / cdf[-1]
In [8]:
fig = plt.figure(figsize=(12, 8))
plt.plot(cdf)
plt.xlabel("road n°")
plt.title("Cumulative distribution function of traffic jams in SP")
plt.show()
The 180 most congestioned roads make up for 90% of all traffic jams in Sao Paulo between 2001 and 2019. That is where we will focus our renovation efforts.
In [9]:
roads_to_renovate = sorted_jam_count[-180:]
3. Mathematical modeling#
In the following 2 sections, we establish a precise framework, listing the hypotheses and simplifications supporting our model. In particular: - 3.1. gives an introduction to the Gamma manifold and explains how each road can be represented by a point on it. - 3.2. justifies the use of information geometry to tackle the problem at hand, by seeing a renovation effort on a given road as a tangent vector based at its associated point.
3.1. Road representation: introduction to the Gamma manifold.#
The modeling of the study relies heavily on the representation of a traffic jam as a random variable. In fact, the waiting time in a given traffic jam can be predicted by a Gamma distribution.
3.1.1. Hypotheses#
We consider that a traffic jam has a fixed exit rate, meaning that on average, in a given unit of time the same count of cars will exit the jam. The waiting time to exit the traffic jam once a car is ahead of the lane is independent of other cars and depends on the road only.
In addition, switching lanes rarely helps, and if so, to a negligible extent; furthermore a car entering the traffic jam will almost always choose the least crowded lane (all drivers are a priori mentally sane). These two observations allow to reduce the modeling of a whole traffic jam to that of a single lane, although only in representation, because cars next to each other will have the same behavior. This means that in our modelling the width of the road is not taken into account, as mentioned in the introduction.
Both of these hypotheses are central to the model.
3.1.2. Model#
In a traffic jam, you wait until every car in front of you has exited the traffic jam, meaning that the waiting time for a car entering the jam is merely the sum of the exit times of all the cars in front.
As a \(\nu\)-exponential process predicts the waiting time until one very first event (where \(\nu\) is a rate of a unit of time), a \((k,\, \nu)\)-Gamma process will predict the waiting time until the \(k\)-th event: mathematically, it is the sum of \(k\) i.i.d. \(\nu\)-exponential processes. In the context of congestion time in a traffic jam, we are summing exit times, hence the connection between waiting time and Gamma disribution.
Therefore, the congestion time of the jam follows a Gamma distribution associated to the road. Its parameters are: - \(k\), the length of the car lane (jam size) in arbitrary units; - \(\nu\), the exit time rate of the traffic jam, i.e. the number of cars (in the same arbitrary unit) that exit the traffic jam in a given amount of time, so essentially the speed of the traffic jam.
By arbitrary units we mean that there exists a number \(n\) of cars, common to every road, such that \(n\) cars will exit the jam every \(\frac{1}{\nu}\) (depending on the road) unit of time on average. From this we draw that a road with car length \(k\) is in fact as long as \(kn\) cars.
For a given road \(r\), we note \(T_r\) the congestion time that cars will have to wait in the case the traffic is jammed: \(T_r \rightsquigarrow G(k_r, \nu_r)\), with distribution:
As a road \(x_r\) can be represented by two parameters \(k_r\) and \(\nu_r\), we can consider our space of study to be the space of such parameters (i.e. \(\mathbb{(R_+^*)^2}\)).
For the following, we denote Gamma distributions’ parameters by \((\kappa_r, \gamma_r)\), where \(\kappa_r\)=\(k_r\) (expected jam size) and \(\gamma_r\)=\(\frac{k_r}{\nu_r}\) is the expected congestion time (mean of the Gamma distribution). The space of study is still \(\mathbb{(R_+^*)^2}\), and we are instantiating it in the next cell.
In [10]:
import matplotlib.pyplot as plt
from geomstats.information_geometry.gamma import (
NaturalToStandardDiffeo,
GammaDistributions,
)
space = GammaDistributions()
Let’s also adapt the exp_solver, as the default does not allow automatic differentiation due to the use of scipy.integrate.solve_ivp (we need to choose a different integrator).
In [11]:
from geomstats.numerics.ivp import GSIVPIntegrator
space.metric.exp_solver.integrator = GSIVPIntegrator(n_steps=100, step_type="euler")
For instance, on the following graph we are representing 3 roads.
In [12]:
road1 = gs.array([1.0, 1.0])
road2 = gs.array([2.0, 1.0])
road3 = gs.array([1.0, 2.0])
fig = plt.figure(figsize=(12, 8))
plt.scatter(*road1, label="road1")
plt.scatter(*road2, label="road2")
plt.scatter(*road3, label="road3")
plt.xlabel("$\\kappa$ (expected jam size)")
plt.ylabel("$\\gamma$ (expected time spent in traffic)")
plt.title(
"3 roads subject to traffic jams, represented as points on the Gamma manifold."
)
plt.legend()
plt.xlim(0, 5)
plt.ylim(0, 5)
plt.show()
Here: - road 1 is \((\kappa_1=1,\gamma_1=1)\); - road 2 is \((\kappa_2=2,\gamma_2=1)\); - road 3 is \((\kappa_3=1,\gamma_3=2)\).
This means that cars on road 1 will spend half as much time as cars on road 3 in the case of a traffic jam, on average. On the other hand, cars on road 1 and road 2 will spend the same time in traffic on average, but the line is twice as long on road 2.
3.2. Mathematical representation of renovation efforts#
3.2.1. Hypotheses#
Renovating a road initially aims at reducing the expected time spent in traffic. This means that for a given road \(x_r = (\kappa_r, \gamma_r)\), we want to reduce \(\gamma_r\) as efficiently as possible. But, the efficiency of the renovation in that regard heavily depends on the road: one can argue that it is more efficient to renovate a road where traffic jams are frequent than a road on which the traffic is almost fluid. This is where information geometry comes in handy: as a riemannian manifold, the metric of the Gamma manifold is point-dependent.
By seeing renovation as an effort in reducing the expected time in traffic, we can model the advancement of the renovation as the geodesic departing from the point representation of the road, and with initial tangent vector in the direction and orientation \(-\gamma\). This reflects the fact that the advancement of the renovation will follow the most natural path, i.e. the distribution of the waiting time of the associated road will change as little as possible throughout the renovation.
3.2.2. Model#
We decide to model a renovation effort of budget/effort \(r_i\) on road \(x_r\) as the tangent vector \(r_i \left(\begin{array}{c} 0 \\ -1 \end{array}\right)_{x_r}\), where \(\left(\begin{array}{c} 0 \\ -1 \end{array}\right)_{x}\) is the unit tangent vector at \(x\) with direction and orientation \(-\gamma\). The amount of effort/resources invested in the renovation of a given road is directly represented by the norm of the tangent vector.
Investing as much as \(r_i\) renovation resources on road \(x_r\) will result in having the renovated road \(x_r' = \exp_{x_r} \left( r_i \times \left(\begin{array}{c} 0 \\ -1 \end{array}\right)_{x_r} \right)\), where \(\exp_{x}\) is the exponential map at \(x\).
The following plot shows a comparison of similar renovations undertaken on the roads in the previous example.
In [13]:
fig = plt.figure(figsize=(12, 8))
t = gs.linspace(0, 1, 10)
plt.scatter(*road1, label="road 1")
plt.scatter(*road2, label="road 2")
plt.scatter(*road3, label="road 3")
effort = gs.array([0.0, -1.0])
effort1 = space.metric.normalize(effort, road1)
renovation1 = space.metric.geodesic(initial_point=road1, initial_tangent_vec=effort1)
renovation1 = renovation1(t)
plt.plot(*gs.transpose(renovation1), label="advancement of renovation effort on road 1")
effort2 = space.metric.normalize(effort, road2)
renovation2 = space.metric.geodesic(initial_point=road2, initial_tangent_vec=effort2)
renovation2 = renovation2(t)
plt.plot(*gs.transpose(renovation2), label="advancement of renovation effort on road 2")
effort3 = space.metric.normalize(effort, road3)
renovation3 = space.metric.geodesic(initial_point=road3, initial_tangent_vec=effort3)
renovation3 = renovation3(t)
plt.plot(*gs.transpose(renovation3), label="advancement of renovation effort on road 3")
plt.xlabel("$\\kappa$ (expected jam size)")
plt.ylabel("$\\gamma$ (expected time spent in traffic)")
plt.title("Comparison of different renovation efforts")
plt.legend()
plt.axis("equal")
plt.show()
print(
f"Road 1 renovation: expected waiting time has decreased from {road1[1]} to {str(renovation1[-1,1])[:5]}, expected jam size has increased from {road1[0]} to {str(renovation1[-1,0])[:5]}."
)
print(
f"Road 2 renovation: expected waiting time has decreased from {road2[1]} to {str(renovation2[-1,1])[:5]}, expected jam size has increased from {road2[0]} to {str(renovation2[-1,0])[:5]}."
)
print(
f"Road 3 renovation: expected waiting time has decreased from {road3[1]} to {str(renovation3[-1,1])[:5]}, expected jam size has increased from {road3[0]} to {str(renovation3[-1,0])[:5]}."
)
Road 1 renovation: expected waiting time has decreased from 1.0 to 0.409, expected jam size has increased from 1.0 to 1.443.
Road 2 renovation: expected waiting time has decreased from 1.0 to 0.536, expected jam size has increased from 2.0 to 2.995.
Road 3 renovation: expected waiting time has decreased from 2.0 to 0.818, expected jam size has increased from 1.0 to 1.443.
We observe that it is much more efficient to renovate road 3 rather than road 1 in terms of gained expected waiting time. This was expected given road 1 is much more fluid than road 3. In terms of relative time gain however, the result is the same: this is specific to Gamma distributions. In addition, renovating road 3 is more efficient than renovating road 2, either in absolute or relative time gain. We observe furthermore that investing similar efforts in renovating roads 3 and 2 result in different evolutions regarding the expected jam size: it increases by 44% in the first case and by as much as 50% in the second one. This becomes delicate especially considering the expected car line on road 2 was already long.
We notice that renovations increase the expected jam size: this can be interpreted as the fact that a renovated roads allows drivers to go faster and the lane becomes longer, in a sense the traffic becomes more diluted. This can be observed in the following plot: renovations increase at once the expected jam size and the expected exit time rate, rendering the road open to much more traffic.
In [14]:
fig = plt.figure(figsize=(12, 8))
diffeo = NaturalToStandardDiffeo()
road1 = diffeo.diffeomorphism(road1)
road2 = diffeo.diffeomorphism(road2)
road3 = diffeo.diffeomorphism(road3)
plt.scatter(*road1, label="road 1")
plt.scatter(*road2, label="road 2")
plt.scatter(*road3, label="road 3")
renovation1 = diffeo.inverse_diffeomorphism(renovation1)
renovation2 = diffeo.inverse_diffeomorphism(renovation2)
renovation3 = diffeo.inverse_diffeomorphism(renovation3)
plt.plot(*gs.transpose(renovation1), label="advancement of renovation effort on road 1")
plt.plot(*gs.transpose(renovation2), label="advancement of renovation effort on road 2")
plt.plot(*gs.transpose(renovation3), label="advancement of renovation effort on road 3")
plt.xlabel("$\\kappa$ (expected jam size)")
plt.ylabel("$\\nu$ (expected exit time rate in traffic)")
plt.title("Comparison of different renovation efforts in natural coordinates")
plt.legend()
plt.show()
The fact that these results validate our observations and expected consequences of renovations legitimates the use of information geometry to model the situation. For instance, a euclidean modeling of the situation would make no sense: all renovations would have the same impact although applied to different roads, because the norm of a tangent vector (i.e. the renovation effort) would be independent of its base point (the road).
Therefore, the key to optimizing Sao Paulo’s traffic obviously lies in maximizing the efficiency of the renovation, with limited renovation resources.
3.3. Optimization problem#
The aim is to minimize the mean expected congestion time in Sao Paulo, weighted by the frequencies \(f_i\) of traffic jams \(1 \leq i \leq n\), under the constraint of a total quantity of resources \(r\). This reads:
\begin{equation} \begin{cases} \min_{(r_i)} \sum_{i=1}^n f_i \times \exp_{x_i} \left( r_i \times \left(\begin{array}{c} 0 \\ -1 \end{array}\right)_{x_i} \right)_{\gamma} \\ \forall i \in \{1,...,n\}, r_i \geq 0 \\ \sum_{1 \leq i \leq n} r_i = r \\ \end{cases}, \end{equation}
where: - \((x_i)\) are the roads; - \(\left(\begin{array}{c} 0 \\ -1 \end{array}\right)_{x_i}\) is the unit tangent vector at \(x_i\) with direction and orientation \(-\gamma\); - \(\exp_{x_i}\) is the exponential map at \(x_i\); - for \(x \in G\) (the Gamma manifold), \(x_{\gamma}\) is its \(\gamma\) coordinate; - \(r_i\) is the resource allocated for renovating road \(i\).
We could rewrite the problem in a simpler way analytically, making use of the following results: - the relative efficiency of renovation (i.e. the ratio of expected congestion times) does not depend on the original expected congestion time of the road (\(\gamma\)); - similarly, the length of the car lane of the renovated road does not depend on the original expected congestion time of the road (\(\gamma\)).
However, we will not use these results to make way for a better computational solution of the problem.
4. Dataset processing#
First, we associate to each of the roads eligible for renovation its parameters for a Gamma distribution, through a maximum likelihood fit of the durations of traffic jams: jam_table gives, for each road \(r\), a sample of size \(n_r\) of all the traffic jams and their durations from 2001 to 2019.
In [15]:
names, kappas, gammas = [], [], []
for road in roads_to_renovate:
frame = df.loc[df["name"] == road]
sample = frame["duration"]
try:
kappa, gamma = space.maximum_likelihood_fit(sample)
if not (gs.any(gs.isnan([kappa, gamma]))):
names.append(road)
kappas.append(kappa)
gammas.append(gamma)
except:
continue
Having focused on the 180 most congestioned roads makes sense now, as the estimations for the Gamma parameters of the roads are much more relevant. Accounting for all the roads would result in having outliers in our set of roads, rendering the computation far more complex. In addition, roads with a negligible count of traffic jams in such a long time span do not necessarily call for renovation.
That is why, for the following and for the problem at hand, we can consider the following simplification: the roads eligible for renovation represent SP’s roads subject to traffic jams, i.e. the exact dataset we want to be working on.
In [16]:
dict_parameters = {"name": names, "kappa": kappas, "gamma": gammas}
data = pd.DataFrame.from_dict(dict_parameters)
To each of the roads eligible for renovation we associate a weight proportional to the number of traffic jams between 2001 and 2019.
In [17]:
good_points = list(data["name"])
weights = gs.array(list(map(jam_count.get, good_points)))
weights = weights / gs.sum(weights)
The 180 most congestioned roads of SP can be represented as follows on the Gamma manifold.
In [18]:
kappa, gamma = data["kappa"], data["gamma"]
fig = plt.figure(figsize=(12, 8))
mean = gs.array([gs.sum(weights * kappa), gs.sum(weights * gamma)])
plt.scatter(kappa, gamma, label="road eligible for renovation")
plt.scatter(*mean, color="r", s=100, label="mean road eligible for renovation")
plt.xlabel("$\\kappa$ (number of cars in arbitrary units)")
plt.ylabel("$\\gamma$ (expected time spent in traffic in hours)")
plt.title(
"Sao Paulo's roads most subject to traffic jams, as represented as points on the Gamma manifold."
)
plt.legend()
plt.show()
We observe that the vast majority of traffic jams in SP can take from 2 to 6+ hours of congestion time. On the most impactful roads (eligible for renovation), the mean waiting time is 3h 24min.
5. Solving the problem at hand#
Arbitrarily (and for computational purposes), we are allocated a total of 10 resources to allocate on the renovations. It might seem like the amount of total resources should not matter that much as the original aim is simply knowing how to allocate the total quantity of resources between all the roads eligible for renovation, but renovations are not linear.
In [19]:
total_resources = 10
In [20]:
points = gs.transpose(gs.stack([kappa, gamma]))
n_points = len(points)
We optimize the allocation of resources for renovation here.
In [21]:
from geomstats.numerics.optimizers import ScipyMinimize
minimizer = ScipyMinimize(
method="SLSQP",
constraints=(
{"type": "ineq", "fun": lambda x: total_resources - gs.sum(x)},
{"type": "ineq", "fun": lambda x: x.min()},
),
jac="autodiff",
options={"disp": False, "maxiter": 100},
tol=gs.atol,
)
In [22]:
def rebuilding(point, resources):
vec = gs.array([0.0, -1.0])
norm = resources * total_resources
tangent_vec = gs.einsum("...,...j->...j", norm, vec)
end_point = space.metric.exp(tangent_vec, point)
return end_point
def objective(resources):
end_points = rebuilding(points, resources)
gammas = end_points[:, 1]
return gs.mean(weights * gammas)
resources = total_resources * weights
res = minimizer.minimize(objective, resources)
resources = res.x
new_points = rebuilding(points, resources)
WARNING: Iteration limit reached
In [23]:
original_SP = gs.sum(gs.einsum("...,...j->...j", weights, points), axis=0)
fig = plt.figure(figsize=(16, 12))
plt.scatter(points[:, 0], points[:, 1], label="original points", s=20)
plt.scatter(*original_SP, label="original SP", s=50)
plt.scatter(new_points[:, 0], new_points[:, 1], label="points after renovation", s=20)
for i in range(n_points):
plt.arrow(
points[i, 0],
points[i, 1],
(new_points - points)[i, 0],
(new_points - points)[i, 1],
head_width=0.01,
linestyle="",
length_includes_head=True,
)
percentage = resources[i] * 100 / total_resources
if percentage > 2:
plt.text(points[i, 0], points[i, 1], f"{str(percentage)[:5]} %")
new_SP = gs.sum(gs.einsum("...,...j->...j", weights, new_points), axis=0)
plt.scatter(*new_SP, label="SP after renovation", s=50)
plt.arrow(
*original_SP,
*(new_SP - original_SP),
head_width=0.05,
linestyle="-",
length_includes_head=True,
)
plt.xlabel("$\\kappa$ (expected jam size)")
plt.ylabel("$\\gamma$ (expected time spent in traffic in hours)")
plt.title("Optimization of SP's traffic")
plt.legend()
plt.show()
Above, the percentages represent the proportion of the total resources that have been allocated to the renovation of each road: they are visible if greater than 1%.
In [24]:
original_size, original_time = original_SP
new_size, new_time = new_SP
relative_time_reduction = (original_time - new_time) / original_time
original_variance, new_variance = (
original_time**2 / original_size,
new_time**2 / new_size,
)
relative_variance_reduction = (original_variance - new_variance) / original_variance
print(
f"Mean expected congestion time has been reduced by as much as {str(relative_time_reduction*100)[:5]} % in Sao Paulo :)"
)
print(
f"Variance in congestion time has been reduced by as much as {str(relative_variance_reduction*100)[:5]} % in Sao Paulo :)"
)
Mean expected congestion time has been reduced by as much as 24.84 % in Sao Paulo :)
Variance in congestion time has been reduced by as much as 48.33 % in Sao Paulo :)
Conclusion#
We have managed to substantially reduce the mean expected congestion time in SP by as much as 25%, not at great expense of the expected jam sizes! We also happen to have halved the variance of the mean congestion time, rendering long traffic jams rarer. This is a great success!