Discussion :

[dreamsmoon]

Bonjour tous le monde ,

Dans le cadre de mon projet de mémoire ,je suis en train d'essayer les différents problèmes d'optimisation combinatoire : problème de voyageur de commerce,tournée de véhicules et le PDP (problème de tournée de véhicule avec ramassage).
j'ai commencé d'implémenter le TSP avec une petite instance de 10 villes -chaque ville est décrite par un identifiant,abscisse et ordonnée),voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
dexpr float total_length = sum(i in cities, j in cities : i != j) d[i][j] * x[i,j];
minimize total_length;
//contraintes 
subject to 
 {  ct_assign: 
    forall (i in cities) 
     {sum(j in cities: i.id < j.id)  x[i][j] + sum(j in cities: i.id > j.id) x[j][i] == 2;}
}

avec cette contrainte on veut exiger que le voyageur passe une et une seule fois par un sommet i ,or voici ce que ça donne :

1	1	 <5 476 802>	1	472
1	1	 <9 518 116>	1	343
2	2	 <8 732 222>	1	380
2	2	 <10 876 757>	1	195
3	3	 <4 578 867>	1	75
3	3	 <5 476 802>	1	49
4	4	 <7 662 821>	1	96
6	6	 <7 662 821>	1	140
6	6	 <10 876 757>	1	140
8	8	 <9 518 116>	1	239

aidez moi s'il vous plait ,merci

[CliffeCSTL]

C'est quoi le pb ?