Discussion :

[euphoriste]

Bonjour, J'ai un problème lorsque j'essaye de modéliser le problème du voyageur de commerce dans GLPK :

Voici mon modèle :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
###Données 
 
#nombre de Villes
param n; 
set V:={1..n};
 
#Matrice des Arcs entre les villes
param d{i in V, j in V}; 
 
###Variables
 
#Booléen pour dire qu'un arc a été emprunté
var x{i in V, j in V} binary; 
 
### Contraintes
 
#Il faut passer par toutes les villes
s.t. arcs : sum {i in V, j in V} x[i,j] = n-1;
 
#On ne peut entre et sortir d'une ville qu'une seule fois
s.t. Entrer { i in V} : sum {j in V : i!=j} x[i,j] <=1; 
s.t. Sortir {i in V} : sum{j in V : i!=j} x[j,i] <= 1;
 
#On ne passe par un chemin qu'une seule fois
s.t. CheminUnique{i in V,j in V} : x[j,i]+x[i,j]<=1;
 
#chemin non nul
s.t. non_nul {i in V, j in V} : x[i,j]*(d[i,j]-1) >= 0;
 
### Fonction Objectif
minimize f: sum {i in V, j in V} d[i,j]*x[i,j]; #On cherche le plus court chemin
 
solve;
display x;
 
###Affichage
printf "Distance min : %d\n",
  sum {i in V, j in V} d[i,j]*x[i,j];
printf("   De la ville    vers     \n");
printf{i in V, j in V: x[i,j]} "      %2d          %3d       \n",
   i, j;
end;

et voici mes données ( C'est le problème " Ulysse" de dim16, problème connu dont le résultat du chemin le plus cours est 6859 ) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
data;
 
#nombre de villes
param n := 16;
 
#distance entre les villes
param d: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 :=
1	0  509	501	312	1019	736	656	60	1039	726	2314	479	448	479	619	150
2	509	0	126	474	1526	1226	1133	532	1449	1122	2789	958	941	978	1127	542
3	501	126	0	541	1516	1184	1084	536	1371	1045	2728	913	904	946	1115	499
4	312	474	541	0	1157	980	919	271	1333	1029	2553	751	704	720	783	455
5	1019	1526	1516	1157	0	478	583	996	858	855	1504	677	651	600	401	1033
6	736	1226	1184	980	478	0	115	740	470	379	1581	271	289	261	308	687
7	656	1133	1084	919	583	115	0	667	455	288	1661	177	216	207	343	592
8	60	532	536	271	996	740	667	0	1066	759	2320	493	454	479	598	206
9	1039	1449	1371	1333	858	470	455	1066	0	328	1387	591	650	656	776	933
10	726	1122	1045	1029	855	379	288	759	328	0	1697	333	400	427	622	610
11	2314	2789	2728	2553	1504	1581	1661	2320	1387	1697	0	1838	1868	1841	1789	2248
12	479	958	913	751	677	271	177	493	591	333	1838	0	68	105	336	417
13	448	941	904	704	651	289	216	454	650	400	1868	68	0	52	287	406
14	479	978	946	720	600	261	207	479	656	427	1841	105	52	0	237	449
15	619	1127	1115	783	401	308	343	598	776	622	1789	336	287	237	0	636
16	150	542	499	455	1033	687	592	206	933	610	2248	417	406	449	636	0;
 
end;

Voilà le résultat :


Mon problème est le fait de définir la ville de départ et d'arrivée car comme vous pouvez le voir le trajet ne se termine pas à la ville 1
Je ne sais pas trop comment faire, j'avais déjà résolu ce problème en java en indiquant un compteur ( égal à 0 en début de trajet ) que l'on itérait après chaque passage dans une ville pour facilement déterminer lorsque l'on arrive à la dernière lligne mais je ne sais pas comment implémenter cette méthode sous GLPK.

Voilà, si vous avez des suggestions ou des questions merci de me le faire savoir

[euphoriste]

C'est bon finalement j'ai réussi à modéliser cette contrainte

[dourouc05]

Ta solution semble avoir un problème assez grave : tu as des cycles. Par exemple, 1 -> 16 -> 8 -> 1, alors que toutes les villes ne sont pas prises en compte dans ce cycle. Quelle contrainte as-tu implémenté ? Normalement, tu dois en avoir un nombre exponentiel en le nombre de villes pour que ce soit correct (élimination des sous-tours, par exemple).