La solution Kardinal est une plateforme SaaS d’optimisation des opérations de transport qui intègre deux axes produits forts : un module d’optimisation des tournées en continu et un outil de sectorisation stratégique dédié aux acteurs de la messagerie. Kardinal exploite les services de son partenaire HERE technologies pour les données cartographiques et de trafic de ces 2 modules.
Le webinar du 7 juin 2021 avait pour objectif de présenter l’approche Kardinal d’une optimisation de tournées plus réaliste, impliquant entre autres, la prise en compte et la bonne utilisation des données trafic.
Utilisation des données trafic dans l'optimisation de tournées Kardinal
Zoom sur la réalité du trafic routier
Avant d’aborder le sujet de l’intégration du trafic dans les algorithmes d’optimisation de tournées, voyons la réalité du trafic routier et en quoi cet élément peut être très complexe. Voici deux exemples de profils de trafic assez typiques (ici représentés à Grenoble).
# Exemple 1
Le premier trajet part du nord de la ville et passe par l’un des axes périphériques pour rejoindre un centre commercial. Le graphique nous montre qu’en fonction de l’heure de la journée, le temps de trajet varie. Le pic du matin et celui du soir correspondent à un profil typique d’un axe très emprunté aux heures de pointe.
Profil typique d’un grand axe périphérique, avec une forte variation la journée et deux pics de trafic, le matin et le soir.
# Exemple 2
Le second exemple part d’un point encore plus au nord de Grenoble, en lointaine banlieue, et qui va jusqu’à l’entrée de la ville. Cet exemple illustre un cas typique d’un axe alimentant une grande ville et que l’on retrouve dans toutes les grandes agglomérations. De nombreuses personnes y circulent le matin, notamment pour aller travailler en ville. Cependant, le trafic est beaucoup moins dense le soir car les voitures circulent en sens inverse.
Profil typique d’un grand axe qui alimente une ville, avec un pic d’affluence le matin, mais peu le soir où l’axe est chargé en sens inverse.
Comment le trafic est-il pris en compte en optimisation de tournées ?
Dans la méthode classique, l’algorithme accède à une matrice des durées / distances et optimise les tournées en tenant compte de ces durées/distances sans trafic. Pour prévoir le fait qu’il va y avoir du trafic, des coefficients sont appliqués afin de surpondérer ces durées / distances et ainsi éviter la planification de tournées totalement irréalisables.
Une fois les tournées obtenues, les ETA peuvent être recalculés en tenant compte du trafic prédictif de chaque trajet à l’heure à laquelle il est prévu de réaliser ce trajet. Il arrive alors souvent que les créneaux horaires ne puissent finalement pas tous être respectés.
Dans cette méthode, le trafic n’est donc pas calculé de manière exacte, il s’agit essentiellement d’appliquer un coefficient global aux durées (par exemple, tout augmenter de 10%).
Chez Kardinal, le processus d’optimisation est un peu différent.
Comme dans la méthode classique, nous récupérons les durées et distances sans trafic mais nous allons également capter les variations de trafic sur la journée. Nous ne travaillons donc pas avec une matrice mais avec un cube composé d’une dimension supplémentaire qui est la dimension temporelle. Cela permet à notre algorithme (spécifiquement conçu pour pouvoir appréhender un cube au lieu d’une matrice) de comprendre la totalité des évolutions de durées sur la journée et de s’en servir dans sa planification.
Notre algorithme est alors capable d’exploiter ces informations pour tenir compte des moments de pics et de creux pour planifier des trajets à des moments de la journée où il y a moins de trafic.
Quelles différences en pratique sur les tournées entre une utilisation du trafic à priori et à postériori ? Exemple sur un cas concret
Qu’est-ce que la donnée trafic apporte réellement à l’optimisation ? Est-ce seulement une question de précision ?
Pour répondre à ces questions, prenons un exemple sur un cas concret : une tournée de livraison à réaliser dans Paris et sa proche banlieue Ouest.
Contraintes de la tournée :
- 2 véhicules au départ de Nanterre
- Départ à 9h45 / Retour à 17h45
- 1h de pause à prendre entre 12h et 14h
- 34 points à livrer (points bleus sur la carte)
- Des créneaux horaires de 2h à respecter sur certains points
- 10 minutes de temps prévu pour livrer chaque point
Pour mesurer l’impact du trafic, les algorithmes d’optimisation ont reçu l’objectif de minimiser le temps total de travail de la tournée.
Des tournées optimisées sans prise en compte du trafic
Dans ces deux tournées, le trafic n’est pas pris en compte. On s’attend à ce qu’elles soient plus longues que prévu dans la pratique. La deuxième tournée est particulièrement critique car ce type de trajet, le matin en région parisienne, est très compliqué à gérer. Démarrer la tournée dans Paris le matin n’est pas vraiment une bonne idée, les axes indiqués par l’algorithme étant très encombrés. Cette tournée sera, sans nul doute, considérablement rallongée par les embouteillages.
Des tournées optimisées sans trafic avec ajout du trafic via un coefficient global
La méthode d’ajout du trafic via des coefficients ne modifie pas la structure des tournées. Seuls les KPI sont corrigés pour prendre en compte un impact du trafic routier sur les ETA et les durées de trajet.
Après ajout du trafic à posteriori, le temps de travail global est donc rallongé de 50 minutes versus la version sans trafic. Plus grave : presque 10% des créneaux horaires ne sont plus respectés.
Des tournées optimisées avec prise en compte du trafic
Quand l’algorithme « a connaissance » du trafic et peut en tenir compte dans ses calculs de tournées, ses choix sont radicalement différents et la structure même des tournées est modifiée.
La première tournée est relativement similaire à celle optimisée sans trafic (elle couvre toujours le nord de Paris), à la différence qu’elle a récupéré des points à livrer de l’autre tournée. La deuxième tournée, quant à elle, est radicalement différente : plutôt que commencer par le centre de Paris, elle livre d’abord tous les points en banlieue. Les points dans Paris seront plutôt livrés vers 13h-14h, horaires où la circulation est moins dense que le matin. Ces cartographies nous montrent que les tournées sont fortement impactées dans leur structure même par les prévisions de trafic.
Comparatif des tournées
Chaque tableau représente :
(1) Le résultat de l’optimisation sans trafic
(2) Les résultats des tournées optimisées sans trafic auxquelles nous avons ajouté le trafic à posteriori
(3) Les résultats de l’optimisation avec trafic
Les deux premiers tableaux montrent bien que le trafic impacte les livraisons et notamment le respect des créneaux horaires qui ne seront pas tous honorés. Le temps de travail est fortement impacté (50 minutes supplémentaires sur la totalité des tournées) alors qu’il s’agissait du critère à optimiser dans cet exemple. La deuxième tournée dépasse les 8h de travail (8h03), 3 minutes n’étant pas excessif mais représentant bien le décalage entre les prévisions initiales, que l’on pensait répondre aux contraintes déterminées, et les tournées finales, qui ne les respectent pas.
Les tournées optimisées avec le trafic en amont présentent, quant à elle, un nombre de kilomètres parcourus, de temps de trajet et de travail inférieurs mais également un respect total des créneaux horaires. Cette diminution de temps significative est possible car l’algorithme a la capacité d’exploiter les moments de la journée où le trafic est moins dense. Le trafic n’a donc pas seulement un impact sur la précision des tournées mais également sur leur structure même.
Quelle utilisation du trafic temps réel dans la solution Kardinal ?
La donnée trafic est donc cruciale pour l’optimisation des tournées en amont des opérations mais elle l’est tout autant pendant leur déroulé.
Cette vidéo présente une tournée en cours de livraison impactée par le trafic routier. Les embouteillages sont détectés avant même que les livraisons ne soient impactées. L’algorithme va ainsi réoptimiser la tournée en temps réel, suggérant un itinéraire alternatif pour maintenir une qualité de service maximale et minimiser les retards. La tournée peut subir un allongement de sa durée totale mais celui-ci permet de ne pas se laisser surprendre par les variations de trafic.
Origine des données trafic utilisées par Kardinal : zoom sur les services HERE technologies
Les solutions de Kardinal s’appuient sur les données HERE pour offrir à ses clients des tournées plus réalistes et performantes. L’enjeu pour les logisticiens est de disposer d’un service trafic très précis à chaque instant, mis à jour en temps réel.
Quels services HERE propose-t-il ?
Depuis 35 ans, HERE propose une offre globale et complète de services cartographiques, conformes à la RGPD. La plateforme se place leader sur son marché, devant Google, TomTom et Mapbox. Présent dans plus de 80 pays, HERE propose une couverture trafic globale, nécessaire aux transports à l’international.
Les cartographies de HERE permettent d’afficher les flux de trafic et les incidents pouvant perturber le flux habituel. Ces données en temps réel sont actualisées toutes les minutes. A partir de cette data, HERE est capable de créer des modèles de trafic avec les vitesses standards pour chaque jour de la semaine par intervalle de 15 minutes.
Les incidents recensés par la technologie peuvent notamment concerner des fermetures dues à des travaux, des accidents, des véhicules en panne ou encore des éléments encombrants la voie (animal, objet, personne). En plus de la localisation et du type d’incident, HERE fournit :
- Sa direction
- Une description détaillée
- Son heure de début et de fin
Les informations sur les embouteillages ou incidents permettent de visualiser les conditions du trafic sur la carte et de calculer un itinéraire prenant en compte les conditions de circulation pour un calcul précis d’ETA (Estimated Time of Arrival).
En milieu urbain, HERE renforce son service trafic avec une couverture détaillée, ce qui permet d‘augmenter la précision de l’état du trafic sur les segments de voie, comme on peut le voir pour les villes de Paris et Lyon ci-dessous.
Pour accéder aux services trafic de HERE, les méthodes sont multiples :
- L’API Trafic de HERE
- Une solution logicielle embarquée dans le véhicule et connectée au serveur
- Une émission / broadcast (par exemple : RDS ou TNC)
- Une API de calcul d’itinéraires intégrant le service trafic en tant que paramètre, comme le fait Kardinal
Comment sont créés les services trafic de HERE ?
Les deux sources principales alimentant les services de HERE sont :
- Des données GPS de véhicules (Probe data) récupérées grâce à des accords avec des constructeurs automobiles et des sociétés de transport
- Des données provenant de capteurs sur les véhicules (par exemple : capteurs sur les essuies-glasse, les phares, les freins, des capteurs d’humidité, etc.), les capteurs se développant avec l’émergence des véhicules autonomes
86% des données proviennent de véhicules mobiles : voitures, taxis, flotte de camions… Le reste est capté par des smartphones ou les PND (Portable Navigation Device) encore présents dans certains véhicules.
HERE s’appuie sur les données de 125 fournisseurs présents dans plus de 80 pays afin d’avoir la meilleure représentativité et fiabilité possibles du trafic.
L’équipe Qualité de HERE effectue une vérification initiale des données, puis les envoie à l’équipe Développement pour une évaluation approfondie incluant deux phases :
- Une phase de Pré-intégration : une semaine d’échantillon de données du fournisseur est analysée.
- Une phase de Post-intégration : une semaine de données de production complète du fournisseur est analysée dans l’environnement de test avant exploitation
Les équipes de HERE roulent environ 70 000 kilomètres par an pour tester et valider les temps calculés ainsi qu’évaluer ses services trafic par rapport à ceux de la concurrence.
A propos des intervenants
HERE Technologies est la première plateforme de données et de services de localisation. Elle a été rachetée en 2015 par le consortium allemand de constructeurs automobile constitué de Daimler, BMW et Audi et est ainsi alimentée par les données de millions de véhicules de particuliers.
Kardinal réalise l’optimisation des opérations de transport et de la logistique, principalement du dernier kilomètre en continu et en temps réel. La solution Kardinal a la capacité de réoptimiser les plannings en direct en fonction des remontées du terrain que ce soit des informations trafic mais également des véhicules eux-mêmes (leur position, l’avancement de ce qu’ils sont en train de réaliser). Kardinal est composé d’une vingtaine de collaborateurs en France.
Retrouvez le replay du webinar Kardinal & HERE « Optimisation de tournées : boostez la pertinence de vos tournées grâce aux données trafic »
