Algorithmes métaheuristiques pour quelques problèmes de routage

Cette thèse porte sur quatre problèmes d’optimisation de tournées : le problème du voyageur de commerce avec des temps de tâches (TSPJ), le problème de routage de véhicules capacitaires cumulatifs avec un dépôt unique (CCVRP) et plusieurs dépôts (MDCC-VRP), le problème de localisation et routage avec latence (LLRP) et le problème d’orienteering d’équipe capacitaire (CTOP). Ces problèmes apparaissent fréquemment dans des applications réelles et sont connus pour être NP-difficiles, rendant leur résolution particulièrement complexe. Pour faire face à cette complexité, des approches métaheuristiques sont naturellement envisagées pour traiter des instances de grande taille. Cette thèse vise à développer des algorithmes métaheuristiques avancés afin de faire progresser l’état de l’art dans la résolution de ces problèmes. Plus précisément, nous proposons une recherche locale avec évasion (breakout local search) pour le TSPJ, un algorithme évolutionnaire à deux individus pour le CCVRP et le MDCCVRP, un algorithme évolutionnaire hybride guidé par l’apprentissage par renforcement pour le LLRP, et un algorithme mémétique guidé par l’apprentissage pour le CTOP. Les résultats expérimentaux montrent que les algorithmes proposés obtiennent des performances compétitives par rapport aux méthodes de référence, dans des temps de calcul raisonnables. De plus, une analyse approfondie des principaux composants algorithmiques est réalisée afin de mieux comprendre leur influence sur les performances des algorithmes proposés.