Discussion :

[laureat]

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.
Des idées??

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

Merci par avance de vos aides.
Cordialement

[laureat]

Re,

Voici ce que j'ai réalisé. Est-ce correcte?
Merci par avance de vos réponses.

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

[Acrim]

Si tu cherches à construire une solution, vérifiant les contraintes, de cette manière, il faut que tu prennes aussi en compte les fenêtres de temps.

Pour chaque nœud participant à la solution tu peux, par exemple, maintenir l'heure d'arrivée au plus tôt sur le site et l'heure de départ au plus tard (étant les temps de trajet etc). Il faut ensuite que tu t'assures que chaque nouveau nœud ajouté ne pose pas de problème (retard etc).