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 !
