Un algorithme tabou pour résoudre, grâce aux groupes d'opérations permutables, un problème d'ordonnancement et de routing robuste

Azeddine Cheref (1, 2) , Teddy Bouchard (1) , Jean-Charles Billaut (1) , Christian Artigues (2)

1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
2 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes

Nous abordons dans cet article un problème conjoint d'ordonnancement et de routing de véhicule, pour minimiser le plus grand retard algébrique. Une incertitude porte les données (incertitude prise en compte par des scénarios) et une solution robuste est recherchée. L'approche proposée consiste a utiliser le concept de groupes d'opérations permutables pour converger selon le scénario vers la solution la plus intéressante (ici la regle FIFO est utilisée pour donner priorité a l'opération disponible le plus tôt). Deux algorithmes Tabou sont proposés, l'un sans groupe et l'autre avec des groupes. Les expérimentations numériques montrent l'interêt de l'approche par les groupes, qui s'avère la plus robuste.

Mots clés: méthode tabou; routing; robustesse; Ordonnancement

Domaines: Recherche opérationnelle [math.OC]

Azeddine Cheref, Teddy Bouchard, Jean-Charles Billaut, Christian Artigues. Un algorithme tabou pour résoudre, grâce aux groupes d'opérations permutables, un problème d'ordonnancement et de routing robuste. Conférence Internationale de MOdélisation, Optimisation et SIMulation - MOSIM'14, Nov 2014, Nancy, France. ⟨hal-01107890⟩