L’optimisation de tournées en temps réel

LokadTV a invité notre Chief Product Officer, Cédric Hervet, pour parler de l’optimisation de tournées en temps réel. Joannes Vermorel, CEO et fondateur de Lokad & Kieran Chandler, Business Development Manager chez Lokad, l’ont reçu.

K : Grâce aux récentes avancées en matière de données sur le trafic routier, il est maintenant possible de prévoir l’impact de la congestion routière avec plus de précision que jamais auparavant. Cette semaine sur Lokad TV, nous sommes ravis de recevoir Cédric Hervet qui va nous expliquer comment le développement de l’informatique quantique et la capacité à optimiser les itinéraires en temps réel ont conduit les transporteurs à changer leur mode de fonctionnement. Cédric, merci d’être avec nous aujourd’hui. Pour commencer, pouvez-vous nous dire ce que vous faites chez Kardinal, la société que vous avez co-fondée ?

C : Bonjour, merci de m’accueillir. Kardinal est une société spécialisée dans l’optimisation des tournées en temps réel, notre particularité étant de tenir compte du contexte au sein duquel la tournée se réalise.

Le plus souvent, les tournées sont optimisées par des humains, manuellement. Les opérations de leurs chauffeurs ou de leurs techniciens sont planifiées à la main, ce qui est clairement sous-optimal d’un point de vue mathématique. Mais d’un autre côté, les humains ont une grande capacité à savoir gérer les urgences, les problèmes et autres événements inattendus qui se produisent sur le terrain et ils sont capables d’envisager la portée globale de leurs actions ainsi que de gérer les priorités afin de prendre la bonne décision. De leur côté, les algorithmes sont mal équipés pour cela, en particulier les algorithmes d’optimisation de tournées classiques.
La plupart des logiciels d’optimisation de tournées disponibles sur le marché fournissent une optimisation de tournées statique. Cela signifie qu’à partir des données, des opérations à réaliser et des ressources disponibles pour le faire, ils vont fournir une solution optimisée mais figée. Et c’est problématique car le premier événement inattendu qui sera rencontré sur le terrain altérera la qualité de la tournée qui a été calculée. Une fois que les camions sont partis sur la route, pleins de problèmes sont rencontrés, comme vous venez de le dire : les embouteillages, les clients qui sont en retard ou absents, qui veulent reporter leur rendez-vous. Tous ces événements peuvent altérer la performance de l’activité de nos clients. Chez Kardinal, nous sommes convaincus que la bonne façon d’optimiser les tournées, c’est en fait de ne jamais cesser de les optimiser. De cette façon, vous obtenez une plus grande capacité à vraiment gérer les problèmes au fur et à mesure. Un autre aspect clé de ce que nous faisons, c’est que nous nous efforçons de ne pas retirer l’humain de l’équation parce, qu’à bien des égards, les humains ont une expertise qui ne peut pas être remplacée par la machine. Les équipes terrain savent des choses qui ne sont disponibles, ni ne peuvent être modélisées dans aucune base de données et il est vraiment important de ne pas les retirer de tout le processus car ils ont une vision stratégique de leur activité.

K : Oui, cette idée d’utiliser un cerveau humain et d’en tirer le meilleur parti, en particulier dans ce genre de scénarios d’urgence, est vraiment intéressante. Je pense que c’est quelque chose avec laquelle tu es probablement d’accord Joannes : utiliser l’intelligence humaine dans le but d’affiner une optimisation ?

J : Oui absolument, c’est l’idée de tirer le meilleur parti de l’intelligence des Hommes, qui comprennent parfaitement le problème que leur société essaie de résoudre au sein de sa Supply Chain, tout en utilisant le meilleur de ce que la puissance de calcul moderne a à offrir. C’est à peu près, à un très haut niveau, aussi la stratégie de Lokad.

K : Ok super. Aujourd’hui, nous allons parler de l’optimisation des tournées en temps réel. En quoi cela vous intéresse-t-il du point de vue de la Supply Chain ?

J : Chez Lokad, quand on pense à l’optimisation de la Supply Chain, on ne réfléchit pas exactement à la même échelle de temps. Si je compare un peu ce que font Kardinal et Lokad, qui sont tous deux des éditeurs de logiciels pour les entreprises :  Kardinal fait de l’optimisation de tournées, cela concerne des décisions qui peuvent être remises en question à chaque minute environ. C’est en temps réel, même si ce n’est pas exactement à la microseconde près car vous ne pilotez pas non plus des robots en temps réel qui font de la préparation de commandes dans un entrepôt. Lokad se place davantage au niveau de la décision que vous avez besoin de prendre pour demain ou jusqu’à, disons, un an à l’avance. La différence se situe donc au niveau de l’échelle temporelle. Ainsi, le fait pour Lokad d’optimiser la Supply Chain, nous oblige à faire certaines hypothèses sur la livraison, notamment quand nous proposons de rééquilibrer certains entrepôts ou sites de production. L’efficacité de notre optimisation dépend donc fortement de l’agilité offerte par des outils d’optimisation de tournées tels que celui de Kardinal. Et la façon dont nous voyons les choses est que plus vous avez d’agilité dans la gestion de vos tournées, plus il vous sera facile de rééquilibrer vos stocks, ce qui implique un coût plus faible et, à terme, une plus grande capacité à réaliser ces optimisations sur le terrain.

K : Ok, passons à la question de l’agilité. Il n’y a pas si longtemps, j’imprimais les directions sur Google Maps et je ne pouvais pas modifier mon itinéraire s’il y avait du trafic devant moi. Aujourd’hui, nous sommes beaucoup plus dépendants de nos téléphones portables et des systèmes GPS. Comment l’optimisation des itinéraires s’est-elle développée au cours des dernières années ?

C : Eh bien, concernant l’optimisation des itinéraires, vous mentionnez en fait deux problèmes. Il y a le problème d’aller d’un point à un autre et de trouver le bon chemin à emprunter et c’est spécialement pour ce cas d’utilisation que des outils comme Google Maps sont conçus et il y a le problème plus général d’avoir N arrêts à visiter et de trouver dans quel ordre vous allez visiter tous ces arrêts, en tenant compte des données de trafic.

Chez Kardinal, nous nous concentrons sur le deuxième problème, qui est un problème très complexe à résoudre. En effet, si vous avez par exemple 20 points à visiter, le nombre de combinaisons est si élevé qu’il faudrait des milliers d’années à un ordinateur très puissant pour calculer toutes les tournées possibles. Il est donc évident qu’il est nécessaire d’utiliser des algorithmes qui sont beaucoup plus intelligents que ceux qui énumèrent simplement toutes les possibilités de tournées. C’est là que les mathématiques entrent en jeu : cette capacité des mathématiques à modéliser ce problème et à essayer de fournir des algorithmes pour le résoudre efficacement a été développée depuis de nombreuses années. Je pense même que cela avait déjà débuté dans les années 60, mais la mise en œuvre opérationnelle de tels algorithmes dépend beaucoup des données et de leurs disponibilités. Les données de trafic en particulier, parce que si vous construisez des tournées optimisées mais que les données que vous avez fourni à l’algorithme sont fausses ou inexactes, vous n’obtiendrez que des tournées infaisables. Vous pourriez obtenir de très bons KPI prédits, comme 10 à 20% de conducteurs en moins, moins de kilomètres parcourus, etc…, mais si c’est irréalisable sur le terrain, cela n’a pas vraiment de sens. Ce que nous faisons chez Kardinal, c’est vraiment de fournir des tournées qui sont faisables dans la pratique. Cela signifie que lorsque nous les donnons à un conducteur, il se dira : ” D’accord, je n’aurais probablement pas fait cela exactement de cette façon, mais c’est évidemment intelligent, et je pense que je peux réussir à le faire dans ma journée, sans finir 2 heures plus tard.”, ce qui est en fait leur quotidien aujourd’hui. Ils font souvent des heures supplémentaires, alors oui, ce sur quoi nous nous concentrons en ce moment, c’est : utiliser les mathématiques, tout ces beaux théorèmes, ces belles mathématiques, ces beaux algorithmes pour rendre les choses réalistes et faisables en pratique. C’est vraiment comme ça que nous voyons notre travail chez Kardinal.

K : Joannes, d’après ce que vous avez observé, qui sont les entreprises et les acteurs clés qui ont vraiment été les moteurs de cette croissance et de cette expertise en matière d’optimisation des itinéraires ?

J : J’ai pu observer qu’il y a eu énormément d’investissements dans le développement de solutions dites “online”, avec des applications dans tous les domaines. Par exemple, je pense qu’historiquement, la première entreprise à avoir proposé quelques chose de quasiment magique dans ce style était Google. Vous savez, les gens ne réalisent pas qu’avant Google, les moteurs de recherche comme celui de Yahoo réalisaient une mise à jour de leur index une fois par trimestre. En d’autres termes, vos résultats de recherches étaient toujours périmés ! Ainsi, si vous aviez une page qui avait été créée hier, elle n’aurait jamais pu apparaître dans vos résultats. Google a été très innovant sur de nombreux sujets, mais l’un d’entre eux a été de rendre ce processus complètement “online”. Quand vous faites une requête au moteur, vous vous attendez à avoir le meilleur résultat possible. En réalité, au début, ils n’étaient pas capables de faire cette mise à jour permanente. Je crois qu’ils réalisaient seulement des mises à jour hebdomadaires au début, mais c’était déjà 20 fois plus rapide que la concurrence ! C’était le début d’une transition vers un problème où vous souhaitez avoir, en permanence, les résultats les plus à jour possible. Bien sûr, ni Kardinal, ni Lokad n’utilisent des algorithmes de moteurs de recherche, mais c’est clairement une source d’inspiration quand vous souhaitez faire ce genre de choses complexes à grande échelle, avec la preuve que ça peut fonctionner. Par la suite, de nombreux acteurs ont cherché à faire des choses similaires sur de nombreux types de problèmes et je crois que beaucoup de gens se sont posés la question : “comment puis-je attaquer la version online de ce problème ?”, ce qui est plus intelligent. Cette même différence se retrouve dans ce que Kardinal réalise maintenant sur son marché par rapport à ce qui était fait dans les années 50, avec toutes ces contraintes, toutes ces non-linéarités, et une optimisation qui doit gérer beaucoup de choses difficiles à représenter d’un point de vue mathématique. Par exemple, le fait qu’un chauffeur ne peut pas conduire plus de X heures car il y a une convention collective qui dit ceci, ou cela…

K : Ok, et parlons un peu des données. Quelles sont les données qui intéressent vraiment Kardinal et d’où proviennent-elles ?

C : Eh bien, il y a deux sources principales de données. La première source est évidemment notre client qui nous fournit les commandes que nous devons optimiser. Il nous donne la description la plus précise possible de son activité. Cela peut être, comme vous l’avez dit, les contraintes légales de temps de travail de ses chauffeurs, la disponibilité des chauffeurs, où commencent-ils, où finissent-ils leur service, quel type de véhicule ils conduisent, quelles capacités ont les véhicules, est-il agréé pour le transport de marchandises dangereuses, lui est-il possible de réaliser des interventions techniques spécifiques qui nécessitent des compétences particulières. Toutes ces données définissent les contraintes qui pèsent sur leur activité, et nous devons donc prendre tout cela en compte. Il y a aussi des données, toujours en provenance du client, qui décrivent les commandes : il peut s’agir de colis à livrer mais il peut aussi s’agir d’interventions comme par exemple la réparation de matériel informatique. De notre côté, nous nous appuyons sur des partenaires technologiques comme Here Technologies, qui nous permet d’obtenir les données de distance. Nous avons besoin de tenir compte du temps nécessaire pour aller d’un point à l’autre et nous devons comprendre comment le trafic va évoluer dans le temps. Nous avons également besoin, une fois que les camions sont sur la route, d’obtenir le trafic en temps réel pour adapter nos tournées, et c’est Here qui est notre fournisseur de données à ce niveau là. Nous traitons ces données avec nos algorithmes pour fournir des solutions actualisées. Ce sont donc nos deux principales sources d’information.

K : Vous avez parlé des solutions en ligne et de leur croissance. D’un point de vue technique, quels genres de défis représente le fait de travailler en temps réel ?

J : Le temps réel a introduit des complications massives. Tout d’abord, le temps réel n’existe pas, la vitesse de la lumière est finie. Vous diriez : “c’est incroyablement rapide”, oui mais quand on y pense, ce n’est pas si rapide. Le problème est qu’une fois que vous avez des systèmes informatiques distribués et que vous devez faire des allers-retours entre plusieurs centres de données et que vous faites des milliers de kilomètres à chaque fois, vous diriez : “ce ne sont que des millisecondes”. Mais si vous devez faire des milliers d’allers-retours, alors vous commencez à réaliser qu’il faut quelques secondes pour obtenir des résultats. En fait, pour réaliser des systèmes en temps réel lorsque vous opérez à l’échelle mondiale, il faut beaucoup de compétences. De plus, il y a tellement de choses qui peuvent vous empêcher d’avoir un bon système en temps réel. Vous pensez ” oh mon système est en moyenne super rapide”, mais pensez à votre ordinateur, combien de fois essayez-vous de faire quelque chose avec votre ordinateur et pendant 2 minutes, il est bloqué du fait d’une mise à jour de Windows ou autre. La réalité est que nos ordinateurs sont en moyenne très rapides oui, mais si vous commencez à penser au pire scénario…, le pire scénario est qu’ils peuvent en fait être assez lents.

Là encore, dans tout système informatique d’entreprise, la vitesse du système est en fait celle du composant le plus lent. Ce qui, quand vous avez beaucoup de machines impliquées, augmente les chances de très forts ralentissements, car il suffit que l’une d’elles soit impactée par une mise à jour, ou quoique ce soit d’autre, pour ralentir tout le système. Donc le temps réel porte en lui un ensemble de challenges très complexes à relever.

Un autre aspect de la complexité inhérente au temps réel est que vous introduisez tout à coup une dépendance vis à vis de vos partenaires. Ce qui signifie : comment pouvez-vous, en tant qu’éditeur de logiciels d’entreprise, rendre votre service disponible et très fiable, même si vos partenaires ne le sont pas. Une fois de plus, le problème est que plus vous avez de dépendances, plus les problèmes potentiels de temps d’arrêt sont nombreux. La performance de votre service ne peut être au mieux qu’aussi bonne que celles de vos partenaires technologiques. Cela signifie qu’à chaque fois que vous étendez la chaîne, vous ajoutez un composant qui va faire que votre système aura une disponibilité et une performance globale inférieure ou égale à ce que vous aviez avant. C’est donc un gros challenge !

K : Ok. Nous entrons maintenant dans une ère où les utilisateurs peuvent avoir le contrôle de ces données : par exemple avec Waze, vous pouvez maintenant dire qu’il y a un radar de police qui se déplace quelque part. Pensez-vous que le fait que nous puissions maintenant contrôler ces données soit un point positif ?

C : C’est évidemment quelque chose de très important, d’avoir cette capacité de contrôler les données. Surtout dans les contextes que je décrivais auparavant. Chez Kardinal, nous sommes très attentifs à garder les humains à bord du système. Parce qu’une fois qu’ils en perdent le contrôle, et que tout est automatisé, ils ne peuvent pas vraiment vérifier si l’algorithme propose quelque chose de pertinent pour eux. Et surtout, ils perdent tellement de compréhension sur ce qu’il se passe qu’ils ne peuvent plus vraiment apporter leur expertise.

Il y a cette petite histoire qui date de nos débuts. Nous essayions de challenger les tournées de livreurs de colis en proposant nos propres tournées optimisées. Les chauffeurs nous remontaient toujours des exemples de choses que l’algorithme ne pouvait pas prendre en compte. Un exemple amusant est que, nous avions fourni une tournée magnifiquement optimisée qui était de façon évidente la manière parfaite de réaliser toutes les livraisons. Mais le chauffeur, en la regardant, ne se concentrait pas sur l’aspect général de la tournée (qui était de toute façon mieux que ce qu’il aurait fait manuellement), mais il se focalisait plutôt sur certains points spécifiques. Il nous disait : “ok, donc vous me dites que je vais livrer cette personne ici, à 16h45, or ici il y a une école et je sais que tous les parents vont se garer dans cette rue à cette heure là et je ne pourrai pas me garer pour faire cette livraison ! Donc d’accord, c’est évidemment mathématiquement optimal mais je sais que cette livraison à cette heure précise, sur cet intervalle de 30 minutes est juste impossible à réaliser…”. Pour nous chez Kardinal, le fait d’intégrer ce niveau de détail à nos données pour ne pas proposer de tournées infaisables aurait un coût faramineux. Et dans la pratique et grâce à la manière que nous avons de fonctionner, c’est inutile parce que nous avons dans le camion quelqu’un qui le sait déjà. Donc, la philosophie clé que nous essayons de mettre en place avec eux est la suivante : “ok, vous savez des choses que nos algorithmes ne saurons jamais, et nous n’essaierons jamais vraiment de les connaître parce que cela nous coûterait trop cher. Alors donnez-nous juste cette information, et vous pourrez contester l’algorithme même quand vous serez sur la route ! Beaucoup d’événements peuvent se produire : il peut s’agir de problèmes provenant des clients, des données, de n’importe quoi. Nous considérons donc que les données de l’utilisateur sont des événements à part entière. Et si vous, en tant que chauffeur, pensez que quelque chose  doit être fait autrement, vous pouvez choisir de faire autre chose que ce que nous venons de suggérer.”. Ce que nous ferons est : “ok, vous prenez cette décision, en voici l’impact”. Nous réoptimisons les choses avec la nouvelle information provenant de l’utilisateur, nous leur en donnons l’impact, pour qu’ils puissent prendre une décision informée. Ainsi, le chauffeur reste le maître de sa tournée car il sait probablement des choses que l’algorithme ignore. Donc, pour répondre à votre question, il est très important de considérer la donnée et le contrôle que l’utilisateur peut avoir dessus. Car la donnée en elle-même est inutile si vous ne pouvez pas la comprendre car vous n’avez pas d’outil qui vous explique ce que cette donnée veut vraiment dire. Mais dès que vous êtes en capacité d’apporter de la compréhension de ce que signifie la donnée, et sur les décisions que le système recommande, alors l’Homme n’est plus retiré du système, il est en quelque sorte “augmenté”. Il prend de meilleures décisions car il connaît leurs impacts d’après nos calculs et grâce à l’ensemble des éléments qu’il a en tête. C’est vraiment ce que nous essayons de réaliser : la bonne combinaison entre les deux.

K : Un autre exemple que j’ai rencontré lors de mes recherches à ce sujet, c’est qu’aux Etats-Unis, quand il y avait les feux de forêt et que les gens se mettaient en route pour y échapper, évidemment les routes où il y avait des feux, Waze les indiquait comme étant sans trafic et ils dirigeaient les gens de ce côté. Donc, avoir un moyen d’ajuster cela et d’éviter cette zone…

C : Absolument, parce que les humains savent des choses qui sont hors de la portée de l’algorithme. Donc il faut vraiment en tenir compte quand tu fais ce que nous faisons.

K : Joannes, diriez-vous, du point de vue des données, que nous sommes un peu trop dépendants de certaines grandes compagnies telles qu’Amazon, Google, Microsoft, etc ?

J : Je dirai probablement oui. Mais il faut considérer le fait que la technologie bouge très rapidement et si vous vous intéressez à la donnée cartographique, il n’y a pas beaucoup de fournisseurs dans le monde. Cela soulève également la question de savoir si la donnée cartographique devrait ou non être un bien commun, ce que certaines personnes essaient de réaliser avec des projets de cartographie en open data. Mais la réalité est qu’avec la technologie qui évolue aussi rapidement, il est difficile pour la plupart des entreprises de suivre. Habituellement, les gens considèrent que “le gagnant rafle la mise”, mais ils oublient que dans les domaines technologiques, on observe très souvent une rotation de la position dominante du “gagnant”, qui n’est jamais longtemps le même. Donc, pour l’instant, sur les aspects cartographiques, il n’y a que peu d’acteurs sur le marché. C’est très concentré, mais je vois aussi beaucoup de changements se produire avec des données qui étaient auparavant très difficiles d’accès se rapprocher du domaine public avec les projets d’open data. Cela prendra du temps, mais je pense qu’à terme, ces données deviendront vraiment la base, et les problèmes qu’on rencontre aujourd’hui se seront transformés en autre chose. Mais pour résumer ce qui se passe en ce moment, et Kardinal est probablement en pointe sur le sujet, pour ce qui est de la donnée cartographique il y a probablement 4 ou 5 acteurs majeurs, ce qui en fait un marché très concentré.

K : Ok et pour conclure aujourd’hui, un dernier point : je pense que vous êtes impliqué dans la recherche et le développement. Vous avez vraiment bénéficié de certaines avancées dans le domaine de l’IA ces derniers temps. Quels sont les sujets de recherche qui vous passionnent pour les deux prochaines années ?

C : Bon tout d’abord, il y a ce que nous faisons chez Kardinal, qui m’enthousiasme beaucoup. Nous avons des doctorants qui travaillent à la résolution des versions “en ligne” des problèmes d’optimisation classique et qui, se faisant, contribuent à étendre le champ de la Recherche Opérationnelle en tant que discipline mathématique, afin de nous permettre d’attaquer ces problèmes de la bonne façon. Mais nous avons également vu d’autres choses se produire dans la communauté de l’IA. Il y a des choses sur l’apprentissage par renforcement qui est vraiment une approche différente de ce que nous faisons en Recherche Opérationnelle. Cette approche consiste à laisser apprendre aux algorithmes quelles sont les meilleurs décisions, sans leur indiquer explicitement, ce qui est philosophiquement très différent de ce que nous faisons chez Kardinal, où nous explicitons à l’algorithme l’ensemble des solutions possibles au problème et nous lui indiquons ce qui fait qu’une solution est meilleure qu’une autre. De cette façon, il se concentre sur le fait de trouver la meilleure solution parmi un ensemble de solutions possibles. L’apprentissage par renforcement propose une autre façon de faire cela, qui présente sur le papier de nombreux avantage pour la prise de décision en temps réel. Je pense que la limite actuelle de cette approche est qu’elle ne peut pas vraiment gérer la variété de contraintes que nous gérons avec nos techniques, mais qui sait, nous avons été très surpris par ce que l’apprentissage par renforcement a permis sur le jeu de Go ou même dans les jeux vidéo. Ces algorithmes sont capables de battre des joueurs très forts, donc c’est vraiment quelque chose que nous suivons de près. Et, c’est vraiment prospectif, mais nous avons vu récemment Google annoncer la “suprématie quantique” : c’est à dire le moment où un ordinateur quantique a réussi à résoudre un problème plus rapidement que ce qu’un ordinateur classique aurait pu réaliser. Nous savons qu’il existe des algorithmes quantiques qui conviennent pour résoudre le problème du voyageur de commerce qui est l’un de nos problèmes principaux. Ces algorithmes peuvent résoudre en quelques secondes et de manière optimale des problèmes qui prendraient des milliers d’années pour un ordinateur qui ne ferait qu’énumérer les solutions. C’est donc aussi quelque chose que nous devons suivre. Évidemment, c’est un travail à très long terme, et avec nos algorithmes, nous sommes, en étant intelligents dans leur conception, déjà à la même vitesse que les algorithmes quantiques. L’informatique quantique fournit une sorte de démocratisation de la résolution de tous ces problèmes qui sont, par nature, difficiles à résoudre. Et c’est quelque chose d’intéressant pour nous parce qu’évidemment, si nos problèmes deviennent faciles à résoudre demain, nous devrons être à la pointe de cette technologie pour aider nos clients à être beaucoup plus performants qu’aujourd’hui.

K : Ok, génial. Merci pour votre temps aujourd’hui, c’était vraiment intéressant.

C : Merci beaucoup.

K : C’est tout pour cette semaine. Merci d’être resté jusqu’à la fin, et nous vous reverrons la prochaine fois. Au revoir !

Découvrez la vidéo de la table ronde organisée par Lokad, à laquelle à participé Cédric Hervet (cofondateur de Kardinal), au sujet de la réponse de la Supply Chain en situation de pandémie