Thursday 27
Graphs, flows, combinatorial algorithms and approximation
Mariem Mekki
› 14:00 - 14:20 (20min)
› Bât B - TD 43
Une méthode exacte pour le problème de multiple-tournées cumulatifs avec un véhicule
Juan Carlos Rivera  1, *@  , H. Murat Afsar  1@  , Christian Prins  1@  
1 : Institut Charles Delaunay, Laboratoire d'Optimisation des Systèmes Industriels  (ICD-LOSI, UTT)  -  Website
Université de Technologie de Troyes
12, rue Marie Curie, CS 42060, 10004, Troyes CEDEX -  France
* : Corresponding author

Dans ce travail nous étudions le problème de tournées de véhicules cumulatif avec capacités et routes multiples où les tournées sont réalisées avec un seul véhicule. Ce dernier doit visiter tous les sommets une et une seule fois et minimiser la somme des temps d'arrivée. Nous rencontrons ce problème lors des opérations logistique en cas de catastrophe où cette fonction objectif reflète mieux l'urgence de la situation.

Une méthode exacte basée sur un algorithme de plus court chemin élémentaire avec des contraintes de ressources est proposée afin de résoudre ce problème. Le problème est formulé comme un modèle de plus court chemin où chaque route se transforme en un super-nœud, les sites à visiter deviennent des ressources. Ce réseau est orienté et acyclique grâce à des propriétés du problème de base. La méthode de résolution décompose le problème en deux phases. Dans la première phase le problème de plus court chemin est résolu sur un sous-ensemble de super-nœuds. Dans la deuxième phase l'arbre généré pendant la première phase est intégré pour résoudre le problème complet et le résultat de la première phase devient une borne supérieure pour la deuxième. Plusieurs règles de dominance, bornes supérieures et bornes inférieures sont ajoutés afin d'accélérer la procédure de recherche. Les résultats numériques sont présentés sur des instances issues de la littérature pour le CVRP classique et comparés avec un modèle linéaire en nombres entiers mixtes.


Online user: 1