Catégorie : Optimisation de tournées

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.