| Les problèmes de tournées de véhicules en planification industrielle : classification et comparaison d’opérateurs évolutionnaires (Vehicle routing problem in industrial planning : classification and comparison of evolutionary operators) | ||
HAJ RACHID, Mais - (2010-08-30) / Université de Franche-Comté - Les problèmes de tournées de véhicules en planification industrielle : classification et comparaison d’opérateurs évolutionnaires en : Français Directeur(s) de thèse: SPIES, François Laboratoire : LIFC - Laboratoire d'informatique de l'UFC Ecole doctorale : SPIM Classification : Informatique | ||
Mots-clés : Classification, Algorithmes, Gestion d’entreprise, Problème de tournée de véhicules Résumé : Le problème de tournées de véhicules est l un des problèmes d optimisation combinatoire les plus étudiés car il a de multiples applications en planification industrielle. La littérature associée est très riche, en variantes de problèmes et en approches de résolution. Face à un problème réel, il est difficile d identifier la classe de problème à laquelle il appartient, de recenser les travaux correspondants, et de déterminer le type de méthode de résolution le plus approprié. Cette thèse étudie la faisabilité d un projet destinée à faciliter ces démarches, en s intéressant plus particulièrement aux approches de résolution évolutionnaires. Il repose sur trois éléments : une notation des variantes de VRP, un recensement d opérateurs évolutionnaires de la littérature, et la construction d une base de règles liant les variantes de problèmes à l efficacité des opérateurs évolutionnaires. L objectif est de guider la conception d un algorithme en fonction des caractéristiques du problème, en proposant les opérateurs qui ont la plus grande probabilité d être efficaces. Appliquer la notation proposée à plusieurs articles montre qu elle permet à chacun de classifier les travaux de manière précise, et d identifier ainsi plus facilement les approches et résultats comparables aux siens. La méthode expérimentale proposée est illustrée en considérant 3 types de croisement et 3 types de mutation. Cette étude montre qu il est possible d estimer quels éléments de l algorithme ont un impact détectable sur les performances, et d établir des relations entre les choix de conception de l algorithme ou entre l instance de problème et l efficacité des opérateurs. Résumé (anglais) : Solving vehicle routing problems have been some of the most studied problems in combinatorial optimization because they have many applications in the field of industrial planning. The related literature is diversified both in terms of variants of the problems and in terms of solving approaches. Identifying which class of problems a given real-world problem belongs to, in order to gather related works and determine the most relevant resolution method, is a difficult task. The present thesis constitutes a feasibility study of a project to make these tasks easier, privileging evolutionary solving approaches. This project relies on three essential bases: a notation of the variants of VRP, a compilation of evolutionary operators from the literature, a set of rules linking VRP variants to evolutionary operators according to the efficiency. The objective is to find guidelines to design a solving algorithm according to the characteristics of the problem by identifying the subset of operators showing the greater estimated efficiency. Putting the proposed notation into practice using several papers demonstrated that anyone using this notation can classify accurately papers and can recognize easily approaches and results that are similar to their own. The experimental methodology proposed is illustrated by considering three types of crossover and three types of mutation. This study confirms that is possible to determine which elements of an algorithm have a discernable impact on the performance. It reveals relationships between choices in the design of the algorithm or between the variant of problem and the efficiency of the operators. Identifiant : UFC-885 | ||
| Exporter au format XML |