Heuristiques basées sur la programmation mathématique pour des problèmes de localisation et de routage
Institution:
ValenciennesDisciplines:
Directors:
Abstract EN:
The aim of this PHD is the modelisation of two transportation problems of operationnal research. . These problems are routing problem and location problem. The first one studied is the location-routing problem with capacity constraints on facilities. Three methods are proposed to solve this problem. The two first are hybrid heuristics, mixing linear programs and a tabou search. The third method is based on a column generation method. These three contributions have been developped and tested to see their efficienty. We obtain good results, the best method giving most of the best results of the thirty instances. The second problem studied is a biobjectif travelling salesman problem on a particular graphe where some vertices have to be visited. A heuristic has been developed to solve this biobjective problem. To evaluate results obtained, an exacte method has been developed too.
Abstract FR:
Les travaux de cette thèse portent sur la définition et la résolution de deux problèmes de transport dans le domaine de la recherche opérationnelle. Ces deux problèmes entrent dans le cadre des problèmes de tournées de véhicules et des problèmes de localisation. Le premier problème abordé est le problème de localisation et routage avec contraintes de capacités aux dépôts. Trois méthodes de résolution sont proposées pour résoudre ce problème. Les deux premières sont des heuristiques hybrides, combinant programmes linéaires et une recherche tabou. La troisième méthode est également une méthode approchée, elle est basée sur une approche par génération de colonnes. Ces trois contributions ont ensuite été implémentées afin de tester leur efficacité. Les résultats obtenus sont de bonne qualité, la meilleure méthode implémentée améliorant la majorité des trente instances testées. Le second problème abordé est un problème de voyageur de commerce bi-objectif adapté à un graphe particulier où seuls certains des sommets sont à visiter obligatoirement. Une méthode approchée a été développée pour résoudre ce problème bi-objectif. Afin d’évaluer les qualités des solutions obtenues par cette méthode, une méthode exacte a également été développée.