Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

Introduction Générale

La recherche opérationnelle s'attache à étudier des problèmes d'optimisation combinatoire dont la résolution constitue un véritable challenge. Il s'agit de trouver une affectation de valeurs à un certain nombre de variables tout en respectant un ensemble de contraintes donné. Parmi les paradigmes de résolution, la programmation par contraintes est particulièrement adaptée pour étudier la réalisabilité d'un problème de satisfaction de contraintes, tandis que la programmation linéaire en nombres entiers s'inscrit davantage dans le cadre de la recherche d'un extremum d'une fonction linéaire. Cependant, ces approches partagent une procédure de résolution commune qui consiste en l'énumération implicite de l'ensemble des solutions du problème. Il s'agit alors de parcourir l'espace de recherche et d'en extraire une solution admissible (problèmes de satisfaction de contraintes) ou optimale (problèmes d'optimisation combinatoire) ou de prouver qu'il n'en existe pas. Le schéma classique consiste en une recherche arborescente qui évalue à chaque noeud la solution partielle courante et l'étend si possible en affectant une valeur à une variable non encore instanciée.

Les problèmes combinatoires difficiles ont depuis longtemps attiré l'attention des chercheurs. On peut citer Garey et Johnson (1979) qui ont approfondi les bases des concepts de problèmes NP-difficiles et ont montré que de nombreux problèmes n'avaient que peu de possibilités d'être résolus efficacement par des méthodes exactes. Ces méthodes exactes permettent d'obtenir une ou plusieurs solutions dont l'optimalité est garantie. Cependant, dans certaines situations, il est nécessaire de disposer d'une solution de bonne qualité (c'est-à-dire assez proche de l'optimale) dans un contexte de ressources (temps de calcul et/ou mémoire) limitées. Dans ce cas, l'optimalité de la solution n'est pas garantie, ni même l'écart avec la valeur optimale. Néanmoins, le temps nécessaire pour obtenir cette solution est beaucoup plus faible que dans le cas d'une méthode exacte. Ce type de méthodes, dites heuristiques, est particulièrement utile pour les problèmes nécessitant une solution en temps limité ou pour résoudre des problèmes difficiles.

Ces méthodes approchées peuvent se classer en différentes catégories:

- Constructives (algorithmes gloutons),

- Recherche locale (algorithmes de descente, recherche à grand voisinage, ...), - Métaheuristiques (recuit simulé, recherche Tabou,...),

- Évolutionnaires (algorithmes génétiques, algorithmes d'optimisation par colonies de fourmis, algorithmes mémétiques,...).

L'intuition qui est à la base des travaux menés sur la plupart des méthodes heuristiques réside dans le fait que dans la majorité des problèmes d'optimisation combinatoire, les bonnes solutions sembleraient partager des « structures» communes, ou du moins, se trouver dans de mêmes régions de l'espace de recherche. Ainsi, l'idée de la recherche locale est d'atteindre les solutions optimales d'un problème en modifiant itérativement les bonnes solutions, trouvées par exemple par des méthodes gloutonnes.

Dans cette thèse, nous nous intéressons aux possibilités d'hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : systématicité et optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l'objectif de résoudre des problèmes NP-difficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Ce mémoire se situe dans la lignée des travaux de recherche menés précédemment au sein de l'équipe de Recherche Opérationnelle du Laboratoire Informatique d'Avignon sur l'hybridation entre recherche exacte et recherche heuristique (Demassey, 2003; Oliva, 2004; Palpant, 2005).

Ce mémoire est composé de trois parties, qui soulèvent les questions suivantes :

- Comment favoriser l'obtention rapide de solutions dans les méthodes de recherche arborescente sans perdre la complétude de la recherche?

- Comment utiliser des méthodes exactes au détriment de la propriété de complétude au sein des métaheuristiques?

- Comment obtenir de bonnes solutions à partir des méthodes exactes?

Dans la première partie de ce mémoire, nous nous intéressons aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, appelée Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l'ordre des valeurs sur lesquelles brancher. Nous mettons en particulier l'accent sur le caractère générique de la méthode, c'est-à-dire sa capacité à s'appliquer à tout type de problème, sans information extérieure sur la structure du problème. Le principe général de la méthode est de tenir compte par une technique d'apprentissage de l'impact qu'ont eu les décisions de branchement dans les parties déjà explorées de l'arbre. Le but est de favoriser l'obtention rapide de solutions dans les méthodes de recherche arborescente. Nos travaux s'appuient en partie sur les travaux de plusieurs autres chercheurs (Harvey et Ginsberg, 1995; Hooker, 2000; Fischetti et Lodi, 2003; Refalo, 2004). Nous évaluons l'efficacité de la méthode proposée sur plusieurs problèmes classiques comprenant des problèmes d'optimisation combinatoire et des problèmes de satisfaction de contraintes. Nous montrons que notre méthode propose des résultats en moyenne meilleurs que les méthodes par défaut d'un solver commercial.

Dans la deuxième partie de ce mémoire, nous proposons d'utiliser des méthodes exactes au sein de métaheuristiques. Pour cela, nous nous intéressons à une classe des problèmes de tournées de véhicules. Ces problèmes constituent l'une des classes les

plus étudiées de la recherche opérationnelle, en particulier puisqu'elle comprend le fameux Problème du Voyageur de Commerce. Le Problème du Voyageur de Commerce (Traveling Salesman Problem ou TSP) a été étudié dès le 19ème siècle par les mathématiciens Hamilton et Kirkman. En 1972, Karp (1972) a montré que le problème du voyageur de commerce, entre autres, est NP-complet. Nos recherches nous ont amenés à nous focaliser sur une sous catégorie de problèmes de tournées de véhicules que nous nommons Problèmes de Tournées avec Couverture Partielle, pour lesquels la visite de l'ensemble des sommets du graphe n'est pas obligatoire. Après une présentation d'opérateurs de voisinage classiques adaptés à cette famille de problèmes, nous présentons un nouvel opérateur de voisinage, Dropstar, qui détermine par un algorithme de programmation dynamique, la sous-séquence optimale d'un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d'être visités. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l'efficacité de l'opérateur que nous proposons sur deux problèmes, respectivement le Problème de l'Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur de grand voisinage basé sur une méthode exacte peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d'Optimisation par Colonies de Fourmis.

Dans la troisième partie du mémoire, nous nous intéressons aux méthodes de résolution exactes tronquées. Nous appliquons la méthode que nous proposons sur le problème de Tournées de Véhicules avec Contraintes de Chargement en Deux Dimensions (Vehicule Routing Problem with Two-Dimensional Loading Constrains ou 2L-VRP). Nous proposons de résoudre ce problème à l'aide d'une procédure de type Branch & Price, c'est-à-dire une procédure de résolution de type Branch & Bound utilisant une méthode de génération de colonnes pour le calcul de bornes. Nous présentons dans un premier temps un schéma classique de résolution par Branch & Price. De par la complexité des contraintes de chargement, le problème esclave de la génération de colonnes n'est pas résolu de manière exacte. Notre travail s'est donc porté sur les moyens dont nous disposions afin d'accélérer la résolution. Nous montrons ainsi dans ce chapitre une partie des possibilités qu'il existe afin de tronquer une méthode a priori exacte pour la rendre heuristique. Enfin, nous évaluons ces possibilités à l'aide de tests expérimentaux. Nous montrons que les méthodes que nous proposons, sans être de mauvaises qualités, ne dépassent pas les résultats des meilleurs algorithmes.

Pour chacune des parties, une validation expérimentale a été réalisée sur divers problèmes académiques ou applicatifs. Les résultats obtenus montrent l'intérêt des méthodes proposées et laissent entrevoir les nombreuses perspectives ouvertes par ce type d'hybridation.

Les travaux présentés sont issus de la collaboration entre le Laboratoire Informatique d'Avignon et la société Daumas Autheman et Associés ¹. Daumas Autheman et Associés est une société de service et d'ingénierie informatique créée en 1988, spécialisée dans l'informatique avancée, en particulier dans l'optimisation de ressources et

1. http :// www.daumas-autheman.com

gestion de l'expertise métier. Le problème d'Emploi du Temps de Garde d'Infirmières du chapitre 1, ainsi que le problèmes de Tournées de Véhicules avec Contraintes de Chargement du chapitre 5 sont des problèmes issus de la collaboration avec cette société. Les travaux de recherche ont été financés conjointement par Daumas Autheman et Associés et par le Conseil Régional de Provence-Alpes-Côte d'Azur.

Les travaux présentés dans ce mémoire ont fait l'objet des publications suivantes :

B. Bontoux et D. Feillet, 2006. Résolution heuristique du problème de l'acheteur itinérant. Dans les actes de 7ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2006). CDROM.

B. Bontoux, D. Feillet, et C. Artigues, 2007a. Une méthode dynamique de parcours
d'arbre de recherche : Dynamic Coperative Search. Dans les actes de 8ème congrès de la
société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2007), 99-100.

B. Bontoux, D. Feillet, et C. Artigues, 2007b. Large neighborhood search for variants of TSP. Dans les actes de The Seventh Metaheuristics International Conference (MIC 2007), Montréal, Canada. CDROM.

B. Bontoux, D. Feillet, C. Artigues, et E. Bourreau, 2007c. Dynamic cooperative search for constraint satisfaction and combinatorial optimization: application to a rostering problem. Dans P. Baptiste, G. Kendall, A. Munier-Kordon, et F. Sourd (Eds.), 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA 2007), Paris, France, 557-560.

B. Bontoux et D. Feillet, 2008. Ant colony optimization for the traveling purchaser problem. Computers & Operations Research 35, 628-637.

B. Bontoux, C. Artigues, et D. Feillet, 2008a. Algorithme mémétique avec un opérateur de croisement à voisinage large pour le problème du voyageur de commerce généralisé. Dans les actes de 9ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008), Clermont-Ferrand, 79-80.

B. Bontoux, C. Artigues, et D. Feillet, 2008b. A memetic algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem. Meta-heuristics for Logistics and Vehicle Routing, EU/ME, the European Chapter on Metaheuristics, Université de Technologie de Troyes, France.

B. Bontoux, C. Artigues, et D. Feillet, February 2008c. Memetic algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem. LAAS report, Université de Toulouse, LAAS-CNRS, Toulouse, France.