Séminaire Sandra Ulrich Ngeuveu

Jeudi 22 Avril 2010 (14h00)

Sandra Ulrich Ngeuveu, Laboratoire d'Optimisation des Systèmes Industriels, Université de Technologie de Troyes.

Titre : Résolution de problèmes de transport avec maîtrise des risques - Optimisation de tournées.

Résumé : L'exposé portera 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 premiers secours.

Le m-PTVP fera l'objet de la majeure partie de la présentation. 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é une fois par période. Nous présenterons un algorithme de recherche taboue guidée par 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 de coupes. Un tiers des instances ont ainsi été résolues optimalement, pour le reste l'écart entre les meilleures bornes inférieures et supérieures varie de 1 à 3%. 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 présenterons 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. Cet MA est à ce jour la meilleure métaheuristique publiée pour le cas mono-véhicule et la seule pour le cas multi-véhicule.