Catégorie : API

Les flottes dédiées à la logistiques évoluent, notamment avec l’électrification des véhicules qui impose la prise en compte de nouvelles contraintes pour la planification opérationnelle.

Notre service d’optimisation de tournées s’adapte en s’appuyant comme d’habitude sur la dernière version de VROOM, le logiciel open-source que nous développons.

Rayon d’action des véhicules

Nous avions déjà fait un premier pas vers la modélisation de l’autonomie des véhicules en donnant la possibilité de limiter par véhicule le temps de trajet total. Mais bien souvent la distance totale parcourue est tout aussi limitante que le temps de trajet, sinon plus. D’où la nécessité de pouvoir la maîtriser, par exemple pour des véhicules électriques ou des coursiers à vélo.

Nous avons ajouté un paramètre max_distance utilisable par véhicule afin de maintenant garantir la génération de tournées qui respectent l’autonomie des véhicules sur les deux critères : temps de trajet et/ou distance parcourue.

Un modèle de coûts plus réaliste

Pour prendre en compte les temps de trajet des véhicules et des chauffeurs dans les coûts, notre précédente mise à jour avait déjà introduit la notion de « coût par heure », une pondération réglable individuellement pour chaque véhicule.

Mais au-delà du temps, la distance parcourue a un impact important pouvant varier largement : coût du carburant pour un véhicule thermique ou coût du rechargement des batteries pour un véhicule électrique. Notre modélisation ajoute maintenant à l’objectif d’optimisation un coût par km parcouru, ajustable pour chaque véhicule.

Finalement, il ne s’agit plus de simplement minimiser les temps de trajet, mais de considérer au cœur de l’optimisation l’ensemble des coûts associés aux véhicules, qu’ils soient fixes, liés à des temps ou à des distances parcourues.

Contactez-nous si vous souhaitez travailler sur la modélisation des coûts de votre flotte pour l’optimisation de vos tournées !

Vélo-cargos, véhicules électriques légers, camionnettes : l’utilisation de moyens complémentaires est désormais un classique de la logistique. Comment construire des tournées pertinentes avec une flotte de véhicules aux caractéristiques et coûts d’exploitation radicalement différents ?

Notre service d’optimisation de tournées modélise aujourd’hui finement les coûts, en s’appuyant comme d’habitude sur la dernière version de VROOM, le logiciel open-source que nous développons.

Flotte hétérogène

Notre optimisation multi-profil gère déjà la variabilité des temps de trajet suivant les types de véhicules, mais ce n’est là qu’un aspect du coût. En réalité chaque véhicule a un coût horaire spécifique et les coûts fixes peuvent également être radicalement différents suivant le type de véhicule, voire même selon le contexte : recours à des véhicules complémentaires en location, sous-traitance, etc.

Notre API prend désormais en compte un coût fixe et un coût horaire défini par véhicule. L’objectif d’optimisation n’est plus le temps de trajet global, mais le coût opérationnel réel associé au plan de tournées. Résultat : en plus de l’affectation et de l’ordonnancement des tâches, nous optimisons le choix des ressources à utiliser en fonction de l’ensemble des coûts.

Autonomie des véhicules

Sur le terrain, l’autonomie des véhicules est déterminante, qu’elle découle de contraintes matérielles comme les batteries des véhicules électriques, ou de choix opérationnels. Il est par exemple souhaitable de pouvoir maîtriser l’effort total à fournir pour la tournée d’un cycliste.

Se contenter de restreindre l’amplitude des horaires de travail est une approche beaucoup trop rigide donnant des solutions largement sous-optimales. C’est pourquoi nous avons introduit, en complément des fenêtres horaires, la possibilité de limiter le temps de trajet total par véhicule. Nos algorithmes évitent donc maintenant les dépassements d’autonomie tout en garantissant un maximum de flexibilité dans le modèle, et donc de meilleures solutions.

Performances

L’implémentation de ces nouvelles fonctionnalités ajoute à la résolution des traitements qui augmentent inévitablement les temps de calculs. Fidèles à notre obsession de la performance, nous avons fait en sorte de minimiser ce surcoût sur le plan algorithmique. Et surtout, nos travaux récents d’accélération de la résolution ont fourni en amont une marge de manœuvre compensant largement le prix à payer pour ces évolutions fonctionnelles importantes.

Contactez-nous si vous souhaitez optimiser votre gestion de flotte !

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 !

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

L’API d’optimisation de tournées de Verso est en constante évolution pour répondre au mieux aux besoins des utilisateurs. La mise à jour d’octobre 2019 apporte des fonctionnalités attendues pour affiner le contrôle de la forme des solutions obtenues et permettre la résolution de nouveaux types de problèmes. Cette mise à jour repose sur la version 1.5 de VROOM, le logiciel d’optimisation de tournées open-source que nous développons.

Gérer les priorités

En cas de ressources limitées (nombre de véhicules, horaires de travail, capacité, etc.) il n’est pas toujours possible d’assurer tous les jobs à réaliser. Dans l’exemple ci-dessus (à gauche), le job qui est exclus est naturellement celui qui est le plus éloigné. Mais que se passe-t-il si il devait être assuré prioritairement par rapport aux autres ? Il est maintenant possible d’associer des priorités plus élevées à certains jobs de manière à garantir qu’ils soient assurés dans la solution proposée (à droite).

Mélanger des livraisons et des collectes

Nous pouvions jusqu’ici facilement modéliser un problème de logistique simple : soit les véhicules partent chargés d’un dépôt pour effectuer un ensemble de livraisons, soit ils partent à vide pour réaliser un ensemble de collectes qui sont rapportées en fin de tournée. La réalité du terrain est plus complexe, car les tournées mélangent généralement ces deux types d’actions, y compris parfois au même point. Garantir la validité des solutions vis-à-vis des capacités est alors plus difficile qu’il n’y paraît. En effet la charge d’un véhicule dépend à chaque instant de l’ensemble des collectes déjà effectuées, des livraisons restant à faire, et de leur ordonnancements respectifs dans la tournée.

Cette fonctionnalité est maintenant implémentée : il est possible de mélanger les livraisons et les collectes avec la garantie qu’à chaque étapede la tournée la capacité du véhicule est respectée.

Des performances améliorées

L’ajout de ces fonctionnalités augmente la complexité de résolution, mais – cerise sur le gâteau – n’occasionne aucun allongement des temps de calculs. Au contraire, ceux-ci ont diminué grâce en premier lieu à diverses optimisations lors de la compilation du code. Ensuite, nous atteignons maintenant les mêmes solutions en effectuant moins de tests de validité, notamment ceux dont la complexité a augmenté pour gérer simultanément les livraisons et les collectes. Résultat : le temps de calcul sur les benchmarks VRPTW classiques a diminué en moyenne de près de 40 %.

Pour en savoir plus, consultez la documentation de l’API ou contactez-nous pour découvrir comment vous pouvez tirer parti de ces nouvelles fonctionnalités.

L’API d’optimisation de tournées Verso s’intègre de manière simple et transparente dans tout logiciel métier pour augmenter sa valeur en faisant gagner temps et argent aux utilisateurs. Après le succès de son intégration chez nos clients ayant bénéficié d’un accès en avant-première, nous avons le plaisir d’annoncer la mise à disposition officielle de l’API.

Résoudre les vrais problèmes du terrain

Que ce soit dans le domaine de la logistique ou des services, les professionnels dont l’activité nécessite des déplacements coordonnés veulent des tournées optimisées, rentables, calculées rapidement afin de pouvoir se concentrer sur leur cœur de métier. Par ailleurs, la prise en compte de leurs contraintes spécifiques de plus en plus complexes est une nécessité. Notre API automatise en temps réel la planification des déplacements, permet la réduction de l’ensemble des coûts d’exploitation tout en garantissant le respect des contraintes : horaires, délais d’acheminement et d’intervention, limitations de capacités, compétences spécifiques etc. L’intégration dans un logiciel métier apporte une plus-value immédiate pour les utilisateurs finaux et un retour sur investissement garanti.

Performance, fiabilité et évolutions

Notre API est conçue d’emblée pour passer à l’échelle sur des problèmes de très grande taille en fournissant des solutions efficaces et adaptées en un temps record. Les performances de nos approches de résolution sont reconnues et attestées sur de nombreux benchmarks et problèmes réels, car notre API est basée sur le logiciel VROOM, que nous développons en open-source pour de meilleures garanties de pérennité. En intégrant notre service dans votre logiciel, vous bénéficierez ainsi sans aucun surcoût des évolutions fonctionnelles constantes développées selon une roadmap définie en concertation avec nos clients.

Pour en savoir plus, consultez la documentation de l’API et contactez-nous pour découvrir comment nous pouvons vous permettre d’améliorer votre propre logiciel.