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.

Julien Coupey

Auteur : Julien Coupey

Julien est développeur et responsable de la R&D chez VERSO.