De meilleures solutions, plus vite

Nous améliorons en continu les algorithmes de notre API d’optimisation de tournées pour obtenir toujours plus efficacement des solutions de qualité. En jeu : la rapidité d’interaction avec les outils métiers et la possibilité de résoudre rapidement des problèmes toujours plus grands. Coup d’œil sous le capot de la dernière version de VROOM, le logiciel open-source que nous développons.

Mieux, plus vite

Le schéma ci-dessus résume ces améliorations à travers différents compromis entre qualité des solutions et temps de calcul sur le benchmark de Solomon, une référence dans la littérature. Le meilleur écart aux solutions optimales, auparavant déjà faible à 1,81 % en moyenne, descend à 1,63 %. Une gageure au regard du temps d’exécution réduit lui de moitié : à peine 360 millisecondes en moyenne sur ces 56 problèmes comportant chacun 100 livraisons !

Sur le terrain, nous avons pu constater une diminution de 42 % du temps de calcul sur les problèmes réels issus de l’exploitation d’un de nos clients.

Amélioration des solutions

La complexité combinatoire des problèmes de tournées de véhicules rend illusoire une étude exhaustive des solutions possibles. Nous utilisons donc une stratégie de recherche locale visant à explorer efficacement des zones prometteuses de l’espace des solutions. Cette exploration doit être tout à la fois suffisamment poussée pour accéder à de bonnes solutions, mais limitée afin de conserver des temps de calculs ultra-rapides.

Grâce à l’implémentation d’un nouvel opérateur de recherche locale, nous accédons maintenant à de meilleures solutions, tout en améliorant la qualité perçue, avec moins de croisements de routes dans les solutions.

Des records de vitesse de résolution

Pour réduire drastiquement les temps de calculs, nous « coupons » de manière anticipée des branches d’exploration de la recherche locale. En calculant et stockant de nouvelles informations, nous sommes à même de repérer plus tôt des modifications vouées à l’échec, car donnant des solutions violant des contraintes horaires ou de capacité. Voire même des contraintes non nécessairement explicites comme le nombre de tâches maximum par véhicule, qui peut être borné implicitement par d’autres contraintes.

Résultat : des solutions obtenues jusqu’à deux fois plus rapidement sans restreindre l’exploration des solutions valides, donc la qualité finale.

Contactez-nous si vous souhaitez mesurer l’impact de ces améliorations sur votre cas d’usage !

Nouvelles fonctionnalités pour l’API d’optimisation de tournées

Nous travaillons constamment à l’amélioration de notre API d’optimisation pour fournir à nos clients des tournées toujours plus pertinentes sur le terrain. Focus sur la dernière mise à jour reposant sur une nouvelle version de VROOM, le logiciel d’optimisation de tournées open-source que nous développons.

La pertinence opérationnelle des tournées
passe par la modélisation fine des temps de service et l’équité des
solutions proposées. – Map data © OpenStreetMap contributors

Nouveaux leviers pour la modélisation

Tournées trop chargées

Obtenir des tournées réduisant globalement les coûts n’est pas suffisant si les écarts de charge de travail sont inadaptés à l’organisation opérationnelle (illustration ci-dessus à gauche). Il faut alors pouvoir garantir une forme d’équité (à droite).

Il était jusqu’ici possible de limiter la charge de travail par tournée dans certains cas avec une restriction de capacité dédiée. Dorénavant, le nombre de tâches maximum peut être fourni nativement en entrée, par véhicule. En plus de fonctionner pour tous les types de tâches, cette nouvelle modélisation divise les temps de calcul par deux, tout en se combinant aux restrictions habituelles des contraintes horaires.

Modélisation des temps de service

Il arrive régulièrement que plusieurs tâches se succèdent au même endroit, par exemple pour livrer les habitants d’un même immeuble ou enlever plusieurs colis dans le même magasin pour le compte de destinataires différents. Dans ce cas, une partie du temps passé sur place est mutualisé entre les tâches et ne peut pas être décrit par le seul temps de service. Nous avons donc ajouté la notion de temps de setup qui modélise le temps nécessaire pour se garer, accéder aux locaux, bref une durée fixe relative au lieu. Les temps de service de
tâches qui se succèdent au même endroit se cumulent comme d’habitude mais le temps de setup n’est appliqué qu’une seule fois.

Utiliser un planning existant

Il n’est pas toujours pertinent de chercher une solution en partant de zéro, par exemple quand on souhaite amender à la marge un planning existant ou simplement tester la faisabilité de l’ajout de quelques tâches. C’est notamment le cas lors de prises de rendez-vous en ligne où il faut très rapidement valider (ou non) un nouveau créneau horaire. Dans cette situation, il est maintenant possible de fournir le planning existant en entrée de l’optimisation. Il servira alors de solution initiale lors d’une phase d’optimisation ultra-rapide.

Amélioration de la résolution

La conception et l’amélioration de nos approches d’optimisation sont au cœur même de notre expertise. Outre les ajouts fonctionnels, nous avons implémenté un nouvel opérateur de recherche locale. Il s’agit d’une version de l’opérateur SWAP* proposé par le chercheur Thibaut Vidal dans un article récent, que nous avons adapté dans notre contexte pour la gestion d’un plus grand nombre de contraintes, notamment horaires. Sur des benchmarks de référence, l’écart moyen à l’optimal déjà faible (+1,73 %) a été ramené à +1,32 %, une amélioration significative au vu des temps de calculs toujours très rapides.

Contactez-nous si vous souhaitez tester les nouvelles évolutions de notre API d’optimisation.

Socleo optimise les circuits courts

L’éditeur Socleo, spécialiste des circuits courts, propose désormais à ses clients d’optimiser leurs tournées de livraison. Les utilisateurs de Socleo ont immédiatement accès à cette nouvelle fonctionnalité sans sortir de leur outil habituel grâce à l’intégration de notre API d’optimisation de tournées.

Un spécialiste des circuits courts

Socleo édite un logiciel à destination des acteurs des circuits courts : producteurs, transformateurs ou distributeurs. L’outil s’adapte aussi bien aux structures individuelles, qu’aux collectifs et aux plateformes territoriales.

Multifacette, le logiciel permet de gérer à la fois le commercial avec une boutique en ligne et un site vitrine, la logistique grâce à la gestion des stocks et des livraisons, et également l’administratif avec l’édition de factures. Il s’agit donc d’une plateforme complète de gestion et de pilotage totalement adaptée aux besoins des circuits courts.

Un partenariat au service des acteurs du terrain

Grâce à l’intégration de notre API, Socleo met l’optimisation de tournées à la portée de ses utilisateurs. L’adoption est d’autant facilitée qu’ils n’ont pas à sortir de l’environnement familier de leur outil de travail habituel, qui contient déjà la plupart des données nécessaires à la mise en forme de leurs problèmes d’optimisation.

Ces acteurs des circuits courts pourront ainsi mieux maîtriser leur gestion logistique. En premier lieu, ils gagneront un temps considérable en automatisant une grande partie de la planification de leurs tournées. Ensuite l’optimisation leur permettra de passer moins de temps sur la route tout en réduisant l’impact environnemental de leurs déplacements, en cohérence avec l’esprit même des circuits courts.

Contactez-nous pour toute question sur l’intégration de l’optimisation de tournées dans votre propre logiciel de gestion.

Optimisation multi-profil

Gérer efficacement une flotte de véhicules hétérogène est crucial pour la logistique du dernier kilomètre. C’est ce que permet désormais notre API grâce à une nouvelle version de VROOM, le logiciel d’optimisation de tournées open-source que nous développons.

Example de répartition naturelle des tâches entre voitures et vélos électriques – Map data © OpenStreetMap contributors

La gestion des profils

Le « profil » d’un véhicule décrit ses caractéristiques et conditionne les itinéraires qu’il peut emprunter ainsi que sa vitesse sur chaque portion de trajet. Calculer efficacement des temps de trajet pour un vélo-cargo électrique, un véhicule léger ou un poids lourd est évidemment primordial pour la pertinence des tournées optimisées.

Différents profils de véhicule sont disponibles à travers notre API, mais jusqu’ici le choix devait être fixé à l’échelle d’un problème. C’est à dire qu’il n’était pas possible d’optimiser des tournées pour une flotte hétérogène du point de vue des types de véhicule. Une limitation importante car il est souvent nécessaire de faire intervenir des véhicules différents de manière complémentaire, et cette tendance s’accentue. Par exemple les zones urbaines sont de plus en plus réservées aux mobilités douces pour des raisons environnementales et réglementaires.

Dorénavant, notre API intègre ces contraintes pour utiliser à bon escient le type de véhicule pertinent pour son efficacité en fonction du contexte. Les distinctions de profil s’ajoutent aux autres spécificités hétérogènes déjà gérées comme les capacités ou les horaires de disponibilité. Dans l’illustration ci-dessus, cinq vélos électriques sont naturellement affectés à des tournées urbaines courtes et denses, tandis que les tournées plus longues et extérieures à la ville sont assurées en voiture.

Implémentation efficace

Faire évoluer la gestion des temps de trajet est délicat car il s’agit d’une primitive au cœur de tous nos algorithmes d’optimisation. Sur le plan technique, il a fallu restructurer notre code. Nous en avons profité pour ajouter au passage une notion de coefficient de vitesse, qui permet au-delà du profil d’affiner encore davantage les temps de trajets estimés pour chacun des véhicules.

Ensuite, il a fallu ajuster la stratégie de résolution afin de prendre en compte l’hétérogénéité. Enfin, cette fonctionnalité ouvrant à la résolution de nouveaux types de problèmes, nous avons validé sur de nouveaux benchmarks la pertinence de nos algorithmes. Les solutions fournies sont bonnes, tant pour la réduction des coûts que pour la rapidité du calcul, toujours au rendez-vous grâce à diverses optimisations des structures de données utilisées.

Contactez-nous si vous souhaitez échanger sur l’utilisation de votre flotte hétérogène.

Deliverme.City innove pour la livraison du dernier kilomètre

DeliverMe.City propose une solution de livraison en main propre offrant aux utilisateurs de choisir exactement où et quand ils reçoivent leurs colis. Sélectionnée par le magazine Challenges parmi les start-up les plus innovantes et prometteuses de 2021, la société a un positionnement écologique et social fort. Son ambition de faire bouger les lignes de la livraison du dernier kilomètre impose une organisation agile, laquelle s’appuie sur notre API d’optimisation de tournées.

La singularité de DeliverMe.City

À contre-courant de certaines plateformes, DeliverMe.City fait le choix de proposer un service opéré par des coursiers salariés. Au-delà de la question sociale, ce choix fait des coursiers les ambassadeurs de l’offre, garants d’une qualité de service irréprochable.

Afin de réduire l’impact écologique et les nuisances, les livraisons sont effectuées avec des vélos à assistance électrique et l’ensemble des approvisionnements motorisés en amont utilisent des véhicules électriques. Par souci de la fiabilité technique et de la qualité, DeliverMe.City fait appel à un créateur français de vélos cargos.

Surtout le client est replacé au centre du dispositif, choisissant le lieu de livraison et l’heure souhaitée en fonction de son propre planning. Cette liberté va jusqu’à la possibilité de changer d’avis sur le lieu ou l’heure même lorsque les opérations de livraison sont déjà en cours.

La souplesse offerte aux utilisateurs signifie que ce sont leurs besoins qui « tirent » les flux, à rebours d’une organisation généralement « poussée » par la chaîne logistique et subie par les destinataires. Cette approche au cœur de l’offre de DeliverMe.City est une gageure en terme d’optimisation.

Organisation et modélisation

En effet, la multiplication des contraintes et les possibilités de mise à jour en temps réel tendent naturellement à augmenter les coûts opérationnels. Une stratégie qui ne peut être viable qu’avec une organisation ad-hoc.

DeliverMe.City a donc conçu un système de distribution multi-échelon qui, en synchronisant divers intervenants, offre à la fois flexibilité et réactivité. Que ce soit en amont lors des premières prises de commandes ou dans le feu de l’action, les allers-retours avec l’API d’optimisation permettent une mise à jour en continu de la planification.

Confronter la vision de DeliverMe.City à notre expertise en optimisation a été une expérience très enrichissante qui a permis de passer de l’idée à la réalisation. La modélisation du problème que nous avons réalisée ensemble a permis de structurer l’organisation déployée. Nous souhaitons maintenant à l’équipe de DeliverMe.City une réussite à la hauteur de son enthousiasme !

Contactez-nous si vous aussi vous avez un challenge d’optimisation à nous soumettre.

Nouvelle fonctionnalité de planification

La fonction solve de notre API affecte des tâches géolocalisées à diverses tournées en les ordonnant efficacement. En complément, la nouvelle fonction plan va fournir des indicateurs précieux pour éclairer les choix de nos utilisateurs lors des modifications de planning.

Ah ! j’arriverai trop tard ! (Alice au pays des merveilles, chapitre premier)- Photo de Veri Ivanova sur Unsplas

Des indicateurs pour l’aide à la décision

Sur le terrain, les opérateurs gérant la planification peuvent modifier à la marge des tournées optimisées pour satisfaire des besoins non explicités ou réagir aux aléas. Ces choix découlent d’une expertise mélangeant empiriquement les critères de coût et de qualité de service liée au respect des contraintes métiers, notamment horaires.

La fonction plan permet pour n’importe quelle route de mettre à jour les horaires d’arrivée prévus (ETA) tout en évaluant le coût opérationnel et l’impact sur le respect des contraintes. Pour chaque ajustement, il devient possible d’obtenir instantanément des indicateurs pertinents : nombre de tâches en retard, niveau de retard, dépassement des horaires ou des capacités théoriques des véhicules, modification du coût… Les utilisateurs peuvent apporter leur expertise avec une plus grande valeur ajoutée en appuyant leurs décisions sur des éléments factuels précis.

Un problème simple… en apparence

Dans le cas d’une tournée surchargée, il est impossible de respecter tous les horaires. Faut-il alors partir comme prévu mais arriver en retard pour certaines tâches ? Dans ce cas, notre API permettra de quantifier les retards. Mais pourra également proposer de partir plus tôt, dans la mesure de la marge sur le terrain, afin de réduire les retards pour limiter la dégradation de service perçue.

Autre exemple d’un opérateur qui souhaite déplacer le matin en début de tournée une tâche censée être faite après 14 h. Le respect de cette contrainte changerait toute la physionomie de la planification en décalant tous les horaires. L’API détecte dans ce cas qu’il faut violer la seule contrainte de la tâche déplacée, avec une avance importante, mais sans occasionner de retard plus tard.

L’optimisation sous le capot

Pour la fonction plan, les contraintes horaires habituelles deviennent souples afin d’autoriser les violations horaires, l’objectif principal étant de les minimiser. En second lieu, on assure une amplitude de travail réduite au maximum tout en cherchant à faire les tâches au plus tôt.

L’approche de programmation linéaire que nous avons implémentée garantit l’optimalité de la solution obtenue, tout en évitant l’écueil fréquent de temps de calcul déraisonnables. Grâce à un travail de modélisation ad-hoc poussé, les temps de réponse de l’API permettent une utilisation en temps réel.

Pour mieux cerner l’apport de cette nouvelle fonctionnalité pour votre cas d’usage, contactez-nous.

Prise en compte des pauses

Planifier des tournées de véhicule pertinentes nécessite de prendre en compte les besoins du terrain, en particulier la gestion des pauses des chauffeurs. Cette fonctionnalité attendue avec impatience par nos utilisateurs est désormais disponible via notre API grâce à une nouvelle version de VROOM, le logiciel d’optimisation de tournées open-source que nous développons.

C’est l’heure de la pause ! – Photo de Phil Garrison sur Unsplash

Flexibilité géographique et temporelle

Jusqu’ici, il était techniquement possible de définir une pause au sein des plages de travail d’un chauffeur sous la forme d’une tâche particulière. Cependant, cela supposait de fixer le lieu associé à la pause. Si ce cas d’usage est parfois pertinent, le lieu d’une pause doit généralement découler de la route optimisée. La nouvelle notion de pause décrit donc une tâche non géolocalisée à insérer dans les étapes d’une route.

Ensuite, figer l’horaire d’une pause est contre-productif du point de vue de l’optimisation. On ne souhaite pas annuler la précédente tâche qui ferait commencer une pause à 12 h 03 sous prétexte que celle-ci était prévue à 12 h 00. À l’inverse, on doit être capable d’assurer que la pause est faite suffisamment tôt pour garantir le respect des deadlines des tâches suivantes. Notre API offre cette flexibilité tout en garantissant pour chaque pause sa durée et une plage horaire de faisabilité adaptée aux besoins du terrain.

Plus subtil : imaginons le cas où la dernière tâche du matin se termine avant le début potentiel de la pause du midi qui est toutefois impossible à reporter. Il faut éviter un temps d’attente, et retarder la pause pourrait occasionner des retards pour certaines des tâches suivantes. Nous sommes alors en mesure de fractionner le temps de trajet avant et après la pause. Cela nous permet de minimiser les temps d’attente et d’accéder à des solutions pertinentes même dans les cas où les contraintes horaires sont très fortes.

Nouveaux cas d’usage sans dégradation des performances

Chaque route peut se voir affecter de multiples pauses, ce qui ouvre le champ pour modéliser un grand nombre de situations nouvelles. Entre autres exemples, la planification d’activités sur plusieurs jours prenant en compte les arrêts nocturnes est rendue triviale.

La bonne nouvelle est que nous avons réussi à ajouter cette fonctionnalité sans augmenter significativement la complexité algorithmique de notre approche de résolution. En clair, nous conservons des temps de calculs records, avec ou sans pauses.

Si vous souhaitez tester cette nouvelle fonctionnalité, contactez-nous pour demander votre clé d’API.

Teliae intègre l’API Verso

Teliae est spécialisée dans l’édition de logiciels métier pour les acteurs du monde de la logistique et du transport. Ses TMS (Transport Management System) sont utilisés par plus de 450 transporteurs et logisticiens de toutes tailles tels que Ciblex, XPO, Kuehne Nagel Road, Michelin, Groupe Mazet, GFS, Office Depot, DGS, Normatrans, Noyon, etc. Afin de donner toujours plus de valeur ajoutée à ses solutions, l’éditeur a intégré notre API d’optimisation de tournées, permettant à ses clients de gagner du temps de planification et de réduire leurs coûts opérationnels.

Le TMS Teliway en action – Map data © OpenStreetMap contributors

Les clés d’une intégration réussie

Les utilisateurs du TMS Teliway accèdent en un seul clic aux fonctionnalités d’optimisation de tournées. Pas d’outil supplémentaire à utiliser, pas d’échange de données à configurer : les exploitants restent dans le contexte de leur environnement de travail familier. La valeur ajoutée de l’optimisation est immédiatemment accessible, et devient une simple étape du processus opérationnel ergonomique proposé par Teliway.

Mais surtout le succès de l’intégration d’un outil d’optimisation de tournées réside en grande partie dans sa capacité à prendre en compte finement les besoins afin de produire des solutions pertinentes sur le terrain. Teliae a fait un important travail d’intégration des contraintes de ses utilisateurs : sectorisation plus ou moins flexible basée sur le plan de transport, contraintes liées à l’organisation des quais de chargement, priorités des tâches, horaires et temps de service, etc.

« Je suis toujours bluffé par la rapidité des calculs »

Jérôme Petit, directeur des opérations chez Teliae

Enfin, notre rapidité de calcul permet au module d’optimisation de fonctionner comme une aide à la décision en temps réel, permettant de faire des choix métiers éclairés. Fort de son expertise, l’utilisateur a évidemment toujours le dernier mot pour ajuster les tournées depuis l’écran de camionnage ou même la vue cartographique.

La complémentarité comme maître mot

« Je suis toujours bluffé par la rapidité des calculs », nous confiait à l’issue de l’intégration Jérôme Petit, le directeur des opérations de Teliae. C’est tout le sens de notre démarche qui est de nous concentrer sur une « brique logicielle » qui résoud un problème précis et le fait très efficacement. Nous sommes donc ravis de la confiance de Teliae qui recherche justement dans cette collaboration une expertise très spécifique en optimisation. À l’inverse, Teliae dispose d’une riche et longue expérience du terrain qui lui permet de faire de cette intégration un succès au service de ses utilisateurs.

Contactez-nous si, comme Teliae, vous souhaitez optimiser les tournées de vos utilisateurs et apporter une valeur ajoutée à votre logiciel.

Gestion du pickup and delivery

L’API d’optimisation de tournées Verso vient de connaître une évolution importante avec la modélisation des problèmes de pickup and delivery, ce qui permet d’adresser de nombreux nouveaux contextes. Comme toujours, cette mise à jour repose sur une nouvelle version de VROOM, le logiciel d’optimisation de tournées open-source que nous développons.

Photo by RoseBox

Nouvelle fonctionnalité

Depuis la précédente mise à jour, nous pouvions déjà mélanger des livraisons et des collectes au sein d’une même tournée. Cependant, l’ensemble des objets à livrer ou à collecter devaient être chargés au départ du véhicule, ou ramenés en fin de tournée. Dans le jargon, le terme pickup and delivery désigne la situation où un objet est collecté et livré plus tard
au cours d’une même tournée. La nouvelle entitéshipment ajoutée à l’API décrit précisément ce besoin de déplacement d’un lieu à un autre.

Tout les cas d’usages hybrides sont envisageables car les objets shipment peuvent être utilisés pour créer des tournées mixtes, conjointement avec les objets job décrivant déjà des livraisons ou collectes classiques.

De nouveaux cas d’usage

L’optimisation de livraisons ou collectes chez de nombreux clients depuis – ou vers – de multiples points de stockage (dépôts, magasins…) est maintenant possible. Les contraintes habituelles telles que capacités, plages horaires, compétences, priorité sont bien entendu prises en compte. Dans le cas d’une flotte de véhicules distribuée, l’optimisation choisira automatiquement les véhicules les plus adaptés pour une série de collectes et livraisons associées, de manière à minimiser le coût opérationnel.

La mobilité des personnes rentre également dans le champ d’application avec des possiblités d’optimisation intégrées aux solutions innovantes avec mutualisation de véhicules. Dans les contextes de mobilité à la demande, la rapidité de calcul permet alors de ré-optimiser et mettre à jour le planning en temps réel.

Les performances toujours au rendez-vous

Comme toujours, nos résultats sont transparents et reproductibles. Sur le benchmark Li & Lim 100 de la littérature académique, notre approche atteint les solutions optimales dans plus de 46 % des cas avec un écart moyen au coût optimal de +1,22 % seulement. Et ce toujours en un temps record : ces problèmes comportant environ une centaine de points sont résolus en moyenne en 256 millisecondes !

Si vous souhaitez tester cette nouvelle fonctionnalité, contactez-nous pour demander votre clé d’API.

Place du local simplifie l’accès aux produits locaux

L’impact de nos modes de consommation devient aujourd’hui un critère de choix important. Place du local permet à tout un chacun de consommer de manière plus vertueuse sur le plan économique et écologique.

Josselin Pradier, fondateur de Place du local – © Lionel Vadam, Est Républicain

Mieux se nourrir facilement

De nombreuses personnes souhaitent (re)donner du sens à leurs actes d’achat en favorisant des produits locaux sains et de qualité, ce afin de soutenir le tissu de producteurs locaux tout en réduisant l’impact environnemental lié à leur consommation. Pour autant, peu de consomateurs ont les moyens ou le temps de le faire pour l’ensemble de leur « panier » de courses habituel. Place du local s’approvisionne auprès de nombreux producteurs pour proposer un e-marché qui garantit à tous un accès à des produits locaux avec la souplesse des moyens modernes : commandes en ligne, livraisons à domicile ou en point relais avec choix des horaires.

Un impact réel et quantifié

Place du local utilise notre API d’optimisation pour planifier ses tournées de livraison de manière efficace tout en garantissant le respect de l’ensemble des contraintes, notamment les jours et horaires de livraison choisis par ses clients. Au-delà du gain de temps lors de la planification et de la réduction des coûts de livraison qui rend le service plus accessible à tous, l’optimisation est devenu un maillon essentiel de l’organisation logistique. Avec des résultats impressionnants : aujourd’hui, la distance parcourue en moyenne par panier livré est de seulement 6 km en incluant tournées de livraisons et d’approvisionnement. À titre de comparaison, le temps de trajet quotidien en voiture pour les courses est de 15 minutes en moyenne1, et ce chiffre ne tient pas compte des trajets nécessaires à l’approvisionnement des magasins.

Nous sommes heureux d’accompagner un partenaire local dont l’action favorise des modes de consommation plus soutenables sur le plan économique et écologique.

[1] Source INSEE