Algorithme d'insertion à coût minimum

[invite8b421ec7]

Bonjour,

Je suis novice en algorithme. Je sollicite votre aide.
Je souhaiterais implémenter en C l’algorithme d’insertion à moindre coût pour le problème de tournées de véhicules avec collecte et livraison et fenêtre de temps ou de RDV c’est les horaires préférées de visite des nœuds).
Dans ce problème, on connait la fenêtre de rendez-vous sur chaque nœud, le temps de service sur chaque nœud, la demande de collecte pour sur les nœuds de collecte (valeur positive), la demande de ramassage sur les nœuds de livraison (valeur négative), le temps de parcours entre nœud i et nœud j et la capacité des camions.
Les contraintes sont : le respect de fenêtre de RDV (c'est à dire que le temps de début de service sur le noeud j doit etre supérieur ou égale au temps de début de service sur le noeud i plus le temps de trajet entre le neoud i et j plus le temps de service sur le noeud i) et la charge entre les nœuds est positive.
Il s’agit de déterminer l’ensemble de routes qui minimisent le cout total de transport pour ramasser le produit des différents fournisseurs et les livrer aux différents clients ainsi que le temps de début de service sur chaque nœud et la charge de camion entre les nœuds.

Bon, voici l’algorithme d’insertion à coût minimum pour le problème de voyageur de commerce

1. A partir du dépôt, trouver le nœud a le plus loin. Créer l’arc 0-a.
2. 2. Calculer les coûts supplémentaires d’ajout de chacun des nœuds non visités de façon individuel. Ces valeurs se calculent comme suit
3. Coût d’insérer le nœud i sur l’arc a1-a2 = ca1i+ca2i-ca1a2
Cij : représente le cout pour circuler du nœud i au nœud j
4. Insérer el nœud le moins couteux à intégrer à la tournée actuelle
5. Répéter les étapes 2 et 3 jusqu’à ce que tous les nœuds soient visités.

Je ne sais pas comment adapter cet algorithme à mon problème. Il faut que la tournée calculée respecte les contraintes de capacité du camion, la fenêtre de RDV ainsi que la charge du camion qui doit être positive.
Voici mon essai. Est ce correcte?

While (la liste de client est non vide) do

la charge du camion = 0 
temps de service sur ce noeud = 0
coût total = 0
1. A partir du dépot, trouver le noeud i le plus éloigné. Créer l'arc 0-i. 
2. Calculer les coûts supplémentaires d'ajout de chacun des noeuds. 
3. Choisir le noeud le moins coûteux. 
4. Calculer la charge du camion = demande de ce noeud+demande du noeud précédent. 
5. Calculer le temps de service sur ce noeud= temps de trajet entre ce noeud et le noeud précédent+temps de trajet+temps de service sur le noeud précédent. 
6. Si la capacité du camion est respectée et la charge du camion est poisitive alors 
        Insérer le noeud non visité le moins coûteux à la tournée
        Déterminer la position de ce noeud
        Mise à jour de la charge du camion
        Mise à jour du temps de service
   Sinon 
   Choisir un autre noeud non visité et répéter les étapes 2, 3, 4, 5, 6

Des idées??

D’autre part, l’emploi de la liste doublement chainée est-il judicieux ?

Merci par avance de vos aides.
Cordialement
-----

[boulbidor]

trop d'info d'un seul coup ! vas-y doucement pour qu'on puisse comprendre ton ...

[Dormeur74]

Il y a deux trucs qui me chagrinent dans le listing des contraintes :
Tu dis qu'on connaît la fenêtre de rendez-vous sur chaque nœud, comme si on avait déjà trouvé le chemin le plus court. Dans ce cas, la recherche opérationnelle ne peut rien pour toi, il suffit d'être à l'heure aux heures de rendez-vous, en admettant que la chose soit possible.

Tu parles du voyageur de commerce, donc probablement du modèle de Little. Je ne crois pas qu'il existe un algorithme fiable à 100% ; de plus il y a dans ce modèle la contrainte de passer sur chacun des noeuds une seule fois. Donc qui n'est pas adapté à un simple circuit en "8" lorsque le noeud de départ n'est pas au centre.

[Xoxopixo]

Bonjour,

J'avais vu ce post un peu plus tôt, et j'y revient, ayant réflechi un peu au probleme, qui m'interresse énormement, ayant moi-même travaillé dans le transport.
Voyant également que c'est la solution de l'insertion à moindre coût qui a été privilégié je tenais quand même à proposer une autre solution.

Une solution simple consiste à simuler entierement le terrain.
Donc créer des automates qui se deplacent en allant charger et decharger des marchandises depuis les lieux indiqués, position, et heure d'ouverture.
Comme des scarabés.
Revenus au depot, ils reçoivent une note d'évaluation, indiquent les trajets effectués. Et une note globale est attribuée à l'ensemble.
On laisse les choses se faire plus ou moins au hasard, on selectionne les groupes les mieux notés.
De toutes facons, on va pas faire zigzager les camions d'un coté à l'autre, autant simuler le trajet en temps reel pour les coordonner pendant les operations de chargement. Les depots servis etant connus au fur et a mesure. Donc autant simuler l'avancement du processus plutot que de chercher ne solution globale d'un seul coup.

L'intention finale etant d'optimiser l'utilisation des camions.

Ca doit être jouable, non ?
Si quelqu'un a un peu d'experience dans ce domaine, un petit feed-back ?

[A voir en vidéo sur Futura]

[Dormeur74]

J'ai eu des problèmes de logistique à tenter de régler il y a une vingtaine d'années (déplacement sur 800 km des 500 véhicules d'une division légère blindée à optimiser), mais un truc assez simple à mettre en place, qui n'a rien à voir avec ce terrible problème du voyageur de commerce. Nos contraintes étaient assez simples (poids, hauteur et largeur maximum des véhicules par rapport aux oeuvres d'art du terrain, aux gabarits et taux de saturation des itinéraires, aux contraintes imposées par les cartes du Génie, aux points de ravitaillement en carburant, etc.).

Tout s'est relativement bien passé, mais nous avons dû faire de la conduite du premier jour au dernier, ce qui est à l'opposé du modèle entièrement planifié. En gros, chaque soir nous devions préparer la journée du lendemain en fonction des écarts entre prévisions et réalité. J'ai bien peur qu'on ne soit dans le même scénario, pour ne pas dire dans un scénario encore plus complexe.

[Xoxopixo]

Tout s'est relativement bien passé, mais nous avons dû faire de la conduite du premier jour au dernier, ce qui est à l'opposé du modèle entièrement planifié. En gros, chaque soir nous devions préparer la journée du lendemain en fonction des écarts entre prévisions et réalité. J'ai bien peur qu'on ne soit dans le même scénario, pour ne pas dire dans un scénario encore plus complexe.

Oui,
et j'ai remarqué que ca fonctionne, c'est les managers qui se chargent également d'évaluer en fonction des résultats quelles tournées sont les plus rentables, par experience.

Ca met un peu de temps à se mettre en place, et on ne bouge plus grand chose quand on a des tournées qui fonctionnent.
Du coup on sait bien que ce n'est pas la meilleur tournée, mais comment ensuite refondre tout ça ? Donc on vit avec.

D'ou l'interet je pense, de faire la même chose, mais avant, par simulation.