Discussion :

[laureat]

Bonjour,


En fait, j'ai une question qui me tringue l'esprit concernant la modélisation du problème de tournées de véhicules.

En fait, on trouve deux type de formulations. Une danslaquelle le dépot est représenté par deux noeuds 0 et n+1 et une autre où le dépot est représenté par le noeud 0 .

Je n'ai pas compris qu'elle est l'utilité de dédoublement de noeud pour le dépot.

Pourriez m'expliquer dans quel cas on utilise telle formulation plutot que l'autre?

Merci d'avance de votre aide.

Bonne journée

[pseudocode]

Je n'ai pas compris qu'elle est l'utilité de dédoublement de noeud pour le dépot.

Pourriez m'expliquer dans quel cas on utilise telle formulation plutot que l'autre?

Généralement on cherche les chemins qui ne passent pas 2 fois par le meme client, mais qui partent et reviennent au dépot .

Rajouter le noeud Vn+1 (=V0) permet de formuler cette contrainte sans faire de cas particulier pour le dépot : un chemin "valide" ne passe jamais deux fois par le même noeud.