<figure><img src="image_1.png" /></figure>

HAL
open science

# Algorithmes d'apprentissage pour le cyclisme urbain : modèles implicites et infrastructure dynamique

Lucas Magnana

<figure><img src="image_2.png" /></figure>

## To cite this version:

Lucas Magnana. Algorithmes d'apprentissage pour le cyclisme urbain: modèles implicites et infrastructure dynamique. Informatique [cs]. INSA LYON, 2024. Français. NNT: 2024ISAL0019. tel-04487508

HAL Id: tel-04487508

https://hal.science/tel-04487508

Submitted on 3 Mar 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.
## THESE de DOCTORAT DE L'INSA LYON,
membre de l'Université de Lyon

Ecole Doctorale EDA 512
InfoMaths

**Spécialité/ discipline de doctorat :**
Informatique

Soutenue publiquement le 14/02/2024, par :
**Lucas Magnana**

# Algorithmes d'apprentissage pour le cyclisme urbain : modèles implicites et infrastructure dynamique

Devant le jury composé de :

<table><tr><td>DUCOURTHIAL Bertrand</td><td>Professeur des Universités, Heudiasyc</td><td>Président</td></tr><tr><td>MITTON Nathalie<br>BILLOT Romain</td><td>Directrice de Recherche, INRIA Lille-Nord Europe<br>Professeur des Universités, IMT Atlantique</td><td>Rapportrice<br>Rapporteur</td></tr><tr><td>GARIN Federica<br>GARCIA Christophe<br>ROCHE Stéphane</td><td>Chargée de Recherche, INRIA Grenoble<br>Professeur des Universités, INSA Lyon<br>Professeur des Universités, Université Laval</td><td>Examinatrice<br>Examinateur<br>Examinateur</td></tr><tr><td>RIVANO Hervé<br>CHIABAUT Nicolas</td><td>Professeur des Universités, INSA Lyon<br>Directeur des Nouvelles Mobilités,<br>Département de la Haute-Savoie</td><td>Directeur de thèse<br>Directeur de thèse</td></tr></table>
Référence : TH1079_MAGNANA Lucas

L'INSA Lyon a mis en place une procédure de contrôle systématique via un outil de détection de similitudes (logiciel Compilatio). Après le dépôt du manuscrit de thèse, celui-ci est analysé par l'outil. Pour tout taux de similarité supérieur à 10%, le manuscrit est vérifié par l'équipe de FEDORA. Il s'agit notamment d'exclure les auto-citations, à condition qu'elles soient correctement référencées avec citation expresse dans le manuscrit.

Par ce document, il est attesté que ce manuscrit, dans la forme communiquée par la personne doctorante à l'INSA Lyon, satisfait aux exigences de l'Etablissement concernant le taux maximal de similitude admissible.
Département FEDORA – INSA Lyon - Ecoles Doctorales

<table><thead><tr><th>SIGLE</th><th>ECOLE DOCTORALE</th><th>NOM ET COORDONNEES DU RESPONSABLE</th></tr></thead><tbody><tr><td>ED 206<br>CHIMIE</td><td><strong>CHIMIE DE LYON</strong><br>https://www.edchimie-lyon.fr<br>Sec. : Renée EL MELHEM<br>Bât. Blaise PASCAL, 3e étage<br>secretariat@edchimie-lyon.fr</td><td><strong>M. Stéphane DANIELE</strong><br>C2P2-CPE LYON-UMR 5265<br>Bâtiment F308, BP 2077<br>43 Boulevard du 11 novembre 1918<br>69616 Villeurbanne<br>directeur@edchimie-lyon.fr</td></tr><tr><td>ED 341<br>E2M2</td><td><strong>ÉVOLUTION, ÉCOSYSTÈME, MICROBIOLOGIE, MODÉLISATION</strong><br>http://e2m2.universite-lyon.fr<br>Sec. : Bénédicte LANZA<br>Bât. Atrium, UCB Lyon 1<br>Tél : 04.72.44.83.62<br>secretariat.e2m2@univ-lyon1.fr</td><td><strong>Mme Sandrine CHARLES</strong><br>Université Claude Bernard Lyon 1<br>UFR Biosciences<br>Bâtiment Mendel<br>43, boulevard du 11 novembre 1918<br>69622 Villeurbanne CEDEX<br>e2m2.codir@listes.univ-lyon1.fr</td></tr><tr><td>ED 205<br>EDISS</td><td><strong>INTERDISCIPLINAIRE SCIENCES-SANTÉ</strong><br>http://ediss.universite-lyon.fr<br>Sec. : Bénédicte LANZA<br>Bât. Atrium, UCB Lyon 1<br>Tél : 04.72.44.83.62<br>secretariat.ediss@univ-lyon1.fr</td><td><strong>Mme Sylvie RICARD-BLUM</strong><br>Laboratoire ICBMS - UMR 5246 CNRS - Université Lyon 1<br>Bâtiment Raulin - 2ème étage Nord<br>43 Boulevard du 11 novembre 1918<br>69622 Villeurbanne Cedex<br>Tél : +33(0)4 72 44 82 32<br>sylvie.ricard-blum@univ-lyon1.fr</td></tr><tr><td>ED 34<br>EDML</td><td><strong>MATÉRIAUX DE LYON</strong><br>http://ed34.universite-lyon.fr<br>Sec. : Yann DE ORDENANA<br>Tél : 04.72.18.62.44<br>yann.de-ordenana@ec-lyon.fr</td><td><strong>M. Stéphane BENAYOUN</strong><br>Ecole Centrale de Lyon<br>Laboratoire LTDS<br>36 avenue Guy de Collongue<br>69134 Ecully CEDEX<br>Tél : 04.72.18.64.37<br>stephane.benayoun@ec-lyon.fr</td></tr><tr><td>ED 160<br>EEA</td><td><strong>ÉLECTRONIQUE, ÉLECTROTECHNIQUE, AUTOMATIQUE</strong><br>https://edeea.universite-lyon.fr<br>Sec. : Philomène TRECOURT<br>Bâtiment Direction INSA Lyon<br>Tél : 04.72.43.71.70<br>secretariat.edeea@insa-lyon.fr</td><td><strong>M. Philippe DELACHARTRE</strong><br>INSA LYON<br>Laboratoire CREATIS<br>Bâtiment Blaise Pascal, 7 avenue Jean Capelle<br>69621 Villeurbanne CEDEX<br>Tél : 04.72.43.88.63<br>philippe.delachartre@insa-lyon.fr</td></tr><tr><td>ED 512<br>INFOMATHS</td><td><strong>INFORMATIQUE ET MATHÉMATIQUES</strong><br>http://edinfomaths.universite-lyon.fr<br>Sec. : Renée EL MELHEM<br>Bât. Blaise PASCAL, 3e étage<br>Tél : 04.72.43.80.46<br>infomaths@univ-lyon1.fr</td><td><strong>M. Hamamache KHEDDOUCI</strong><br>Université Claude Bernard Lyon 1<br>Bât. Nautibus<br>43, Boulevard du 11 novembre 1918<br>69 622 Villeurbanne Cedex France<br>Tél : 04.72.44.83.69<br>direction.infomaths@listes.univ-lyon1.fr</td></tr><tr><td>ED 162<br>MEGA</td><td><strong>MÉCANIQUE, ÉNERGÉTIQUE, GÉNIE CIVIL, ACOUSTIQUE</strong><br>http://edmega.universite-lyon.fr<br>Sec. : Philomène TRECOURT<br>Tél : 04.72.43.71.70<br>Bâtiment Direction INSA Lyon<br>mega@insa-lyon.fr</td><td><strong>M. Etienne PARIZET</strong><br>INSA Lyon<br>Laboratoire LVA<br>Bâtiment St. Exupéry<br>25 bis av. Jean Capelle<br>69621 Villeurbanne CEDEX<br>etienne.parizet@insa-lyon.fr</td></tr><tr><td>ED 483<br>ScSo</td><td><strong>ScSo<sup>1</sup></strong><br>https://edsciencessociales.universite-lyon.fr<br>Sec. : Mélina FAVETON<br>Tél : 04.78.69.77.79<br>melina.faveton@univ-lyon2.fr</td><td><strong>M. Bruno MILLY</strong> (INSA : J.Y. TOUSSAINT)<br>Univ. Lyon 2 Campus Berges du Rhône<br>18, quai Claude Bernard<br>69365 LYON CEDEX 07<br>Bureau BEL 319<br>bruno.milly@univ-lyon2.fr</td></tr></tbody></table>

<footnote n="1">¹ ScSo : Histoire, Géographie, Aménagement, Urbanisme, Archéologie, Science politique, Sociologie, Anthropologie</footnote>
Résumé

L'augmentation de l'utilisation du vélo comme mode de transport est essentielle pour diminuer la congestion ainsi que la pollution dans les villes. Le développement de nouvelles technologies ainsi qu'une prise de conscience des dangers du dérèglement climatique ont permis entre autres une augmentation du nombre de cyclistes dans les villes au cours des 20 dernières années. Cela s'est naturellement accompagné de nouveaux moyens de récupérer des données comportementales de cyclistes, diversifiant et multipliant les jeux de données existants. Ces données peuvent être utilisées pour affiner les politiques urbaines visant à augmenter la part modale du vélo dans les transports urbains. L'objectif de cette thèse est d'utiliser certaines données comportementales de cyclistes ainsi que des algorithmes récents d'intelligence artificielle pour créer des outils innovants d'aide aux politiques urbaines d'incitation au cyclisme. Dans un premier temps, un état de l'art des différentes sources de données de comportements de cyclistes est dressé. Cet état de l'art permet de se rendre compte de la diversité ainsi que du nombre de jeux de données, mais aussi des difficultés d'utilisation accompagnant chaque source. Cet état de l'art est aussi l'occasion de justifier les sources de données utilisées ensuite. Dans un second temps, une méthode de création de modèles de choix d'itinéraire implicites est développée à partir de traces GPS. Les modèles créés avec cette méthode permettent de générer un itinéraire cyclable à partir d'une origine et d'une destination. Le développement d'un modèle commence par l'identification des segments de route préférés par les cyclistes ayant généré les traces GPS. Un réseau de neurones artificiels choisit ensuite un groupe de segments de route préférés pertinents à partir d'une origine et d'une destination. Une pondération de graphe routier est ensuite effectuée à l'aide des segments de route sélectionnés pour générer un itinéraire cyclable. Les modèles créés permettent de créer des itinéraires plus proches de comportements réels de cyclistes lorsque comparés à d'autres méthodes de génération d'itinéraires. Enfin, un feu de signalisation intelligent permettant de sécuriser le passage des cyclistes à l'intersection qu'il régule est développé. L'utilisation de l'intelligence artificielle permet de séparer les flux de vélos et de véhicules motorisés en limitant l'impact sur le trafic à l'intersection. Les simulations dans lesquelles ce feu est testé ont un volume de trafic de voitures et de vélos réaliste grâce à l'utilisation de données de compteurs. La méthode d'apprentissage utilisée pour la régulation surpasse les performances d'autres méthodes de gestion de feu utilisées en comparaison.
# Table des matières

## Résumé

## 1 Introduction 1

## 2 Les sources de données 5

2.1 Les questionnaires de préférence 6

2.2 Les systèmes de vélo en libre service 9

2.3 Les capteurs GPS 12

2.3.1 Strava Metro 14

2.3.2 Véléval 15

2.3.3 MonRésoVélo 16

2.4 Les comptages de vélos 17

2.5 Positionnement 19

2.6 Résumé 22

## 3 Modèles de choix d'itinéraire implicites 24

3.1 Introduction 24

3.2 Détail des données 26

3.2.1 Traces expérimentées 26

3.2.2 Traces générées 27

3.2.3 Comparaisons des traces expérimentées et des traces générées 27

Cartes de chaleurs 29

CDF 31

Suppression des traces faisant de trop gros détours 32

3.2.4 Résumé de la section 33

3.3 Identification des segments de route préférés 33

3.3.1 Métriques de distance 33

Distance personnalisée 34

Distance géodésique 35

3.3.2 Algorithmes de clustering 35

DBSCAN 35

k-médoïdes 35

3.3.3 Paramétrage 37

DBSCAN 39

k-médoïdes 40

Algorithmes et paramètres retenus 43

3.3.4 Analyse visuelle des plus grands clusters 44

3.3.5 Résumé de la section 48

3.4 Générateur de traces basées sur l'expérience 49

3.4.1 Coefficient de cyclabilité 49

3.4.2 Modification du graphe routier 49

3.4.3 Qualité des traces basées sur l'expérience 50

3.4.4 Traces de comparaison 50
<table>
  <tbody>
    <tr>
      <td>3.4.5</td>
      <td>Résultats</td>
      <td>51</td>
    </tr>
    <tr>
      <td></td>
      <td>Veleval</td>
      <td>51</td>
    </tr>
    <tr>
      <td></td>
      <td>MonRésoVélo</td>
      <td>53</td>
    </tr>
    <tr>
      <td>3.4.6</td>
      <td>Résumé de section</td>
      <td>53</td>
    </tr>
    <tr>
      <td>3.5</td>
      <td>Classifieur</td>
      <td>54</td>
    </tr>
    <tr>
      <td></td>
      <td>3.5.1 Réseau de neurones LSTM</td>
      <td>55</td>
    </tr>
    <tr>
      <td></td>
      <td>3.5.2 Prétraitement des traces</td>
      <td>56</td>
    </tr>
    <tr>
      <td></td>
      <td>3.5.3 Structure du classifieur et hyperparamètrage</td>
      <td>57</td>
    </tr>
    <tr>
      <td></td>
      <td>3.5.4 Performances</td>
      <td>57</td>
    </tr>
    <tr>
      <td></td>
      <td>3.5.5 Résumé de la section</td>
      <td>58</td>
    </tr>
    <tr>
      <td>3.6</td>
      <td>Modèles finaux</td>
      <td>59</td>
    </tr>
    <tr>
      <td></td>
      <td>3.6.1 Analyse quantitative</td>
      <td>59</td>
    </tr>
    <tr>
      <td></td>
      <td>3.6.2 Analyse visuelle de traces basées sur l'expérience</td>
      <td>60</td>
    </tr>
    <tr>
      <td></td>
      <td>3.6.3 Résumé de la section</td>
      <td>62</td>
    </tr>
    <tr>
      <td>3.7</td>
      <td>Conclusion et discussion</td>
      <td>63</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Feu de circulation intelligent pour cyclistes</td>
      <td>66</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Introduction</td>
      <td>66</td>
    </tr>
    <tr>
      <td></td>
      <td>4.1.1 Les cyclistes et feux de signalisation</td>
      <td>66</td>
    </tr>
    <tr>
      <td></td>
      <td>4.1.2 DRL pour le contrôle de feux de signalisation en simulation</td>
      <td>67</td>
    </tr>
    <tr>
      <td></td>
      <td>4.1.3 Positionnement</td>
      <td>68</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Apprentissage par renforcement profond</td>
      <td>68</td>
    </tr>
    <tr>
      <td></td>
      <td>4.2.1 Double Dueling Deep Q-Network (3DQN)</td>
      <td>69</td>
    </tr>
    <tr>
      <td></td>
      <td>Deep Q-Network</td>
      <td>69</td>
    </tr>
    <tr>
      <td></td>
      <td>Double Deep Q-Network</td>
      <td>70</td>
    </tr>
    <tr>
      <td></td>
      <td>Dueling Deep Q-Network</td>
      <td>70</td>
    </tr>
    <tr>
      <td></td>
      <td>Algorithme final</td>
      <td>70</td>
    </tr>
    <tr>
      <td></td>
      <td>4.2.2 Proximal Policy Optimization</td>
      <td>71</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Approche DRL</td>
      <td>72</td>
    </tr>
    <tr>
      <td></td>
      <td>4.3.1 Environnement</td>
      <td>72</td>
    </tr>
    <tr>
      <td></td>
      <td>4.3.2 États</td>
      <td>72</td>
    </tr>
    <tr>
      <td></td>
      <td>4.3.3 Actions</td>
      <td>73</td>
    </tr>
    <tr>
      <td></td>
      <td>4.3.4 Récompenses</td>
      <td>73</td>
    </tr>
    <tr>
      <td></td>
      <td>Fonction de récompenses</td>
      <td>74</td>
    </tr>
    <tr>
      <td></td>
      <td>Facteur d'étalement</td>
      <td>74</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Simulation de l'environnement</td>
      <td>74</td>
    </tr>
    <tr>
      <td></td>
      <td>4.4.1 Environnement simulé</td>
      <td>74</td>
    </tr>
    <tr>
      <td></td>
      <td>4.4.2 Données de comptage et demande de trafic</td>
      <td>75</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Entraîvements</td>
      <td>76</td>
    </tr>
    <tr>
      <td></td>
      <td>4.5.1 Architecture des réseaux de neurones</td>
      <td>76</td>
    </tr>
    <tr>
      <td></td>
      <td>4.5.2 Hyperparamètrage</td>
      <td>78</td>
    </tr>
    <tr>
      <td></td>
      <td>4.5.3 Performances</td>
      <td>79</td>
    </tr>
    <tr>
      <td></td>
      <td>Agent 3DQN</td>
      <td>79</td>
    </tr>
    <tr>
      <td></td>
      <td>Agent PPO</td>
      <td>80</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Résultats</td>
      <td>83</td>
    </tr>
    <tr>
      <td></td>
      <td>4.6.1 Approches de comparaison</td>
      <td>83</td>
    </tr>
    <tr>
      <td></td>
      <td>4.6.2 Résultats horaires</td>
      <td>84</td>
    </tr>
    <tr>
      <td></td>
      <td>4.6.3 Robustesse aux changements du trafic vélos</td>
      <td>85</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Analyse du comportement du feu</td>
      <td>89</td>
    </tr>
    <tr>
      <td></td>
      <td>4.7.1 Journée entière</td>
      <td>90</td>
    </tr>
    <tr>
      <td></td>
      <td>4.7.2 Heure de pointe</td>
      <td>91</td>
    </tr>
  </tbody>
</table>
<table><tr><td>4.8 Conclusion et discussion</td><td>93</td></tr><tr><td>5 Conclusion</td><td>94</td></tr><tr><td>5.1 Résumé</td><td>94</td></tr><tr><td>5.2 Discussion et perspectives</td><td>95</td></tr><tr><td>A Distribution des véhicules comptés à Paris</td><td>98</td></tr><tr><td>Bibliographie</td><td>99</td></tr></table>
# Table des figures

<table><tr><td>1.1 Diagramme résumant cette thèse.</td><td>4</td></tr><tr><td>2.1 Exemple de question posée par Tilahun et al.[10]</td><td>8</td></tr><tr><td>2.2 Carte contenant une partie des données ouvertes de Velo'v, le BSS de Lyon.</td><td>10</td></tr><tr><td>2.3 Carte affichant certaines données Strava ajoutées au graphe routier de la ville de Glasgow.</td><td>15</td></tr><tr><td>2.4 Carte affichant certaines traces GPS du jeu de donnée Véléval.</td><td>16</td></tr><tr><td>2.5 Visuel de l'application MonRésoVélo.</td><td>17</td></tr><tr><td>2.6 Carte montrant les compteurs automatiques de vélos dans la métro-pole de Lyon.</td><td>18</td></tr><tr><td>3.1 Diagramme résumant la méthode de création de modèles de choix d'itinéraire implicites présentée dans ce chapitre.</td><td>25</td></tr><tr><td>3.2 CDF des différences de distances entre les traces expérimentées et les traces générées des jeux de données.</td><td>28</td></tr><tr><td>3.3 Cartes de chaleur des traces expérimentées (à gauche) et des traces générées (à droite) du jeu de données Véléval (Lyon).</td><td>30</td></tr><tr><td>3.4 Cartes de chaleur des traces expérimentées (à gauche) et des traces générées (à droite) du jeu de données MonRésoVélo (Montréal).</td><td>30</td></tr><tr><td>3.5 CDF des différences de distances entre les traces expérimentées et les traces générées des jeux de données après la suppression des traces faisant de trop gros détours.</td><td>32</td></tr><tr><td>3.6 Exemple graphique de l'intersection entre les ensembles étendus de 2 traces.</td><td>34</td></tr><tr><td>3.7 Évolution du nombre de grands clusters (courbe noire), du score de silhouette moyen (courbe bleue), du nombre de clusters (courbe rouge) et du bruit (courbe verte) des clusters créés par DBSCAN selon ε pour le jeu de données Véléval.</td><td>41</td></tr><tr><td>3.8 Évolution du nombre de grands clusters (courbe noire), du score de silhouette moyen (courbe bleue), du nombre de clusters (courbe rouge) et du bruit (courbe verte) des clusters créés par DBSCAN selon ε pour le jeu de données MonRésoVélo.</td><td>42</td></tr><tr><td>3.9 Évolution du nombre de grands clusters (courbe noire) et du score de silhouette moyen (courbe bleue) des clusters créés par k-médoïdes selon k pour le jeu de données Véléval.</td><td>43</td></tr><tr><td>3.10 Évolution du nombre de grands clusters (courbe noire) et du score de silhouette moyen (courbe bleue) des clusters créés par k-médoïdes selon k pour le jeu de données MonRésoVélo.</td><td>44</td></tr><tr><td>3.11 Cartes de chaleurs des plus grands clusters pour les trois paramétrages retenus avec le jeu de données Véléval.</td><td>46</td></tr><tr><td>3.12 Cartes de chaleurs des plus grands clusters pour les trois paramétrages retenus avec le jeu de données MonRésoVélo.</td><td>47</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>3.13</td>
      <td>Boîtes à moustaches des distances entre les traces expérimentées de Véléval et les quatre autres types de traces.</td>
      <td>52</td>
    </tr>
    <tr>
      <td>3.14</td>
      <td>Boîtes à moustaches des distances entre les traces expérimentées de MonRésoVélo et les quatre autres types de traces.</td>
      <td>54</td>
    </tr>
    <tr>
      <td>3.15</td>
      <td>Diagramme montrant la structure d'une cellule LSTM.</td>
      <td>55</td>
    </tr>
    <tr>
      <td>3.16</td>
      <td>Prédictions des classificateurs avec les sous-jeux de test.</td>
      <td>58</td>
    </tr>
    <tr>
      <td>3.17</td>
      <td>Boîtes à moustaches des distances entre les traces expérimentées de Véléval et les trois types de traces basées sur l'expérience.</td>
      <td>60</td>
    </tr>
    <tr>
      <td>3.18</td>
      <td>Boîtes à moustaches des distances entre les traces expérimentées de MonRésoVélo et les trois types de traces basées sur l'expérience.</td>
      <td>60</td>
    </tr>
    <tr>
      <td>3.19</td>
      <td>Cartes montrant 2 traces expérimentées (en orange), les traces générées correspondantes (en bleu) et les traces calculées par le modèle de choix d'itinéraire entraîné avec le jeu Véléval (en rouge).</td>
      <td>62</td>
    </tr>
    <tr>
      <td>3.20</td>
      <td>Cartes montrant 2 traces expérimentées (en orange), les traces générées correspondantes (en bleu) et les traces calculées par le modèle de choix d'itinéraire entraîné avec le jeu MonRésoVélo (en rouge).</td>
      <td>63</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Diagramme de la construction d'une matrice de position à partir du schéma d'une intersection.</td>
      <td>73</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Capture d'écran de l'environnement simulé par SUMO.</td>
      <td>75</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Somme des véhicules comptés par heure dans les 2 directions sur le boulevard Montparnasse le 20 juin 2023.</td>
      <td>77</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Diagramme de la structure du Q-réseau.</td>
      <td>78</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Évolution du temps d'attente moyen des véhicules pendant l'entraînement de l'agent 3DQN.</td>
      <td>81</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Évolution du temps d'attente moyen des véhicules pendant l'entraînement de l'agent PPO.</td>
      <td>82</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Résultats d'une simulation d'un jour.</td>
      <td>86</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>Nombre de véhicules et sommes des temps d'attentes entre selon le coefficient multiplicateur du trafic vélo (de 6h à 20h).</td>
      <td>88</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Temps d'attente moyen des véhicules selon le coefficient multiplicateur du trafic vélo (de 6h à 20h).</td>
      <td>89</td>
    </tr>
    <tr>
      <td>4.10</td>
      <td>Nombre d'étapes passées en phase verte et orange par voie durant une simulation d'un jour.</td>
      <td>91</td>
    </tr>
    <tr>
      <td>4.11</td>
      <td>Chronologie des phases par voie de 19h à 20h.</td>
      <td>92</td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>Somme des véhicules comptés dans la ville de Paris le 20 juin 2023.</td>
      <td>98</td>
    </tr>
  </tbody>
</table>
# Liste des tableaux

<table><tr><td>2.1</td><td>Tableau résumé des quatre sources de données et des caractéristiques les différenciant.</td><td>7</td></tr><tr><td>4.1</td><td>Tableau des hyperparamètres.</td><td>79</td></tr></table>
À mon père, puisse-t-il avoir enfin trouvé la paix...
# Chapitre 1

# Introduction

La mobilité urbaine est en train de vivre un changement significatif avec le retour de l'utilisation du vélo pour les trajets quotidiens. Les motivations d'un tel changement modal sont nombreuses. Individuellement, cela permet d'être en meilleure santé [1, 2], d'économiser du temps et de l'argent. À l'échelle de la ville, cela permet une réduction de la congestion des véhicules motorisés ainsi que de la pollution de l'air [3]. Pour ces raisons, les décideurs politiques lancent de nombreux projets pour promouvoir l'utilisation du vélo en ville. Classiquement, ces projets visent à redistribuer l'espace urbain plus équitablement entre les véhicules motorisés et les autres modes de transport. Les villes sont en effet dans l'immense majorité des cas structurées autour de la voiture individuelle. En conséquence, la part des trajets quotidiens effectués en voiture dans les pays de l'OCDE varie de 46% à 86% selon les études [4].

La pandémie de COVID-19 a temporairement augmenté l'attrait des modes de transports individuels au détriment des transports publics pour des raisons de distanciations sociales. Pour éviter un report modal massif vers la voiture, les villes ont cherché à rapidement augmenter l'attrait de l'utilisation du vélo en leur sein. Pour y parvenir, celles-ci ont beaucoup utilisé l'urbanisme tactique pour augmenter la part d'infrastructures cyclables dans leurs réseaux routiers [5]. L'urbanisme tactique consiste à fermer temporairement certaines voies aux véhicules motorisées pour les réserver aux modes de transport actifs. Les modes de transport actifs comprennent tous les moyens de se déplacer utilisant l'activité physique humaine comme principale source d'énergie. L'urbanisme tactique s'effectue la plupart du temps par l'ajout d'un marquage au sol sur les voies ciblées.

Cette stratégie n'est cependant pas durable, car elle se concentre surtout sur la quantité des infrastructures sans intégrer la dimension qualitative de celles-ci dans la planification. Le nombre des aménagements cyclables étant positivement liés au nombre de cyclistes [6, 7], les décideurs politiques estiment que la présence d'infrastructures cyclables sur les voies principales suffit pour une pratique du vélo rapide et sécurisée [8]. Les cyclistes, bien que d'accord avec cette affirmation, évoquent également les effets positifs d'autres facteurs, comme la présence d'espaces verts, le sentiment de sécurité ou des infrastructures séparées des véhicules motorisés [8, 9, 10]. L'installation d'une bande cyclable, un type d'infrastructure séparée de la chaussée par un marquage au sol, n'aura pas le même impact que l'installation d'une piste cyclable, un type d'infrastructure séparé lui par un terre-plein non franchissable. À noter qu'un cycliste désigne un individu pratiquant le cyclisme. Le cyclisme se réfère tout au long de cette thèse à l'utilisation du vélo, quelle qu'en soit la raison. Une compréhension précise des comportements de cyclistes est cruciale pour mettre en place des politiques urbaines efficaces d'incitation au cyclisme. L'étude des comportements de cyclistes dans le but de créer une structure cyclable optimale est devenue
un sujet de recherche récurrent pour cette raison. Une partie de cette compréhension
doit se faire à l'échelle des trajets individuels, car être capable de reproduire des iti-
néraires de cyclistes est décisif pour anticiper les performances de futurs aménage-
ments. Un verrou important de ce travail scientifique a longtemps été l'absence de
données quantitatives de trajets effectués par des cyclistes.

Malgré les limites évoquées de certaines politiques, le nombre de cyclistes aug-
mente dans les villes d'Europe [11]. Ce regain d'intérêt pour le cyclisme, accompa-
gné de l'essor technologique démarré au début du siècle, a permis de transformer
l'utilisation du vélo en ville [12]. On peut citer parmi les innovations technologiques
l'automatisation de la location de vélos individuels à la demande, ou la création
de vélos avec assistance électrique utilisable sur de plus longues distances et sur
des topographies qui demandent des efforts importants. Ces transformations se sont
naturellement accompagnées de nouvelles possibilités de récupération de données
comportementales de cyclistes. Ces nouvelles données sont de différentes natures, et
sont regroupées en jeux de différentes tailles n'ayant pas tous le même niveau d'ac-
cessibilité. Ces données sont aussi multidimensionnelles, avec des propriétés spa-
tiales mais aussi temporelles, pouvant rendre difficile leur exploitation. Néanmoins,
analyser, comprendre et même prédire les comportements de cyclistes est possible
lorsque cette exploitation est effectuée correctement.

Parallèlement à l'émergence de ces nouvelles données, l'apprentissage automa-
tique, une branche de l'intelligence artificielle, a fait d'énormes progrès. L'apprentis-
sage automatique consiste à développer et à analyser des algorithmes pouvant géné-
raliser certaines tâches sans instructions spécifiques. L'apprentissage automatique a
été appliqué à de nombreux domaines comme l'agriculture [13, 14], la médecine [15,
16] ou encore le transport [17, 18]. Il est possible d'identifier 4 types d'apprentissage
automatique, chacun regroupant une multitude d'algorithmes différents. L'appren-
tissage supervisé consiste à construire un modèle mathématique à partir d'un jeu
de données contenant des entrées et des sorties désirées [19]. L'apprentissage non
supervisé consiste à prendre un jeu de données ne possédant que des entrées et à
regrouper celles-ci en paquets (appelés clusters) d'entrées qu'une métrique estime
similaires. L'apprentissage semi-supervisé est un mixte entre les deux précédents
apprentissages. Certaines données utilisées possèdent une sortie désirée et d'autres
non [20]. Enfin, l'apprentissage par renforcement consiste à apprendre à un agent à
effectuer des actions dans son environnement pour maximiser un signal de récom-
pense numérique. Le but de l'agent est de découvrir par lui-même quelles actions
sont les plus profitables dans les différentes situations dans lesquelles il peut se trou-
ver [21].

L'apprentissage supervisé est le type d'apprentissage le plus utilisé. Deux types
de problèmes sont traitables par de l'apprentissage supervisé : la régression et la
classification. La régression consiste à approcher une variable de sortie à partir de
variables explicatives corrélées à celle-ci. Dans le cas du cyclisme, la régression peut
par exemple permettre de prédire si un individu est propice à utiliser son vélo à
partir de variables comme la météo, l'heure de la journée, le genre ou encore la
situation financière de celui-ci. La classification consiste à identifier à quelle caté-
gorie une observation appartient parmi un ensemble prédéfini de catégories. Pour
le cyclisme, cela peut servir par exemple à trouver le niveau d'expérience d'un in-
dividu à partir des distributions de vitesse de ses trajets. Dans le cadre de cette
thèse, les algorithmes d'apprentissage supervisé sont divisés en 2 catégories : implicites et explicites. Durant ce travail de recherche, les données utilisées en entrée des algorithmes d'apprentissage supervisé sont des données comportementales de cyclistes. Les algorithmes dits explicites comprennent les algorithmes nécessitant la définition explicite de variables descriptives représentant certaines caractéristiques de ces comportements. On peut citer entre autres les algorithmes de régression ou les arbres de décision. Un algorithme de régression affilie un poids à chacune des variables explicatives dont le but de prédire la variable de sortie. Les algorithmes de régression étant fréquemment utilisé sur des données de comportements individuels de cyclistes, plus de détails sont présentés plus tard. Les algorithmes dits implicites ne nécessitent eux pas de variables descriptives, car ils apprennent des représentations implicites des données d'entrée dans le but de renvoyer la sortie délivrée. C'est par exemple le cas des réseaux de neurones artificiels qui sont inspirés du cerveau des êtres vivants. Il existe différents types de réseaux de neurones permettant d'apprendre différents types de représentations. Certains réseaux de neurones sont capables de traiter des données multidimensionnelles, comme celles représentant les comportements de cyclistes. Les réseaux de neurones convolutifs permettent par exemple de faire de l'apprentissage sur des données spatiales. Les réseaux de neurones récurrents sont eux adaptés aux données temporelles. Ces dernières années, les réseaux de neurones ont permis de faire avancer de nombreux domaines scientifiques, comme la reconnaissance d'image [22], la reconnaissance vocale [23] ou encore la modélisation du langage [16, 24].

L'objectif de cette thèse est de développer des outils innovants ayant comme objectif d'inciter au cyclisme. Ces outils utilisent des algorithmes d'apprentissage automatique sur des données comportementales de cyclistes en ville. Deux approches différentes sont testées. La première est construite autour de la politique urbaine la plus répandue pour inciter au cyclisme : la création d'infrastructures cyclables pertinentes. La pertinence de ces infrastructures est fortement dépendante de la capacité à prédire le comportement des cyclistes. Une méthode de création de modèles de choix d'itinéraire permettant de générer des trajets individuels de cyclistes est développée dans ce but. La deuxième, plus innovante, vise à développer un nouveau type d'infrastructure dynamique permettant de sécuriser le passage des cyclistes à un feu de circulation en limitant l'impact sur le trafic. Les trois contributions de cette thèse peuvent être résumées comme suit :

1. **Identification de segments de routes préférés de cyclistes.** Cette méthode utilise des traces GPS et un algorithme d'apprentissage non supervisé (clustering) pour identifier les segments de route que les cyclistes utilisent le plus.

2. **Développement d'une méthode de génération d'itinéraires cyclables.** Cette méthode est capable de générer des trajets individuels entre n'importe quelle origine et destination dans une ville en utilisant des segments de routes préférés identifiés au préalable. Celle-ci utilise un algorithme d'apprentissage supervisé (apprentissage profond) et une pondération de graphe routier.

3. **Création d'un feu de circulation intelligent sécurisé pour les cyclistes.** Ce feu est contrôlé par un algorithme d'apprentissage par renforcement, utilisant lui-même des réseaux de neurones. Le développement de ce feu se fait en simulations, et des données de comptage vélos et voitures sont utilisées pour paramétrer celles-ci.
Ces contributions ont pu être valorisées par l'écriture de 2 articles, un premier publié dans la revue PLOS ONE [25] et un second soumis dans la revue Journal of Intelligent Transportation [26]. La Figure 1.1 résume cette thèse, les données et les types d'apprentissage utilisés, ainsi que les contributions qui ont été permises par leurs combinaisons. Ce manuscrit est divisé en 5 chapitres, le premier étant cette introduction.

Le Chapitre 2 résume les différentes sources de données décrivant le comportement des cyclistes, et argumente le choix des 2 types de données utilisés ensuite.

Le Chapitre 3 décrit une méthode de création de modèles de choix d'itinéraire implicites. Les modèles implicites créés avec cette méthode diffèrent des modèles existants tant par leur objectif que par la manière de l'atteindre. L'objectif des modèles implicites est de prédire le comportement des cyclistes à partir de données comportementales. Celui des modèles plus classiques est de quantifier l'impact de certaines variables sur le choix des cyclistes. L'identification par les modèles implicites de patterns (c.-à-d. de schémas) dans les données comportementales remplace le choix explicite de variables descriptives effectué lors du développement de modèles plus classiques. Cela permet, entre autres, d'outrepasser certaines limites amenées par cette sélection. Au cours du développement de cette méthode, l'existence de segments de route préférés par les cyclistes est démontrée.

L'idée derrière le Chapitre 4 est de développer un nouveau type d'infrastructure, pour inciter l'utilisation de certains segments de route. Cette infrastructure est un feu de circulation intelligent sécurisé pour les cyclistes. Les infrastructures séparant les flux de vélos et de voitures sont particulièrement plébiscitées par les cyclistes. Les approches classiques sont cependant très couteuses en place, car la séparation est effectuée physiquement grâce à la construction de pistes cyclables. Ajouter des phases vertes pour cyclistes à un feu de circulation permet d'effectuer cette séparation virtuellement. Cette solution permet de ne pas modifier la voirie, mais augmente significativement le temps d'attente des véhicules à l'intersection si implémentée de manière naïve. Un algorithme d'apprentissage par renforcement est proposé pour contrôler le feu de manière à limiter le coût en temps d'attente d'une telle installation.

Enfin, le Chapitre 5 conclut le travail effectué durant cette thèse et met en lumière les perspectives de celui-ci.

<figure><img src="image_3.png" /><figcaption>FIGURE 1.1 – Diagramme résumant cette thèse.</figcaption></figure>
# Chapitre 2

## Les sources de données

Les données décrivant le comportement des cyclistes peuvent venir de différentes sources. La description et la modélisation du comportement des cyclistes est une problématique ancienne, et les moyens technologiques ont grandement évolué depuis la naissance de cette discipline scientifique. Aujourd'hui, il existe 4 sources de données majeures utilisées dans la littérature scientifique :

- *Les réponses à des questionnaires de préférences* : plus ancienne manière de récupérer des données comportementales, les questionnaires ont tout de même évolué au fil des avancées technologiques, notamment celles relatives à l'enregistrement vidéo ainsi qu'à la transmission d'informations.

- *Les systèmes de location de vélos en libre-service* : le premier système totalement informatisé est déployé à Rennes en 1998¹. Depuis, la majorité des grandes villes sont dotées de ce type de systèmes et partagent certaines données les concernant.

- *Les capteurs GPS* : d'abord accrochés aux vélos ou portés par les cyclistes, la miniaturisation et l'inclusion de capteurs GPS dans les smartphones a permis la multiplication des jeux de données de traces GPS de cyclistes.

- *Les compteurs vélos* : installés sur certaines pistes cyclables, ils permettent de quantifier leur utilisation à différentes échelles temporelles. Les villes rendent publiques les données agrégées qu'ils enregistrent.

Ces différents types de données sont complémentaires et peuvent être utilisés ensemble [27], mais peu de travaux ont été effectués pour les fusionner entre eux [28]. Ce travail de fusion est difficile car il demande la récupération de jeux de données de différentes sources comparables temporellement et géographiquement. De plus, il est souvent nécessaire d'émettre des hypothèses fortes demandant des connaissances préalables sur le comportement des cyclistes et pouvant compromettre la représentativité des jeux de données initiaux. Il a donc été décidé d'utiliser individuellement les sources de données choisies. Pour choisir les sources les plus pertinentes, quatre grandes caractéristiques permettant de discriminer celles-ci sont utilisées :

- *La disponibilité* qui prend en compte le nombre de jeux de données existants ainsi que leurs modalités de mise à disposition.

- *La compatibilité avec les méthodes d'apprentissage* qui décrit les prétraitements qui doivent être faits sur les données avant de pouvoir utiliser un algorithme d'apprentissage sur celles-ci.

- *Le degré d'information du comportement des cyclistes* qui représente à quel point des trajets individuels peuvent être retracés à partir des données.

<footnote n="1">1. https://fr.wikipedia.org/wiki/Vélos_en_libre-service</footnote>
— Les problèmes principaux auxquels les données répondent qui listent les problématiques les plus communément trouvées dans la littérature utilisant la source de donnée pour être étudiées.

Les sources de données ainsi que ces caractéristiques sont résumées dans le tableau 2.1. Les sections 2.1 à 2.4 sont structurées de la même façon. Premièrement, les données récupérables à partir de la source ainsi que la méthode de collecte sont décrites. Deuxièmement, un état de l'art de l'utilisation des données provenant de la source est effectué. La Section 2.5 discute ensuite des différentes sources de données au vu des contributions de cette thèse, et argumente le choix des sources de données utilisées. Enfin, la Section 2.6 est un résumé du chapitre.

## 2.1 Les questionnaires de préférence

L'analyse du comportement des cyclistes est un sujet présent dans la littérature scientifique depuis de nombreuses années. Au départ, l'un des moyens principaux de récupérer des données comportementales de cyclistes était de les interroger grâce à un questionnaire de préférences. Cela permettait de récupérer des données tant qualitatives que quantitatives. L'avènement des systèmes de vélos en libre-service, des puces GPS ou autres compteurs ont amené de nouvelles manières de récupérer des données quantitatives relatives au comportement des cyclistes. Cependant, lorsqu'il s'agit de récupérer des données qualitatives, ce sont ces questionnaires qui sont encore aujourd'hui privilégiés. Par conséquence, de nombreux questionnaires ont été développés [29, 30, 31, 37, 32, 33, 10, 34, 35, 36]. Les études utilisant un questionnaire de préférences proposent à des personnes interrogées différents itinéraires ou parties d'itinéraires représentés par certaines variables descriptives. Ces variables sont dans la majorité des cas similaires entre les études. Elles peuvent être relatives au type de voie (vitesse maximum des voitures, fréquentation...), aux infrastructures cyclables (présence ou non de pistes cyclables, continuité de celles-ci...), ou encore à l'itinéraire en lui-même (nombre de feux rouges, temps de trajet...). Additionnellement, ces questionnaires demandent diverses informations personnelles aux personnes interrogées, ce qui permet d'éviter à l'une d'entre elles de répondre plusieurs fois, mais surtout de vérifier si certaines variables sociales comme le genre, la fourchette de revenu ou la possession d'un ou plusieurs véhicules motorisés influent sur le comportement des cyclistes.

Une fois le questionnaire créé, celui-ci est diffusé que ce soit par voie électronique (chaîne de mail, sites web...) ou directement dans des lieux propices à la création de mobilités (universités, arrêts de bus ou de métro, hôpitaux...). Les réponses sont ensuite triées et analysées. Dans la plupart des cas, l'analyse porte sur la représentativité du profil des répondants, mais celle-ci peut être plus poussée. En 2007, Tilahun et al. [10] ont par exemple cherché à quantifier le temps que les cyclistes sont prêts à ajouter à leurs trajets pour utiliser des infrastructures cyclables de meilleures qualités. Ils ont pour cela identifié 5 niveaux de qualités d'infrastructures cyclables allant de la piste cyclable à la voie sans bande cyclable avec voitures garées le long du trottoir. Durant l'expérience, les répondants étaient invités à choisir entre deux itinéraires utilisant des infrastructures de niveaux de qualités différentes, comme montré dans la Figure 2.1. Les itinéraires sont hypothétiquement composés du même type
<table><caption>TABLE 2.1 – Tableau résumé des quatre sources de données et des caractéristiques les différenciant.</caption><thead><tr><th>Source de données</th><th>Disponibilité</th><th>Compatibilité avec l'apprentissage automatique</th><th>Degré d'information du comportement individuel des cyclistes</th><th>Problèmes principaux solvables avec les données</th></tr></thead><tbody><tr><td>Questionnaires de préférences</td><td>Réponses contenant des données personnelles, donc non publiées</td><td>Utilisable avec des variables décrivant les réponses</td><td>Choix des cyclistes dans des situations précises en situation contrôlée</td><td>— Analyse de choix d'itinéraire [29, 30, 31, 32, 33, 34, 35, 36]<br>— Classement de perception de types d'infrastructures [37]<br>— Quantification de détours [10]</td></tr><tr><td>Systèmes de vélo en libre-service</td><td>Données publiques et à accès restreint, plusieurs jeux de données disponibles</td><td>Utilisable avec peu ou pas de prétraitements</td><td>Coordonnées géographiques des origines et des destinations, horodatage ou temps de trajet</td><td>— Optimisation du remplissage du système [38, 39, 40, 41, 42, 43, 44, 45, 46]<br>— Analyses diverses à l'échelle de la ville [47, 48, 3, 49, 50, 51, 52, 53]<br>— Prédiction de trajets individuels [52, 54]</td></tr><tr><td>Capteurs GPS</td><td>Jeux de données majoritairement privés, mais certains publics avec prétraitement</td><td>Utilisable avec ou sans variables décrivant les traces</td><td>Détail des trajets individuels, sauf si application d'un prétraitement d'anonymisation spécifique</td><td>— Prétraitement des traces [55, 56, 57, 58, 59, 60]<br>— Analyse d'infrastructures cyclables [61, 62]<br>— Modèles de choix d'itinéraire [63, 64, 65, 66, 67]</td></tr><tr><td>Comptage de vélos</td><td>Données publiques</td><td>Pas d'études utilisant des méthodes d'apprérentissage trouvées</td><td>Nombre de vélos à certains points dans la ville, données assez représentatives théoriquement</td><td>— Prédiction du nombre moyen annuel de cyclistes à certains points [68, 69, 70, 71]<br>— Quantification/Amélioration de le représentativité de jeux de données de traces GPS [62, 72, 73, 74, 75, 76]</td></tr></tbody></table>
<figure><img src="image_4.png" /><figcaption>FIGURE 2.1 – Exemple de question posée par Tilahun et al.[10]</figcaption></figure>

d'infrastructure en continu. Chaque itinéraire a un temps de trajet affilié, celui utilisant l'infrastructure de qualité supérieure ayant un temps de trajet initial de 40 minutes et celui utilisant l'infrastructure de niveau inférieur un temps de trajet de 20 minutes. Si le répondant choisit l'infrastructure de qualité supérieure, il est de nouveau confronté au même choix, mais le temps de trajet de l'itinéraire de meilleure qualité est augmenté. À l'inverse, s'il choisit l'infrastructure de plus basse qualité, le temps de trajet de l'itinéraire de meilleure qualité est diminué. Les expériences étaient menées durant 4 itérations, et les auteurs concluent entre autres que les cyclistes interrogés sont prêts à rajouter 23 minutes environ pour utiliser une piste cyclable à la place d'une voie sans bande cyclable et voitures garées le long du trottoir.

Après la première analyse des réponses, un ou plusieurs algorithmes de régression logistique sont utilisés pour affilier un poids à chacune des variables descriptives des trajets étudiés. Ces poids permettent de quantifier à quel point une variable influence le choix des personnes interrogées, et si cette influence est positive ou négative. En 2009, Sener et al. [35] ont étudié l'influence de variables démographiques, d'accessibilité aux parkings, d'infrastructure cyclable et de chaussée sur le choix d'itinéraire. Les personnes interrogées étaient séparées en 2 groupes : celles répondant dans le cadre d'un trajet domicile-travail et celles répondant dans le cadre d'un trajet loisir. Les personnes interrogées devaient choisir entre 3 trajets, chacun décrits avec 5 variables descriptives prises sur les 11 identifiées au total (10 seulement pour les trajets loisir, le temps de trajet n'étant pas inclus). Un modèle logistique multinomial mixte est ensuite appliqué sur les réponses. Les auteurs concluent que les cyclistes préfèrent la non-présence de parking le long de leurs itinéraires, et que si un parking doit être présent, ils préfèrent un stationnement en biais à un stationnement parallèle. Les résultats montrent aussi une préférence pour des infrastructures cyclables en continu, ainsi qu'un trafic automobile, une vitesse maximum, un nombre de panneaux stop, de feux de circulation et de croisements faible, ce qui est cohérent avec le résultat de précédentes études. Seul point surprenant, les cyclistes interrogés
préfèrent les faibles pentes aux trajets plats. Ce résultat est influencé par les cyclistes faisant des trajets pour le loisir, car l'effort physique induit par le passage sur une faible pente peut être recherché par ceux-ci. Les auteurs argumentent que leur étude, et ainsi toutes celles du même type, permet de trouver le coût maximum (que ce soit en temps de trajet ou en argent) que les cyclistes interrogés sont prêts à payer pour que leurs trajets possèdent ou ne possèdent pas une caractéristique.

L'évolution des technologies et particulièrement la démocratisation des puces GPS a permis la création de nouveaux moyens de récupération de données de cyclistes. Ces méthodes ne nécessitent pas la création d'un questionnaire et sont capables de récupérer les données de manière passive, limitant ainsi les biais psychologiques, ainsi que de manière massive, limitant les biais démographiques des échantillons étudiés. Cependant, cette évolution technologique a aussi permis le développement de nouveaux moyens de décrire les choix auxquels les auteurs veulent confronter les cyclistes. En 2020, Monsere et al. [37] se sont ainsi filmés à vélo, prenant différentes intersections sans véhicule tournant, avec véhicule tournant au loin et avec véhicule tournant proche, obligeant le cycliste à changer de trajectoire. Ils ont ensuite demandé à 275 personnes interrogées de noter le niveau de confort de chacun des extraits vidéo. Sans surprise, la piste cyclable reçoit la meilleure note de confort, et la bande cyclable reçoit la moins bonne note de confort. Les auteurs remarquent aussi que le niveau de confort perçu baisse quasiment systématiquement lorsqu'un véhicule tourne près du cycliste, à l'exception de la bande cyclable. Les personnes interrogées étaient ensuite invitées à choisir parmi 4 types d'intersection et d'expliquer leur choix. Le média vidéo permet dans cette étude de montrer différentes situations plus ou moins dangereuses à différents types d'intersections sans avoir à décrire celles-ci textuellement. Cela permet aux personnes interrogées d'expliquer leurs choix sans être biaisés par la description des situations et/ou des intersections faites par les auteurs.

## 2.2 Les systèmes de vélo en libre service

Les systèmes de vélo en libre-service (BSSs pour *Bike-Sharing Systems*) se démocratisent depuis une vingtaine d'années partout dans le monde<fnref n="2" />. Les plus anciens sont constitués de stations disséminées dans la ville sur lesquelles sont attachés les vélos. Les utilisateurs empruntent et rendent les vélos à ces stations. Il existe deux types de données issues de ces systèmes. Les premières sont les données dites "ouvertes", car disponibles en ligne dans la plupart des cas. Ces données sont composées des localisations et tailles de toutes les stations ainsi que du nombre de vélos accrochés à celles-ci en temps réel. Un exemple graphique des données ouvertes du système de BSS de Lyon est montré dans la Figure 2.2. D'autres données sont à accès restreint. Celles-ci sont composées des stations de départ et d'arrivée de chacun des trajets effectués sur une période donnée. À cela s'ajoute un temps de trajet ou un horodatage de départ et d'arrivée. On trouve aussi souvent un identifiant d'utilisateur permettant probablement de retrouver un individu, posant donc des problèmes de respect de la vie privée. Ces données ne sont donc accessibles que dans certaines situations, chaque ville étant libre de les distribuer selon ses propres modalités. Plus récemment, un nouveau type de BSS se développe dans différentes villes. Ces nouveaux BSSs fonctionnent de manière très similaire aux anciens, mais n'ont plus de stations.

<footnote n="2">2. https://en.wikipedia.org/wiki/List_of_bicycle-sharing_systems</footnote>
<figure><img src="image_5.png" /><figcaption>FIGURE 2.2 – Carte contenant une partie des données ouvertes de Velo’v, le BSS de Lyon.</figcaption></figure>

Les utilisateurs peuvent emprunter et rendre les vélos partout dans la zone d'opération du système (souvent une ville entière), à condition de respecter certaines règles dictées par la ville. Ces nouveaux systèmes n'ont pas de données ouvertes. Cela s'explique par l'absence de stations, mais aussi par la nature privée des exploitants de ces systèmes, là où les systèmes à stations sont dans la plupart des cas des légations de service public. Cependant, les BSSs sans stations peuvent fournir des données de trajets ayant la même structure que celles des anciens systèmes. À noter que certains BSSs, à stations ou non, mettent à disposition des vélos équipés de capteurs pouvant être de différentes natures [77]. Les plus couramment utilisés sont les capteurs GPS qui permettent de récupérer les traces des trajets. Celles-ci ne sont cependant pas souvent mises à la disposition du public. Le cas de figure des traces GPS n'est pas évoqué ici, mais dans la Section 2.3.

Beaucoup d'études utilisent des données issues de BSSs [48, 51, 47, 50, 40, 43, 53, 38, 39, 46, 52, 44, 3, 54, 41, 49, 42, 45]. Cela s'explique d'abord par leur facilité d'accès. Ces données ne sont pas considérées comme privées, car rien ne permet de relier un individu à un trajet si l'identifiant utilisateur est supprimé. Certaines villes sensibles aux améliorations rendues possibles grâce aux travaux de recherche n'hésitent pas à fournir leurs données. Il existe plusieurs problématiques pouvant être étudiées à l'aide des données provenant d'un ou plusieurs BSSs. Les impacts produits par l'installation d'un de ces systèmes à l'échelle de la ville en font partie. Les impacts étudiés sont de différentes natures : ils peuvent être d'ordre environnemental [47, 48, 3], relatif au trafic routier [47, 48], au trafic cyclable [49, 50], à la santé [47, 48], et même à l'utilisation du système en lui-même [51, 49, 52, 53]. Ces analyses sont intéressantes pour améliorer les BSSs existants, mais aussi le déploiement des futurs systèmes. Cependant, elles n'essaient pas ni de modéliser ni de prédire les composements individuels des utilisateurs de ces systèmes.
La structure des données issues des BSSs à stations est assez simple, l'espace des coordonnées géographiques possibles étant limité par le nombre de stations existantes. Cette particularité permet de facilement utiliser des algorithmes d'apprentissage supervisé explicites [38, 42] ou implicites [39, 40] sur ce type de données. Cela permet de faire de la prédiction en plus de l'analyse simple. Beaucoup d'études tentent de prédire l'état futur du système. Ce type de prédiction est primordial au bon fonctionnement des BSSs car il permet d'optimiser le processus de rééquilibrage. En effet, certaines stations voient leurs vélos plus souvent empruntés que rendus, et inversement. Pour assurer une offre cohérente avec la demande, des transferts de vélos doivent être effectués entre certaines stations. Pour optimiser le rééquilibrage, certains auteurs croisent les données de trajets avec des données de trafic, de météo et/ou événementielles. Ces croisements sont utilisés en entrée d'algorithmes d'apprentissage supervisé implicites et/ou explicites dans le but de prédire le nombre d'emprunts et/ou de rendus de vélos à différentes échelles [38, 39, 40, 41, 42, 43, 44, 45, 46]. En 2019, Li et al. [42] ont regroupé les stations proches géographiquement et ayant des matrices de transitions similaires à l'aide d'un algorithme d'apprentissage non supervisé. Ils ont ensuite utilisé un algorithme d'apprentissage supervisé et un outil d'inférence ainsi que des données temporelles (heure de la journée et jour de la semaine), météorologiques et événementielles pour prédire le nombre de départs de trajets à trois échelles différentes (ville entière, clusters de stations et stations individuelles). Enfin, ils ont conçu une méthode utilisant la matrice de transition entre clusters et une approximation du nombre total de départs de trajets pour déduire le nombre d'arrivée à chacune des échelles. Leurs travaux surpassent les capacités de prédiction des méthodes précédentes à l'échelle de la ville et des clusters, mais échouent à prédire correctement l'utilisation des stations individuellement, celle-ci étant trop variable.

Ces dernières années, les réseaux de neurones profonds ont démontré leurs capacités prédictives dans de nombreux domaines. Les réseaux de neurones récurrents sont particulièrement performants face à des problèmes utilisant des données temporelles, telles que celui de la prédiction de l'état futur d'un BSS. En 2019, Pan et al. [40] ont utilisé un réseau LSTM (Long Short Term Memory : un type de réseau de neurones récurrent adapté aux longues séquences détaillée dans le Chapitre 3) sur les données du BSS de New-York pour prédire le nombre de vélos loués et rendus dans le système. Leur réseau de neurones est capable d'effectuer des prédictions sur des stations individuelles à l'échelle horaire. La structure du LSTM permettant de prendre en compte les aspects temporels des données, les capacités de prédiction qui en résultent surpassent celles des réseaux de neurones dits fully-connected (c.-à-d. les réseaux de neurones profonds ayant la structure la plus simple). Les réseaux LSTM peuvent également être utilisés sur les systèmes de BSS sans station. Les données issues de ce type de BSS sont plus compliquées à traiter, car les points de départ et d'arrivée sont dans un domaine pouvant être considéré comme continu contrairement aux BSSs plus anciens. Des études récentes divisent la ville en plusieurs parties et utilisent un réseau LSTM pour prédire la distribution des vélos [45] ou les départs et arrivées de trajets [46] dans chacune de ces parties. Toutes ces études sont intéressantes, car elles démontrent que l'utilisation d'outils de prédiction sur les données BSSs permet de modéliser une partie du comportement des cyclistes à différentes échelles. Cependant, même l'échelle la plus précise (les stations) ne permet pas de faire de la prédiction de comportements individuels, le but de ces études étant uniquement de prédire l'état futur du BSS.
Malgré la prédominance des travaux de prédictions concernant le rééquilibrage du système, des auteurs ont tenté d'utiliser les données BSS à d'autres fins. En 2016, Zhang et al. [52] se sont intéressés à la prédiction de trajets. Cette problématique consiste à prédire les caractéristiques d'un trajet individuel. Ils ont utilisé un premier algorithme de régression pour prédire la station d'arrivée et un second pour prédire le temps de trajet. Leur étude est centrée sur les variables descriptives à fournir aux algorithmes pour obtenir la plus grande précision de prédiction possible. Ces variables sont propres aux stations, à l'utilisateur et au moment de départ. Les auteurs concluent que c'est la combinaison de toutes ces variables qui permet de faire les meilleures prédictions. Cette étude prouve la possibilité de prévoir un trajet individuel à partir des données BSSs. Cependant, les données prédites comprennent uniquement l'origine, la destination et le temps du trajet. La prédiction finale n'est que partielle, car les données ne contiennent pas assez d'informations sur les trajets effectués. Une reconstitution plus complète est néanmoins possible à condition d'ajouter de fortes hypothèses. C'est ce qu'ont fait en 2017 Caggiani et al. [54]. Ces auteurs ont développé un modèle de choix d'itinéraire en utilisant les données ouvertes de deux BSSs ainsi que les conclusions de différents modèles de choix d'itinéraire publiés au préalable. Ce modèle de choix d'itinéraire est implémenté dans une application de test et fonctionne comme suit. Premièrement, l'utilisateur choisi un point de départ et un point d'arrivée. À partir des données BSSs, le système calcule le chemin le plus court jusqu'au vélo en libre-service le plus proche. Le modèle calcule ensuite un chemin optimal pour atteindre le point d'arrivée dans le cas d'un vélo sans station, ou de la station la plus proche du point d'arrivée sinon. Le chemin calculé est optimal au regard des hypothèses formulées par les auteurs, provenant des conclusions de précédentes études. Il est obtenu en pondérant le graphe routier avec des données structurelles, de trafic et de pollution. Caggiani et al. réussissent à prédire le comportement d'un cycliste individuel de manière détaillée. Cependant, ils ne prennent en considération que la perception de la pollution de l'air et la perception de sécurité des itinéraires possibles, toutes les deux calculées de manière assez arbitraire. De plus, leur modèle de choix d'itinéraire n'est jamais confronté à des données réelles.

## 2.3 Les capteurs GPS

La démocratisation des capteurs GPS depuis une vingtaine d'années a permis le développement d'une nouvelle manière de collecter des données de trajets de cyclistes. Cette méthode de récupération a l'avantage d'être passive et mise en place dans des conditions réelles. Les traces récupérées sont constituées de points GPS que le capteur enregistre à intervalles réguliers. Chaque point est constitué à minimum d'une latitude, d'une longitude et d'un horodatage. À cela peuvent s'ajouter des informations supplémentaires comme l'altitude ou une estimation de la vitesse par exemple. Les traces GPS de cyclistes présentent cependant deux inconvénients qui demandent chacun un prétraitement distinct avant leur utilisation. Le premier est un problème de précision inhérent aux capteurs GPS utilisés. En effet, il arrive à une fréquence non négligeable qu'un ou plusieurs points GPS soient imprécis, c'est-à-dire éloignés de l'endroit où se trouvait réellement le capteur lorsqu'ils ont été enregistrés [78]. Pour pouvoir utiliser un jeu de données de traces GPS, les traces contenant ces imprécisions doivent être *mapmatchées* lorsque cela est possible, ou
supprimées sinon. Les algorithmes de mapmatching ont pour objectif de transformer une trace composée d'une succession de points géographiques en une succession d'arêtes d'un graphe routier. Chaque point géographique doit être ramené sur l'arête sur laquelle se trouvait le capteur GPS lors de l'enregistrement de celui-ci. L'ensemble des arêtes ou l'ensemble des points ramenés sur les arêtes peuvent en suite être utilisés, suivant les besoins. Le deuxième problème est spécifique à l'étude de traces GPS cyclables. Dans de nombreuses études, les capteurs sont portés par les candidats durant toute la journée. Il faut donc diviser l'unique trace récupérée au cours de la journée en différentes activités, puis les labelliser dans le but de retrouver les sous-traces capturées durant un trajet à vélo. Les problématiques liées au prétraitement des traces GPS forment une discipline scientifique qui mérite que l'on s'y attarde un instant.

De nombreuses études se concentrent sur ces problématiques [55, 56, 57, 58, 59, 60]. En 2021, Lisner et al. [60] ont développé une méthode complète de prétraitement orientée sur le cyclisme. Les auteurs ont commencé par calculer la vitesse du capteur à chaque point GPS, puis ont supprimé les points ayant une vitesse supérieure à 90 km/h, les considérant comme aberrants. Ils ont ensuite appliqué un algorithme de lissage de gradient dans le but de lisser les vitesses pour que celles-ci soient plus réalistes. Pour la segmentation en différentes activités, les auteurs ont remarqué que lorsque le porteur du capteur n'est pas en train d'effectuer un trajet, les variations de vitesse et d'orientation entre les points GPS sont plus élevées. Ils ont donc développé une méthode de calcul utilisant les variations de vitesse et d'orientation dans une fenêtre de temps pour identifier si un point GPS fait partie d'un trajet ou non. Un algorithme d'apprentissage supervisé implicite est ensuite utilisé sur des traces GPS de test pour la détection du mode de transport. Des variables DESCRIPTIVES du trajet telles que la distance, la distribution des vitesses ou encore le détour par rapport au trajet à vol d'oiseau sont utilisées. Le résultat de cette étude est une méthode flexible, transparente et interprétable de prétraitement de traces GPS, avec une bonne précision pour la reconnaissance de trajets cyclables.

Une fois les traces GPS nettoyées, le jeu de données peut être utilisé à différentes fins. Même si certaines études se concentrent sur d'autres problématiques comme l'analyse des infrastructures cyclables [61, 62] ou la représentativité de jeux de données [79], la grande majorité des études utilisant des traces GPS cyclables font de la modélisation de choix d'itinéraire [63, 64, 65, 66, 67]. Les traces GPS de cyclistes ne suffisent pas à modéliser leurs choix d'itinéraire. Celles-ci décrivent les choix effectués, mais ne donnent aucune information sur les autres possibilités qui s'offraient aux cyclistes lorsqu'ils les effectuaient, ni sur les motivations de leurs choix. Il faut donc au préalable construire un jeu de trajets possibles artificiellement. Une version naïve de construction de ce jeu de trajets possibles est d'utiliser le chemin le plus court entre les origines et destinations des traces, mais des méthodes plus complexes utilisant notamment le clustering des origines et des destinations [64], l'optimisation d'attribut [65] ou encore la pénalité de lien [63] existent. La construction de trajets de choix est une question scientifique à part entière à laquelle certaines études sont entièrement dédiées [80]. Une fois le jeu de trajets possibles généré, des variables descriptives de différentes natures sont choisies pour décrire chaque trajet. Ces variables sont du même type que celles choisies dans les études utilisant les questionnaires de préférences, et tout comme dans celles-ci, un ou plusieurs algorithmes de
régression logistique sont utilisés pour affilier un poids à chaque variable. La prédiction est aussi faisable à partir des modèles finaux. L'utilité d'un trajet est calculable à partir du modèle, et prédire quel trajet est le plus proche du comportement d'un cycliste est donc possible en choisissant celui ayant l'utilité la plus grande à partir de différents trajets possibles. Une description plus détaillée des modèles de choix d'itinéraire discrets est faite dans la Section 3.1.

Les traces GPS générées par des cyclistes permettent donc de décrire leurs comportements individuels en situation réelle. À partir de celles-ci, il est possible d'analyser, de modéliser et même de prédire ces comportements. De plus, les traces GPS sont compatibles avec certaines méthodes d'apprentissage profond, moyennant des prétraitements spécifiques [81]. Néanmoins, les traces GPS individuelles sont considérées comme données privées, car elles peuvent donner des informations sur le lieu de vie et/ou de travail des individus. Il n'est donc pas possible de les publier sans utiliser d'algorithmes d'anonymisation au préalable. Après des recherches tant internes qu'externes au laboratoire, 3 jeux de données de traces GPS ont été identifiés. Deux sont publics et le dernier est privé. Les Sections 2.3.1, 2.3.3 et 2.3.2 présentent ces jeux, et décrivent les travaux de recherches effectués avec ceux-ci jusqu'à présent.

## 2.3.1 Strava Metro

Strava est une solution commerciale permettant d'enregistrer des activités physiques. Conçue à l'origine par des cyclistes et principalement utilisée par ceux-ci, Strava détient un jeu de données de traces GPS cyclables crowdsourcé mondial mis à disposition de la recherche et des politiques urbaines par le biais du projet Strava Metro<fnref n="3" />. La nature privée des traces GPS empêche la distribution du jeu de données brut. Strava agrège donc celles-ci en premier lieu. Le jeu de données mis à disposition est un graphe routier avec les données de cyclistes ajoutées sur chaque segment de route et sur chaque intersection, ainsi que des polygones décrivant les origines et destinations. Un exemple de graphe routier contenant les données Strava de la ville de Glasgow est montré en Figure 2.3. Les données ajoutées au graphe sont le nombre de cyclistes qui sont passés sur le segment ou à l'intersection sur une période donnée (heure, année, jour de semaine ou weekend), ainsi que le temps d'attente moyen (uniquement aux intersections). Strava met à disposition leurs données par zones géographiques. Les équipes de recherche travaillant avec les responsables de la politique urbaine de leurs villes y ont accès gratuitement. Ces données sont donc beaucoup utilisées dans la littérature [82]. Celles-ci permettent, tout comme les données BSSs, de faire différentes analyses à l'échelle de la ville. La nature plus détaillée des données Strava permet cependant d'effectuer des analyses à plus fine échelle. Il est par exemple possible d'évaluer l'impact de l'installation d'une nouvelle infrastructure cyclable en comparant les données Strava dans la zone concernée avant et après l'installation [73, 83]. Certains auteurs se sont aussi intéressés à l'exposition des cyclistes à la pollution [84, 85] ou aux risques d'accidents [75]. Pour ce qui est du comportement des cyclistes, les données Strava permettent tout d'abord d'identifier les caractéristiques de leurs trajets, qu'elles soient géographiques [86], temporelles [87] ou selon le type de trajets (domicile-travail ou autre) [85]. Associées à des données infrastructurelles et/ou de compteurs de vélos, les données Strava peuvent aussi augmenter la précision de modèle de prédiction de volume de cyclistes, que ce soit au niveau de compteurs [76, 68] ou sur le réseau entier [88]. Enfin,

<footnote n="3">3. https://metro.strava.com/</footnote>
<figure><img src="image_6.png" /><figcaption>FIGURE 2.3 – Carte affichant certaines données Strava ajoutées au graphe routier de la ville de Glasgow.</figcaption></figure>

les données Strava permettent de faire de l'analyse de choix d'itinéraire. Une étude s'intéressant aux comportements individuels des utilisateurs de l'application Strava a été conduite par Huber et al. en 2019 [89]. Les auteurs ont réussi à reconstruire un trajet à partir d'une origine, d'une destination et des données Strava. Ils ont pour cela créé des zones de transit et ont utilisé un algorithme de routage associé à deux contraintes. Les trajets créés ont été validés par un modèle de choix d'itinéraire existant.

## 2.3.2 Véléval

Véléval est un projet lancé en 2016, et financé par le LabEx IMU 4. Son but est d'évaluer la cyclabilité en milieu urbain, en intégrant dans l'analyse les conditions matérielles, techniques, mais aussi sociales. Durant ce projet, 40 cyclistes volontaires ont été invités à effectuer des trajets domicile-travail à vélo de mai 2016 à octobre 2019 à Lyon et à Saint-Étienne. Chaque cycliste était équipé d'un capteur GPS ainsi que d'une caméra. Les cyclistes participaient ensuite à un entretien qui leur permettaient, avec l'appui des vidéos de leurs trajets, d'expliquer les choix fait durant ceux-ci. Une collecte participative a parallèlement été menée. Le résultat de ce projet est, entre autres, un jeu de données privé de traces GPS de cyclistes. Certaines traces de ce jeu de données sont montrées en Figure 2.4.

À cause de son statut de jeu de données privé, Véléval n'a pas été beaucoup utilisé dans la littérature. Les porteurs du projet ont sorti un article en 2020 [27] ainsi qu'un chapitre de livre en 2022 [90]. Cependant, ceux-ci se concentrent plus sur ce

<footnote n="4">4. https://imu.universite-lyon.fr/</footnote>
<figure><img src="image_7.png" /><figcaption>FIGURE 2.4 – Carte affichant certaines traces GPS du jeu de donnée Véléval.</figcaption></figure>

qu'apporte la capture de vidéos en parallèle de la capture de traces GPS pour des entretiens sociologiques que sur l'analyse des traces GPS seules. L'objectif du projet était de comprendre plus que de modéliser le comportement des cyclistes.

### 2.3.3 MonRésoVélo

MonRésoVélo est une initiative de la ville de Montréal. En 2013, l'application mobile MonRésoVélo, dont un aperçu de l'interface est montré en Figure 2.5, est mise à la disposition du public. Cette application permet à ses utilisateurs d'afficher les infrastructures cyclables de la ville de Montréal, de sauvegarder et de consulter leurs trajets à la manière d'un tableau de bord, et d'afficher la vitesse moyenne et une estimation des calories dépensées lors du trajet en cours. Pour la ville, c'est un moyen de récupérer les traces GPS des cyclistes volontaires pour mieux comprendre leurs comportements, dans le but d'améliorer les aménagements cyclables. Les traces GPS sont anonymisées en supprimant les premiers et derniers points GPS ainsi que l'horodatage, et mises à la disposition de tout le monde<fnref n="5" />. Le jeu de données ainsi constitué contient 4881 traces GPS, générées exclusivement par des cyclistes entre juin 2013 et octobre 2015. D'autres informations sont disponibles, comme le motif du trajet ou les heures de départ et d'arrivée.

Malgré son statut de jeu de données public, MonRésoVélo n'est que peu utilisé dans la littérature. Cela est probablement dû à une méconnaissance de son existence, ainsi qu'à sa taille pouvant être considérée comme insuffisante pour certains travaux. Le peu d'études effectuées avec ces données, écrites par Strauss et al. entre

<footnote n="5">5. https://donnees.montreal.ca/ville-de-montreal/trajets-individuels-velo-enregistre-monresovelo</footnote>
<figure><img src="image_8.png" /><figcaption>FIGURE 2.5 – Visuel de l’application MonRésoVélo.</figcaption></figure>

2015 et 2017 [72, 74, 91], utilisent d'ailleurs directement les données générées pendant le projet sans avoir à passer par le portail de données ouvertes de la ville de Montréal. Leur jeu de données est donc plus grand, contenant 10000 traces GPS générées par environ 1000 cyclistes différents. Ces études s'intéressent à la vitesse des cyclistes aux intersections, ainsi qu'aux risques d'accidents. Elles démontrent entre autres une forte corrélation entre les endroits où les utilisateurs de l'application effectuent de fortes décélérations et les accidents impliquant un cycliste rapportés aux autorités.

## 2.4 Les comptages de vélos

Compter le nombre de vélos passant à un endroit précis dans la ville ne permet que de quantifier l'utilisation d'une voie ou d'un type de voie. Cette quantification est plutôt représentative en théorie, car elle englobe tous les cyclistes passant par un point donné. Lorsque les comptages sont disséminés dans une zone géographique donnée, le comportement des cyclistes peut être étudié de manière plus globale. Il existe différentes manières de compter les vélos, classées en deux types : les manières temporaires et les manières durables. Les comptages temporaires peuvent être faits manuellement en positionnant une personne à une intersection par exemple, et en lui demandant de compter les cyclistes qu'il voit. Ils peuvent aussi être automatisés en positionnant un capteur pneumatique sur la voie que l'on souhaite étudier. Les comptages durables sont eux effectués via l'installation de compteurs automatiques fixes. Ces compteurs peuvent prendre la forme de détecteur/caméra infra-rouge, mais la grande majorité sont des boucles d'induction magnétique. Ce type de capteur utilise un aimant pour induire un courant électrique lors du passage d'un véhicule. La reconnaissance du type de véhicule détecté est difficile [92], obligeant ces capteurs à être déployés sur des pistes cyclables séparées. Une fois installés, les compteurs enregistrent des données sur des périodes relativement longues, plusieurs années dans la plupart des cas. Les comptages durables remontent donc des données plus représentatives que les comptages temporaires, qui sont eux effectués sur des périodes beaucoup plus courtes allant de quelques heures à quelques jours. Installer un compteur de vélos automatique peut être fait pour différentes raisons. Premièrement, certains de ces compteurs affichent en temps réel le nombre de cyclistes comptés le jour et/ou l'année courant(e). Cela a pour but d'informer les
<figure><img src="image_9.png" /><figcaption>FIGURE 2.6 – Carte montrant les compteurs automatiques de vélos dans la métropole de Lyon.</figcaption></figure>

habitants et de les inciter à se déplacer à vélo. Deuxièmement, la plupart des villes publient gratuitement les données de ces compteurs, ce qui permet d'étudier les flux de cyclistes à leurs emplacements. Une carte interactive présentant les compteurs de vélos de la ville de Lyon est montrée en Figure 2.6. Les données publiées contiennent la position des compteurs ainsi que le nombre de cyclistes détectés par ceux-ci pendant une période donnée. Les agrégations temporelles des mesures proposées diffèrent selon les villes, pouvant aller de l'heure jusqu'à l'année entière.

Beaucoup de villes mettent les données de leurs capteurs de vélos permanents à disposition du public, permettant la publication de nombreuses études utilisant celles-ci [69, 71, 68, 11, 70]. En 2021, Nordengen et al. [11] ont utilisé les données de 89 compteurs de vélos en Norvège pour étudier l'évolution du nombre de cyclistes. Ils ont pour cela calculé l'indice de trafic cyclable à 3 échelles (nationale, régionale et locale). Cet indice est le nombre de cyclistes comptés pendant une année divisé par le nombre de cyclistes comptés pendant une année de référence. Les 89 compteurs étant tous opérationnels depuis le 1er janvier 2018 minimum, c'est naturellement cette année qui a été choisie comme année de référence. Les auteurs observent une augmentation de 11% des cyclistes comptés sur la période 2018-2020 au niveau national, mais avec des différences au niveau local et régional. Ils concluent que leurs observations au niveau national sont en accord avec la littérature au regard de l'impact de la Covid-19 sur la pratique du cyclisme, et que les différences locales et régionales mettent en évidence la nécessité de privilégier les politiques cyclables à ces échelles plutôt qu'à l'échelle nationale. Certaines études font plus que de l'analyse en tentant de prédire le nombre moyen de cyclistes moyen annuel à différentes échelles. En 2016, Schmiedeskamp et al. [71] ont construit un modèle estimant la moyenne annuelle de cyclistes comptés par jour de la semaine au pont de Fremont à Seattle, où un compteur automatique est installé. Ils ont pour cela entraîné un modèle binomial négatif en y intégrant des variables descriptives saisonnières (la durée du jour et la fermeture ou non de l'université proche du point étudié) et météorologiques (température et précipitations entre autres). À celles-ci s'ajoute le jour de la semaine ainsi
que le numéro du jour depuis le début de la période étudiée, car la tendance générale du nombre de cyclistes comptés par jour au point étudié est à la hausse durant les 2 ans pendant lesquels l'étude s'est déroulée. Les auteurs concluent que le moindre binomial négatif est performant pour la prédiction du nombre de cyclistes par jour et conseillent de réfléchir à une manière de limiter l'impact négatif de la météo sur le nombre de cyclistes, notamment durant l'hiver.

L'accessibilité des données de compteurs de vélos les rend attractives. Cependant, leur principal problème est leur non-continuité spatiale. En effet, les compteurs sont positionnés à différentes localisations dans les villes et ne donnent aucune information sur la situation entre ces points. C'est pour cela que la majorité des études utilisent d'autres données en complément, et notamment des données GPS [62, 72, 73, 74, 75, 76]. Celles-ci utilisent les données de compteurs vélos pour quantifier voire améliorer la représentativité des données GPS utilisées. En 2019, Rupi et al. [62] ont utilisé des données de compteurs de vélos et des traces GPS récupérées suite à un appel public pour étudier l'utilisation par les cyclistes des liens du graphe routier de la ville de Bologne en Italie. Les données de compteurs vélos ont permis d'augmenter la représentativité des traces GPS récupérées : une régression linéaire entre le nombre de traces GPS passant par les liens possédant des compteurs et les measures de ceux-ci permet de trouver un coefficient multiplicateur *c*. Il suffit ensuite de multiplier *c* par le nombre de traces GPS passant par un lien pour estimer le nombre de cyclistes passant par celui-ci. Une comparaison de la carte de chaleur obtenue à partir de cette estimation et de celle fournie par Strava permet de confirmer la représentativité des données. Les auteurs génèrent ensuite le chemin le plus court entre les origines et les destinations de chaque trace GPS pour étudier les détours faits par les cyclistes. Ils concluent entre autres que le chemin emprunté par un cycliste est en moyenne 20% plus long que le chemin le plus court entre son origine et sa destination. Cette notion de détours effectués par les cyclistes est utilisée comme hypothèse pour la méthode de création de modèles de choix d'itinéraires implicites décrites dans le Chapitre 3.

## 2.5 Positionnement

Comme expliqué en introduction de ce chapitre, les sources de données choisies sont utilisées individuellement, car la fusion entre les données de deux sources différentes est un travail nécessitant des connaissances préalables sur le comportement des cyclistes et constituant un domaine de recherche à lui tout seul. Dans cette section, les possibilités des 4 sources de données étudiées sont discutées au vu des contributions de cette thèse, et le choix d'utiliser ou non chacune d'entre elle est argumenté.

Les questionnaires de préférence permettent de récolter des données sur les choix faits par les cyclistes. Le niveau de détails de ces données est assez important, car elles contiennent certaines étapes intermédiaires des trajets étudiés. Cela permet une analyse fine du comportement individuel des cyclistes dans une situation donnée, ce qui est notamment utile lors de la création et/ou de l'amélioration d'infrastructures cyclables. Cependant, les situations auxquelles sont confrontés les cyclistes sont choisies à l'avance, et leurs choix sont effectués en situation contrôlée (le plus souvent en laboratoire). Ces deux caractéristiques de la méthode de récupération des données sont sources de biais pouvant amener les cyclistes interrogés à prendre
des décisions non réalistes, c'est-à-dire des décisions qu'ils n'auraient pas pris en
situation réelle. Cette particularité rend l'utilisation de données provenant de cette
source problématique pour la génération de trajets individuels de cyclistes, car celle-
ci nécessite un jeu de données contenant des informations réalistes. Il est donc pré-
férable que les données utilisées soient générées en situation réelle, et non dans
un laboratoire face à des choix restreints. Ensuite, les réponses aux questionnaires
comprennent quasiment systématiquement des données personnelles. Celles-ci ne
sont donc pas publiées par les auteurs. Chaque étude doit donc développer son
propre questionnaire, ce qui requiert des connaissances préalables dans le domaine
du transport. Enfin, le développement d'un questionnaire de préférences demande
de choisir des variables descriptives dans la plupart des cas. En effet, les situations
proposées aux cyclistes doivent être décrites, et certaines caractéristiques sont donc
préalablement sélectionnées. C'est pour cette raison que les seuls algorithmes d'ap-
prentissage utilisés sur celles-ci sont des régressions. Une régression permet en effet
d'assigner un poids à chaque caractéristique choisie. Les études utilisant des ques-
tionnaires de préférences se concentrent sur ces poids et analysent quelles caracté-
ristiques influent le plus le choix des cyclistes. L'utilisation d'algorithmes d'appren-
tissage ne nécessitant pas de variables descriptives serait inadaptée, car ils rendent
l'analyse de l'importance des différentes caractéristiques impossibles. À noter que le
développement de nouvelles technologies, notamment dans le domaine de la vidéo,
a permis la création de questionnaires ne décrivant pas explicitement les situations
présentées. Cependant, les études trouvées utilisant ce type de questionnaires ne
font que de l'analyse de choix sans utiliser d'algorithmes d'apprentissage. Toutes
ces remarques rendent l'utilisation de questionnaires de préférences incompatibles
avec les travaux de cette thèse.

Les données issues de systèmes de vélos en libre-service offrent 2 avantages. Premièrement, elles sont facilement accessibles. Une partie est ouverte à tous mais l'acès aux données les plus intéressantes demandent tout de même souvent l'accord de la ville ou de l'opérateur privé du système. Deuxièmement, leur structure est relativement simple. Un point d'origine, un point d'arrivée et une information temporelle (horodatage ou temps de trajet) par trajet. Ces caractéristiques ont permis à de nombreux auteurs d'étudier l'impact de ces systèmes sur les villes dans lesquelles ils sont déployés, mais surtout de faire de la prédiction de comportement des utilisateurs de ces systèmes grâce à des algorithmes d'apprentissage. Cependant, ces prédictions sont dans la plupart des cas à l'échelle du système et non pas à celle de l'individu. Les rares études tentant de prédire des trajets individuels le font soit de manière partielle, soit en formulant plusieurs hypothèses fortes. Cela s'explique par la structure même des données, qui ne contiennent pas d'informations suffisantes pour étudier les trajets individuels des utilisateurs de ces systèmes. Il n'est pas non plus possible de connaître la quantité de ces utilisateurs traversant une intersection donnée pour la même raison. Il est enfin important de noter que ces utilisateurs ne représentent qu'une partie biaisée de la totalité des cyclistes, avec une faible utilisation par les minorités et les personnes à faible revenu aux États-Unis notamment [93]. Il a donc été décidé de ne pas utiliser les données provenant de BSSs.

Les données récoltées par des capteurs GPS n'ont pas les inconvénients de celles
récoltées par les deux sources de données précédentes. Les traces GPS décrivent en
effet les trajets dans leur entièreté, et sont récoltées de manière passive, ce qui permet
de décrire des trajets effectués en situation réelle. Elles sont de plus utilisables relativement facilement avec des algorithmes d'apprentissage sans utiliser de variables descriptives. Ces caractéristiques font de cette source de données une candidate intéressante pour produire des trajets individuels de cyclistes. Le problème principal de ces données est cependant leur accessibilité limitée. Les traces GPS étant considérées comme des données privées, peu de jeux sont disponibles. Trois ont tout de même été trouvés, présentant chacun leurs propres avantages et inconvénients :

- *Strava* : Cette thèse n'a pas été effectuée en collaboration avec des responsables de politiques urbaines. Strava a pour cette raison refusé la demande d'accès aux données de Lyon qui leur a été adressée. Il a tout de même été possible de récupérer des données en provenance de Grande-Bretagne. Ces données ont été mises à disposition par l'université de Glasgow, qui se propose de faire l'intermédiaire entre Strava et d'autres acteurs de la recherche en transport cyclable. Celles-ci, bien qu'elles reflètent le comportement des cyclistes, décrivent difficilement les comportements individuels. Les études autour de ce jeu de données ont principalement pour but d'analyser et de prédire le comportement des cyclistes à une échelle plus globale, bien que la granularité des analyses soit plus fine que la granularité de celles utilisant les données de BSSs. La seule étude trouvée s'intéressant à la reconstruction de trajets individuels à partir de données Strava n'utilise comme validation qu'un modèle de choix d'itinéraire simple. Les auteurs parlent d'ailleurs eux-mêmes de chemins plausibles, et leur méthode ne peut donc pas être utilisée pour générer un chemin décrivant précisément un comportement individuel. Ces caractéristiques du jeu de données Strava ne lui permettent pas d'être utilisé dans ce travail comme données de base pour génération de trajets individuels. Le jeu Strava a donc été mis de côté au profit de traces GPS non agrégées.

- *Véléval* : Le laboratoire au sein duquel ce travail a vu le jour ayant participé au projet Véléval, il a été possible d'accéder à ce jeu de données privé. Celui-ci présente un biais certain de représentativité, les nombres de traces et de cyclistes les ayant générées étant peu élevés. Ceux-ci ont cependant été jugés suffisants pour que le jeu de données Véléval soit utilisé dans le Chapitre 3. En effet, la représentativité du jeu de données n'est pas un point indispensable au développement de modèles de choix d'itinéraire capable de générer des trajets individuels, tant que les résultats de ceux-ci sont interprétés en gardant à l'esprit ce biais.

- *MonRésoVélo* : Le jeu de données MonRésoVélo est plus représentatif que le jeu de données Véléval car celui-ci est *crowdsourcé* et contient plus de traces générées par de plus nombreux cyclistes. Cependant, il ne peut pas non plus être considéré comme représentatif. De plus, les cyclistes ayant généré les traces de ce jeu de données n'ont pas majoritairement effectué des trajets domicile-travail, contrairement à ceux ayant généré le jeu Véléval. Les différences entre les deux jeux de données sont tout de même intéressantes, car elles permettent une analyse plus détaillée des avantages et des inconvénients des modèles de choix d'itinéraire créés par la méthode détaillée dans le Chapitre 3. Le jeu de données MonRésoVélo est donc utilisé pour créer un modèle de choix d'itinéraire implicite. Celui-ci est comparé au modèle développé avec le jeu Véléval à toutes les étapes de leurs créations respectives.

Les données GPS permettent de connaître le nombre de cyclistes passant à une intersection donnée. Cependant, le manque de représentativité est plus problématique.
En effet, une intersection intelligente doit être capable de fonctionner avec une quantité de trafic réaliste, pouvant être élevée en heure de pointe. Les jeux de traces GPS trouvés ne peuvent que sous-estimer le nombre de vélos passant à une intersection, car ils sont générés par un sous-ensemble de cyclistes. Par conséquent, des données plus représentatives ont été privilégiées.

Les jeux de données de comptages vélos sont nombreux et mis à la disposition du public. Ils sont de plus assez représentatifs du nombre de cyclistes passant aux points où sont installés les capteurs. Ces deux caractéristiques font des données de compteurs de vélos un choix facile pour l'étude du comportement des cyclistes. Cependant, les capteurs sont souvent peu nombreux et disséminés dans la ville. Les données qu'ils remontent sont donc partielles, et la faible densité spatiale de celles-ci empêchent l'inférence des données manquantes. Cette partialité limite les possibilités qu'offre ce type de données. Pour palier ce problème, certains auteurs utilisent les données de compteurs vélos en complément d'autres types de données, des traces GPS principalement. Dans la plupart des cas, les données de compteurs sont utilisées pour améliorer la représentativité des données GPS utilisées. Comme expliqué précédemment, les jeux de données de traces GPS choisis dans le cadre de ce travail de recherche n'ont pas vocation à être représentatifs. Utiliser des données de compteurs vélo pour augmenter leur représentativité aurait été un travail intéressant, mais en dehors du cadre de cette thèse. Cette partialité n'est cependant pas un problème lorsque l'on cherche à quantifier le nombre de cyclistes traversant une intersection. Des hypothèses fortes, notamment relatives au comportement des cyclistes lorsqu'ils traversent l'intersection, doivent tout de même être émises. Cela est moins problématique que lors de la construction de trajets individuels, car la quantité de véhicules est plus importante que leurs comportements lors de la simulation d'une intersection. Des données de compteurs de vélos sont donc utilisées dans le Chapitre 4.

## 2.6 Résumé

Cette section synthétise les différentes sources de données qu'il est possible d'utiliser pour décrire/analyser/prédire le comportement des cyclistes, leurs avantages ainsi que leurs inconvénients, et le choix de les utiliser ou non dans le cadre de ce travail de recherche.

**Les questionnaires de préférences :** Ils permettent d'avoir des informations détaillées sur les choix faits par les cyclistes. Mis devant plusieurs choix en situation contrôlée, les cyclistes peuvent effectuer et expliquer leurs choix. Cela permet de mieux comprendre la perception qu'ont les cyclistes de différentes situations, et donc d'adapter les politiques cyclables. Les situations sont présentées selon certaines variables descriptives. L'utilisation d'algorithmes d'apprentissage sur ces données a pour but d'expliquer l'influence de chacune de ces variables sur le choix des cyclistes. Utiliser les données comportementales issues de questionnaires de préférences sans variables descriptives n'a donc pas beaucoup de sens. Ces questionnaires posent de plus un problème de fiabilité, les choix théoriques faits par les cyclistes en situation contrôlée pouvant être différents de ceux qu'ils effectueraient en situation réelle. À cela s'ajoute le besoin de connaissances dans le domaine du transport pour la conception d'un questionnaire, les réponses des questionnaires précédents n'étant
pas publique. Ces 3 limitations majeures font des questionnaires de préférences un choix peu pertinent pour les travaux de cette thèse.

**Les systèmes de vélos en libre-service :** Les données sont abondantes et accessibles relativement facilement, car elles ne présentent que peu de caractéristiques relatives à la vie privée des cyclistes étudiés une fois un prétraitement basique effectué. Elles permettent d'étudier les flux de cyclistes à l'échelle d'une ville ou d'un quartier. Leur structure simple les rend utilisables par des algorithmes d'apprentissage sans utiliser de variables descriptives, pour faire de la prédiction de flux notamment. Cependant, les systèmes de vélo en libre-service ne récoltent dans la grande majorité des cas que des informations au niveau des stations dont ils sont constitués. Par conséquence, les analyses et les prédictions effectuées avec ces données sont majoritairement faites à l'échelle de la ville, et non à celle de trajets individuels. Cette limitation fait des données de systèmes de vélos libre-service un candidat non compatible avec les travaux de cette thèse.

**Les capteurs GPS :** Les traces GPS générées à l'aide de capteurs GPS outrepassent les limites de celles récoltées à partir des deux sources précédentes. Contrairement aux données des systèmes de vélos en libre-service, les traces GPS permettent d'étudier le comportement individuel des cyclistes. De plus, les informations sont passivement récoltées pendant des trajets réels et, moyennant un prétraitement adapté, sont utilisables par des algorithmes d'apprentissage sans nécessiter la définition de variables descriptives. Néanmoins, les traces GPS sont considérées comme données privées. Un prétraitement est donc nécessaire avant leur publication. Cet inconvénient limite le nombre de jeux de données disponibles publiquement. De plus, le prétraitement effectué avant publication peut faire perdre l'aspect "comportement individuel" des données. C'est notamment le cas des jeux de données Strava. Deux jeux de données de traces GPS sans prétraitements supprimant les comportements individuels ont cependant été trouvés : Véléval et MonRésoVélo. Le Chapitre 3 de cette thèse utilise ces jeux comme base d'une méthode de développement de modèle de choix d'itinéraire implicites. Le premier est le résultat d'un précédent projet auquel le laboratoire a participé. Il n'est pas mis à la disposition du public et n'a donc pas subi de prétraitement. Le deuxième est un jeu de données public dont le prétraitement (la suppression des premier et dernier points GPS de chaque trace) n'a pas supprimé les informations relatives aux comportements individuels des cyclistes.

**Les comptages de vélos :** Les données issues de comptages présentent les mêmes avantages et inconvénients que les systèmes de vélos en libre-service. Les jeux de données sont nombreux et accessibles publiquement, mais ceux-ci ne permettent pas d'étudier les trajets individuels des cyclistes lorsqu'ils sont utilisés seuls. Ils sont toutefois régulièrement utilisés en complément d'autres données, majoritairement des traces GPS. Les données de capteurs de vélos permettent de quantifier et/ou d'augmenter la représentativité des données utilisées. La représentativité n'étant pas un élément nécessaire à l'atteinte des objectifs du Chapitre 3, les données de capteurs de vélos n'ont pas été utilisées en complément des jeux de traces GPS choisis. Cependant, les données de capteurs de vélos sont assez représentatives du passage de cyclistes en un point donné. Celles-ci sont donc utilisées pour paramétrer les simulations d'un feu de circulation intelligent dans le Chapitre 4.
# Chapitre 3

## Modèles de choix d'itinéraire implicites

### 3.1 Introduction

L'objectif de ce chapitre est de générer des trajets individuels de cyclistes à partir de données comportementales. Ces trajets sont appelés des itinéraires cyclables dans la suite. Les études trouvées dans la littérature capables de produire des itinéraires cyclables utilisent majoritairement des modèles de choix d'itinéraire discrets. Les modèles de choix d'itinéraire discrets ont pour but l'analyse des comportements individuels parmi un ensemble limité d'options [94]. Une mesure de préférence, appelée utilité, est calculée pour chacune des options. L'utilisateur, considéré comme un être rationnel, est supposé choisir l'option ayant l'utilité la plus importante. Chaque option est décrite par des caractéristiques sélectionnées en amont. Un poids est affilé à chaque caractéristique. Ces poids sont le plus souvent calculés à l'aide d'une régression logistique. La somme des caractéristiques pondérées par leurs poids permet ensuite de calculer l'utilité de chaque option. Les modèles de choix d'itinéraire discrets créés spécifiquement pour les cyclistes [35, 34, 66, 65, 67, 36, 64, 63, 95] utilisent des itinéraires possibles comme options. Ces modèles sont donc capables de produire des trajets individuels, en sélectionnant l'itinéraire ayant l'utilité la plus importante. Les itinéraires choisis par les cyclistes peuvent être collectés par le biais de questionnaires de préférences [35, 34] ou bien de capteurs GPS [66, 65, 67, 36, 64, 63]. Dans le cas des questionnaires, les cyclistes choisissent leurs itinéraires parmi un ensemble d'itinéraires possibles. Dans le cas de capteurs GPS, les cyclistes choisissent leurs itinéraires eux-mêmes, et les itinéraires possibles doivent être générés à posteriori. Les variables utilisées pour décrire les caractéristiques des itinéraires choisis et possibles peuvent être de différentes natures. Elles sont cependant principalement d'ordre infrastructurel, comme le nombre de virages ou la proportion de pistes cyclables, global, comme la longueur du trajet ou la différence avec le chemin le plus court, dynamique, comme les conditions météorologiques ou le volume du trafic, ou encore social, comme l'âge, le sexe ou bien la possession d'une voiture.

Un problème bien connu associé aux modèles de choix d'itinéraire discrets est la taille très importante de l'ensemble des chemins possibles entre une origine et une destination. L'ensemble des itinéraires envisagés par un cycliste est bien évidemment un sous-ensemble de celui-ci. Ce sous-ensemble est néanmoins inconnu. Comme le modèle doit choisir un itinéraire parmi un ensemble de trajets possibles, la précision de la prédiction du modèle est étroitement liée à la qualité de cet ensemble. De plus, la sélection explicite de variables décrivant certaines caractéristiques des itinéraires ne permet qu'une analyse partielle des choix des cyclistes, car
toutes les caractéristiques ne peuvent être analysées en même temps. Cette limitation est d'autant plus présente que les caractéristiques sélectionnées sont pratiquement les mêmes dans toutes les études. La conception de nouvelles caractéristiques susceptibles d'affecter le comportement d'individus est une tâche difficile et multidisciplinaire. Enfin, les études développant des modèles de choix d'itinéraire discrets se concentrent principalement sur les caractéristiques influençant le plus les choix des cyclistes. En effet, les analyses s'intéressent très souvent plus à la compréhension des poids trouvés par le modèle qu'aux capacités de celui-ci à produire des trajets individuels.

Dans ce chapitre, une méthode de création de modèle de choix d'itinéraire est développée. L'objectif des modèles créés est de générer des itinéraires cyclables à partir d'une paire origine/destination (O/D). Les modèles créés sont dits implicites, car des représentations implicites remplacent les variables descriptives choisies explicitement dans les méthodes plus classiques. Les modèles développés avec cette méthode apprennent des représentations implicites de trajets effectués à l'aide d'algorithmes d'apprentissage automatique. Cette méthode a de plus l'avantage de ne pas nécessiter de jeu de trajets possibles. Les caractéristiques de celle-ci lui permettent donc de limiter les biais relatifs à la sélection des facteurs externes, ainsi qu'à la génération d'un jeu de trajets possibles. Les 2 contributions de ce chapitre peuvent être résumées comme suit :

- Les segments de route préférés des cyclistes d'un jeu de données sont identifiés à l'aide de la création de *clusters*.

- Une méthode de génération de traces basées sur l'expérience utilisant ces segments de route préférés ainsi qu'un réseau de neurones profond est développée.

<figure><img src="image_10.png" /><figcaption>FIGURE 3.1 – Diagramme résumant la méthode de création de modèles de choix d'itinéraire implicites présentée dans ce chapitre.</figcaption></figure>
## 3.2 Détail des données

Le temps de trajet (ou son coût) est le facteur principal pris en compte par les automobilistes lors du choix de leurs itinéraires [96, 97]. Si ce facteur reste crucial pour les cyclistes, les modèles de choix d'itinéraire existants montrent qu'ils sont également influencés par d'autres caractéristiques des trajets considérés. On peut citer par exemple le sentiment de sécurité sur les routes empruntées, le nombre d'intersections, la minimisation des pentes/tournants ou la maximisation de l'utilisation d'infrastructures cyclables [9]. Par conséquent, une première hypothèse est émise :

**Hypothèse 1.** Les cyclistes ont tendance à utiliser des segments de route qu'ils préfèrent, quitte à dériver du chemin le plus court jusqu'à leurs destinations.

Une comparaison qualitative et quantitative entre les itinéraires choisis par des cyclistes et les plus courts chemins entre leurs origines et destinations permet d'obtenir une première intuition sur la forme et la quantité de détours que les cyclistes sont prêts à faire. Dans cette section, les 2 jeux de données utilisés sont d'abord formellement présentés. La manière dont les plus courts chemins sont générés est détaillée et une comparaison quantitative puis qualitative entre ceux-ci et les itinéraires des cyclistes est effectuée.

### 3.2.1 Traces expérimentées

Le choix des jeux de données n'est pas discuté ici, car celui-ci est détaillé en dans le Chapitre 2. Deux jeux de données sont utilisés :

- Un ensemble privé de traces GPS provenant du projet Véléval (voir Section 2.3.2). Le résultat de ce projet est entre autre 2527 traces GPS contenues dans des fichiers GPX. Chaque trace GPS $t$ est une séquence de $N$ points ordonnés $t = \{p_1, ..., p_N\}$ avec chaque point $p_t = (\text{lat}_t, \text{lon}_t, \text{time}_t)$ composé d'une latitude, d'une longitude et d'un horodatage.

- L'ensemble de données fourni par la ville de Montréal au Canada, collecté par leur application MonRésoVélo (voir Section 2.3.3). 4881 traces GPS issues de cette application sont publiques. Elles ont été générées par des cyclistes entre juin 2013 et octobre 2015 et sont contenues dans un fichier JSON. Chaque trace $t$ est une séquence de $N$ points ordonnés $t = \{p_1, ..., p_N\}$ avec chaque point $p_t = (\text{lat}_t, \text{lon}_t)$ contenant une latitude et une longitude. D'autres informations telles que l'heure de départ et d'arrivée sont disponibles, seuls les points GPS sont utilisés. Les traces sont *mapmatchées* (voir Section 2.3) et anonymisées.

Les propriétés temporelles des traces sont ignorées, au profit d'une exploitation des propriétés spatiales uniquement. Ce choix a été fait dans le but de faciliter le paramétrage des algorithmes d'apprentissage utilisés plus tard. Les horodatages des traces du projet Véléval sont donc ignorés. L'algorithme Ramer-Douglas-Peucker [98] est utilisé sur les 2 jeux de données afin de réduire le nombre de points GPS des traces en minimisant la perte d'information. Le nombre de points GPS des jeux de données est environ divisé par 26 après utilisation de cet algorithme. Moins de points GPS signifie un temps de traitement plus court. Les différences de performances entre les 2 jeux de données sont discutées tout au long de ce travail. À noter tout de même que les trajets de Véléval sont quasiment tous des trajets domicile/travail là où les trajets MonRésoVélo peuvent avoir été effectués dans d'autres
buts comme la pratique sportive par exemple. Il est important de le préciser dans la mesure où l'hypothèse 1 n'a de sens que si le cycliste utilise le vélo dans le but d'atteindre une destination, et non pour une autre raison. Une méthode permettant de supprimer une partie des traces n'ayant probablement pas été générées dans ce but est explicitée en Section 3.2.3. Les traces GPS des cyclistes sont appelées "traces expérimentées" dans la suite de ce chapitre.

### 3.2.2 Traces générées

Dans le but de valider la première hypothèse émise, le chemin le plus court reliant l'origine et la destination de chaque trace expérimentée est généré en utilisant l'algorithme de Dijkstra. Celui-ci est exécuté sur un graphe routier $G$ mis à disposition par OpenStreetMap. Un graphe routier est un graphe orienté pondéré qui est une paire $G = (V, E)$ avec $V$ un ensemble de sommets et $E \subset \{(x,y) | (x,y) \in V^2 \wedge x \neq y\}$ un ensemble d'arêtes qui sont des paires ordonnées de sommets. Chaque arête possède un poids. Dans un graphe routier, les sommets représentent les intersections et les arêtes représentent les routes reliant 2 intersections. Les graphes routiers des villes de Lyon et Saint-Etienne pour les traces de Véléval et de Montréal pour les traces de MonRésoVélo sont générés. Leurs tailles sont respectivement de 451344 arêtes reliant 167243 nœuds, 91896 arêtes reliant 34138 nœuds et 1058253 arêtes reliant 381824 nœuds. Les poids attribués aux arêtes sont les longueurs des routes qu'elles représentent. L'algorithme de Dijkstra utilise les poids des arêtes pour calculer le chemin le plus court entre 2 points.

Une fonction de distribution cumulative (CDF pour *cumulative distribution function*) des différences de distance entre les traces expérimentées et les plus courts chemins est tracée par jeu de données. Elles sont montrées en Figure 3.2a et Figure 3.2b. Les détours en dessous des lignes rouges en pointillé sont négatifs. 8,5% des traces expérimentées de Véléval et 10,8% de celles de MonRésoVélo sont donc plus courtes que leurs plus courts chemins. Respectivement 4,5% et 7,7% de ces traces sont plus courtes de moins de 100 mètres. Cela est principalement dû à l'imprécision des capteurs GPS ayant capturé les traces : si une trace expérimentée et son chemin le plus court correspondant passent exactement par la même suite de segments de route, leurs distances ne seront pas les mêmes. Parfois, la trace expérimentée sera légèrement plus courte que le chemin le plus court, même si cela paraît paradoxal à première vue. Pour les traces plus courtes que leurs chemins le plus court restantes (4% des traces Véléval et 3,1% des traces MonRésoVélo), les différences de distance se situent entre 100 m et 4,1 km. Ce phénomène est dû au graphe routier mis à disposition par OpenStreetMap. Certaines routes existantes ne figurent pas dans le graphe. Si une trace expérimentée emprunte l'une d'entre elles, Dijkstra est obligé de faire un détour par rapport à la trace originale. Les traces dans ce cas de figure sont cependant minoritaires, et la différence de distance est dans la plupart des cas peu élevée. Leurs présences dans les jeux de données n'a donc pas d'influence significative sur les performances des modèles créés. Dans la suite de ce travail, les chemins le plus court sont appelés "traces générées".

### 3.2.3 Comparaisons des traces expérimentées et des traces générées

Pour vérifier que les trajets effectués par les cyclistes sont bien différents des chemins le plus court, 2 cartes de chaleurs sont tracées par jeu de données. La première contient toutes les traces expérimentées et la deuxième toutes les traces générées.
<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /><figcaption>FIGURE 3.2 – CDF des différences de distances entre les traces expérimentées et les traces générées des jeux de données.</figcaption></figure>
Une analyse qualitative des différences permet de confronter l'hypothèse 1. Il faut cependant noter qu'effectuer un détour à vélo entraîne une augmentation de l'effort physique fourni ainsi que du temps de trajet. Ces coûts ne doivent pas annuler les avantages offerts par l'utilisation de routes préférentielles. Dès lors, une seconde hypothèse peut être formulée :

**Hypothèse 2.** Il existe un seuil d'acceptation au-delà duquel les cyclistes refusent de faire un détour plus important.

Une analyse détaillée des CDFs précédemment tracées permet de confronter cette deuxième hypothèse.

## Cartes de chaleurs

Les cartes de chaleurs des trajets Véléval effectués à Lyon sont montrées en figure 3.3. Quel que soit le type de traces, il est possible de séparer la ville en trois : la partie Ouest, la partie centrale et la partie Est. La quasi-totalité des segments de route affichés en rouge se trouve dans la partie centrale, quel que soit le type de traces. Cela démontre une grande densité de traces, signe que le centre est très utilisé par les cyclistes, mais aussi par l'algorithme de chemin le plus court. La partie Est est elle aussi utilisée, mais contient moins de segments de route rouges et plus de segments de route bleus. L'utilisation des segments de cette partie de la ville est plus homogène, quel que soit le type de traces. Enfin, la partie Ouest est en grande partie délaissée par les traces expérimentées ainsi que par les traces générées. Même si ces trois parties sont discernables sur les 2 cartes de chaleur, il existe des différences notables entre celles-ci. Les plus marquantes se situent au centre. En effet, les traces générées forment un amas en plein centre de la ville, empêchant la distinction de plusieurs segments tant tous sont très utilisés. Les traces expérimentées quant à elles utilisent quelques segments discernables, notamment plusieurs successifs le long du Rhône traversant la partie centrale du Nord au Sud. À mesure que l'on s'éloigne de la partie centrale pour rentrer dans la partie Est, les segments affichés en rouge deviennent plus rares. Certains deviennent vert-jaune et d'autres deviennent bleus. Cependant, la carte des traces expérimentées contient plus de segments vert-jaune et ceux-ci vont plus loin, atteignant les bordures Sud et Est dans certains cas. Enfin, peu de différences sont notables entre les 2 cartes de chaleurs dans la partie Ouest.

Les cartes de chaleur du jeu de données MonRésoVélo sont montrées en figure 3.4. Les 2 cartes sont séparables en trois parties : l'hypercentre, le centre et le reste de la ville. Dans l'hypercentre, on observe une forte utilisation d'un nombre important de segments de route. À mesure que l'on s'éloigne de celui-ci, l'utilisation s'amenuise de manière assez hétérogène : certains segments restent très utilisés là où d'autres le sont beaucoup moins. Enfin, les segments de route éloignés du centre de la ville sont dans la plupart des cas utilisés de manière homogène. Il existe tout de même des différences entre traces expérimentées et traces générées dans chacune de ces trois parties. Dans l'hypercentre, les traces générées sont disséminées de manière à pouvoir discerner quelques routes particulièrement utilisées. Les traces expérimentées, elles, montrent une forte utilisation d'une grande partie des routes, créant ainsi un amas rendant la distinction de segments de route plus utilisés que les autres difficile. Lorsque l'on s'éloigne de l'hypercentre, les segments de route affichés en rouge sont moins nombreux pour les traces expérimentées et disparaissent quasi totalement pour les traces générées. La partie de la ville la plus éloignée du centre présente
<figure><img src="image_13.png" /><figcaption>FIGURE 3.3 – Cartes de chaleur des traces expérimentées (à gauche) et des traces générées (à droite) du jeu de données Véléval (Lyon).</figcaption></figure>

le plus de différences entre les 2 types de traces. Les traces générées utilisent cette partie de manière quasi homogène, avec une majorité de segments de route affichés en bleu. À l'inverse, on peut observer au moins 4 routes affichées en rouge qui atteignent quasiment la bordure de la carte de chaleur des traces expérimentées, signe que ces voies sont utilisées par une majorité des cyclistes. À ces voies rouges s'ajoute une multitude de segments de route affichés en jaune ou en vert, montrant une certaine hétérogénéité d'utilisation parmi les segments qui ne sont pas très fortement utilisés.

<figure><img src="image_14.png" /><figcaption>FIGURE 3.4 – Cartes de chaleur des traces expérimentées (à gauche) et des traces générées (à droite) du jeu de données MonRésoVélo (Mont-réal).</figcaption></figure>

Les observations faites sur les Figures 3.3 et 3.4 montrent des points communs mais aussi des différences dans le comportement des cyclistes ayant généré les 2 jeux de données. Tout d'abord, on observe une forte concentration de traces dans le centre des 2 villes. Que ce soit sur la carte de chaleur des traces expérimentées ou celles des traces générées, une grande partie des voies affichées en rouge s'y trouve. Il est plus facile de discerner certaines routes dans la partie centrale de Lyon sur la carte des traces expérimentées que sur celle des traces générées. Cela indique que
les cyclistes ont tendance à utiliser certaines voies plus que d'autres, quitte à ne pas
utiliser le chemin le plus court jusqu'à leurs destinations. Le constat semble être
opposé sur les cartes de chaleurs de MonRésoVélo. Cela est dû à la différence de
taille entre Montréal et Lyon. Lyon étant environ 10 fois plus petite que Montréal,
il est nécessaire de dézoomer les cartes de chaleurs de MonRésoVélo pour englober
une majorité des traces du jeu de données. Si l'on zoome sur l'hypercentre de Mont-
réal, on observe que les traces expérimentées se concentrent principalement sur trois
axes, là où les traces générées utilisent l'espace de manière plus homogène. Lorsque
l'on s'éloigne du centre de la ville en direction de l'Ouest, une zone très peu utilisée
par les cyclistes Véléval est discernable. Cela s'explique par la topologie de la ville
de Lyon. En effet, celle-ci est constituée de 2 collines, toutes 2 situées dans sa par-
tie Ouest. Ces collines sont généralement évitées par les cyclistes pour des raisons
évidentes de dénivelé. La ville de Montréal est aussi constituée d'une colline ainsi
que d'un mont. Au Sud de l'hypercentre, ils sont tous 2 évités par les cyclistes ainsi
que par l'algorithme de chemin le plus court, bien que ce dernier fasse quelques
exceptions. Le comportement des cyclistes face aux dénivelés semblent là encore
identiques au sein des 2 jeux de données, malgré des différences évidentes visibles
entre les 2 figures. Enfin, lorsque l'on s'éloigne du centre sur une partie relativement
plane, les observations sont identiques quel que soit le jeu de données : les segments
de route affichés en rouge sont moins nombreux au profit de segments vert-jaune
et bleus. Les segments rouges et vert-jaune sont tout de même plus longs et plus
nombreux à l'extérieur du centre sur les cartes de chaleurs des traces expérimentées.
Cela montre que les cyclistes utilisent certains segments de route spécifiques quitte
à s'éloigner du chemin le plus court jusqu'à leurs destinations dans ces zones aussi.

Toutes ces observations confirment la première hypothèse. Les cyclistes sont prêts
à emprunter des segments de route préférés, même si cela signifie faire un détour par
rapport au chemin le plus court jusqu'à leurs destinations. Cependant, ils semblent
vouloir minimiser la distance parcourue pour accéder à ces routes préférées. C'est
pourquoi de moins en moins de segments routes spécifiques sont visibles à mesure
que l'on s'éloigne du centre-ville, au profit d'une utilisation de l'espace de plus en
plus homogène. Les itinéraires des cyclistes ayant généré les 2 jeux de données se-
raient donc un compromis entre l'utilisation de segments de route préférés, et de
chemins le plus court pour y accéder.

CDF

L'hypothèse 1 semble être valide pour les 2 jeux de données étudiés. Une analyse
des CDFs des différences de distances entre les traces expérimentées et les traces
générées (Figure 3.2) peut être effectuée pour confronter la deuxième. Les 2 CDFs
sont très similaires, avec une grande majorité des détours compris entre 0 et 3 km.
Une augmentation assez importante de la taille des détours est visible lorsque l'on
regarde les 10 derniers pourcents de traces. En effet, 90 % des détours faits par les
cyclistes sont inférieurs à 2,4 km pour Véléval et inférieurs à 3,2 km pour MonRéso-
Vélo, là où le détour maximal atteint presque 100 km pour les 2 jeux de données. Cela
est cohérent avec la deuxième hypothèse. La plupart des cyclistes ne souhaitent pas
faire de détours au-delà d'une certaine distance, car cela signifierait pour eux que le
coût de celui-ci devient plus important que les bénéfices qu'il apporte.
## Suppression des traces faisant de trop gros détours

Même si une majorité des trajets des 2 jeux de données font moins de 3 km de détour, certains en effectuent des beaucoup plus grands. Il est probable que les cyclistes acceptant d'effectuer des détours de quasiment 100 km n'utilisent pas le vélo comme un moyen de transport, mais comme une activité sportive ou pour le loisir. Le comportement des cyclistes ayant pour but d'arriver à une destination et ceux ayant pour but de faire du sport sont sans aucun doute très différents, et peuvent difficilement être étudiés en parallèle. Les hypothèses formulées dans ce chapitre ne sont cohérentes que dans le cas de cyclistes cherchant à atteindre une destination. C'est pourquoi les 10% de traces faisant les détours les plus longs sont supprimés des 2 jeux de données. La Figure 3.5 montre les CDFs des différences de distances entre les traces expérimentées et les traces générées des 2 jeux de données après cette suppression. Le nombre de traces du jeu de données Véléval passe à 2300 et celui du jeu de données MonRésoVélo à 4365.

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

FIGURE 3.5 – CDF des différences de distances entre les traces expérimentées et les traces générées des jeux de données après la suppression des traces faisant de trop gros détours.
### 3.2.4 Résumé de la section

La Section 3.2 présente les jeux de données utilisés en détail. Un chemin le plus court (appelées traces générées dans la suite) est calculé entre l'origine et la destination de chaque trace GPS (appelées traces expérimentées dans la suite). Deux hypothèses sont alors formulées :

- les cyclistes n'empruntent pas le chemin le plus court au profit de segments de route qu'ils préfèrent

- les cyclistes ont une distance de détour maximum qu'ils acceptent d'effectuer pour utiliser ces segments

Ces hypothèses ne sont valables que dans le cadre de l'utilisation du vélo pour atteindre une destination. L'affichage de cartes de chaleur affichant les différents types de traces permet de confirmer la première hypothèse. Une CDF des différences de distance entre les traces générées et les traces expérimentées permet de confirmer la seconde.

## 3.3 Identification des segments de route préférés

Les cyclistes des 2 jeux de données étudiés ont tendance à faire des détours pour emprunter des segments de route qu'ils préfèrent, même si ceux-ci ont une limite à partir de laquelle ils considèrent que le détour est trop long. Afficher toutes les traces expérimentées sous la forme de carte de chaleurs permet d'identifier visuellement les segments de route utilisés par une majorité de cyclistes. Des segments de route préférés plus locaux, c'est-à-dire utilisés uniquement par des cyclistes passant par un même secteur, doivent cependant exister. Ces segments ne seraient que peu voir pas identifiables lors de l'affichage de l'entièreté des jeux de données. La décomposition des jeux de données en groupes de traces expérimentées partageant des segments de route permettrait de confirmer l'existence de ces segments de route préférés, et de les identifier par la même occasion. L'utilisation d'un algorithme de clustering parait dès lors une approche intéressante pour ajouter de l'information aux jeux de données. Les algorithmes de clustering sont des algorithmes d'apprentissage non supervisé permettant de former des groupes de données similaires appelés clusters. Dans le cas des traces expérimentées, chaque cluster créé permettra l'identification d'un ou plusieurs segments de route préférés par les cyclistes. Les clusters les plus grands contiendront les segments de route préférés globaux, et les plus petits les segments de route préférés locaux. Dans cette section, 2 métriques de distance ainsi que 2 algorithmes de clustering sont testés pour construire des clusters pertinents.

### 3.3.1 Métriques de distance

Pour pouvoir regrouper des traces partageant des segments de route, il est nécessaire de quantifier la distance entre celles-ci. Il existe plusieurs méthodes pour y parvenir, la plus connue étant l'utilisation d'un algorithme de mapmatching (voir Section 2.3). La différence symétrique des ensembles d'arêtes de 2 traces permet de quantifier la distance entre celles-ci. Malgré la robustesse de ces algorithmes, 2 méthodes plus simples sont utilisées ici. Ce choix est motivé par la difficulté d'implémentation d'un algorithme de mapmatching, ainsi que par les besoins de ce travail qui se limitent à une quantification de segments en commun, sans avoir besoin de plus de détails. La première métrique utilise une méthode développée spécialement pour ces travaux. La deuxième utilise la distance géodésique, une distance couramment utilisée dans le cadre de points géographiques.
## Distance personnalisée

Cette métrique de distance a pour but de quantifier les segments de route communs entre 2 traces. Elle utilise pour se faire une réduction de l'espace. La carte est divisée en cellules. Pour limiter le coût en temps et en ressources, seules les cellules par lesquelles passe au moins une trace sont calculées. Chaque trace se voit attribuée un ensemble de cellules appelé ensemble direct. Cet ensemble de cellules contient toutes les cellules par lesquelles la trace passe directement. Les traces expérimentées de Véléval n'étant pas *mapmatchées*, il arrive que 2 traces sur un même segment de route passent par 2 cellules différentes. Pour corriger ce problème, un deuxième ensemble est attribué à chaque trace. Cet ensemble, appelé ensemble étendu et noté $\tau$ par la suite, contient les cellules que la trace traverse directement ainsi que toutes les cellules existantes voisines de celles-ci. Pour rappel, une cellule est considérée comme existante uniquement si au moins une trace la traverse directement. Les ensembles étendus dépendent de l'ensemble de traces utilisé, et doivent donc être calculés après la génération des ensembles directs. La figure 3.6 montre un exemple graphique de l'intersection entre les ensembles étendus de 2 traces.

<figure><img src="image_17.png" /><figcaption>FIGURE 3.6 – Exemple graphique de l'intersection entre les ensembles étendus de 2 traces.</figcaption></figure>

Soit $t_1$ et $t_2$ 2 traces, $\tau_1$ l'ensemble étendu de $t_1$ et $\tau_2$ l'ensemble étendu de $t_2$, la distance $D_{t_1t_2}$ entre $t_1$ et $t_2$ est la distance de Jaccard [99] entre $\tau_1$ et $\tau_2$, définie comme suit :

$$D_{t_1t_2} = 1 - \frac{|\tau_1 \cap \tau_2|}{|\tau_1 \cup \tau_2|}$$
## Distance géodésique

La distance géodésique entre 2 points géographiques est la plus courte distance à la surface d'un modèle ellipsoïdal de la terre entre ses 2 points. Cette distance est couramment utilisée dans le cadre de points géographiques. Dans ce chapitre, la distance géodésique est calculée en utilisant la méthode développée par Karney [100] avec le modèle ellipsoïdal WGS 84. La distance géodésique entre 2 traces est la moyenne des distances géodésiques entre les points de celles-ci. Les traces doivent donc être pré-traitées au préalable pour avoir le même nombre de points géographiques. Cette distance couramment utilisée dans le cadre de points géographiques a l'avantage de nécessiter moins de calculs que la distance personnalisée.

### 3.3.2 Algorithmes de clustering

Soit un ensemble de $n$ observations $(x_1, x_2, ..., x_n)$ et une métrique permettant de mesurer la distance entre elles. L'objectif d'un algorithme de *clustering* est de former différents *clusters* d'observations proches les unes des autres. Il existe une multitude d'algorithmes de *clustering* possédant tous leurs avantages et leurs inconvénients. La pertinence de l'utilisation d'un algorithme de *clustering* ainsi que son paramétrage dépend du type de données (avec ou sans bruit, taille du jeu...) et des propriétés des *clusters* recherchés (nombre, taille, forme...) [101]. Deux des algorithmes les plus connus sont comparés dans ce chapitre : DBSCAN [102] et k-médoïdes [103] (basé sur k-means [104]). Le fonctionnement de chacun d'eux est d'abord expliqué.

#### DBSCAN

DBSCAN (*Density-Based Spatial Clustering of Applications with Noise*) est un algorithme de *clustering* basé sur la densité. Ce type d'algorithme est particulièrement adapté aux données contenant du bruit. DBSCAN permet de former des *clusters* de formes arbitraires et d'évincer les observations trop éloignées des autres (aussi appelé le bruit). DBSCAN possède 2 paramètres : *minPts* et $\varepsilon$. *minPts* définit le nombre minimum de points dans une région dense pour qu'elle puisse appartenir à un *cluster*. $\varepsilon$ définit la distance maximale que 2 points peuvent avoir pour appartenir à la même région dense. DBSCAN parcourt les observations et construit le $\varepsilon$-voisinage de celles-ci. Si ce voisinage contient un nombre de points supérieur ou égal à *minPts*, un nouveau *cluster* contenant l'observation et ses voisins est créé. DBSCAN tente ensuite d'agrandir le *cluster* en rajoutant les voisins des voisins ayant un $\varepsilon$-voisinage suffisant et ainsi de suite, jusqu'à ce que plus aucun $\varepsilon$-voisinage ne soit assez grand. L'algorithme 1 montre le fonctionnement détaillé de DBSCAN.

- **Avantage** : peu de temps de calcul (complexité d'environ $O(n\log(n))$ avec des paramètres corrects)

- **Inconvénient** : assez difficile à paramétrer (2 paramètres pouvant être assez abstraits)

#### k-médoïdes

L'algorithme de *clustering* le plus connu et le plus utilisé est sûrement k-means. k-means prend en paramètre un nombre de *clusters* $k$ et en entrée les observations
Algorithme 1 : Algorithme DBSCAN

Data : ε une distance, minPts une taille de cluster minimum et X un ensemble de n observations

Result : S un ensemble de clusters

S ← {};
/* l'ensemble des clusters est initialisé vide */
B ← {};
/* l'ensemble du bruit est initialisé vide */
T ← {};
/* l'ensemble des observations traitées est initialisé vide */
for x ∈ X do

/* pour toutes les observations */

if x ∉ T then

Vₓ ← trouverVoisins(x,ε);
if |Vₓ| < minPts then
/* si le nombre de voisin est insuffisant */
B ← B/{x};
T ← T/{x};
/* x est considéré comme étant du bruit */

else

c ← {x};
/* un nouveau cluster c est initialisé avec x */
T ← T/{x};
/* ...et à T l'ensemble des observations traitées */

for v ∈ Vₓ do

/* pour tous les voisins de x */
if v ∈ B then

/* si v est considéré comme du bruit */
B ← B\{v};
/* v n'est plus considéré comme du bruit... */
c ← c/{v};
/* ... et est intégré à c */

else if v ∉ T then

/* si v n'a pas encore été traité */
c ← c/{v};
/* on ajoute v au cluster c... */
T ← T/{v};
/* ...et à T l'ensemble des observations traitées */
V_v ← trouverVoisins(v,ε);

if |V_v| ≥ minPts then

/* si le nombre de voisin de v est suffisant... */
Vₓ ← Vₓ ∪ V_v;
/* ... ils sont ajoutés aux candidats potentiels de c */

end

end

S ← S/c;
/* le cluster c est ajouté à l'ensemble des clusters */

end

end

end
sous la forme de vecteurs de même dimension. Son but est de partionner les *n* observations en *k* clusters $S = \{S_1, S_2, S_3, ..., S_k\}$ en minimisant la variance inter-cluster. Formellement, l'objectif est de trouver :

$$ \operatorname*{argmin}_{S} \sum_{i=1}^{k} \sum_{x_{j} \in S_{i}} \|x_{j} - \mu_{i}\|^{2} $$

où $\mu_i$ est le barycentre de $S_i$ et $||.||^2$ la norme euclidienne. La notion de barycentre n'est pas définie pour la distance personnalisée. k-means est donc difficilement utilisable avec celle-ci. k-médoïdes est un algorithme similaire à k-means. Il prend lui aussi un nombre de clusters *k* en paramètre et minimise la distance entre les points d'un même cluster et un point désigné comme central. Cependant, ce point central n'est plus le barycentre, mais une des observations appelée médoïde. La distance personnalisée est donc utilisable avec cet algorithme. Plusieurs variantes de k-médoïdes existent. L'algorithme 2 décrit le fonctionnement de PAM (Partitioning Around Medoids), la variante utilisée dans ce chapitre. La fonction intialise Medoides prend en paramètre un nombre *k* et l'ensemble des observations X et renvoie un ensemble de *k* observations médoïdes. La fonction creerClusters prend en paramètres l'ensemble des observations X et un ensemble de *k* médoïdes *M*. Chaque observation est mise dans le cluster du médoïde le plus proche. L'ensemble des clusters finaux ainsi que la somme des distances entre chaque observation et le médoïde de son cluster sont renvoyés.

- **Avantage** : facile à paramétrer (un seul paramètre, le nombre de clusters dé- siré)

- **Inconvénient** : temps de calcul assez long (complexité $O(k(n-k)^2)$ quand non optimisé)

### 3.3.3 Paramétrage

Pour paramétrer correctement un algorithme de clustering, il est nécessaire de définir les caractéristiques des clusters recherchées. Le choix de ces caractéristiques dépend du cadre dans lequel ceux-ci vont être utilisés. Quatre caractéristiques sont choisies pour mesurer la qualité des clusters créés. Elles sont expliquées ainsi que les raisons de leur choix dans le cadre de l'identification de segments de route préférés. Ces caractéristiques, ainsi qu'une analyse visuelle des clusters, sont ensuite utilisées pour trouver les meilleurs paramètres des algorithmes testés. DBSCAN et k-médoïdes fonctionnant assez différemment, certaines caractéristiques ne sont pertinentes que pour un seul d'entre eux.

- **Nombre de grands clusters** : Un grand cluster est défini comme un cluster contenant au moins 2 % des observations du jeu de données. La présence de grands clusters permet de s'assurer que les segments de route préférés globaux sont bien identifiés. Cependant, ceux-ci demandent vérification pour s'assurer qu'ils ne contiennent pas de traces trop éloignées les unes des autres.

- **Coefficient de silhouette** : La silhouette est un coefficient couramment utilisé pour valider la pertinence de clusters. Le coefficient de silhouette d'une observation est la différence entre la distance moyenne avec les observations appartenant au même cluster (cohésion) et la distance moyenne avec les observations appartenant aux clusters voisins (séparation). La silhouette varie de -1 à 1. Une valeur élevée indique que l'observation est bien intégrée à
Algorithme 2 : Algorithme PAM

Data : k un nombre de clusters , X un ensemble de n observations

Result : Un ensemble S de k clusters

M ← intialiseMedoides(k, X);
/* M est l'ensemble des médoïdes */
S, cbest ← creerClusters(M, X \ M);

do

c ← cbest;
for m ∈ M do
| /* pour tout les médoïdes m */
for o ∈ X \ M do
| /* pour toutes les observations non médoïdes o */
Mnew ← M \ {m} ;
Mnew ← Mnew / {o} ;
/* Mnew est l'ensemble des médoïdes M avec o à la place
de m */
Snew, cnew ← creerClusters(Mnew, X \ Mnew) ;
if cnew < cbest then
| /* si la nouvelle configuration est mieux que la
meilleure vue jusqu'à maintenant, on la retient */
cbest ← cnew;
obest ← o;
mbest ← m;
Sbest ← Snew;
end
end
end
if cbest < c then
| /* si une configuration testée est meilleure que la
configuration actuelle, la configuration actuelle
devient la configuration testée */
M ← M \ {mbest} ;
M ← M / {obest} ;
S ← Sbest;
end
while cbest < c;
/* tant qu'une meilleure configuration a été trouvée */
son *cluster*, et suffisamment éloignée des *clusters* voisins. La moyenne de la silhouette de toutes les observations non considérées comme du bruit est calculée. Un bon score de silhouette signifie que les segments de route préférés sont bien discernables dans les *clusters*, et que chaque segment de route n'est identifié que dans un seul d'entre eux.

- **Bruit (uniquement pour DBSCAN)** : Comme dit plus haut, DBSCAN considère les observations trop éloignées des autres comme du bruit. Un DBSCAN mal paramétré peut soit considérer la majorité des données comme du bruit, soit ne pas détecter les observations trop éloignées des autres. Si une majorité des traces sont considérées comme du bruit, les segments de route identifiés ne seraient représentatifs que d'une petite partie des cyclistes ayant généré les jeux de données. D'autre part, si aucune trace n'est considérée comme du bruit, les *clusters* risquent de contenir des traces ne partageant pas ou peu de segments de route. La qualité des segments de route préférés identifiés serait alors moindre.

- **Nombre de clusters (uniquement pour DBSCAN)** : Un trop grand nombre de *clusters* peut signifier qu'ils ne contiennent en moyenne pas suffisamment de traces pour identifier les segments de route préférés globaux, ou que les mêmes segments de route préférés sont identifiées dans plusieurs *clusters*. Peu de *clusters* peut en revanche signifier que des segments de route locaux existent et ne sont pas identifiés. Afficher le nombre de *clusters* créé n'est pas pertinent pour k-médoïdes, car c'est *k* qui le définit.

## DBSCAN

Les Figures 3.7 et 3.8 montrent l'évolution de chaque variable pour les *clusters* produits par DBSCAN selon $\varepsilon$. Cet affichage est effectué dans un premier temps pour plusieurs *minPts* dans le but de le fixer. *minPts* = 3 s'est avéré être le meilleur choix pour Véléval quelle que soit la métrique de distance utilisée (Figures 3.7a et 3.7b), ainsi que pour MonRésoVélo avec la distance personnalisée (Figure 3.8a). Pour MonRésoVélo et la distance géodésique, *minPts* = 2 est utilisé (Figure 3.8b). $\varepsilon$ varie de 0.1 à 0.9 pour la distance personnalisée et de 0.1 à 2 pour la distance géodésique. La distance personnalisée ne pouvant dépasser 1, un $\varepsilon$ supérieur n'aurait pas de sens. Pour la distance géodésique, les résultats avec $\varepsilon$ > 2 sont peu intéressants avec très peu de *clusters* contenant quasiment toutes les traces. Le bruit diminue à mesure que $\varepsilon$ augmente quel que soit le jeu de données ou la métrique utilisée. Une faible valeur de $\varepsilon$ signifie que seuls les points très proches les uns des autres sont regroupés. À mesure que $\varepsilon$ augmente, des points plus éloignés peuvent être placés dans le même *cluster*. DBSCAN trouve donc de moins en moins de points ne pouvant appartenir à aucun *cluster*.

Le comportement de DBSCAN avec le jeu de données Véléval diverge cependant selon la métrique de distance utilisée. Avec la distance personnalisée, le nombre de *clusters* ainsi que le score de silhouette commencent par augmenter jusqu'à atteindre une valeur maximum après laquelle ils diminuent. Lorsque le $\varepsilon$-voisinage des observations augmentent, plus de *clusters* se créent et ceux-ci s'étendent plus. À partir de $\varepsilon$ = 0.4, le $\varepsilon$-voisinage des observations permet à certains *clusters* de trop s'étendre. Ces *clusters* absorbent des observations qu'il aurait mieux valu affilier à des *clusters* distincts, faisant ainsi chuter le score de silhouette et le nombre de *clusters*. À partir de $\varepsilon$ = 0.5, le nombre de grands *clusters* chute aussi, car certains *clusters* s'étendent
tellement qu'il est plus difficile de créer des grands *clusters* avec les observations restantes.

Avec la distance géodésique, il y a 2 grands *clusters* lorsque $\varepsilon$ vaut 0.1 contre cinq avec la distance personnalisée. Le nombre maximum de grands *clusters* formés est de sept avec la distance personnalisée contre cinq avec la distance géodésique. Les traces semblent donc plus éloignées les unes des autres lorsque la distance géodésique est utilisée. Cela est confirmé par le nombre de *clusters*, constamment plus important avec la distance géodésique lorsque $\varepsilon$ est dans l'intervalle [0.1, 0.9]. Le score de silhouette commence par augmenter jusqu'à $\varepsilon = 0.3$ avant de diminuer jusqu'à son minimum à $\varepsilon = 0.6$ puis de réaugmenter jusqu'à son maximum à $\varepsilon = 2$. Là en-core, certains *clusters* s'étendent de plus en plus, améliorant les performances dans un premier temps puis les dégradant ensuite. Mais, avec la distance géodésique, les performances augmentent lorsque certains de ces grands *clusters* deviennent assez volumineux pour empêcher la formation d'autres grands *clusters*. La meilleure confi-guration trouvée par DBSCAN est avec $\varepsilon = 2$. Cette configuration créée trois *clusters*, dont un possédant 76 % des traces et un autre en possédant 23 %. Les traces semblent tellement uniformément distantes les unes des autres que DBSCAN ne peut diviser ces grands *clusters* sans diminuer le score de silhouette moyen. DBSCAN est donc peu adapté à la distance géodésique pour le jeu de données Véléval.

On observe les mêmes phénomènes lorsque DBSCAN est utilisé avec le jeu Mon-RésoVélo (Figure 3.8). Les différences avec Véléval ne se situent pas sur les variations des caractéristiques selon le paramétrage, mais sur les valeurs qu'elles atteignent. Par exemple, il y a systématiquement moins de grands *clusters* créés avec MonRéso-Vélo. MonRésoVélo contient des traces crowdsourcées et situées sur une zone plus large que celle de Véléval. Les différences entre les traces de MonRésoVélo sont telles que DBSCAN a plus de mal à étendre les *clusters*. Pour les mêmes raisons, le score de silhouette moyen est systématiquement plus bas avec MonRésoVélo. On peut enfin noter que la meilleure configuration trouvée avec la distance géodésique avec Mon-RésoVélo est constitué de 13 *clusters* dont un contenant 97 % des traces. Il semble que DBSCAN ne soit pas non plus adapté à la distance géodésique lorsqu'il est uti-lisé avec MonRésoVélo.

## k-médoïdes

La Figure 3.9 montre l'évolution du nombre de grands *clusters* et du score de silhouette moyen des *clusters* produits par k-médoïdes selon *k* pour le jeu de données Véléval. Le nombre de *clusters* *k* varie de 10 à 300 avec un pas de 10. *k* ne dépasse pas 300 car le temps de calcul devient trop long. La Figure 3.9a montre ces résultats pour la métrique de distance personnalisée et la Figure 3.9b pour la métrique de distance géodésique. On remarque que l'évolution des 2 caractéristiques est quasi-ment la même quelle que soit la métrique de distance utilisée. Le nombre de grands *clusters* commence par augmenter rapidement jusqu'à ce que *k* atteigne 30. La majorité des *clusters* créés jusque-là sont des grands *clusters*. Le nombre de *clusters* total semble insuffisant, car k-médoïdes est obligé de mettre une grande partie du jeu de données dans chacun d'eux. Cela est confirmé par l'évolution du score de silhouette moyen qui augmente grandement entre $k = 10$ et $k = 30$ *clusters*. Le nombre de grands *clusters* chute ensuite entre $k = 30$ et $k = 130$, passant de 24 à 7 pour la distance personnalisée et de 21 à 5 pour la distance géodésique. Le score de silhouette augmente lui constamment sur cet intervalle. *k* a atteint une valeur suffisante pour permettre à k-médoïdes de diviser les grands *clusters* en plus petits. Les traces trop
<figure><img src="image_18.png" /><figcaption>FIGURE 3.7 – Évolution du nombre de grands *clusters* (courbe noire), du score de silhouette moyen (courbe bleue), du nombre de *clusters* (courbe rouge) et du bruit (courbe verte) des *clusters* créés par DBS-CAN selon $\varepsilon$ pour le jeu de données Véléval.</figcaption></figure>
<figure><img src="image_19.png" /><figcaption>FIGURE 3.8 – Évolution du nombre de grands *clusters* (courbe noire), du score de silhouette moyen (courbe bleue), du nombre de *clusters* (courbe rouge) et du bruit (courbe verte) des *clusters* créés par DBS-CAN selon $\varepsilon$ pour le jeu de données MonRésoVélo.</figcaption></figure>
éloignées ne sont désormais plus dans les mêmes grands *clusters*. Cela augmente naturellement le score de silhouette moyen. Cette tendance continue plus doucement jusqu'aux alentours de $k = 200$. Le nombre de grands *clusters* et le score de silhouette stagnent ensuite, respectivement à 5 et 0.48 pour la distance personnalisée et 3 et 0.54 pour la distance géodésique. Une légère augmentation du nombre de grands *clusters*, accompagnée d'une légère diminution du score de silhouette, sont visibles sur un intervalle aux alentours de $k = 250$. Ce phénomène est probablement dû à un minimum local trouvé par k-médoïdes.

<figure><img src="image_20.png" /><figcaption>FIGURE 3.9 – Évolution du nombre de grands *clusters* (courbe noire) et du score de silhouette moyen (courbe bleue) des *clusters* créés par k-médoïdes selon $k$ pour le jeu de données Véléval.</figcaption></figure>

On observe une évolution similaire des 2 caractéristiques pour le jeu de données MonRésoVélo (Figure 3.10). On peut noter cependant quelques différences. Premièrement, le nombre de grands *clusters* augmente cette fois-ci jusqu'à $k = 50$. MonRésoVélo étant plus grand que Véléval, il est logique que k-médoïdes ait besoin d'un nombre de *clusters* plus important avant de pouvoir se permettre de commencer à diviser ceux-ci. La chute du nombre de grands *clusters* est aussi plus rapide, se finissant cette fois-ci à $k = 100$. La tendance à la baisse continue jusqu'à $k = 200$, où le nombre de grands *clusters* atteint 0. Les différences plus importantes entre les traces MonRésoVélo en sont là encore la cause. Celles-ci semblent être trop éloignées les unes des autres pour permettre la création d'un *cluster* contenant 2 % du jeu de données, quelle que soit la métrique de distance utilisée. Cela explique aussi le score de silhouette moyen qui augmente moins vite et n'atteint que 0.22 pour la distance personnalisée et 0.31 pour la distance géodésique.

## Algorithmes et paramètres retenus

Au vu des courbes détaillées précédemment, DBSCAN ne semble pas être un algorithme adapté lorsque utilisé avec la distance géodésique. Cependant, les performances de celui-ci sont proches de celles de k-médoïdes avec la distance personnalisée. En parallèle, les performances de k-médoïdes sont assez similaires quelle que soit la métrique de distance utilisée. Une analyse plus détaillée des *clusters* est
<figure><img src="image_21.png" /><figcaption>FIGURE 3.10 – Évolution du nombre de grands *clusters* (courbe noire) et du score de silhouette moyen (courbe bleue) des *clusters* créés par k-médoïdes selon *k* pour le jeu de données MonRésoVélo.</figcaption></figure>

nécessaire pour trouver le paramétrage le plus adapté à la problématique de cette section pour chaque jeu. L'analyse effectuée précédemment permet tout de même de ne retenir que six paramétrages. Ceux-ci permettent un compromis entre le score de silhouette moyen et le nombre de grands *clusters*. Ils sont présentés dans le tableau 3.3.3.

<table><thead><tr><th>Jeu de données</th><th>Algorithme</th><th>Distance</th><th>Paramétrage</th><th>clusters</th><th>Grands clusters</th><th>Silhouette</th></tr></thead><tbody><tr><td rowspan="3">Véléval</td><td>DBSCAN</td><td>personnalisée</td><td>ε = 0.4</td><td>144</td><td>4</td><td>0.42</td></tr><tr><td>k-médoïdes</td><td>personnalisée</td><td>k = 150</td><td>150</td><td>7</td><td>0.45</td></tr><tr><td>k-médoïdes</td><td>géodésique</td><td>k = 110</td><td>110</td><td>7</td><td>0.5</td></tr><tr><td rowspan="3">MonRésoVélo</td><td>DBSCAN</td><td>personnalisée</td><td>ε = 0.5</td><td>254</td><td>3</td><td>0.13</td></tr><tr><td>k-médoïdes</td><td>personnalisée</td><td>k = 190</td><td>190</td><td>1</td><td>0.18</td></tr><tr><td>k-médoïdes</td><td>géodésique</td><td>k = 180</td><td>180</td><td>1</td><td>0.28</td></tr></tbody></table>

### 3.3.4 Analyse visuelle des plus grands clusters

Une analyse visuelle des *clusters* est effectuée pour chaque paramétrage. L'objectif des *clusters* est d'identifier des segments de route préférés. Afficher toutes les traces contenues dans un *cluster* permet de confirmer ou non si celles-ci passent effective-ment par un ou plusieurs segments de route communs. Des cartes de chaleurs sont affichées dans un souci de visibilité. Celles-ci utilisent les mêmes cases que la mé-trique de distance personnalisée (voir Section 3.3.1). Toutes les cases traversées par au moins une trace d'un *cluster* sont générées. Un point est affiché pour chacune d'entre elles. La position du point est le centre de la case, et plus la case est traversée par des traces, plus le point est gros et rouge. Les Figures 3.3 et 3.4 utilisent le même principe. Pour rester concis, seules les cartes de chaleurs des plus grands *clusters* de chaque paramétrage sont affichées. Plus un *cluster* contient de traces, plus il est pro-bable qu'au moins l'une d'entre elles ne partage de segments de route avec aucune
autre. Cela fait de la qualité du plus grand *cluster* créé un indicateur assez pertinent de la qualité générale d'un paramétrage.

Les cartes de chaleur des trois paramétrages retenus pour le jeu de données Véleval sont affichées en Figure 3.11. Le *cluster* contenant le plus de traces est celui créé par DBSCAN (Figure 3.11a) avec 70 traces. On discerne trois segments de route particulièrement rouges. Ces segments sont utilisés par quasiment toutes les traces du *cluster*. Une zone bleue assez importante est visible à l'est de ces segments. Cette zone peut être représentative de traces ne passant pas par les segments rouges, ou le début de traces passant par ceux-ci. Une petite zone bleue est aussi visible au Nord-Ouest. Le plus grand *cluster* créé par k-médoïdes avec la distance personnalisée contient les mêmes segments rouges (Figure 3.11b). Celui-ci ne contient cependant que 61 traces. Il est intéressant de constater que les mêmes segments de route préférés sont identifiables dans le plus grand *cluster* des 2 algorithmes. La petite zone bleue au Nord-Ouest est visible elle aussi. Le *cluster* créé par k-médoïdes ne contient néanmoins pas la zone bleue à l'est des segments rouges. Celle-ci est remplacée par un mince filet bleu, probablement causé par une ou 2 traces rejoignant ceux-ci. Le *cluster* créé par k-médoïdes avec la distance géodésique contient lui aussi 61 traces (Figure 3.11c). Deux segments de route sont visibles, différents de ceux des 2 premiers *clusters*. Ceux-ci sont reliés à 2 segments rouge-verts, utilisés par une majorité des traces, mais non par la quasi-totalité de celles-ci. Une grande zone bleue semblable à celle présente sur la Figure 3.11a s'étend dans toutes les directions autour de ces segments. La distance géodésique quantifie la proximité entre les points géographiques des traces. Logiquement, les traces proches géographiquement sont regroupées dans les mêmes *clusters*. Cependant, 2 traces proches géographiquement ne partagent pas systématiquement de segments de route. Des segments de route préférés sont donc logiquement moins identifiables sur la Figure 3.11c.

La Figure 3.12 montre les cartes de chaleurs des paramétrages retenus pour Mon RésoVélo. Le plus grand *cluster* créé par DBSCAN contient 552 traces (Figure 3.12a), soit cinq fois plus que les *clusters* créés par k-médoïdes. Celui-ci contient de nombreux segments rouges, reliés à quelques segments rouge-verts. Une grande zone bleue s'étend dans toutes les directions tout autour de ces segments. Le *cluster* créé par k-médoïdes avec la distance personnalisée est assez surprenant (Figure 3.12b). Il contient certes un segment de route rouge bien défini en son centre, mais celui-ci n'est pas relié aux autres zones visibles. Beaucoup des traces affichées dans ce *cluster* créent des zones indépendantes les une des autres, bleues ou bleu-verts dans la plupart des cas. Les traces de MonRésoVélo semblent tellement éloignées les unes des autres que l'algorithme n'arrive pas à créer un grand *cluster* contenant des traces partageant toutes ou presque un segment de route. k-médoïdes fait cependant mieux avec la distance géodésique (Figure 3.12b) et est capable de créer un *cluster* avec 93 traces dans une même zone géographique. Aucun segment de route n'est cependant visible dans ce *cluster*. Celui-ci ne contient qu'une zone rouge sur plusieurs segments indistincts. La distance géodésique a une fois de plus permis de rassembler des traces proches géographiquement, mais qui ne partagent pas forcément de segments de route.

Les scores de silhouette moyens que les 2 algorithmes arrivent à obtenir sont systématiquement plus importants avec la distance géodésique qu'avec la distance personnalisée. Cependant, une analyse visuelle montre que les *clusters* créés avec cette
<figure><img src="image_22.png" /><figcaption>FIGURE 3.11 – Cartes de chaleurs des plus grands clusters pour les trois paramétrages retenus avec le jeu de données Véléval</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>(A) DBSCAN avec distance personnalisée (552 traces).</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(B) k-médoïdes avec distance personnalisée (98 traces).</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(C) k-médoïdes avec distance géodésique (93 traces).</figcaption></figure>

FIGURE 3.12 – Cartes de chaleurs des plus grands *clusters* pour les trois paramétrages retenus avec le jeu de données MonRésoVélo.
métrique ne permettent pas l'identification de segments de route préférés. Pour ce
qui est des différences de performances entre k-médoïdes et DBSCAN lorsque utili-
sés avec la distance personnalisée, elles dépendent du jeu de données utilisé. Avec le
jeu de données MonRésoVélo, le plus grand *cluster* créé par k-médoïdes contient des
traces ne partageant aucun segment de route. DBSCAN quant à lui génère un plus
grand *cluster* contenant beaucoup de traces (12 % du jeu de données). Malgré sa
taille importante, il permet l'identification de plusieurs segments de route préférés.
Cependant, ces segments sont entourés d'une zone utilisée de manière homogène
par très peu de traces. La combinaison entre DBSCAN et la distance personnalisée
est tout de même acceptable, car plusieurs segments de route préférés sont identi-
fiables. De plus, cette combinaison est meilleure que les 2 autres paramétrages testés.
Pour Véléval, les performances de k-médoïdes sont bien plus acceptables. En effet,
les segments de route visibles dans le plus grand *cluster* qu'il crée sont identiques et
autant identifiables que ceux présents dans le plus grand *cluster* de DBSCAN. Cepen-
dant, le plus grand *cluster* formé par DBSCAN contient plus de traces passant par
les segments de route préférés identifiables. C'est pour cette raison que DBSCAN
est aussi choisi pour le jeu de données Véléval. DBSCAN identifie certaines traces
comme étant du bruit, respectivement 1444 traces pour MonRésoVélo et 557 pour
Véléval. Celles-ci sont supprimées des jeux de données pour la suite de ce travail.
Véléval ne contient donc plus que 1743 traces et MonRésoVélo 2921 traces.

3.3.5 Résumé de la section

L'objectif de la Section 3.3 est d'identifier les segments de route préférés des cy-
clistes des 2 jeux de données. Une approche utilisant un algorithme de clustering
est proposée. Diviser les jeux de données en groupes de traces partageant un ou
plusieurs segments de route permet d'identifier les segments de route préférés, et
ainsi d'ajouter de l'information à ceux-ci. Deux métriques de distance sont propo-
sées pour quantifier les différences entre 2 traces. La première est une distance per-
sonnalisée utilisant une réduction de l'espace pour quantifier les segments de route
communs à 2 traces. La deuxième, plus classique, est la distance géodésique. Celle-ci
permet d'estimer le nombre de kilomètres entre 2 points géographiques. Deux algo-
rithmes de clustering sont ensuite proposés. DBSCAN qui est un algorithme basé
sur la densité. Celui-ci sépare les zones denses des jeux de données en cluster. k-
médoïdes est lui un algorithme basé sur k-means. Les clusters formés par celui-ci
possèdent chacun un médoïde. k-médoïdes minimise la somme des distances entre
les médoïdes et les points appartenant à leurs clusters. Une analyse quantitative est
d'abord effectuée pour trouver quelques paramétrages acceptables. Cette analyse
est basée sur des caractéristiques de clusters intéressantes au vu de l'objectif fixé.
Enfin, une analyse qualitative est faite pour trouver le meilleur paramétrage pour
chaque jeu de données. Cette analyse qualitative s'effectue en affichant les clusters et
en déterminant si les traces qu'ils contiennent partagent des segments de route. Les
paramétrages retenus sont les suivants :

— Pour Véléval, DBSCAN est utilisé avec la distance personnalisée, *minPts* = 3 et *ε* = 0.4.

— Pour MonRésoVélo, DBSCAN est utilisé avec la distance personnalisée, minPts = 3 et ε = 0.5.
## 3.4 Générateur de traces basées sur l'expérience

Les modèles de choix d'itinéraire implicites finaux doivent être capables d'utiliser les segments de route préférés identifiés dans la section précédente. Il est montré que les cyclistes des 2 jeux de données font un compromis entre le chemin le plus court et des segments de route préférés en Section 3.2. C'est sur cette hypothèse que se base la méthode de génération de traces basées sur l'expérience détaillée dans cette section. Celle-ci utilise une paire d'O/D ainsi qu'un *cluster* de traces expérimentées pour créer un compromis entre le chemin le plus court et l'utilisation des segments de route préférés. L'algorithme de Dijkstra ainsi qu'une pondération des poids d'un graphe routier sont utilisés.

### 3.4.1 Coefficient de cyclabilité

Les cellules créées pour la métrique de distance personnalisée (Section 3.3.1) sont réutilisées. Chaque trace possède 2 ensembles de cases, un ensemble direct et un ensemble étendu. De la même manière, chaque cellule possède 2 ensembles de traces. Soit une cellule *c*. Son premier ensemble $\delta_c$ contient les traces passant directement par celle-ci, et son deuxième ensemble $\nu_c$ contient les traces passant par ses voisines directes. Un coefficient de cyclabilité normalisé quantifiant l'utilisation de *c* par les cyclistes peut être calculé à partir de ces ensembles. Celui-ci est défini comme suit :

$$C_c = \frac{|\delta_c \cup \nu_c|}{\max_m |\delta_m \cup \nu_m|}$$

Le coefficient de cyclabilité se situe donc dans l'intervalle $[0, 1]$, car les cellules par lesquelles ne passent aucune trace ne sont pas générées et que $C_m = 1$. Il peut être calculé en considérant les cellules générées par la totalité d'un jeu de données, ou seulement celles d'un sous-groupe spécifique. Le coefficient de cyclabilité est utilisé pour modifier un graphe routier comme suit.

### 3.4.2 Modification du graphe routier

Soit un *cluster* cl. L'Algorithme 3 modifie les poids des arêtes d'un graphe routier G à partir des traces contenues dans celui-ci. La fonction *creerCellules* prend en entrée une ou plusieurs traces et renvoie l'ensemble étendu des cellules traversées par ces traces. Il est possible de générer les cellules traversées par une arête de G. En effet, une arête représente une route délimitée par 2 intersections possédant une position géographique. Le poids d'une arête *e* est modifié en fonction du coefficient de cyclabilité moyen des cellules qu'elle traverse. Les coefficients de cyclabilité sont ici calculés en ne considérant que les cellules générées avec les traces de cl. Les arêtes de G représentant les routes les plus utilisées par les traces de cl auront les poids les plus faibles à la sortie de l'algorithme 3. L'algorithme de Dijkstra peut ensuite être utilisé sur le graphe modifié. Celui-ci aura plus de chances de sélectionner les routes les plus utilisées lors du calcul du chemin le plus court entre une origine et une destination. L'exploration de chaque arête de G est coûteux en temps, mais ne doit être faite qu'une seule fois par *cluster* si les modifications à faire sont enregistrées.
**Algorithme 3** : Modification d'un graphe routier à partir d'un *cluster* de traces.

**Data** : G un graphe routier et *cl* un *cluster*

**Result** : G avec des poids modifiés

$\tau_{cl} \leftarrow creerCellules(cl);$ /* $\tau_{cl}$ contient l'ensemble des cellules par lesquelles les traces de *cl* passent */

**for** $e \in G$ **do**
| /* pour chaque arête *e* de G */
| $\tau_e \leftarrow creerCellules(e);$ /* $\tau_e$ contient l'ensemble des cellules par lesquelles *e* passe */
| $\tau \leftarrow \tau_{cl} \cap \tau_e;$
| $m \leftarrow moyenne(C_c, c \in \tau);$ /* $C_c$ est le coefficient de cyclabilité de la cellule *c* */
| $e.w \leftarrow e.w * (1 - m);$ /* $e.w$ est le poids de *e* */

**end**

### 3.4.3 Qualité des traces basées sur l'expérience

Une trace basée sur l'expérience est calculée pour chaque trace expérimentée des 2 jeux de données. Un oracle est tout d'abord utilisé pour affilier les traces expérimentées à un *cluster*. L'oracle est capable de renvoyer le numéro de *cluster* dans lequel se trouve une trace expérimentée à partir de son origine et de sa destination. La Section 3.5 est consacrée à l'implémentation d'une solution remplaçant cet oracle. Pour mesurer la pertinence des traces basées sur l'expérience, la distance entre celles-ci et les traces expérimentées qu'elles tentent de reproduire est calculée. La métrique de distance personnalisée est utilisée, car elle quantifie les parties identiques et non pas seulement les parties proches géographiquement. Les traces expérimentées que le générateur doit reproduire sont toutefois présentes dans les *clusters* utilisés pour générer les traces basées sur l'expérience. Pour les *clusters* ne contenant pas beaucoup de traces, cela pourrait grandement influencer la modification du graphe routier, créant ainsi un biais important. Pour résoudre ce problème, 20 % des traces expérimentées de chaque jeu de données sont choisies au hasard et retirées des *clusters*. Ce groupe de traces forme les sous-jeux de test (460 traces pour Véléval et 873 pour MonRésoVélo). Les 80 % de traces restantes forment les sous-jeux d'entraînement (1840 traces pour Véléval et 3492 pour MonRésoVélo). À noter que l'oracle est toujours capable de retrouver le *cluster* dans lequel les traces du jeu de test se trouvaient initialement.

### 3.4.4 Traces de comparaison

Trois autres types de traces sont utilisés pour comparer la qualité des traces basées sur l'expérience. Trois traces de comparaisons sont calculées pour chaque trace expérimentée, à partir de l'origine et de la destination de celles-ci. Les distances entre la trace expérimentée et les trois traces de comparaison sont ensuite calculées en utilisant là aussi la métrique de distance personnalisée. Les trois types de traces de comparaison sont :
- **Traces générées** : Pour rappel, celles-ci sont les chemins le plus court entre l'origine et la destination des traces expérimentées. Elles sont utilisées comme traces de comparaison pour montrer la nécessité de développer d'autres approches.

- **Traces basées sur l'expérience globale** : Un graphe routier global est généré pour chaque jeu de données. L'Algorithme 3 est utilisé avec toutes les traces du jeu de données pour le créer. Les traces basées sur l'expérience globale sont ensuite tracées en utilisant l'algorithme de Dijkstra sur ce graphe. Ces traces permettent de démontrer l'importance d'identifier les segments de route préférés plus locaux pour calculer des traces proches du comportement réel des cyclistes. Ces traces sont appelées "traces globales" dans la suite de ce travail.

- **Traces Mapbox**<fnref n="1" /> : Mapbox propose une API permettant entre autres de générer un itinéraire entre une origine et une destination. Ce service commercial permet de sélectionner le mode de transport utilisé, et le vélo fait partie des possibilités. Mapbox ne divulgue pas l'algorithme utilisé pour le calcul de trajet. Dans le cadre du cyclisme, celui-ci est néanmoins probablement le chemin le plus court sur un graphe pondéré en utilisant les infrastructures cyclables existantes. De nombreux services de calcul de trajet existe, mais seul Mapbox est utilisé pour rester concis. Comparer les traces basées sur l'expérience aux traces Mapbox permet d'évaluer la méthode de génération proposée dans cette section par rapport à une solution commerciale déployée.

### 3.4.5 Résultats

Les Figures 3.13a et 3.13b montrent les résultats avec les sous-jeux d'entraînement et de test de Véléval, et les Figures 3.14a et 3.14b avec les sous-jeux d'entraînement et de test de MonRésoVélo. Ces résultats sont affichés sous la forme de boîtes à moustaches montrant les ensembles de distances entre les quatre types de traces et les traces expérimentées. Les boîtes contiennent les distances dans l'intervalle $[Q1, Q3]$ et les moustaches celles dans l'intervalle $[Q1 - 1.5 * IQR, Q3 + 1.5 * IQR]$, avec $Qx$ le quartile $x$ et $IQR = (Q3 - Q1)$ l'écart interquartile. Les distances hors de ces intervalles sont affichées individuellement, car considérées comme des valeurs aberrantes. La valeur médiane des ensembles de distances est représentée par une ligne orange. On observe tout d'abord que les résultats des 2 sous-jeux de données ne diffèrent pas beaucoup. La présence des traces expérimentées à reproduire dans les clusters n'influe pas beaucoup sur les performances de la méthode de génération de traces. C'est une preuve que les clusters sont plutôt bien construits, car retirer 20 % des traces les formant à peu d'impact sur les segments de route qu'ils identifient. Seuls les résultats avec les sous-jeux de test sont détaillés ici, car les modèles finaux doivent être capables de générer des trajets qui ne sont pas dans les clusters qu'ils utilisent.

#### Veleval

Les traces générées sont les plus éloignées des traces expérimentées, suivies de près par les traces Mapbox. Cela tend à confirmer que les traces Mapbox sont des chemins le plus court calculés sur un graphe routier légèrement modifié. Les distances dans le premier quartile se situent entre 0 et 0.4 pour ces 2 types de traces. Le dernier quartile s'étend jusqu'à la distance maximale pour les 2. La médiane est

<footnote n="1">1. https://www.mapbox.com/</footnote>
légèrement inférieure pour les traces Mapbox, avec environ 0.67 contre environ 0.69. La borne supérieure du troisième quartile est de 0.8 pour les traces générées contre 0.75 pour les traces Mapbox. L'algorithme de Mapbox arrive donc à faire légèrement mieux que l'algorithme de Dijkstra sur un graphe routier non modifié, particulièrement lorsque la trace expérimentée s'éloigne fortement du chemin le plus court. Les cyclistes s'éloignent du chemin le plus court dans le but d'accéder à une infrastructure cyclable. Si le graphe routier de Mapbox est bien modifié à l'aide de ces infrastructures, il est logique que les traces Mapbox performent mieux lorsque les traces générées sont très différentes des traces expérimentées.

Les traces globales font mieux que les 2 types précédents. 75 % de celles-ci ont une distance inférieure à la distance médiane des traces Mapbox. Cependant, le quatrième quartile des distances des traces globales s'étend aussi jusqu'à un, montrant que cette méthode génère de manière non négligeable des traces n'ayant aucun segment de route commun à la trace expérimentée originale. Les traces globales sont calculées sur un graphe routier modifié en prenant en compte l'entièreté du jeu de données. Les poids des segments de route affichés en rouge sur la Figure 3.3 sont donc fortement diminués, et les poids de ceux affichés en bleu très peu. Les traces globales calculées dans des secteurs peu utilisés à l'échelle du jeu de données entier sont donc très proches, voire identique aux traces générées. Au vu des distances entre les traces générées et les traces expérimentées, il n'est pas étonnant qu'un nombre assez important de traces globales soient très différentes des traces expérimentées. Ce sont les traces basées sur l'expérience qui se rapprochent le plus des traces expérimentées, avec une distance médiane d'environ 0.2. 75 % des traces basées sur l'expérience ont une distance inférieure à 0.25. C'est aussi la seule méthode de génération de traces qui ne produit aucune trace entièrement différente de la trace expérimentée originale. Les traces ayant une distance supérieure à 0.5 sont considérées comme aberrantes tant elles sont peu nombreuses et seule une est à une distance supérieure à 0.7. Utiliser les clusters pour cibler les modifications à faire sur le graphe routier permet de calculer des traces qui sont assez proches des traces expérimentées dans la majorité des cas, et de ne jamais totalement diverger de celles-ci.

<figure><img src="image_26.png" /><figcaption>FIGURE 3.13 – Boîtes à moustaches des distances entre les traces expérimentées de Véléval et les quatre autres types de traces.</figcaption></figure>
## MonRésoVélo

La comparaison des performances entre les différents types de traces sont les mêmes pour MonRésoVélo (Figure 3.14). Les traces générées sont les plus éloignées, suivies de près par les traces Mapbox. Les traces Mapbox se différencient moins cette fois-ci, avec une médiane certe un peu moins élevée mais 50 % des traces dans le même intervalle de distance que les traces générées. C'est surprenant, car Montréal possède plus d'infrastructures cyclables que Lyon et Saint-Etienne, ce qui aurait dû améliorer les performances de Mapbox. Il est possible que Montréal ait un nombre suffisant d'infrastructures pour que la modification des poids du graphe routier de Mapbox soit assez homogène. Le cas échéant, le comportement d'un algorithme de chemin le plus court serait le même que sur un graphe non modifié. En effet, ces algorithmes effectuent leurs choix en prenant en compte la différence de poids entre les arêtes, et non les valeurs absolues des poids de celles-ci.

Les traces globales sont de meilleures qualités, mais la différence est moins marquée que pour Véléval. La médiane des distances des traces globales est cette fois-ci aux alentours de 0.5. L'intervalle des quartiles médians commence à environ 0.15 et termine aux alentours de 0.75 pour les traces globales, contre environ 0.3 et 0.85 pour les traces Mapbox. Le problème de la génération de traces globales évoqué pour Véléval semble être plus présent pour MonRésoVélo. Les traces MonRésoVélo sont réparties de manière plus homogène que celles de Véléval, et les segments de route les plus utilisés par les traces expérimentées sont en partie dans le centre. Les segments de route les plus utilisés par les traces générées se situent, eux aussi, dans le centre (voir Figure 3.4). Le graphe modifié utilisé pour calculer les traces globales possède donc beaucoup d'arêtes peu ou pas modifiées, et celles modifiées sont situées dans le centre là où passent les traces générées. Ce n'est donc pas étonnant que les performances des traces globales soient plus proches de celles des traces générées pour le jeu MonRésoVélo. Les traces basées sur l'expérience sont les traces les plus proches des traces expérimentées, avec cette fois-ci 75 % ayant une distance inférieure à 0.3 et une médiane d'environ 0.15. Les valeurs aberrantes commencent cette fois-ci à 0.7. Cela signifie que contrairement à Véléval, de nombreuses traces basées sur l'expérience de MonRésoVélo ont une distante comprise entre 0.5 et 0.7. Aucune des valeurs aberrantes n'atteint une distance de un, même si certaines s'en rapprochent. Les traces basées sur l'expérience de MonRésoVélo sont moins pertinentes que celles de Véléval de manière générale. Cela s'explique par la qualité des clusters. En effet, le plus grand cluster créé avec MonRésoVélo possède beaucoup de zones utilisées par peu de traces autour des segments de route préférentiels en rouge (voir Figure 3.12). Les modifications du graphe routier avec les clusters sont moins précises que celles faites avec Véléval, diminuant la précision des traces basées sur l'expérience. Celles-ci se rapprochent tout de même bien plus des traces expérimentées originales que les types de traces utilisés en comparaison.

### 3.4.6 Résumé de section

La Section 3.4.3 est dédiée à la mise en place d'une méthode de génération de traces basées sur l'expérience. Les segments de route préférés identifiés grâce aux clusters de la Section 3.3 ainsi qu'une pondération de poids de graphe routier sont utilisées. Les poids des arêtes sont diminués proportionnellement à leur utilisation par les traces d'un cluster. L'algorithme de Dijkstra peut ensuite être utilisé sur le
<figure><img src="image_27.png" /><figcaption>FIGURE 3.14 – Boîtes à moustaches des distances entre les traces expérimentées de MonRésoVélo et les quatre autres types de traces.</figcaption></figure>

graphe modifié pour créer un compromis entre le chemin le plus court et l'utilisation de segments de route préférés, imitant ainsi le comportement des cyclistes. Les traces calculées grâce à cette méthode sont ensuite comparées à trois types de traces (générées, globales et Mapbox). Pour cela, les distances entre les traces expérimentées et les quatre autres types de traces sont comparées. La métrique de distance personnalisée est utilisée. Les traces basées sur l'expérience sont les plus proches des traces expérimentées, bien que les performances soient différentes selon le jeu de données utilisé. Ces différences de performances mettent en lumière l'importance d'utiliser des clusters avec des segments de route préférés bien définis.

## 3.5 Classifieur

La méthode de génération de traces basées sur l'expérience se montre assez performante pour calculer des traces proches de traces expérimentées. Cependant, celle-ci a besoin d'un *cluster* de traces expérimentées pour fonctionner. Dans la section précédente, un oracle était utilisé. Celui-ci était capable de renvoyer le numéro de *cluster* d'une trace à partir de sa paire O/D. Le problème de cet oracle est qu'il n'est utilisable qu'avec des O/D de traces expérimentées présentes dans le jeu de données de base. Or les modèles de choix d'itinéraire implicites doivent être capable de créer un itinéraire quelles que soient l'origine et la destination choisies dans le secteur qu'il couvre. Il est donc nécessaire de développer une approche capable de renvoyer un *cluster* à partir d'une paire O/D quelconque. Ce problème est un problème de classification. Ce type de problème est solvable avec un algorithme d'apprentissage supervisé, appelé classifieur par la suite. Ce classifieur (voir le bloc *Prediction* sur la Figure 3.1) doit être implicite pour être entraîné sur les traces sans avoir à définir de variables descriptives. Le classifieur choisi prend en entrée un chemin le plus court et renvoie un numéro de *cluster*. Les traces générées sont utilisées pour l'entraînement. En effet, chaque trace générée correspond à une trace expérimentée. Il est donc possible d'affilier un numéro de *cluster* à chaque trace générée, en prenant celui dans lequel se trouve la trace expérimentée correspondante. Le modèle de choix d'itinéraire final peut ensuite calculer un nouveau chemin le plus court à partir d'une paire O/D et envoyer celui-ci au classifieur entraîné pour obtenir un numéro de *cluster*. La méthode décrite dans la section précédente peut ensuite être appliquée pour générer une trace basée sur l'expérience. Dans cette section, le choix du classifieur est
<figure><img src="image_28.png" /><figcaption>FIGURE 3.15 – Diagramme montrant la structure d'une cellule LSTM.</figcaption></figure>

argumenté. Une description de celui-ci et de son entraînement est ensuite effectuée. Enfin, les résultats obtenus sont discutés.

## 3.5.1 Réseau de neurones LSTM

Une trace générée est une séquence de points géographiques successifs. L'ordre de ces points est un aspect important. Le classifieur à entraîner doit donc être capable de traiter des données séquentielles. Les réseaux de neurones récurrents (RNN pour *Recurrent Neural Network*) sont un type de classifieur ayant montré de bons résultats sur ce type de données. En plus des données d'entrée, un RNN possède un état caché (*h*<sub>t</sub> pour *hidden state*) qui contient des informations sur les données précédemment traitées. *h*<sub>t</sub> sert en quelque sorte de mémoire. Cet état caché lui permet de prendre en compte l'aspect temporel des données qu'il doit traiter. Après expérience, un simple RNN ne s'est cependant pas révélé performant. La raison est la longueur des traces générées. En effet, les réseaux de neurones artificiels sont soumis au problème de disparition du gradient. Dans le cas des RNNs, ce problème empêche l'apprentissage des dépendances à long terme [105, 106]. Les LSTM (pour *Long Short Term Memory*) [107] sont un type de réseau de neurones développés spécialement pour faire de l'apprentissage sur de longues séquences. Ceux-ci sont constitués d'un état cellulaire (*C*<sub>t</sub> pour *cell state*) en plus de l'état caché. L'objectif de l'état cellulaire est de conserver les informations sur le long terme, permettant aux LSTM de performer sur des données séquentielles longues. La Figure 3.15 montre une cellule LSTM.

Les informations contenues dans l'état cellulaire $C_t$ sont contrôlées et modifiées par trois portes (*gates*). Tout d'abord, la porte d'oubli $f_t$ supprime les valeurs inutiles contenues dans l'état cellulaire. Ensuite, la porte d'entrée contrôle les nouvelles valeurs qui y seront ajoutées. La porte d'entrée est divisée en 2 parties. La première partie $i_t$ a pour but de mettre à jour les valeurs existantes, et la seconde partie $\tilde{C}_t$ génère des valeurs candidates qui peuvent être ajoutées à l'état cellulaire. Enfin, la porte de sortie $o_t$ décide quelles valeurs de l'état cellulaire sont utilisées pour créer le nouvel état caché $h_t$. Les trois portes sont définies comme suit :
$$
\begin{align*}
f_t &= \sigma(W_f.[h_{t-1}, x_t] + b_f) \\
i_t &= \sigma(W_i.[h_{t-1}, x_t] + b_i) \\
\tilde{C}_t &= \tanh(W_C.[h_{t-1}, x_t] + b_C) \\
o_t &= \sigma(W_o.[h_{t-1}, x_t] + b_o)
\end{align*}
$$

$x_t$ est l'élément de la séquence d'entrée $x$ à l'instant $t$ et $h_{t-1}$ est l'état caché ren-
voyé le LSTM à l'instant précédent ($t-1$). $h_1$ est initialisé de manière aléatoire. $W_f$, $W_i$, $W_C$, $W_o$ et $b_f$, $b_i$, $b_C$, $b_o$ sont respectivement les matrices de poids et les vecteurs de biais des différentes portes. L'état de la cellule $C_t$ et l'état caché $h_t$ à l'instant présent $t$ sont calculés à l'aide des résultats des différentes portes :

$$
\begin{align*}
C_t &= f_t * C_{t-1} + i_t * \tilde{C}_t \\
h_t &= o_t * \tanh(C_t)
\end{align*}
$$

avec l'opérateur '*' le produit d'Hadamard et $C_{t-1}$ l'état cellulaire calculé par le LSTM à l'étape précédente ($t-1$). $C_1$ est initialisé aléatoirement. $\sigma$ et $\tanh$ sont des fonctions d'activations non linéaires définies par :

$$
\sigma = \frac{1}{1 + e^{-x}}
\tanh = \frac{e^x - e^{-x}}{e^x + e^{-x}}
$$

Lorsque les *N* éléments de la séquence d'entrée $x = \{x_1, ..., x_{t-1}, x_t, ..., x_N\}$ ont été traités par le LSTM, le dernier état caché $h_N$ est utilisé pour la classification.

3.5.2 Prétraitement des traces

Une trace générée est une séquence de *N* points ordonnés $t = \{p_1, ..., p_N\}$ avec chaque point $p_t = (\text{lat}_t, \text{lon}_t)$ contenant une latitude et une longitude. Les réseaux LSTM sont certes adaptés aux longues séquences, mais l'espace de valeurs des latitudes et des longitudes est trop continu pour permettre une convergence. Il est donc nécessaire d'effectuer une discrétisation. La discrétisation utilisée ici est inspirée des travaux de Crivellari et al. [81], qui ont utilisé un réseau LSTM pour prédire les prochaines étapes d'un chemin touristique à partir des étapes déjà effectuées. Ils ont pour cela transformé les traces GPS en séquences de zones touristiques avant de les envoyer à leur LSTM. L'utilisation des infrastructures cyclables en tant que zones cyclables peut sembler être un moyen de discrétiser les traces générées. Cependant, les chemins le plus court ne passent pas nécessairement par des routes en possédant. Pour garder toutes les informations de celles-ci, il faut créer des zones cyclables personnalisées. Les cellules générées pour la métrique de similarité personnalisée sont encore une fois utilisées. Celles-ci sont regroupées en clusters avec l'algorithme k-means. Celui-ci utilise leurs positions géographiques ainsi que leurs coefficients de cyclabilité. Cela permet aux zones cyclables d'être constituées de cellules proches géographiquement, avec un taux d'utilisation par les traces générées proche. Le résultat est 1565 zones cyclables pour Véléval et 3087 pour MonRésoVélo. Une séquence en entrée du LSTM est une suite d'entiers représentant les numéros des zones cyclables par lesquelles la trace générée passe.
### 3.5.3 Structure du classifieur et hyperparamètrage

Un classifieur est entraîné par jeu de données. Chaque classifieur est composé de 2 couches de LSTM suivies d'une couche de 256 neurones fully-connected. La fonction d'activation ReLU [108] est utilisée après chaque couche, exceptée la couche de sortie, afin de donner des propriétés de non-linéarité au classifieur. L'optimiseur Adam [109] est utilisé avec un taux d'apprentissage de $5e^{-4}$. Les apprentissages durent 10 000 étapes pendant lesquelles les traces sont envoyées par groupe de 30. La sortie d'un classifieur est une liste de N log-probabilités obtenues en utilisant $log(Softmax(x))$, avec N le nombre de clusters créés avec le jeu de données utilisé. Chaque valeur de cette liste représente la probabilité que la trace expérimentée correspondant à la trace générée en entrée appartienne à un des clusters. La fonction de perte utilisée est la *negative log likelihood*. Les sous-jeux d'entraînements et de tests formés dans la Section 3.4.3 sont réutilisés. Seules les traces des sous-jeux d'entraînement sont envoyées lors des entraînements. Les traces appartenant aux sous-jeux de test sont ensuite utilisées pour mesurer la capacité des classifieurs à généraliser les connaissances qu'ils ont acquis pendant l'entraînement.

### 3.5.4 Performances

Le classifieur entraîné avec Véléval atteint un taux de réussite de 96 % avec le sous-jeu d'apprentissage et de 78.6 % avec le sous-jeu de test. Celui entraîné avec MonRésoVélo atteint un taux de réussite de 96.6% avec le sous-jeu d'apprentissage et de 56.6% avec le sous-jeu de test. Les différences de performances entre les 2 types de sous-jeux montrent que les classifieurs sur-apprennent pendant l'entraînement. Deux stratégies sont classiquement utilisées pour diminuer le phénomène. Tout d'abord, la dimension ainsi que le nombre des différentes couches des classifieurs ont été diminués. Diminuer la dimension d'un classifieur lui permet d'oublier les caractéristiques les moins importantes des données par faute de neurones dans lesquels les stocker. Un classifieur trop petit n'aura cependant pas assez de neurones pour stocker toutes les caractéristiques importantes des données. Deux cellules LSTM et une couche de 256 neurones apparaît comme la meilleure configuration. La deuxième méthode est le *dropout* qui consiste à mettre certaines sous-parties des neurones d'un classifieur à 0 aléatoirement. Cela permet de réduire la co-adaptation des neurones, permettant à chacun d'entre eux de retenir une caractéristique importante générale des données [110]. Malheureusement, le *dropout* n'a fait que réduire les performances du classifieur et n'est donc pas utilisé.

La Figure 3.16 montre le détail des prédictions pour chaque *cluster* avec les sous-jeux de test. Pour Véléval, plus le *cluster* est grand, moins il y a de chances que le classifieur se trompe dans ses prédictions. Le classifieur semble bien avoir assimilé les caractéristiques communes des traces présentes dans les plus grands *clusters*. Cependant, lorsque les *clusters* sont plus petits, les prédictions sont plus aléatoires. En effet, certains petits *clusters* voient la totalité de leurs traces classifiées correctement, certains ne sont constitués que de traces mal classifiées et certains voient le classifieur prédire correctement environ la moitié de leurs traces. La classifieur entraîné avec Véléval semble délaisser les caractéristiques des traces de certains petits *clusters* au profit des caractéristiques de celles dans les plus grands. Pour MonRésoVélo, la taille des *clusters* ne semble pas affecter les capacités de classification. En effet, une partie non négligeable (autour de 30 %) des traces des plus grands *clusters* est mal classifiée. Pour les plus petits *clusters*, le constat est similaire que pour Véléval. La
différence de performances entre le classifieur de Véléval et de MonRésoVélo semble être concentrée sur les plus grands *clusters*. Les traces des plus grands *clusters* de Véléval ont toutes une grande partie de segments en communs (voir Figure 3.7a). Les caractéristiques de celles-ci sont donc très proches. Mais le nombre conséquent de clusters, et l'hétérogénéité de leurs tailles empêche le classifieur de retenir ces caractéristiques en même temps que celles de traces dans les plus petits clusters. Le problème se pose aussi pour les clusters MonRésoVélo qui sont plus nombreux, et plus hétérogènes en termes de taille. À cela s'ajoute des traces dans les plus grands clusters possédant des parties communes moins importantes. Tout cela explique les différences de performances entre les 2 jeux de données. Le sur-apprentissage n'est donc pas dû à la structure des classifieurs, mais bien à l'hétérogénéité des données.

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /><figcaption>FIGURE 3.16 – Prédictions des classifieurs avec les sous-jeux de test.</figcaption></figure>

### 3.5.5 Résumé de la section

Dans la Section 3.5, une méthode pour remplacer l'oracle de la section précédente est développée. Un classifieur par jeu de données est entraîné. Celui-ci a pour but de retrouver le numéro de *cluster* d'une trace expérimentée à partir du chemin le plus court entre son origine et sa destination. Un LSTM est utilisé, car ce type de réseau de neurones est spécialisé dans l'apprentissage de longues séquences. La structure d'une trace GPS étant dans un espace trop continu pour permettre la convergence d'un réseau de neurones, l'espace est discrétisé à l'aide des cellules générées pour
la métrique de distance personnalisée. Les sous-jeux d'entraînements et de test sont
utilisés pour évaluer la capacité des classificateurs à généraliser ce qu'il apprend sur
les données. Les performances sont différentes selon le jeu de données. Le taux de
réussite est plutôt bon pour Véléval, avec plus de 75 %. Pour MonRésoVélo, le classi-
fieur n'arrive qu'à un taux de réussite de 56 %. Une analyse détaillée des prédictions
permet de conclure que ces différences de performances sont dues aux différences
importantes entre les 2 jeux de données.

3.6 Modèles finaux

3.6.1 Analyse quantitative

La même méthode qu'en Section 3.4 est utilisée pour évaluer les performances des modèles finaux. Une trace basée sur l'expérience est calculée pour chaque trace expérimentée des jeux. Cependant, c'est le classificateur qui est utilisé pour le choix du cluster et non plus l'oracle. La distance personnalisée entre la trace expérimentée et la trace basée sur l'expérience est calculée. Cette distance est comparée à celle entre la trace expérimentée et les 2 autres types de traces basées sur l'expérience (globales et avec l'oracle). Les résultats pour Véléval sont affichés en Figure 3.17 et ceux pour MonRésoVélo en Figure 3.18. Les traces calculées avec les LSTM sont très proches de celles calculées avec l'oracle pour les 2 sous-jeux d'entraînements. Ce n'est pas étonnant, car les LSTM entraînés avec les 2 jeux de données sont proches d'une précision de 100 % avec les sous-jeux d'entraînements. Les différences entre les LSTM et les oracles résident dans les quelques pourcents de traces mal classifiées. Les traces mal classifiées pèsent logiquement plus sur les performances avec les sous-jeux de test.

Pour Véléval, la borne supérieure des 2 quartiles du milieu est 2 fois plus grande avec le LSTM qu'avec l'oracle (environ 0.4 contre 0.2). De plus, la moustache supérieure avec le LSTM atteint 0.8, contre 0.45 avec l'oracle. La médiane est cependant la même entre les 2 manières de trouver le cluster. Les 20 % de traces mal classifiées par le LSTM semblent être assez éloignées des traces expérimentées d'origine. Cependant, les traces créées à l'aide du LSTM sont meilleures que celles des traces globales, avec par exemple aucune trace n'atteignant une distance de 1, et seules quelques traces aberrantes ayant une distance supérieure à 0.8. Cela signifie que, pour le jeu de données Véléval, il vaut mieux se tromper de clusters plutôt que d'utiliser tout le jeu de données pour créer une trace basée sur l'expérience.

Ce constat n'est qu'à moitié partagé par le jeu de données MonRésoVélo. En effet,
les traces calculées à l'aide du LSTM sont plus proches des traces expérimentées
d'origines que les traces globales, avec une distance médiane bien meilleure (environ
0.25 contre 0.5) et un intervalle des 2 quartiles centraux un peu plus bas (de 0.15 à
0.8 pour les traces globales et de 0.08 à 0.75 pour le LSTM). Cependant, une partie
non négligeable des traces calculées à l'aide du LSTM n'a aucun segment de route
en commun avec la trace expérimentée d'origine. Cela signifie que dans certains cas,
entraîner et utiliser un LSTM ne permet pas de créer une trace basée sur l'expérience
de meilleure qualité que la trace globale. Pire, il peut arriver que la trace globale soit
de meilleure qualité que celle calculée avec le LSTM. Cependant, il est important de
noter que la distance médiane des traces créées avec le LSTM est bien plus proche
de celle des traces créées avec l'oracle que de celle des traces globales. Cela signifie
que le LSTM est tout de même utile dans beaucoup de cas. Les traces qu'il génère se
rapprochent de manière générale plus des traces expérimentée que les traces créées sans utiliser d'oracle.

<figure><img src="image_31.png" /></figure>

FIGURE 3.17 – Boîtes à moustaches des distances entre les traces expérimentées de Véléval et les trois types de traces basées sur l'expérience.

<figure><img src="image_32.png" /></figure>

FIGURE 3.18 – Boîtes à moustaches des distances entre les traces expérimentées de MonRésoVélo et les trois types de traces basées sur l'expérience.

## 3.6.2 Analyse visuelle de traces basées sur l'expérience

Les Figures 3.19 et 3.20 montrent chacune 2 cartes sur lesquelles sont affichées une trace expérimentée, sa trace générée correspondante ainsi que la trace basée sur l'expérience créée par le modèle entraîné avec le bon jeu de données. Des traces ayant été calculées avec le bon *cluster* sont montrées en Figures 3.19a et 3.20a. Les Figures 3.19b et 3.20b affichent des traces calculées avec le mauvais *cluster*. Cela permet de montrer les performances des 2 modèles dans un cas favorable ainsi que dans un cas défavorable. Toutes les traces expérimentées d'origine font partie du sous-jeu de test et ne sont donc jamais dans le *cluster* utilisé pour calculer la trace basée sur l'expérience.

La Figure 3.19a est un très bon exemple des capacités de simulation de comportement de cycliste d'un modèle implicite. Sur cette carte, on observe trois traces dont
les points d'origine et de destination sont proches du Rhône. Le point de départ est proche de la rive droite du fleuve, et en amont du point de destination que se situe proche de la rive gauche de celui-ci. Comme dit précédemment, les berges gauches du Rhône sont très prisées par les cyclistes, grâce à des infrastructures cyclables séparées des voitures entre autres. Il est donc assez logique de voir la trace expérimentée atteindre assez rapidement ces berges puis les longer. Le cycliste démarre même en allant à l'opposé de sa destination pour prendre le pont le plus proche et parcourir une plus grande distance sur celles-ci. Celui-ci quitte les berges par une sortie proche de sa destination (les berges étant en contrebas, on ne peut pas y entrer ou les quitter n'importe où). La trace générée commence par longer les berges droites jusqu'au pont le plus proche de la destination, qu'elle traverse. Elle continue sur la route face au pont puis tourne à droite pour minimiser la distance entre cette route et la destination. La trace générée est sans surprise plus courte que la trace expérimentée. La trace créée par le modèle est très proche de la trace expérimentée. En effet, les poids des routes formant les berges gauche semblent avoir été tellement diminués que le chemin le plus court sur le graphe modifié part lui aussi à l'opposé de la destination pour les atteindre. Il entre sur les berges par la même entrée que la trace expérimentée, et en sort par une sortie plus proche de la destination. La fin du chemin jusqu'à celle-ci est ensuite différente. La trace créée par le modèle passe par une rue parallèle à celle utilisée par le cycliste. La diminution des poids semble être moins marquée à cet endroit-là, empêchant le modèle d'effectuer le bon détour. On peut aussi noter qu'à peu près à mi-chemin, la trace du modèle sort puis rentre de nouveau rapidement sur les berges. Cela est dû à la taille des cellules utilisées. La route collée aux berges à cet endroit a vraisemblablement vu son poids diminué car il traverse les mêmes cellules que les segments de berges. L'algorithme de Dijkstra prend donc la décision de l'utiliser malgré le détour que cela implique.

Sur la Figure 3.19b, la trace expérimentée démarre d'un point à l'Est pour atteindre un point au Nord-Ouest. Une fois encore, le cycliste est parti à l'opposé de sa destination en se dirigeant plein Sud. Il atteint rapidement une avenue menant directement au Rhône. Il longe ensuite les berges gauches avant de finalement traverser le fleuve et atteindre sa destination. La trace générée démarre en direction du Nord-Ouest. Elle met plus de temps à atteindre une avenue donnant sur le Rhône, et celle-ci est située plus au Nord que celle empruntée par le cycliste. Une fois arrivée au Rhône, la trace le traverse sans emprunter les berges, par un pont plus au Sud que celui utilisé par le cycliste. Finalement, la trace créée par le modèle rejoint sa destination en se dirigeant vers le Nord-Ouest. On ne distingue pas la trace générée, car celle-ci est entièrement recouverte par la trace créée par le modèle. En effet, le mauvais *cluster* ayant été choisi, des routes peu pertinentes ont vu leurs poids diminuer. Dans le cas présenté, ces routes ne semblent pas être dans le secteur entre l'origine et la destination de la trace expérimentée. La trace basée sur l'expérience est donc le chemin le plus court sur un graphe routier non modifié.

La Figure 3.20a affiche des traces allant d'une origine au Sud-Est à une destination au Nord-Ouest. La trace générée montre qu'aller toujours tout droit sur une route (qui devient un boulevard à terme) permet de quasiment atteindre la destination. Cependant, le cycliste a décidé de partir au Sud pour effectuer un itinéraire bien plus sinueux qui longe cette route, pour finalement la croiser en direction du Nord au dernier moment pour atteindre sa destination. Ce choix a probablement été fait dans le but de traverser le parc visible au Sud de la carte, et que la route empruntée par la trace générée ne fait que longer. Faire du vélo dans un parc permet d'être éloigné des voitures et dans un endroit vert, 2 caractéristiques d'itinéraires recherchées
par les cyclistes. La trace calculée par le modèle est très similaire à la trace expérimentée. Celui-ci simule bien le détour débuté dès le départ par le cycliste dans le but de traverser le parc. Que ce soit avant ou après cette traversée, la trace basée sur l'expérience est parfaitement identique à la trace expérimentée. Les seules différences entre les 2 traces se situent dans le parc. En effet, la trace calculée par le modèle semble plus directe que la trace expérimentée. Les différents chemins dans le parc sont très proches, comparés aux routes dans la ville. Il est probable que plusieurs chemins voisins passent par les mêmes cellules, et que leurs poids aient été diminués de la même façon. Le modèle crée donc un plus court chemin dans le parc, sans parvenir à simuler les petits détours du cycliste.

Les traces sur la Figure 3.20b vont d'un point à l'Ouest à un point à l'Est. La trace générée entre ces 2 points tente le plus possible d'aller en direction de l'Est. À cause de la disposition des routes disponibles, le résultat est une trace avec beaucoup de tournants. Le cycliste a lui décidé de rejoindre un chemin séparé des voitures et qui longe une voie de chemin de fer. Les rails et le chemin sont séparés par un grillage par sécurité. Lorsque le cycliste est proche de sa destination, il quitte ce chemin pour la rejoindre. La trace calculée par le modèle ne partage que peu de segments de route avec les 2 autres traces. De plus, elle semble plus longue que la trace expérimentée. Il semble que le *cluster* choisi ait entraîné une modification des poids des routes dans le secteur entre l'origine et la destination de la trace expérimentée. Cependant, le *cluster* choisi n'étant pas le plus pertinent, ces modifications créent des détours non pertinents. La trace calculée par le modèle est donc une trace plus longue que le chemin le plus court, et ne parvenant pas à reproduire le comportement d'un cycliste.

<figure><img src="image_33.png" /><figcaption>FIGURE 3.19 – Cartes montrant 2 traces expérimentées (en orange), les traces générées correspondantes (en bleu) et les traces calculées par le modèle de choix d'itinéraire entraîné avec le jeu Véléval (en rouge).</figcaption></figure>

### 3.6.3 Résumé de la section

La Section 3.6 évalue les modèles finaux créés à partir de la méthode présentée dans ce chapitre. Deux analyses sont effectuées. La première est quantitative. La même méthode qu'en Section 3.2.3 est utilisée. Des traces sont calculées par les modèles entre les origines et les destinations de traces expérimentées. La distance entre ces traces basées sur l'expérience et les traces d'origine est calculée, et comparée à d'autres traces. Les modèles parviennent à créer des traces plus similaires aux traces
<figure><img src="image_34.png" /><figcaption>FIGURE 3.20 – Cartes montrant 2 traces expérimentées (en orange), les traces générées correspondantes (en bleu) et les traces calculées par le modèle de choix d'itinéraire entraîné avec le jeu MonRésoVélo (en rouge).</figcaption></figure>

expérimentées que les traces globales. Cependant, les traces créées avec l'oracle sont de meilleures qualités, démontrant l'importance d'utiliser le bon *cluster* pour modifier le graphe routier. Enfin, une analyse visuelle des traces créées par les modèles est effectuée. Cette analyse confirme l'importance du choix du *cluster*. Les modèles créent des traces identiques ou de moins bonne qualité que les traces générées lorsqu'ils utilisent le mauvais *cluster*. Avec le bon *cluster* cependant, ils sont capables de simuler de manière très précise le comportement des cyclistes, et ce même lorsque ceux-ci décident d'aller à l'opposé de leurs destinations.

## 3.7 Conclusion et discussion

Il est important d'être capable de reproduire le comportement des cyclistes dans le but de mieux le comprendre. Cela participe à la création d'infrastructures plus pertinentes, incitant à un changement modal vers le cyclisme au sein des villes. Ce chapitre propose une méthode de création de modèles de choix d'itinéraire implicites pour les cyclistes. À partir d'une paire O/D, les modèles finaux sont capables de générer un trajet individuel de cyclistes en se basant sur des données comportementales. L'utilisation d'algorithmes d'apprentissage spécifiques permet d'utiliser les données sans définir de variables descriptives. Cela permet aussi de se passer d'ensemble de trajets possibles. Les modèles sont construits grâce à des traces GPS générées par des cyclistes. Un algorithme de *clustering* utilisant une métrique de distance personnalisée regroupe les traces passant par les mêmes routes. Cela permet d'identifier les segments de route préférés des cyclistes. Une méthode est ensuite déployée pour créer des traces basées sur l'expérience à partir de ces segments. Ces traces sont un compromis entre le chemin le plus court et l'utilisation de ces segments. Un classifieur utilisant des couches LSTM est ensuite entraîné à retrouver un numéro de *cluster* à partir d'un chemin le plus court. Cela permet aux modèles finaux de calculer une trace à partir de n'importe quelle paire O/D. Les modèles finaux fonctionnent en 4 étapes :

- L'algorithme de Dijkstra est utilisé sur un graphe routier non modifié pour créer un chemin le plus court entre une origine et une destination.

- Le chemin le plus court est envoyé au classifieur qui renvoie un numéro de *cluster*.

- Les traces GPS de ce *cluster* sont utilisées pour modifier les poids des arêtes du graphe routier.