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.

Julien Coupey

Auteur : Julien Coupey

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