L’algorithme de parcours en largeur

Le cas de la convergence simple

Dans cette section, nous étudions trois algorithmes de calcul des ACT (Chevrier et al., 2006a). Les deux premières méthodes sont exactes et la troisième utilise les métaheuristiques. Dans le détail, la première méthode est un algorithme d’énumération exhaustive des ACT sur un DAG aux arcs non pondérés. La deuxième méthode, développée consécutivement, est un algorithme de parcours en largeur calculant directement les solutions optimales sur un DAG pondéré. La troisième méthode est un algorithme génétique mono-objectif qui préfigure la méthode généralisée que nous étudions en deuxième section. 6.1.1 Un algorithme d’énumération exhaustive L’algorithme d’énumération exhaustive (AEE), réalisé en étroite collaboration avec P. Canalda, est une construction itérative des branches de l’ACT en démarrant des nœuds minimaux du DAG (Chevrier et al., 2006c). Un sommet est dit « minimal » lorsque celui-ci n’a pas de prédécesseurs (pas d’arcs incidents). Les nœuds minimaux sont nécessairement des feuilles des ACT à construire. A contrario le nœud terminal du DAG, qui n’a pas de successeurs (i.e. pas d’arcs sortants), constitue la racine de l’arbre (qui correspond en fait à l’antiracine vu l’orientation des arcs). D’une manière générale, la racine de l’arbre correspond au point de convergence de la desserte, tandis que les sommets minimaux sont des points de départ des véhicules. Ainsi la première étape de l’AEE consiste à identifier les nœuds minimaux du DAG qui sont les points de départ des ACT. Si nous appliquons l’AEE sur le DAG D(V, E) de la figure 6.1, les sommets minimaux sont les points 0 et 1. Ensuite pour chaque sommet v ∈ V ni minimal, ni terminal, on crée une nouvelle branche b avec le sommet v comme point de départ, que l’on ajoute à chaque ACT. Ces nouveaux ACT sont ajoutés à une liste intermédiaire à fusionner à la liste courante des ACT à la fin de chaque itération. Autrement, pour chaque ACT de la liste courante, nous cherchons si l’on peut fusionner l’arc incident comprenant le sommet v avec une des branches de l’ACT. De cette manière, nous étendons progressivement et incrémentalement l’ensemble des ACT, d’une part en créant de nouvelles branches et d’autre part en fusionnant éventuellement des arcs incidents aux branches des ACT partiels déjà constitués. L’algorithme ci-après décrit formellement la méthode que nous venons d’énoncer. Algorithme d’énumération exhaustive des ACT – v un sommet de V et Vmin ⊂ V l’ensemble des sommets minimaux du DAG ; – act un ACT ; – act′ un ACT temporaire ; – b une branche de l’ACT ; – Lact la liste des ACT à construire ; – L ′ act la liste intermédiaire des ACT ; – racine le nœud terminal du DAG ; – ajout : un booléen

Un algorithme de parcours en largeur

L’algorithme de parcours en largeur, proposé ici, cherche récursivement la solution optimale (Chevrier et al., 2006a). Contrairement au précédent algorithme qui énumérait exhaustivement les ACT du DAG proposé, nous nous contentons dans ce cas de mémoriser le meilleur ACT trouvé, compte tenu d’un ensemble de critères K = {ki} évalués dans une fonction de coût C. En détails, les éléments intervenant dans l’algorithme explicités ci-après sont les suivants : – G(V, E) : le DAG à parcourir avec V = {vi} l’ensemble des sommets v, E l’ensemble des arcs et Vmin ⊂ V l’ensemble des sommets minimaux ; – K = {ki} : l’ensemble des critères k intervenant dans l’évaluation d’un ACT ; – α : l’ACT en cours à évaluer. αi indique le numéro du véhicule desservant le sommet de rang i ; – A : le meilleur ACT trouvé, initialisé avec ∀i < |V| − 1, Ai ← i (i.e. un véhicule par demande), par défaut le meilleur ACT attribue un véhicule par demande ; – A : l’ensemble des meilleurs ACT s’il y en a plusieurs égaux ; – Λ = {λi} : l’ensemble des véhicules disponibles ; – C : α × K → c : la fonction évaluant le coût c d’une solution α compte tenu de l’ensemble des critères K ; – g : α → {0|1} : une fonction vérifiant que la solution α est cohérente (valeur 1, sinon 0). L’algorithme f(α, i) ci-après consiste à attribuer le minimum de véhicules à l’ensemble des requêtes correspondant aux différents points du graphe (V). La contrainte dans cette attribution consiste à vérifier la validité des chemins empruntés par les véhicules à l’aide de la fonction g. Le coût d’une solution, à minimiser, est donné par la fonction C. Cet algorithme est mono-objectif.