Détection de fourche et boucle dans l'algo des écartements

Bonsoir.

Je reviens sur le forum suite à ce sujet là: https://forum.excel-pratique.com/post156191.html#p156191

Je repose le problème qui est assez complexe.

Le but est le suivant: on doit générer aléatoirement un tableau des distances entre un entrepôt et 50 villes, et ensuite

en appliquant la méthode des écartements, on doit définir une tournée de camion.

Pour ceux qui ne la connaissent pas, voici un rappel:

1) Il faut calculer les écartements de tous les couples de points (les clients) par rapport à l'entrepôt central (nous) => C'est fait

2) Classer ces couples par importance décroissante => C'est fait

3) Sélectionner chaque couple de la liste, abandonner ceux qui forment une boucle ou une fourche avec ceux précédemment sélectionnés => je cherche mais j'ai pas trouvé

4)Arrêter la procédure lorsque n-1 couples ont été retenus ou plus tôt si une contrainte (de capacité,...) est violée. => Pas fait

5) Joindre le dépôt aux deux extrémités. => Pas fait

6) Il faut aussi prendre en compte le tonnage à livrer à chaque clients (à faire par la suite).

Concrètement ce que j'ai fait:

- dans la feuille "Ecartements", j'ai généré 50 villes avec les distances ainsi qu'une matrice de distance entre les 50 villes (matrice 50*50)

Cette opération est réalisée dans le module Tableau_Ecartement.

- dans la feuille "Feuil3", je calcule les écartements de tous les couples de points (1225 écartements), je les classe dans l'ordre décroissante.

Cette opération est réalisée dans le module Essai_grand, procédure main et Function Ecartement.

Pour ces deux étapes, je n'ai plus besoin d'aide. Par contre, je bute sur comment détecter une fourche ou une boucle.

Ce que je souhaite faire c'est à partir de ma procédure principale, envoyer la liste des sommets avec écartements triés à des fonctions qui vérifie simultanément

si il y a une fourche ou une boucle et qui arrête le parcours et commence un nouveau dans ce cas.

Pour l'instant, j'ai commencé à creuser une piste pour la fourche (en la mettant dans une procédure pas encore fonction), j'ai un résultat mais je suis pas convaincu de sa validité.

L'idée c'est de créer une variable tableau (ici tabloFourche) qui contient les sommets et le nombre de fois où ils sont visités (= degré du sommet).

La procédure Sub Fourche parcourt donc la liste des écartements de "Feuil3" et ajoute 1 dans tabloFourche, à chaque fois qu'un sommet est visité.

Si le degré du sommet dépasse 2, alors on a une fourche, on sort de ce parcours et on en crée un nouveau. Sinon, on continue ce parcours, tant que les sommets visités ne dépassent pas le degré 2.

Les parcours sont indiqués dans la feuille Fourche.

Quel est l'erreur de raisonnement dans ma procédure fourche ?

Comment faire la détection de boucle ?

Merci pour vos réponses et vos aides.

Si vous avez la moindre question, n'hésitez pas!!!

Personne a une idée ?

Voulez-vous que je vous explique plus en détail ??

Bonsoir

Fortes chances que je dise desc........ies absurdités

Il faut trouver tous les chemins possibles en passant par toutes les villes

Pour 50 villes il y a

608 281 864 034 268 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
 possibilités

Il n'y a que les premiers chiffres de significatifs

J'ai fait des essais pour

5 villes : 24 Possibilités

6 villes : 120

7 villes : 720

8 villes : 5040

9 villes : 40320

après suis hors capacités (pas assez de ligne)

Mais chaque valeur correspond à la fonction

=PERMUTATION(Nombre_de_ville - 1;Nombre_de_ville - 1)

Salut Banzai64 et merci de m'avoir répondu.

Le but n'est pas de trouver tous les chemins possibles en passant par tous les villes.

On a un entrepôt et à partir de celui ci on doit livrer 50 villes. Avec une méthode spéciale, la méthode des écartements, on doit définir les tournées d'un camion qui doit livrer tous les villes. Ceci implique que le camion effectue plusieurs tournées pour livrer toutes les villes.

Par exemple, le camion peut faire; Ville 23 Ville 2 suivi de Ville 34 Ville 2 etc...

J'ai généré aléatoirement les distances entre l'entrepôt et chaque ville.

1) Le première étape de la méthode c'est de calculer tous les écartements entre les 50 villes, ce qui nous donne 25x25 ou 1225 arêtes (ou couple de villes (les sommets)). Pour 1225 arêtes, on a 1225 écartements.

Ex: Soit e(1,2) l'écartement entre le client 1 et le client 2 on le calcule comme:

e(1,2)=d(0,1)+d(0,2)-d(1,2) où d(0,1) et d(0,2) représentent la distance de l'entrepôt vers le client 1 et de l'entrepôt vers le client 2.

2) La deuxième étape c'est de classer les couples d'arêtes (sommets) par écartements décroissants. J'ai une macro qui fait ça et mets dans les deux première colonnes les sommets, et en troisième les écartements dans la feuille, "Feuil3".

Les deux première étapes sont bonnes, je bute après.

La base de travail est la feuille "Feuil3" désormais.

3) En parcourant un par un les 1225 arêtes de cette feuille, si à chaque fois qu'on inclut une arête dans le parcours en cours, on tombe sur une boucle ou une fourche, alors on inclut pas les sommets de cet arête dans le parcours en cours, et on les mets dans un nouveau parcours.

4) On devrait avoir un tableau de parcours du style:

Ville 23

VIle 2

Ville 31

Ville 45

En reliant les bouts à l'entrepoôt on aura:

entrepoôt

Ville 23

VIle 2

entrepoôt

entrepoôt

Ville 31

Ville 45

entrepoôt

Si tu veux autre exemple plus précis demande le moi.

Bonsoir

Pour moi c'est trop complexe

La tournée ne sera déterminée qu'en fonction du tonnage transportée et du nombre de véhicule

si 50 véhicules --> 1 véhicule par ville

Si 10 Véhicules ---> 1 véhicule pour 10 villes/ ou pour x tonnes

Solution envisageable (sans garantie)

Prendre 7 villes au hasard et chercher la route la plus courte

ensuite prendre 7 autres villes etc.....

Salut Banzai64.

Le problème à traiter est décrit dans le dernier poly de lecture que tu m'as envoyé.

Il s'agit d'appliquer l'heuristique de Clarke et Wright.

Je t'ai trouvé un exemple ou la méthode est bien expliquée. (regarde le word ci-joint)

Moi j'ai du mal à la transcrire en VBA, à partir du moment où il faut détecter une boucle ou une fourche.

Bonsoir

Si tu repasses encore par un point tu as soit une boucle ou une fourche, dans les deux cas tu abandonnes ce trajet, alors quelle importance de savoir si c'est l'un ou l'autre

Un essai de ce que j'ai compris

Merci pour ta réponse Banzai64.

J'ai parcouru ton code, mais je t'avouerais que j'ai pas vraiment sais ta démarche dans le module RechercheBis.

Par contre je pense que je viens de trouver les 2/3 de la solutions.

En effet, je crois tenir une méthode qui marche pour détecter les fourches et les boucles.

A) On part de la feuille "Feuil3" où les écartements sont triés.

B) Dans le code, on crée une variable tableau "tablofourche" de 50 lignes et 2 colonnes. La 1ère colonne contient le numéro de la ville et la 2ème colonne le nombre de fois où la ville a été parcourue.

C) Conceptuellement, si une ville est parcourue 3 fois alors ça devient une fourche, ce qui n'est pas souhaitable. Donc si on a une ville parcourue deux fois on doit pas repasser pour éviter une fourche. Donc on saute l'arête (les deux villes associés) qui contient cette ville.

Si dans l'arête qu'on est en train de parcourir, les deux villes ont au moins été parcourue une fois, alors on ne peut pas prendre l'arête en cours sous peine de créer une boucle.

C'est ce que j'ai fait dans le code suivant: (regarde le xlsm joint)

 'si le degré d'un des 2 sommets est au moins égal à 2 (ou strictement supérieur 1), en rajoutant un arc, on va créer une fourche
    'le test mettra le booléen à vrai pour indiquer la fourche à ne pas en prendre en compte

            If (tablofourche(inter, 2) > 1 Or tablofourche(inter2, 2) > 1) Then
                fourchebis = True
            End If

              'détection de boucle
    'si le degré est positif pour chacun des sommets, cela veut dire qu'on a déjà visité une fois les deux sommets de l'arête,
    'on ne doit pas le parcourir sinon c'est une boucle, car on passerait deux fois par les sommets

            If (tablofourche(inter, 2) > 0 And tablofourche(inter2, 2) > 0) Then
                bouclebis = True
            End If

J'ai été courageux puisque j'ai vérifié à la main et c'est bon!!!

J'ai un résultat brut avec tous les arêtes qui ne forment pas de fourche ni de boucle, dans la feuille "Fourche".

En dessous, j'ai mis pour les 50 sommets, le degré (le nombre de fois qu'ils ont été parcourus).

Je constate, qu'il y a 6 villes qui ont un degré 1.

Ce qu'il faut faire, c'est relier les villes au dépôt. Pour cela, il faut relier les villes de degré 1 au dépôt en intégrant les circuits qui passent par ces villes de degré 1.

Si on reprend l'exemple précédent du word, on doit passer de l'étape 4 à l'étape 5.

Là j'ai besoin d'aide, maintenant que j'arrive à détecter les boucles et les fourches.

Merci.

Bonsoir

Voila je ce je trouve avec les données du fichier Word (j'ai remplacé 1 par A, 2 par B etc...)

A D C B

D A C B

C D A B

D C B A

B C D A

C B D A

A C D B

C A D B

Il manque juste les deux extrémités (trajet Entrepôt -> 1ère ville et trajet dernière ville --> Entrepôt)

La 1ére solution trouvée ressemble fortement à la solution dans le fichier Word

A toi de me dire où je me suis planté

J'ai continué un peu et voici les résultats

XX = Entrepôt

En début de ligne la longueur du trajet

• 58 XX A D C B XX
• 67 XX D A C B XX
• 68 XX C D A B XX
• 72 XX D C B A XX
• 58 XX B C D A XX
• 68 XX C B D A XX
• 79 XX A C D B XX
• 76 XX C A D B XX

Peut-être que je ne trouve pas tous les chemins ?

A voir

Salut Banzai64, c'est pas tout à fait mon but mais l'esprit est là.

Ma dernière difficulté c'est de relier les différents entrepôts.

Dans le fichier joint, feuille "Fourche", j'ai la liste de tous les arêtes à prendre en compte.

En dessous, j'ai mis pour les 50 sommets, le degré (le nombre de fois qu'ils ont été parcourus).

Je constate, qu'il y a 6 villes qui ont un degré 1. C'est à dire qu'il y a 6 villes d'où partent seulement une arête.

Ce qu'il faut faire c'est relier le dépôt central à ces 6 villes en évitant les boucles.

(Relis mon dernier message pour plus de précision.)

Bonsoir

Désolé mais pour le moment ma contribution à ce projet va s'arrêter

Je ne comprend pas pourquoi la solution que je propose ne convient pas (je dois rater quelque chose)

Je trouve la même réponse que dans le fichier Word et tu dis que ce n'est pas encore ça, moi je veux bien

Je suivrais ce post et si un déclic revient (bien sur ... c'est ça) je m'empresserais de le communiquer

Bonne continuation

J'ai essayé de t'envoyer un MP mais apparemment tu as désactivé ta boîte MP.

Je t'ai envoyé un mail.

@+

Bonsoir

Suivant mon idée un fichier final

Une MEFC indique la(les) tournée(s) la(les) plus courte(s) ou la (les) moins longue(s)

Entrepôt = 0

Merci Banzai64 pour ta participation et tes réponses.

Je considère que la solution est satisfaisante et je propose de clore le sujet.

Comme je n'ai pas eu le temps de relire le code en détail, je reviendrais peut-être vers toi.

Cordialement,

flyEmirates