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.
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.
