---
title: Compte rendu stage intermodalité
---

# Travail au LaBRI

:::info
2 tâches à réaliser :
* Extraction de données multi-critères.
* Implémentation d'un algo avec préprocess.
:::

:::success
**Notations** :
* $G = (V_G, E_G)$ est un graphe.
* $V_G$ est l'enssemble des sommets du graph $G$.
* $E_G$ est l'enssemble des arrêtes du graph $G$.
* $d \in \mathbb N^*$ est ne nombre de critères des arrêtes
de $G$.
* $PATH_G(u, v)$ est l'ensemble des chemins de G
* $P_{u, v} = (P_1, ... , P_d) \in PATH_G(u, v)$ avec $u, v \in V$
est un chemin de $u$ à $v$ et dont les valeurs pour chaque
critères sont $(P_1, ..., P_d)$.
* $n \in \mathbb N^*$ correspond au nombre de sommets.
* $m \in \mathbb N^*$ correspond au nombre d'arrêtes.
* $\varepsilon \in \mathbb R^{+*}$ un nombre *petit*.
:::

## Définitions

### Graphe Statique et Graphe Temporel

* Graphe statique : lié au réseau routier, au vélo ou à la marche.


Les arrêtes portent des coût de trajet.

* Graphe temporel : lié aux transports en commun.


Les arrêtes portent des horaires de passage.

### Domination, $\varepsilon$-Couverture et Front de Pareto.

:::info
**Domination** : $P$ domine $Q$ ssi
$$
\forall i \in [\![1, d]\!], P_i \leqslant Q_i
$$

**$\varepsilon$-Couverture** : $P$ $(1+\varepsilon)$-couvre $Q$
ssi
$$
\forall i \in [\![1, d]\!], P_i \leqslant (1+\varepsilon)Q_i
$$

**Front de Pareto** : $P$ appartiens au Front de Pareto sur
$PATH_G(u,v)$ ssi
$$
\forall Q \in PATH_G(u, v), Q \text{ ne domine pas } P
$$
:::
Représentation du Front de Pareto :


:::info
**Notion de résumé** : Un résumé du Front de Pareto est un ensemble
de points $P$ tels que
$$
\forall Q \in PATH_G(u, v), Q\text{ ne }(1+\varepsilon)\text{-couvre pas }P
$$
:::
Représentation d'un résumé pour $\varepsilon = 0.85$ :


### Partitionnement de Graphe

:::info
En théorie des graphes et en algorithmique, le partitionnement
de graphe est la tâche qui consiste à diviser un graphe orienté
ou non orienté en plusieurs parties.
:::

Dans le cas des algorithmes de plus court chemin, on essaiera de
minimiser la taille de la coupe ainsi que d'avoir des parties
de tailles similaires :
$$
\cup_{i=1}^k V_i = V \\
\forall i, j \in [\![1, k]\!]^2 \quad i \neq j \quad V_i \cap V_j = \emptyset \\
\forall i \in [\![1, k]\!], |V_i| \leqslant \frac{1}{k} |V|
$$

Il existe plusieurs algorithmes effectuant un partitionnement du
graphe (ex : *Floyd-Fulkerson*).
:::danger
Il n'existe pas d'algorithme *rapide* garantissant simultanément
petite coute **et** partitions équilibrées.
:::

### Interpolation bi-linéaire
Soient $x_1, x_2, y_1, y_2 \in \mathbb R$, $Q_{11} = (x_1, y_1)$, $Q_{12} = (x_1, y_2)$,
$Q_{21} = (x_2, y_1)$ et $Q_{22} = (x_2, y_2)$ dont on connais
les images par $f: \mathbb R^2 \longrightarrow \mathbb R$.


Une approximation de l'image de $Q = (x, y) \in \mathbb R^2$ par $f$
est :
$$
f(Q) \approx \frac{1}{(x_2-x_1)(y_2-y_1)}
\begin{bmatrix}
x_2-x & x-x_1
\end{bmatrix}
\begin{bmatrix}
f(Q_{11}) & f(Q_{12})\\
f(Q_{21}) & f(Q_{22})
\end{bmatrix}
\begin{bmatrix}
y_2-y \\
y-y_1
\end{bmatrix}
$$

## Mesures

* **$\varepsilon$ à posteriori**

Le $\varepsilon$ minimal tel que les éléments du résumé
$\varepsilon$-couvrent le Front de Pareto. On cherche à avoir
un $\varepsilon$ le plus petit possible avec le moins de
propositions possible dans le résumé. Concis et Précis.

* **Distance moyenne $d_C$**

Distance euclidienne moyenne entre les éléments du résumé et
ceux du Front de Pareto. On la définie ainsi, $\Pi^*$ étant
le Front de Pareto obtimal et $\Pi$ la proposition :
$$
d_c(\pi^*, \pi) =
\sqrt{\sum_{i = 0}^d(\pi^*_i - \pi_i)^2}
$$
On voit ici les éléments du Front de Pareto comme des points dans
l'espace composé des critères.
$$
d_C(\Pi^*, \Pi) = \frac{1}{|\Pi^*|}
\sum_{\pi^* \in \Pi^*} \underset{\pi \in \Pi}{min} \space d_c(\pi^*, \pi)
$$

* **Distance moyenne $d_J$**

Distance de Jaccard moyenne entre les éléments du résumé et
ceux du Front de Pareto. La distance de Jaccard est définie ainsi :
$$
d_j(\pi^*, \pi) =
\frac{|(\pi^*\cup\pi)| - |(\pi^*\cap\pi)|}{|(\pi^*\cup\pi)|}
$$
On voit ici les éléments du Front de Pareto comme des ensembles
d'arrêtes.
$$
d_J(\Pi^*, \Pi) = \frac{1}{|\Pi^*|}
\sum_{\pi^* \in \Pi^*} \underset{\pi \in \Pi}{min} \space d_j(\pi^*, \pi)
$$

Dans les cas de $d_C$ et $d_J$, on cherche à les minimiser.
## Critères

:::info
Liste non exhaustive :
* **Dénivelé/Effort physique**
* **Coût**
* **Émission de $CO_2$**
* **Fluidité du trajet (vitesse moyenne/importance des routes)**\
global importance (osm)\
charger données de Bordeaux
* Temps
* Nombre de correspondance
* Temps entre correspondances
* Temps de marche total
:::

Certains critère a un côté *personnalisation* important.
(Dénivelé, temps, coût de péage)

Choix des critères :
* Accessibilité
* Couverture
* intérêt (produit/stratégie)

### Dénivelation

Données OSM touchant uniquement au vélo et à la marche.
Comment intégrer la donnée de dénivelation aux données OSM ?

:::info
Propositions de sources :
* ESA, projet copernicus (Europe) : précision ??m
* OSRM, basé sur SRTM (Monde) : précision ~100m
* MNT Intermap (Europe de l'Ouest) : ~5m
:::

:::warning
rechercher du côté de osmosis.
> https://wiki.openstreetmap.org/wiki/Osmosis\
> https://github.com/locked-fg/osmosis-srtm-plugin
:::

La plus part des sources de données d'élévation la donne sous la
forme d'une image ayant une valeur pour chaque pixel.
On peut utiliser l'interpolation bi-linéaire pour simuler une
précision meilleure que celle de la taille d'un pixel.

Représentation du dénivelé : pourcentage de pente ? hauteur ?

http://confluence/display/Team/Etude+Raster+Intermap\
https://wiki.openstreetmap.org/wiki/SRTM\
https://www.eea.europa.eu/data-and-maps/data/eu-dem\
http://srtm.csi.cgiar.org/srtmdata/\
https://makina-corpus.com/blog/metier/2018/calcul-ditineraires-pietons-avec-osrm\
https://gitlab.mappy.priv/dt.lbs/redpig-process/blob/master/processes/intermap/build_tiles.py\
https://github.com/Project-OSRM/osrm-backend/wiki/Integrating-third-party-raster-data

* OSRM :

Dans OSRM, l'import des données de dénivélation (provenant de SRTM)
est fait via l'outil "raster_source".

La donnée d'élévation est sous forme d'une grille dans un fichier
plaintext ASCII. Ce fichier contiens 6 lignes de metadata au début :

ncols         6001
nrows         6001
xllcorner     -125.00041606132
yllcorner     34.999583357538
cellsize      0.00083333333333333
NODATA_value  -9999

Lorsque viens le moment de charger le niveau d'élévation, un appel
est fait avec la *latitude* et *longitude* de l'endroit demandé.

OSMR n'intègre pas la donnée d'élévation dans la donnée OSM mais,
les utilise séparément en connaissant la latitude et la longitude
d'est points de la polyline OSM.

### Coût

Carburant voiture :
http://confluence/pages/viewpage.action?pageId=24678477

Île-de-France et Toulouse :
http://confluence/display/PRODUITS/Tarification+TC

### Émission de CO$_2$

http://confluence/pages/viewpage.action?pageId=31373169

### Fluidité du trajet

utiliser les FRC ?

## Algorithmes Multi-Critères

* Basés sur Dijkstra(MLS)
* Basés sur Bellman-Ford
* NAMOA$^*$
* McRAPTOR
* CSA
* McHL

### Hub Labelling

On construit $L(s)$ *(en orange)* et $L^{-1}(t)$ *(en vert)* de
sorte que :
* $L(s) \cap L^{-1}(t) \neq \emptyset$
* $L(s) \cap L^{-1}(t)$ contienne un sommet sur un plus court
chemin de $s$ à $t$.

Le calcul des Hubs est non trivial, cependant, ont peut utiliser
tous les sommets d'une coupe en tant que Hub.

On pourra utiliser une structure de coupes récursive pour la
génération de nos Hub.


Lorsque deux sommets sont dans la même partition, alors ils sont
suffisemment proches pour que une méthode *naïve* tel que A$^*$
pour calculer un plus court chemin.

## Misc

* **BRouter** Calcul d'itinéraire orienté vélo avec un systeme de****
profil pour les capacités physiques.
* **Zotero** Bibliographie en ligne.
* **DBLP** Source de papier scientifiques

## Récapitulatif des Algorithmes

| | temporel | statique |
| ---------------:|:-------------------:|:------------------------------------------------------:|
| Type de donénes | Transport en Commun | Voiture/Vélo/Marche |
| Algorithmes MC | McRAPTOR, CSA | MLS (McDijkstra), Bellman-Ford, NAMOA$^*$, CHMC?, McHL |

## Algorithmes multimodaux

:::success
**Notations générales** :
* $G_T = (V_{G_T}, E_{G_T})$ est un graphe temporel.
* $G_S = (V_{G_S}, E_{G_S})$ est un graphe statique.
* $V_T \subseteq V_S$
* $s, t \in V_S$
* $\forall s_1, s_2 \in V_T, PCC_{G_T}(s_1, s_2)$ est connu (ou calculable).
> RAPTOR, CSA, ...
* $\forall s_1, s_2 \in V_T, PCC_{G_S}(s_1, s_2)$ est connu (ou calculable).
> Dijkstra, HL, CH, ...

**Notations pour $G_T$** :
* $K$ lignes de $L_K \leqslant L$ stations
* $J_1, \dots, J_K \leqslant J$ voyages
* Nombre total d'horaires
$$
\sum_{i \leqslant K} J_i L_i \leqslant kJL
$$
:::

### RAPTOR

:::info
cf. https://gitlab.mappy.priv/dt.lbs/tc/-/wikis/itineraires/algorithmes
:::

Complexité moyenne : $O(kLK(1+LK)+JK)$ ?

## Références

* McHL\
Yoan Picchi\
Juin-Août 2019

* Route Planning in Transportation Network\
Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann,
Thomas Pajor, Peter Sanders, Dorothea Wagner and Renato F. Werneck\
11 November 2016
* Practical Multicriteria Urban Bicycle Routing\
Jan Hrnčíř, Pavol Žilecký, Qing Song and Michal Jakob\
3 march 2017
* Un algorithme d'approximation pour le calcul de plus courts
chemins multi-critères\
Nicolas Hanusse, David Ilcinkas et Antonin Lentz

#### questions
:::info
Liens entre graphe TC et routier ?\
regarder Navitia\
Complexité de RAPTOR ?\
Formats utilisés par Mappy ?\
travel time function, OSM-like, on peut utiliser le DIMACS sauf pour le trafic historique\
Stockage des transferts ? (second plan)\
ask aline/william
:::

## Réunion avec Cyril et Alline

Intégration de la dénivélation.
Ajout d'un critère de coût possible.

Liens entre le multicritère et le multimodal ?
bien présenter l'explosion combinatoire lors du passage en multimodal.

Ce que les gens demandent :
plusieurs transport à disposition => combiner tous les moyens de transport avec la possibilité d'éliminer un un moyen de transport.

proposition de 4/5 alternatives avec différents moyens de transport:
- piéton + transport
- voiture + transport
- vélo + transport
- etc ...

Obligé de relancer le calcul à 0 pour chaque modèle ?

sujet de la propriété intellectuelle abordé. (ni à François ni à Clément de le gérer)

Solution de Rome-to-Ryo et prolongation post-stage
méthode simple MC = combinaison linéaire de critères.

Solution multimodale : RAPTOR enrichi par graphe de transferts.

## Mercredi 1er avril

Rapport informations nécéssaires pour implémentation de RAPTOR-MM, avec du pseudo code.