Des chercheurs du MIT se basent sur le machine learning pour résoudre le problème de tournées de véhicules.
Parfois, c'est mieux de se contenter des solutions moyennes que de perdre du temps à trouver la meilleure solution. Les résultats de cette étude sur le routage des véhicules vous le confirmeront.
Le problème du routage des véhicules
Des chercheurs du MIT ont développé une stratégie basée sur le machine learning pour s'attaquer au problème de tournées de véhicules. Aussi connu comme le routage des véhicules, ce problème concerne surtout le secteur de la livraison. Il consiste à effectuer des calculs pour minimiser les coûts de déplacement en trouvant l'itinéraire le plus court.
Généralement, les sociétés de livraison utilisent des solveurs algorithmiques pour résoudre le problème. Cependant, quand il est question d'un grand ensemble de villes, ces solutions deviennent beaucoup plus lentes. Mais une amélioration, même très faible, des solutions permettrait d'augmenter largement les revenus pour les entreprises.
Cette nouvelle étude porte sur le développement d'une méthode qui accélérerait les meilleurs solveurs jusqu'à 100 fois.
Améliorez la performance de vos projets grâce à l’IA générative ?
Améliorer les tournées de véhicules à l'aide de machine learning
Pour résoudre un problème de livraison, les algorithmes le décomposent en sous-problèmes. Une méthode courante consiste à identifier les meilleures solutions à ces sous-problèmes. Les chercheurs partent généralement d'une solution initiale moyenne pour l'améliorer par la suite. Mais cela prend souvent beaucoup de temps. Par ailleurs, une autre approche récente utilise le machine learning pour accélérer la résolution des problèmes, mais au prix de la précision.
L'équipe du MIT a donc combiné les deux approches pour développer des solutions à la fois rapides et de qualité. Ils appellent leur nouvelle méthode « apprentissage par délégation ». En termes simples, le nouvel algorithme de machine learning identifie les sous-problèmes suffisamment utiles à résoudre.
Au lieu de trouver les solutions optimales, le système identifie les problèmes dont la résolution permettrait d'améliorer la qualité des solutions. Autrement dit, en optant pour des solutions de qualité moyenne, il est possible d'obtenir des résultats de haute qualité.
Et cette méthode a effectivement permis d'accélérer la sélection des sous-problèmes de 1,5 à 2 fois, selon les chercheurs. De plus, la résolution du problème de tournées de véhicules à l'aide de machine learning reviendrait 10 à 100 fois moins chère.
- Partager l'article :
