Technique

Prototypes :

Nous disposons de 3 prototypes : 

L’un est un programme qui, à partir d’un point de départ et d’une liste de points à parcourir, renvoie le chemin le plus court pour parcourir l’ensemble des points. 

Ce programme utilise les algorithmes de google OR-Tools, une suite logicielle Open Source pour l’optimisation, conçue pour résoudre les problèmes les plus complexes au monde concernant l’acheminement des véhicules, les flux, la programmation entière et linéaire, et la contrainte. (projet :  FlexRouting)

Le second programme (RoadConstraint) reçoit les résultats du premier et les transforme en une suite de segment que l’on peut coller sur une carte : 

Pour cela, dans un premier temps, il transforme la carte de la ville de Caen en un graphe non orienté et non connexe : 

Dans un second temps, il faut, pour chaque point (qui se présente sous la forme de coordonnées longitude :49.209625501599824, latitude :-0.3647620691874721), chercher le nœud du graphe qui lui correspond. Pour terminer, il suffit d’effectuer un calcul du plus court chemin avec l’algorithme Dijkstra. Le programme est également utilisé pour simuler des trajets effectués par des habitants entre leur domicile et le supermarché. (Projet RoadConstraint) 

Enfin, le dernier prototype se présente sous la forme d’une application web qui interprète les segments obtenus en simulant les trajets avec une interface graphique. Deux simulations se succèdent, l’une représentant le trajet des citoyens de leur domicile au supermarché, et l’autre la livraison des courses par un camion dans les différents quartiers. Pour quantifier les résultats et clarifier les éléments de sortie, nous avons décidé de représenter les valeurs les plus importantes sous forme de graphes. Notamment, la distance kilométrique et la consommation en CO2 pour chacune des deux simulations afin de les mettre en comparaison. De plus, nous avons un troisième graphe faisant la différence de CO2 émis entre les deux simulations. 

Dans la page principale, nous avons la carte de Caen qui a été affichée avec l’API MapLibre. Caen a 19 quartiers, chaque quartier est représenté dans la carte avec un symbole de maison, en plus il y a un supermarché et un entrepôt. En haut à droite, l’utilisateur peut démarrer la simulation en définissant la population. 

Détails de la simulation :

• Les distributions de probabilité utilisées dans la simulation sont basées sur des données du monde réel et sont implémentées à l’aide de fonctions de distribution de probabilité appropriées en JavaScript. Ces distributions sont utilisées pour déterminer la probabilité que certains événements se produisent dans la simulation, ce qui a permis de modéliser des scénarios du monde réel. 

• Dans notre simulation, nous avons utilisé le format JSON pour stocker et utiliser les données recueillies. Le format JSON est un format d’échange de données léger qui est facile à lire et à écrire pour les humains et facile à analyser et à générer pour les machines. Cela nous a permis d’intégrer facilement les données dans notre simulation basée sur JavaScript. Les données utilisées dans la simulation incluent des informations sur les trajets que les véhicules suivront, ainsi que la densité de population dans différents quartiers de la ville simulée. Ces données étaient essentielles pour fournir une représentation réaliste et précise de la ville dans la simulation. Les informations sur les chemins ont permis à la simulation de modéliser le mouvement des véhicules à travers la ville, tandis que les données sur la densité de population nous ont permis d’échantillonner des individus aléatoires de différents quartiers. 

• Dans notre simulation, nous avons utilisé une technique appelée interpolation pour diviser le chemin en segments de longueur égale. Cela nous a permis de modéliser plus précisément le mouvement le long du chemin et d’effectuer des calculs ou des simulations sur des sections spécifiques du chemin. 

Illustration avec un exemple :

Voici un exemple de démarrage de la première simulation avec 1000 habitants :

Chaque cercle rouge représente un citoyen en voiture, les citoyens partent de leur domicile et font leur trajet au marché. En dessous de la carte nous affichons le graphe d’évolution de consommation. À la fin de la première simulation, le site démarre la deuxième simulation, représentant le camion qui part depuis l’entrepôt et parcours les domiciles des clients. 

Voici un exemple de démarrage de la deuxième simulation avec une population de 1000 habitants :

Le cercle vert de la deuxième simulation représente les camions de livraison. 

Notamment, la distance kilométrique et la consommation en CO2 pour chacune des deux simulations afin de les mettre en comparaison. De plus, nous avons un troisième graphe représentant la différence de CO2 émis entre les deux simulations.  

Nous avons utilisé plusieurs logiques visant à produire les résultats les plus réalistes possibles. Notamment le data sampling en se basant sur des données réelles récupérées pour la ville de Caen, les distributions probabilistes pour les valeurs de consommation de carburant et de vitesse, l’interpolation de points afin d’effectuer des sauts de taille égale entre chaque itération, et enfin un lien croissant entre le nombre de camions et la taille de la population. 

Voici le graphe d’évolution de consommation de CO2 et kilomètres sans et avec le panier collectif à gauche et la quantité de CO2 non émis à droite :

Gitlabs:

Projet FlexRouting:

https://gitlab.com/Pignon/flexrouting

Projet RoadConstraint:

https://gitlab.com/Pignon/roadconstraint

Projet site de démo:

https://gitlab.com/Pignon/panniercollectif-prototype

Projet MapLibre :

https://github.com/maplibre/maplibre-gl-js

Sources

Habitants par quartier:

https://actu.fr/normandie/caen_14118/la-question-pas-si-bete-quels-sont-les-quartiers-les-plus-peuples-de-caen_49122698.html