Problèmes de tournées de véhicules avec contraintes particulières pour la maîtrise des risques
Résumé:
Cette thèse porte sur la résolution de deux problèmes de transport qui intègrent des contraintes ou des objectifs de maîtrise des risques :
le problème de tournées de véhicules m-péripatétiques (m-PTVP) et le problème de tournées de véhicules cumulatives avec contraintes de capacité
(PTVCC). Les applications ciblées sont du domaine de la logistique sécurisée, tel le transport de fonds, et de la logistique humanitaire,
tel le transport de 1ers secours.
Le m-PTVP a fait l’objet de la majeure partie de nos travaux. Il consiste à définir des tournées de véhicules de coût total minimal et sans arêtes
communes sur m périodes telles que chaque client soit visité exactement une fois par période. Nous proposons différents modèles mathématiques,
des bornes inférieures polynomiales, deux métaheuristiques dont un algorithme de recherche taboue diversifiée et guidée avec la solution d’un
b-couplage parfait, une approche de type génération de colonnes qui combine des heuristiques duales avec la génération de q-tournées, et enfin
deux algorithmes de branchements et coupes.
Le PTVCC identifie les tournées de véhicules qui minimisent la somme des dates d’arrivées chez les clients tout en respectant les contraintes de
capacité des véhicules. Nous proposons un algorithme mémétique (MA) dont l’efficacité repose sur le découpage optimal de chromosomes en solutions
et l’utilisation de pré-calculs déduits des propriétés du PTVCC que nous avons identifiées, lesquelles produisent également des formules de calcul
de bornes inférieures. Notre MA est à ce jour la meilleure métaheuristique publiée pour le cas particulier du problème du réparateur itinérant
(= PTVCC mono-véhicule = TRP).
Mots clés:
Recherche opérationnelle, Optimisation combinatoire, Logistique, Transport, Tournées de véhicules, Sécurité, Humanitaire,
Métaheuristiques, Génération de colonnes, Branchements et coupes. Thèse de doctorat soutenue:
le 27 Octobre 2009 au sein du LOSI (Laboratoire d'Optimisation des Systèmes Industriels) de l'UTT (Université de Technologie de Troyes).
