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.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Graphs, flows, combinatorial algorithms and approximation |
| Keywords | : | Algorithme exact ; problème de multiple ; tournées cumulatifs avec un véhicule ; algorithme de plus court chemin élémentaire avec des contraintes de ressources ; logistique en cas de catastrophe |
| PDF version | : |  PDF version |
