Techniques hybrides de recherche exacte et approchée : application à des problèmes de transport, Hybrid techniques of exact and approximate search : application in transport problems

De
Publié par

Sous la direction de Christian Artigues, Dominique Feillet
Thèse soutenue le 08 décembre 2008: Avignon
Nous nous intéressons dans cette thèse 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 : 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 NPdifficiles 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. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons 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. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général 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. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, 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. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large 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 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. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux
-Optimisation combinatoire
-Heuristique
-Recherche arborescente
-Metaheuristique
-Problème de transports
-Problème du voyageur de commerce
-Méthode de décomposition
We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization
-Combinatorial optimisation
-Heuristic
-Tree search
-Metaheuristic
-Transportation problems
-Traveling salesman problem
-Branch and price
Source: http://www.theses.fr/2008AVIG0166/document
Publié le : mardi 25 octobre 2011
Lecture(s) : 72
Nombre de pages : 191
Voir plus Voir moins

ACADÉMIED’AIX-MARSEILLE
UNIVERSITÉD’AVIGNONETDESPAYSDEVAUCLUSE
THÈSE
présentée à l’Université d’Avignon et des Pays de Vaucluse
pour obtenir le diplôme de DOCTORAT
SPÉCIALITÉ : Informatique
École Doctorale 166 « Information, Structures, Systèmes »
Laboratoire d’Informatique (EA 4128)
Techniques hybrides de recherche exacte et
approchée : application à des problèmes de transport
par
Boris BONTOUX
Soutenue publiquement le 08 décembre 2008 devant un jury composé de :
M. Marc SEVAUX Professeur, Université de Bretagne-Sud, Lorient Rapporteur
M. Emmanuel NERON Pr, de Tours, Tours
meM Françoise DAUMAS Ingénieur, D2A, Aix-en-Provence Examinatrice
M. Frederic SEMET Professeur, LAGIS, Ecole Centrale Lille Examinateur
M. Eric BOURREAU Maître de Conférences, LIRMM, Montpellier
M. Philippe MICHELON Professeur, LIA, Avignon
M. Christian ARTIGUES Chargé de Recherches, LAAS-CNRS, Toulouse Directeur de thèse
M. Dominique FEILLET Professeur, Ecole des Mines de Saint-Etienne, Gardanne Dir de thèse
Laboratoire d’Informatique d’Avignon École Doctorale 166
Laboratoire d'Informatique
« Information, Structures, Systèmes »
Université d'Av gnon
tel-00459367, version 1 - 23 Feb 2010À Angélique et Nathanael, mes amours
tel-00459367, version 1 - 23 Feb 2010Remerciements
Je tiens tout d’abord à remercier la Région Provence-Aples-Côte d’Azur, pour le
financement de cette thèse, ainsi que la société Daumas Autheman et Associés, qui
m’ont permis d’obtenir ce financement.
Ensuite, je souhaite remercier Renato De Mori et Marc El-Bèze qui en tant que direc-
teurs du Laboratoire m’ont accueilli au sein du Laboratoire Informatique d’Avignon,
ainsi que tous les membres du LIA avec qui j’ai passé de très bons moments et de très
bonnes soirées.
Je tiens aussi à remercier tous les membres passés et présents de l’équipe de Re-
cherche Opérationnelle que j’ai pu rencontrer : Audrey et sa petite merveille Lisa, An-
dréa et son accent si chantant et si dépaysant, Mireille et sa vie si trépidante, Diego,
Rodrigo, Philippe, Dominique Quadri et la dernière arrivée, Claire. . .
Je voudrais également saluer l’ensemble des membres du jury et en particulier, Em-
manuel Neron et Marc Sevaux, rapporteurs de cette thèse, pour avoir eu la patience de
lire ce mémoire.
Un grand merci à Christian Artigues, pour m’avoir attiré à l’IUP, puis m’avoir fait
découvrir la Recherche Opérationnelle. Sans lui, je n’aurais jamais eu l’envie de faire
un doctorat. Son encadrement m’a beaucoup apporté. . .
Un grand merci à Dominique Feillet, co-encadrant de cette thèse, qui m’a poussé
dans la recherche. Ses conseils ont été d’une valeur inestimable, il m’a permis d’avoir
le courage de finir ce doctorat. Je tiens en particulier à souligner la qualité de son enca-
drement, ainsi que ses qualités humaines.
Je remercie également Eric Bourreau pour son aide précieuse pour un sujet que je
maîtrisais peu, Philippe Refalo pour son aide pour l’utilisation d’Ilog, Thierry Garaix
« Titi » dont la thèse et les discussions m’ont beaucoup inspiré, Jérémie Osmont « Jey »
pour son aide miraculeuse en temps de crise (ce qui arriva très souvent) et Olivier Liess
« Kaoru » pour ses compétences inégalées en programmation.
Je remercie mes nombreux collègues de bureau de m’avoir si bien supporté et en
particulier Cédric « Krusty » pour ses petites attentions (merci encore pour ces crois-
sants le matin !) et sa mauvaise humeur si drôle.
Je remercie mes parents, Gilles et Bab, pour leur soutien, leurs encouragements et
3
tel-00459367, version 1 - 23 Feb 2010leurs relectures.
Enfin, je ne pouvais pas finir ces remerciements sans remercier ma femme, Angé-
lique, et mon fils, Nathanaël, mes amours de tous les jours. Vous m’avez été tous deux
d’une grande aide tout au long de cette thèse. Vous retrouver tous les soirs était mon
rayon de soleil et un des mes vrais bonheurs. Je suis désolé de vous avoir un peu dé-
laissés en fin de doctorat. Ce mémoire vous est donc dédié.
4
tel-00459367, version 1 - 23 Feb 2010Résumé
Nous nous intéressons dans cette thèse 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 : 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.
Dans la première partie, nous allons nous intéresser aux méthodes de résolution
par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion
des décisions de branchement, que nous appelons 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 nœud et l’ordre des valeurs sur lesquelles brancher. Ces règles
sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode
indépendamment du problème traité. Le principe général 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. Nous évaluons l’efficacité de la méthode proposée sur
deux problèmes classiques : un problème d’optimisation combinatoire et un problème
à satisfaction de contraintes.
La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous
présentons un nouvel opérateur de voisinage, 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 nœuds ne nécessitent pas d’être visités. Nous appelons
cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons
quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers
des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons
en appliquant cette recherche à voisinage large 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 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.
Enfin, la troisième partie présente des méthodes heuristiques basées sur un algo-
rithme de Génération de Colonnes. Ces sont appliquées sur un problème
5
tel-00459367, version 1 - 23 Feb 2010complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à
Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin
de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons
ces possibilités à l’aide de tests expérimentaux.
6
tel-00459367, version 1 - 23 Feb 2010Table des matières
Introduction Générale 10
I Favoriser l’obtention rapide de solutions dans les méthodes de recherche
arborescente 15
1 Dynamic Learning Search : une méthode par apprentissage 19
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 État de l’art des recherches arborescentes . . . . . . . . . . . . . . . . . . 20
1.2.1 Méthode de parcours de l’arbre de recherche . . . . . . . . . . . . 21
1.2.2 de structuration de l’arbre de recherche . . . . . . . . . 22
1.2.3 Parcours réduit de l’arbre . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.4 Ordre dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.5 Apprentissage : look-back . . . . . . . . . . . . . . . . . . . . . . . . 26
1.2.6 Métaheuristiques combinées à la recherche arborescente . . . . . 27
1.3 Dynamic Learning Search : une méthode par apprentissage . . . . . . . . 28
1.4 Learning : une méthode basée sur un apprentissage . . . . . . . . . . . . 29
1.4.1 Sondage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.2 Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.3 Prévision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.4.4 Remise en question . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.5 Dynamic : un ordre dynamique de choix des variables et de sélection des
valeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.6 Search : un schéma de recherche adapté à la méthode . . . . . . . . . . . 34
1.7 Algorithme général de la méthode . . . . . . . . . . . . . . . . . . . . . . 34
1.8 Méthode Dynamic Learning Search : critères de sélection . . . . . . . . . 34
1.8.1 Problèmes de Satisfaction des Contraintes . . . . . . . . . . . . . . 35
1.8.2 Pr d’Optimisation Combinatoire . . . . . . . . . . . . . . 38
1.8.3 Méthode commune aux deux types de problèmes . . . . . . . . . 39
1.9 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.9.1 Application au problème du Voyageur de Commerce . . . . . . . 40
1.9.2 au pr d’Emploi du Temps de Garde d’Infir-
mières . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.9.3 Application à des problèmes de Satisfaction de Contraintes aca-
démiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7
tel-00459367, version 1 - 23 Feb 20101.10 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
II Utiliser des méthodes exactes au sein des métaheuristiques : méthodes
de grands voisinages 49
2 La recherche à grand voisinage : un nouvel opérateur 53
2.1 Introduction à la recherche locale . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.1 Bases de la recherche locale . . . . . . . . . . . . . . . . . . . . . . 53
2.1.2 Principales classes de recherches locales . . . . . . . . . . . . . . . 54
2.1.3 Recherche locale à voisinage variable . . . . . . . . . . . . . . . . 55
2.1.4 Algorithmes utilisant de la recherche locale . . . . . . . . . . . . . 55
2.2 Recherche à grand voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2.1 Notations et définitions de la recherche à grand voisinage . . . . 58
2.3 Classe des problèmes considérés : Problèmes de Tournées avec Couver-
ture Partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.3.1 Problèmes de Tournées avec Gains . . . . . . . . . . . . . . . . . . 60
2.3.2 Autres variantes de Problèmes de Tournées à Couverture Partielle 61
2.3.3 Complexité des Problèmes de Tournées avece 62
2.3.4 Quelques opérateurs de recherche locale pour les Problèmes de
Tournées avec Couverture Partielle . . . . . . . . . . . . . . . . . 62
2.4 Dropstar : une nouvelle structure de grand voisinage . . . . . . . . . . . 64
2.4.1 Des opérateurs existants : drop, l-ConsecutiveDrop . . . . . . . . 64
2.4.2 L’opérateur de grand voisinage : Dropstar . . . . . . . . . . . . . 69
2.4.3 Plus court chemin avec contraintes de ressources (SPPRC) . . . . 71
2.4.4 Résolution par un algorithme de programmation dynamique . . 71
2.5 Perspectives : variantes possibles de la procédure Dropstar . . . . . . . . 74
3 Application au Problème de l’Acheteur Itinérant 77
3.1 Introduction au problème de l’Acheteur Itinérant . . . . . . . . . . . . . . 78
3.2 Notre algorithme : le DMD-ATA . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.1 Fourmis Parallèles . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.2 Anamorphiques . . . . . . . . . . . . . . . . . . . . . . . 82
3.2.3 Plans Multi-Dimensionnels . . . . . . . . . . . . . . . . . . . . . . 83
3.2.4 Dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.3 Opérateurs de recherche locale . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.1 Procédures de recherches locales basiques . . . . . . . . . . . . . 85
3.3.2 Application de l’opérateur Dropstar . . . . . . . . . . . . . . . . . 85
3.3.3 Intégration de la recherche locale dans l’algorithme DMD-ATA . 89
3.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4 Application au Problème du Voyageur de Commerce Généralisé 95
4.1 Introduction au Problème du Voyageur de Commerce . . . . 96
4.2 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 Algorithme mémétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
8
tel-00459367, version 1 - 23 Feb 20104.3.1 Composants basiques de l’algorithme . . . . . . . . . . . . . . . . 98
4.3.2 Croisement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.3 Implémentation détaillée de l’opérateur de croisement . . . . . . 103
4.3.4 Heuristiques de recherche locale . . . . . . . . . . . . . . . . . . . 106
4.4 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.5 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
III Tronquer les méthodes exactes : méthode de Branch & Price heuris-
tique 121
5 Application au problème de Tournées de Véhicules avec Contraintes de Char-
gement 125
5.1 Préambule : Intérêt du problème . . . . . . . . . . . . . . . . . . . . . . . 126
5.2 Problèmes de calcul de tournées de véhicules . . . . . . . . . . . . . . . . 127
5.2.1 Du problème du Voyageur de Commerce au problème de Tour-
nées de Véhicules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.2 Le 2L-VRP parmi les problèmes de Tournées de Véhicules . . . . 128
5.3 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.1 Résolution du 2L-VRP . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.2 Algorithmes de chargement . . . . . . . . . . . . . . . . . . . . . . 131
5.4 Modèle classique du problème du 2|RO|L-VRP . . . . . . . . . . . . . . 132
5.5 Génération de colonnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.5.1 Modélisation d’un ESPPRC . . . . . . . . . . . . . . . . . . . . . . 138
5.5.2 Résolution par programmation dynamique . . . . . . . . . . . . . 139
5.6 Notre approche : un schéma de Branch & Price . . . . . . . . . . . . . . . 141
5.6.1 Méthode de séparation . . . . . . . . . . . . . . . . . . . . . . . . . 142
5.6.2 Initialisation deW pour la génération de colonnes . . . . . . . . . 143
5.6.3 Remontées de colonnes . . . . . . . . . . . . . . . . . . . . . . . . 143
5.6.4 Problème esclave : ESPPRC . . . . . . . . . . . . . . . . . . . . . . 144
5.6.5 Pr de chargement séquentiel à deux dimensions . . . . . . 147
5.7 Deux approches différentes pour la réalisabilité du chargement . . . . . 153
5.7.1 Vérification de la réalisabilité a posteriori . . . . . . . . . . . . . . . 153
5.7.2 Construction de routes réalisables dans le sous-problème . . . . . 155
5.8 Branch & Price heuristique . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.8.1 Problème esclave heuristique . . . . . . . . . . . . . . . . . . . . . 159
5.8.2 Gestion des colonnes . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.8.3 Méthode de séparation . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.9 Résultats expérimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.9.1 Paramètres retenus . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.9.2 Classes d’instances . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.9.3 Analyses des résultats . . . . . . . . . . . . . . . . . . . . . . . . . 162
5.10 Conclusions et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Conclusion et perspectives 171
9
tel-00459367, version 1 - 23 Feb 2010Liste des illustrations 175
Liste des tableaux 177
Bibliographie 179
10
tel-00459367, version 1 - 23 Feb 2010

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi