Résumé
L'apprentissage automatique, notamment les modèles d'apprentissage profond et les techniques d'apprentissage par renforcement, s'est avéré efficace pour résoudre des problèmes d'optimisation combinatoire difficiles sans recourir à une définition manuelle d'heuristiques de résolution. Dans ce cadre, les problèmes de tournées de véhicule sont largement utilisés pour évaluer l'efficacité de nouvelles approches, notamment le problème de tournées de véhicules avec contrainte de capacité (CVRP).Pour le CVRP, les approches par apprentissage construisent les solutions candidates étape par étape, en choisissant à chaque itération soit de visiter un client, soit de retourner au dépôt pour se réapprovisionner, jusqu'à ce que tous les clients soient servis (à l'instar des méthodes constructives classiques telles que Savings ou Nearest Neighbors). Or, le choix du retour au dépôt peut être crucial pour la qualité des solutions candidates qui résultent des méthodes d'apprentissage ; dans la plupart des cas un plus grand nombre de retours au dépôt implique l'augmentation du coût de la solution candidate.Par ailleurs, il existe, dans la littérature du CVRP, des méthodes à deux phases qui distinguent l'affectation des clients à un véhicule, et l'ordre dans lequel ce dernier doit les parcourir. En fonction du séquencement de ces deux opérations, nous distinguons entre cluster-first route-second, et order-first split-second.Dans ce travail, nous introduisons une méthode en deux phases basée sur la stratégie route-first split-second pour le CVRP. Notre approche est fondée sur une combinaison de réseaux neuronaux profonds entraînés par apprentissage par renforcement et de l'algorithme Split.