Notebook source code: notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb
Run it yourself on binder Binder badge

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.

<img src='figures/sao_paulo_traffic.jpg' width=600px>
Figure 1: Sao Paulo: A city with 180km traffic jams -- BBC News

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.

Setup#

 In [22]:
import os
import subprocess

geomstats_gitroot_path = subprocess.check_output(
    ["git", "rev-parse", "--show-toplevel"], universal_newlines=True
)

os.chdir(geomstats_gitroot_path[:-1])

print("Working directory: ", os.getcwd())
Working directory:  C:\Users\Jules\Documents\geomstats
 In [23]:
import matplotlib.pyplot as plt
import geomstats.backend as gs
import pandas as pd

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.

 In [24]:
from geomstats.datasets.utils import load_sao_paulo
df, jam_count = load_sao_paulo()
INFO: Data has already been downloaded... using cached file ('C:\Users\Jules\.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 [25]:
df
 Out [25]:
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 [26]:
jam_count
 Out [26]:
{'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 [27]:
sorted_jam_count = sorted(jam_count, key = jam_count.get)
 In [28]:
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()
../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_20_0.png
 In [29]:
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 = cdf / cdf[-1]
 In [30]:
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()
../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_22_0.png

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 [31]:
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.

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:

\[\forall t>0, \, \mathbb{f}(t) = \frac{\nu_r^{k_r}}{\Gamma(k_r)} t^{k_r-1} e^{-\nu_r t}.\]
<img src='figures/car_lane.png' width=600px>

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 [32]:
import matplotlib.pyplot as plt
from geomstats.information_geometry.gamma import *

space = GammaDistributions()

For instance, on the following graph we are representing 3 roads.

 In [33]:
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()
../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_37_0.png

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 [34]:
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]}.")

../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_45_0.png
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 [35]:
fig = plt.figure(figsize=(12,8))

road1 = space.natural_to_standard(road1)
road2 = space.natural_to_standard(road2)
road3 = space.natural_to_standard(road3)

plt.scatter(*road1, label = 'road 1')
plt.scatter(*road2, label = 'road 2')
plt.scatter(*road3, label = 'road 3')

renovation1 = space.standard_to_natural(renovation1)
renovation2 = space.standard_to_natural(renovation2)
renovation3 = space.standard_to_natural(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()
../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_47_0.png

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\).

Remark#

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 [36]:
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 [37]:
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 [38]:
good_points = list(data["name"])
weights = 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 [39]:
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()
../_images/notebooks_18_real_world_applications__sao_paulo_traffic_optimization_63_0.png

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 [40]:
total_resources = 10
 In [41]:
points = gs.transpose(gs.stack([kappa, gamma]))
n_points = len(points)

We optimize the allocation of resources for renovation here:

 In [42]:
original_SP = gs.sum(gs.einsum("...,...j->...j", weights, points), axis=0)

def rebuilding(point, resources):
    n_points = point.shape[0] if len(point.shape)>1 else 1
    vec = gs.tile([gs.array([0.0,-1.0])], (n_points, 1))
    norm = resources * total_resources
    tangent_vec = gs.einsum("...,...j->...j", norm, vec)
    end_point = space.metric.exp(tangent_vec, point, n_steps=100)
    return end_point

def objective(resources):
    end_points = rebuilding(points, resources)
    gammas = end_points[:,1]
    return gs.mean(weights*gammas)

objective_with_grad = gs.autodiff.value_and_grad(objective, to_numpy=True)

resources = total_resources * weights

res = minimize(
    objective_with_grad,
    resources,
    method="SLSQP",
    constraints=({'type': 'ineq', 'fun': lambda x: total_resources - gs.sum(x)},
    {'type': 'ineq', 'fun': lambda x: x.min()},
    ),
    jac=True,
    options={"disp": False, "maxiter": 100},
    tol=gs.atol,
)

resources = res.x

new_points = rebuilding(points, resources)

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=.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=.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()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
c:\Users\Jules\Documents\Geomstats\notebooks\18_real_world_applications__sao_paulo_traffic_optimization.ipynb Cell 71' in <cell line: 16>()
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=12'>13</a>     gammas = end_points[:,1]
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=13'>14</a>     return gs.mean(weights*gammas)
---> <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=15'>16</a> objective_with_grad = gs.autodiff.value_and_grad(objective, to_numpy=True)
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=17'>18</a> resources = total_resources * weights
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=19'>20</a> res = minimize(
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=20'>21</a>     objective_with_grad,
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=21'>22</a>     resources,
   (...)
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=28'>29</a>     tol=gs.atol,
     <a href='vscode-notebook-cell:/c%3A/Users/Jules/Documents/Geomstats/notebooks/18_real_world_applications__sao_paulo_traffic_optimization.ipynb#ch0000070?line=29'>30</a> )

File ~\Documents\geomstats\geomstats\_backend\numpy\autodiff.py:23, in value_and_grad(*args, **kwargs)
     21 def value_and_grad(*args, **kwargs):
     22     """Return an error when using automatic differentiation with numpy."""
---> 23     raise RuntimeError(
     24         "Automatic differentiation is not supported with numpy backend. "
     25         "Use autograd, pytorch or tensorflow backend instead.\n"
     26         "Change backend via the command "
     27         "export GEOMSTATS_BACKEND=autograd in a terminal."
     28     )

RuntimeError: Automatic differentiation is not supported with numpy backend. Use autograd, pytorch or tensorflow backend instead.
Change backend via the command export GEOMSTATS_BACKEND=autograd in a terminal.

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 [ ]:
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 :)")

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!