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.

Gestion du pickup and delivery

L’API d’optimisation de tournées de 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.

Nouvelles fonctionnalités de l’API et amélioration des performances

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

Exemple d’utilisation des priorités – Map data © OpenStreetMap contributors

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.

Ouverture de l’API d’optimisation de tournées

L’API d’optimisation de tournées de 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.

Image © Jack Moreh

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.