Pourquoi sommes-nous tellement accros à Google Maps et Waze ? écrit par Ploum, Lionel Dricot, ingénieur, écrivain de science-fiction, développeur de logiciels libres.
J’éditerai ce message quand j’aurai eu le temps de faire plus que survoler l’article mais minute papillon : l’optimisation de déplacement est sûrement une des applications pour lesquels le partage de sa position peut valoir le coût. Pourquoi ? Parce que l’information ne nous sert pas qu’à nous, il permet de mieux connaître les flux circulant dans un graphe et ce qui nous rapproche d’être mathématiquement capable de trouver la solution de déplacement optimale pour l’ensemble de la population.
Il faudrait creuser les méthodes mathématiques qu’utilisent Waze et Google Maps mais c’est probablement un genre de réseau bayésien.
C’est bien ce qui fait la différence entre radio-autoroute et un assistant de navigation. La première solution nous donne l’information et nous laisse prendre une décision qui optimise notre trajet personne au détriment de l’optimisation de la circulation des flux sur le réseau, la deuxième solution permet d’optimiser le flux sur le réseau au détriment de l’optimisation du trajet personnel. Mais les de vitesse induit par l’amélioration totale du flux permettent de contrebalancer la non-optimisation locale (ça se dit local dans ce cas ?). Et vu l’espace que consomme la voiture automobile, il faut bien ça pour essayer d’améliorer un rien l’utilisation de l’espace public et faciliter les déplacements.
Edit : Mon message original était rempli de bêtises. Celui-ci aussi possiblement.
TL ; PL : Beaucoup de question sur des math que je ne maîtrise pas. Une critique de la fermeture des algorithmes. Une critique sociale de la place de la voiture. J’aurai voulu parler de smart-cities mais même moi j’en ai eu marre de me lire.
L’article bien que citant des sources intéressantes ne fait que gratter la surface du problème. L’auteur y discute des méthodes invasives de collecte des données avant de conclure sur le fait que les applications de navigation induisent des comportements égoïstes qui desservent l’ensemble des conducteurs. Ce point-là n’est pourtant pas discuté dans l’article mais seulement dans les liens qu’il référence.
Quand on va un peu plus loin et qu’on lit ces liens, on fait face à un problème passionnant qui donnera sans doute du fil à retordre aux ingénieurs et aux chercheurs en mathématiques des prochaines décennies : Comment passer d’un modèle d’application de navigation où l’utilisateur optimise son trajet personnel à un modèle où on trouve un arbitrage entre fluidité du traffic total et trajet individuel ?
Tout n’est pas une question de vitesse, Ploum le dit bien, on peut préférer des trajets plus beaux, des trajets plus courts mais moins rapide, etc.
Il semble qu’à l’heure actuelle, les logiciels de navigations fonctionnent encore principalement sur de l’optimisation de parcourt personnel. Je dis “il semble” car ils ne divulguent pas la nature de leurs algorithmes. Pour les chercheurs de l’université californienne de Berckley, les conducteurs maintenant mieux informés par ces méthodes modernes se lancent dans une concurrence dans un jeu à information parfaite (ou assimilable) pour atteindre un équilibre de Nash, c’est-à-dire une situation dans laquelle tout le monde a réussi à faire de son mieux au détriment des autres. Pourtant, cette solution n’est pas la meilleure des solutions ni pour tous le monde, ni pour chacun. Dans l’exemple présenté en Ted-talk par Alexandre Bayen, on voit un ensemble de conducteurs qui choisissent de quitter l’autoroute au même moment pour éviter un bouchon et qui vont former un second bouchon sur la sortie d’autoroute. Cette somme de parcours optimal pour un conducteur ne peut pas prendre en compte le déplacement simultané du flot de véhicule vers un goulot d’étranglement. La théorie des graphes nous donnera peut-être la solution à ce problème.
Peut-être… mais le problème est loin d’être aussi simple qu’il y paraît :
On a ici un graphe, notre réseau routier, sur lequel se déplace des flots de voitures qu’on veut optimiser. Mais :
comme dit précédemment, les critères d’optimisation a prendre en compte pour chaque véhicule sont différents ;
nos graphes sont mouvants, ils évoluent sans cesse car les rues se construisent, les routes s’ouvrent et se ferment.
Le problème peut ressembler à celui des transports des données sur l’internet dont la structure change sans cesse. Mais, sur internet, si un packet se peut se perdre et que notre visio-conférences doit freezer une demi-seconde, l’algorithme aura fait son travail correctement. Tandis que si quelques véhicules se voient suggérer un détour de 50 km pour aller au supermarché, l’algorithme ne peut pas être considéré acceptable.
Le problème ressemble aussi à celui de la gestion de trains sur un chemin de fer ; certes, on ne modifie pas les voies ferrées aux rythmes des rues autorisant l’automobile mais les algorithmes de gestion des voies ferrées, eux aussi hélas beaucoup trop fermé, parviennent au prix d’une information des usagers incomplète et changeantes à éviter bouchons et détours sur leur réseau. Cependant, le manque d’information pour les conducteurs sera un facteur de refus de l’algorithme.
En effet, ces deux problèmes se distinguent radicalement du nôtre sur un point-clef : Les conducteurs ne sont pas obligés d’adopter le trajet rendu par l’algorithme. Le conducteur de train ne décide pas de détour et les packets de données ne se rebellent pas contre les routeurs mais les conducteurs d’automobiles, eux, sont libres du choix du trajet. Ils souhaitent améliorer leurs trajets mais ils souhaitent aussi une amélioration perceptible. C’est pourquoi ils choisissent intuitivement le trajet optimisé personnellement plutôt que le trajet optimisant le flot sur le réseau routier.
En informant les conducteurs sur l’utilité sociale d’un tel algorithme, on pourrait augmenter son acceptation et voir le flot de véhicule mieux répartis sur le réseau routier. C’est déjà le cas dans une certaine mesure car l’optimisation individuelle pousse les conducteurs à sortir des axes principaux et découvrir les routes secondaires. Le soulagement des routes principales, quand il n’entraîne pas des bouchons à l’entrée des routes secondaires, et une bonne chose du point de vu de la théorie des graphes. C’est une moins bonne chose du point de vue des résidents de ces routes secondaires. La mentalité NIMBY (Not In My Back Yard), vouloir repousser le traffic loin de chez soit ne réglera pas les problèmes de la circulation et pourrait même les exacerber. Néanmoins, si l’ensemble du traffic routier ne peut se concentrer sur des grandes artères, de vrais arguments contre la circulation sur les petits routes existes. citymonitor.ai cite notamment la question de la sécurité routière : On voit moins souvent des jeunes enfants jouer au foot sur le périph’ que dans une rue résidentielle. Dans ces lieux où les usagers de la route sont moins séparés, les accidents entre eux sont plus nombreux.
On arrive finalement à une critique sociale de la route et de la place de la voiture qui j’aurai du mal à transposer à des concepts mathématiques. Il faut réussir à améliorer le trajet de chaque conducteur de véhicule en améliorant le flot routier totale en prenant en compte un grand nombre de paramètres d’optimisation. Seulement les flots automobiles ne sont les seuls à circuler sur le réseau, il existe des flots cyclistes et piétons, qui se concentrent sur certains axes et pour qui un problème de partage du réseau avec le flot automobile peut correspondre à une situation de vie ou de mort. Une circulation automobile fluide mais importante, sans aucun carambolage et accident, n’est pas non plus une situation désirable pour eux. La pollution aérienne, sonore et lumineuse n’est pas plaisante pour les habitants d’un quartier. La solution la plus efficace pour lutter contre elle est la réduction du traffic. Les maires et les habitants de quartier se lancent dans une guerre contre la circulation traversante, celles des voitures qui passent près de eux pour aller ailleurs mais il existe une bonne et une mauvaise façon de le faire :
La bonne favorise le flot des autres modes de transports (piéton, vélo, transport en commun) pour qu’ils prennent l’espace disponible sur cette partie du réseau. Ainsi, la voiture n’ayant plus la place pour circuler optimisera son trajet pour aller ailleurs et s’il n’y a plus d’ailleurs où aller, le flot total de voiture devant diminuer sur le réseau, le conducteur deviendra passager de transport en commun (TC), piéton ou cycliste, continuant ainsi à circuler dans le réseau mais participant à l’évaporation du traffic automobile. La voiture personnelle étant un objet encombrant, la somme des flots d’humain incluant flots de passager, de conducteur, de cycliste et de piéton pourra augmenter sur les réseaux des différents modes de transport à mesure que la place de la voiture circulera.
La mauvaise rallonge et complique le trajet dans les lieux d’où chasser l’automobile. Cependant, ce rallongement des distances s’appliquent aux flots de tous les modes de transports. La marche et le cyclisme perdent en utilité au profit de la voiture qui augmente donc son flot total sur les réseaux de transports augmentant ainsi la saturation des arcs sur lesquels se concentrent le traffic. Le traffic induit compliquera ainsi la circulation des flots automobiles sur le réseau sans pour autant résoudre le problème initial à savoir comment passer d’une optimisation un trajet personnel à un arbitrage entre fluidité du traffic total et trajet individuel ?
J’éditerai ce message quand j’aurai eu le temps de faire plus que survoler l’article mais minute papillon : l’optimisation de déplacement est sûrement une des applications pour lesquels le partage de sa position peut valoir le coût. Pourquoi ? Parce que l’information ne nous sert pas qu’à nous, il permet de mieux connaître les flux circulant dans un graphe et ce qui nous rapproche d’être mathématiquement capable de trouver la solution de déplacement optimale pour l’ensemble de la population.
Il faudrait creuser les méthodes mathématiques qu’utilisent Waze et Google Maps mais c’est probablement un genre de réseau bayésien.C’est bien ce qui fait la différence entre radio-autoroute et un assistant de navigation. La première solution nous donne l’information et nous laisse prendre une décision qui optimise notre trajet personne au détriment de l’optimisation de la circulation des flux sur le réseau, la deuxième solution permet d’optimiser le flux sur le réseau au détriment de l’optimisation du trajet personnel. Mais les de vitesse induit par l’amélioration totale du flux permettent de contrebalancer la non-optimisation locale (ça se dit local dans ce cas ?). Et vu l’espace que consomme la voiture automobile, il faut bien ça pour essayer d’améliorer un rien l’utilisation de l’espace public et faciliter les déplacements.Edit : Mon message original était rempli de bêtises. Celui-ci aussi possiblement.
TL ; PL : Beaucoup de question sur des math que je ne maîtrise pas. Une critique de la fermeture des algorithmes. Une critique sociale de la place de la voiture. J’aurai voulu parler de smart-cities mais même moi j’en ai eu marre de me lire.
L’article bien que citant des sources intéressantes ne fait que gratter la surface du problème. L’auteur y discute des méthodes invasives de collecte des données avant de conclure sur le fait que les applications de navigation induisent des comportements égoïstes qui desservent l’ensemble des conducteurs. Ce point-là n’est pourtant pas discuté dans l’article mais seulement dans les liens qu’il référence.
Quand on va un peu plus loin et qu’on lit ces liens, on fait face à un problème passionnant qui donnera sans doute du fil à retordre aux ingénieurs et aux chercheurs en mathématiques des prochaines décennies : Comment passer d’un modèle d’application de navigation où l’utilisateur optimise son trajet personnel à un modèle où on trouve un arbitrage entre fluidité du traffic total et trajet individuel ?
Tout n’est pas une question de vitesse, Ploum le dit bien, on peut préférer des trajets plus beaux, des trajets plus courts mais moins rapide, etc. Il semble qu’à l’heure actuelle, les logiciels de navigations fonctionnent encore principalement sur de l’optimisation de parcourt personnel. Je dis “il semble” car ils ne divulguent pas la nature de leurs algorithmes. Pour les chercheurs de l’université californienne de Berckley, les conducteurs maintenant mieux informés par ces méthodes modernes se lancent dans une concurrence dans un jeu à information parfaite (ou assimilable) pour atteindre un équilibre de Nash, c’est-à-dire une situation dans laquelle tout le monde a réussi à faire de son mieux au détriment des autres. Pourtant, cette solution n’est pas la meilleure des solutions ni pour tous le monde, ni pour chacun. Dans l’exemple présenté en Ted-talk par Alexandre Bayen, on voit un ensemble de conducteurs qui choisissent de quitter l’autoroute au même moment pour éviter un bouchon et qui vont former un second bouchon sur la sortie d’autoroute. Cette somme de parcours optimal pour un conducteur ne peut pas prendre en compte le déplacement simultané du flot de véhicule vers un goulot d’étranglement. La théorie des graphes nous donnera peut-être la solution à ce problème.
Peut-être… mais le problème est loin d’être aussi simple qu’il y paraît :
On a ici un graphe, notre réseau routier, sur lequel se déplace des flots de voitures qu’on veut optimiser. Mais :
Le problème peut ressembler à celui des transports des données sur l’internet dont la structure change sans cesse. Mais, sur internet, si un packet se peut se perdre et que notre visio-conférences doit freezer une demi-seconde, l’algorithme aura fait son travail correctement. Tandis que si quelques véhicules se voient suggérer un détour de 50 km pour aller au supermarché, l’algorithme ne peut pas être considéré acceptable.
Le problème ressemble aussi à celui de la gestion de trains sur un chemin de fer ; certes, on ne modifie pas les voies ferrées aux rythmes des rues autorisant l’automobile mais les algorithmes de gestion des voies ferrées, eux aussi hélas beaucoup trop fermé, parviennent au prix d’une information des usagers incomplète et changeantes à éviter bouchons et détours sur leur réseau. Cependant, le manque d’information pour les conducteurs sera un facteur de refus de l’algorithme.
En effet, ces deux problèmes se distinguent radicalement du nôtre sur un point-clef : Les conducteurs ne sont pas obligés d’adopter le trajet rendu par l’algorithme. Le conducteur de train ne décide pas de détour et les packets de données ne se rebellent pas contre les routeurs mais les conducteurs d’automobiles, eux, sont libres du choix du trajet. Ils souhaitent améliorer leurs trajets mais ils souhaitent aussi une amélioration perceptible. C’est pourquoi ils choisissent intuitivement le trajet optimisé personnellement plutôt que le trajet optimisant le flot sur le réseau routier.
En informant les conducteurs sur l’utilité sociale d’un tel algorithme, on pourrait augmenter son acceptation et voir le flot de véhicule mieux répartis sur le réseau routier. C’est déjà le cas dans une certaine mesure car l’optimisation individuelle pousse les conducteurs à sortir des axes principaux et découvrir les routes secondaires. Le soulagement des routes principales, quand il n’entraîne pas des bouchons à l’entrée des routes secondaires, et une bonne chose du point de vu de la théorie des graphes. C’est une moins bonne chose du point de vue des résidents de ces routes secondaires. La mentalité NIMBY (Not In My Back Yard), vouloir repousser le traffic loin de chez soit ne réglera pas les problèmes de la circulation et pourrait même les exacerber. Néanmoins, si l’ensemble du traffic routier ne peut se concentrer sur des grandes artères, de vrais arguments contre la circulation sur les petits routes existes. citymonitor.ai cite notamment la question de la sécurité routière : On voit moins souvent des jeunes enfants jouer au foot sur le périph’ que dans une rue résidentielle. Dans ces lieux où les usagers de la route sont moins séparés, les accidents entre eux sont plus nombreux.
On arrive finalement à une critique sociale de la route et de la place de la voiture qui j’aurai du mal à transposer à des concepts mathématiques. Il faut réussir à améliorer le trajet de chaque conducteur de véhicule en améliorant le flot routier totale en prenant en compte un grand nombre de paramètres d’optimisation. Seulement les flots automobiles ne sont les seuls à circuler sur le réseau, il existe des flots cyclistes et piétons, qui se concentrent sur certains axes et pour qui un problème de partage du réseau avec le flot automobile peut correspondre à une situation de vie ou de mort. Une circulation automobile fluide mais importante, sans aucun carambolage et accident, n’est pas non plus une situation désirable pour eux. La pollution aérienne, sonore et lumineuse n’est pas plaisante pour les habitants d’un quartier. La solution la plus efficace pour lutter contre elle est la réduction du traffic. Les maires et les habitants de quartier se lancent dans une guerre contre la circulation traversante, celles des voitures qui passent près de eux pour aller ailleurs mais il existe une bonne et une mauvaise façon de le faire :
La bonne favorise le flot des autres modes de transports (piéton, vélo, transport en commun) pour qu’ils prennent l’espace disponible sur cette partie du réseau. Ainsi, la voiture n’ayant plus la place pour circuler optimisera son trajet pour aller ailleurs et s’il n’y a plus d’ailleurs où aller, le flot total de voiture devant diminuer sur le réseau, le conducteur deviendra passager de transport en commun (TC), piéton ou cycliste, continuant ainsi à circuler dans le réseau mais participant à l’évaporation du traffic automobile. La voiture personnelle étant un objet encombrant, la somme des flots d’humain incluant flots de passager, de conducteur, de cycliste et de piéton pourra augmenter sur les réseaux des différents modes de transport à mesure que la place de la voiture circulera. La mauvaise rallonge et complique le trajet dans les lieux d’où chasser l’automobile. Cependant, ce rallongement des distances s’appliquent aux flots de tous les modes de transports. La marche et le cyclisme perdent en utilité au profit de la voiture qui augmente donc son flot total sur les réseaux de transports augmentant ainsi la saturation des arcs sur lesquels se concentrent le traffic. Le traffic induit compliquera ainsi la circulation des flots automobiles sur le réseau sans pour autant résoudre le problème initial à savoir comment passer d’une optimisation un trajet personnel à un arbitrage entre fluidité du traffic total et trajet individuel ?
Intéressant
Merci d’avoir pris le temps de me lire.