Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

Math-heuristique pour le problème de tournées de véhicules sélectives avec fenêtres de temps et visites synchronisées.

Le 16 février 2021 à 14h00 Salle des séminaires du LGI2A, FSA, Béthune
Ala-Eddine YAHIAOUI Post-doctorant LGI2A

Nous étudions dans cet article une variante récente des problèmes de tournées de véhicules sélectives. Cette variante, qui prend en compte les contraintes de fenêtres de temps et les visites synchronisées, est proposée initialement pour modéliser et résoudre des problèmes opérationnels liés à la lutte contre les feux de forêts. Dans ce problème, on considère un scénario où un ensemble de sites stratégiques (infrastructures, écoles, usines...) localisés dans une région menacée par l’avancée des feux de forêts. Chaque site est caractérisé par une fenêtre temporelle qui estime le moment optimal d’intervention afin d’assurer sa protection. Chaque site nécessite également pour sa protection l’intervention simultanée de plusieurs types de véhicules ayant des compétences différentes (hétérogènes). Les pompiers disposent d’une flotte de véhicules hétérogènes où chaque type est caractérisé par un vecteur de compétences, une vitesse, un réseau de circulation et un nombre d’unités limité. À cause des contraintes temporelles et le nombre de véhicules limités, protéger tous les sites est a priori impossible. Des valeurs positives, qu’on appelle profits, sont alors associées aux différents sites pour pouvoir les discriminer selon leurs importances. Le profit de chaque site est ainsi obtenu une fois les opérations de protection se sont accomplies. L’objectif dans ce problème est de sélectionner un sous-ensemble de sites à protéger afin de maximiser le profit collecté tout en respectant les contraintes temporelles et de ressources.
Nous proposons une méthode heuristique hybride qui combine des méthodes de recherche locale et une formulation mathématique qui résout un problème de couverture par ensembles. Les résultats préliminaires obtenus sur les instances de la littérature montrent l’efficacité de notre méthode par rapport à celle de la littérature et cela en termes de qualité de solutions ainsi que le temps de calcul.

Compte tenu des circonstances sanitaires, le séminaire aura lieu en ligne