Problèmes de tournées avec gains : étude et application au transport inter-usines

Dans cette these, nous nous interessons a une classe de problemes particuliers issus des problemes de tournees de vehicules, pour lesquels un gain est disponible chez les clients et l'objectif est d'optimiser simultanement la collecte des gains et les couts de parcours des vehicules. En raison d'un manque d'homogeneite rencontre dans la litterature, nous nommons cette classe de problemes « problemes de tournees avec gains » et nous en proposons une classification, avant de faire une synthese detaillee des approches de resolution qui leur sont consacrees. Nous abordons ensuite un probleme de transport inter-usines, rencontre dans le secteur de l'industrie automobile, ou la production se deroule sur plusieurs sites distants les uns des autres. L'objectif est de proposer un plan de transport tactique optimise en tenant compte des plans de production et des formules de transport disponibles. Nous proposons une modelisation originale qui nous conduit a chercher une famille optimale de circuits de longueur limitee dans un graphe sous contraintes de capacites, et qui situe ce modele dans la lignee des problemes de tournees avec gains. Nous proposons un algorithme de resolution exacte du type Branch and Price pour la resolution de ce modele. Des experimentations evaluent l'efficacite de l'algorithme sur des instances generees aleatoirement et sur des instances reelles, proposees par un partenaire industriel, qu'il permet de resoudre en quelques secondes. Des adaptations permettent de resoudre un probleme plus complexe, concernant l'optimisation simultanee du plan de transport et des itineraires de containers vides.