Discussion :

[StabiloHB]

Bonjour à tous !

Bon j'essaye de programmer mon DARP sur CPLEX, je ne peux pas utiliser CP malheureusement car certaines de mes data sont des floats.

Donc j'ai 2 petits soucis :
- premièrement j'ai une erreur 5002 me disant que

'q1 is not convex.->.

j'avoue n'avoir aucune idée de ce que la peut être.

- ensuite j'aimerais savoir comment je pourrai afficher les arcs actifs dans le but d'utiliser python pour les afficher sur un plot.

Merci d'avance et bonne journée !

PS : les fichiers .mod et .data semble ne pas être acceptés je les mets donc entre balises.

Code data :

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
/*********************************************
 * OPL 12.9.0.0 Data
 * Author: Stabilo
 * Creation Date: 13 févr. 2020 at 15:04:42
 *********************************************/
 
//Data sheet
 
n=5;
d=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
q=[0, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 0];
V=2;
T=[1000, 1000];
Q=[4, 4];
e=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
l=[480, 480, 480, 480, 480, 480, 480, 480, 480, 480, 480, 480];
c=[[0.0, 4.123105625617661, 2.23606797749979, 1.4142135623730951, 1.4142135623730951, 3.605551275463989, 1.4142135623730951, 2.8284271247461903, 1.0, 4.47213595499958, 4.123105625617661, 2.0], [4.123105625617661, 0.0, 3.1622776601683795, 3.0, 3.0, 1.4142135623730951, 3.0, 3.605551275463989, 4.47213595499958, 1.0, 2.0, 4.123105625617661], [2.23606797749979, 3.1622776601683795, 0.0, 1.0, 1.0, 2.0, 1.0, 4.123105625617661, 3.1622776601683795, 3.0, 4.242640687119285, 1.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [3.605551275463989, 1.4142135623730951, 2.0, 2.23606797749979, 2.23606797749979, 0.0, 2.23606797749979, 4.123105625617661, 4.242640687119285, 1.0, 3.1622776601683795, 3.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [2.8284271247461903, 3.605551275463989, 4.123105625617661, 3.1622776601683795, 3.1622776601683795, 4.123105625617661, 3.1622776601683795, 0.0, 2.23606797749979, 4.47213595499958, 2.23606797749979, 4.47213595499958], [1.0, 4.47213595499958, 3.1622776601683795, 2.23606797749979, 2.23606797749979, 4.242640687119285, 2.23606797749979, 2.23606797749979, 0.0, 5.0, 4.0, 3.0], [4.47213595499958, 1.0, 3.0, 3.1622776601683795, 3.1622776601683795, 1.0, 3.1622776601683795, 4.47213595499958, 5.0, 0.0, 3.0, 4.0], [4.123105625617661, 2.0, 4.242640687119285, 3.605551275463989, 3.605551275463989, 3.1622776601683795, 3.605551275463989, 2.23606797749979, 4.0, 3.0, 0.0, 5.0], [2.0, 4.123105625617661, 1.0, 1.4142135623730951, 1.4142135623730951, 3.0, 1.4142135623730951, 4.47213595499958, 3.0, 4.0, 5.0, 0.0]];
 
t=[[0.0, 61.84658438426491, 33.54101966249685, 21.213203435596427, 21.213203435596427, 54.08326913195984, 21.213203435596427, 42.42640687119285, 15.0, 67.0820393249937, 61.84658438426491, 30.0], [61.84658438426491, 0.0, 47.434164902525694, 45.0, 45.0, 21.213203435596427, 45.0, 54.08326913195984, 67.0820393249937, 15.0, 30.0, 61.84658438426491], [33.54101966249685, 47.434164902525694, 0.0, 15.0, 15.0, 30.0, 15.0, 61.84658438426491, 47.434164902525694, 45.0, 63.63961030678927, 15.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [54.08326913195984, 21.213203435596427, 30.0, 33.54101966249685, 33.54101966249685, 0.0, 33.54101966249685, 61.84658438426491, 63.63961030678927, 15.0, 47.434164902525694, 45.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [42.42640687119285, 54.08326913195984, 61.84658438426491, 47.434164902525694, 47.434164902525694, 61.84658438426491, 47.434164902525694, 0.0, 33.54101966249685, 67.0820393249937, 33.54101966249685, 67.0820393249937], [15.0, 67.0820393249937, 47.434164902525694, 33.54101966249685, 33.54101966249685, 63.63961030678927, 33.54101966249685, 33.54101966249685, 0.0, 75.0, 60.0, 45.0], [67.0820393249937, 15.0, 45.0, 47.434164902525694, 47.434164902525694, 15.0, 47.434164902525694, 67.0820393249937, 75.0, 0.0, 45.0, 60.0], [61.84658438426491, 30.0, 63.63961030678927, 54.08326913195984, 54.08326913195984, 47.434164902525694, 54.08326913195984, 33.54101966249685, 60.0, 45.0, 0.0, 75.0], [30.0, 61.84658438426491, 15.0, 21.213203435596427, 21.213203435596427, 45.0, 21.213203435596427, 67.0820393249937, 45.0, 60.0, 75.0, 0.0]];

Code 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*********************************************
 * OPL 12.9.0.0 Model
 * Author: stabilo
 * Creation Date: 13 févr. 2020 at 13:37:14
 *********************************************/
//Data
int n = ...; 			//Number of clients
int V = ...;			//Number of vehicles
range P = 1..n; 		//Range of pickup
range D = n+1..2*n;		//Range of drop of
range N = 0..2*n+1; 	//Range of all nodes
range PD= 1..2*n;		//Range of nodes whitout depots
range K = 1..V;			//Range of vehicles
int Q[K]=...;			//Vehicle capacity
int q[N]=...;			//Load at node i
int e[N]=...;			//Earliest time bound 
int l[N]=...;			//Lastest time bound
int d[N]=...;			//Duration service at node i
int L=1000;				//Max ride time of a request
int T[K]=...;			//Max duration of route
float c[N][N]=...;		//Cost of traveling from node i to node j
float t[N][N]=...;		//Timde needed from node i to node j
 
//Decision variables
dvar boolean x[N][N][K];	//1 if the kth vehicle goes from i to j
dvar float u[N][K];			//Time at which k starts servicing i
dvar int w[N][K]; 			//Load of vehicle k after node i
dvar float r[N][K];			//the ride time of user i
 
//Objective function
minimize
  sum(k in K, i in N, j in N)
    c[i][j]*x[i][j][k];
 
//Constraints
subject to {
	forall (i in P)				//Every request is served once
		sum(k in K, j in N)
	 	 x[i][j][k]==1;
 
	forall (k in K)				//Every vehicles leaves the start terminal
	  sum(i in N)
	    x[0][i][k]==1;
 
	forall (k in K)				//Every vehicles enters the end terminal
	  sum(i in N)
	    x[i][2*n+1][k]==1;
 
	forall (i in P)				//Same vehicle services pickup and delivery
	  forall (k in K)
	    (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;
 
	forall (i in PD)			//Same vehicle that enters a node leaves the node
	  forall (k in K)
	    (sum(j in N) x[j][i][k])-(sum(j in N)x[i][j][k])==0;
 
	forall (i in N)				//Setting and checking visit time
	  forall (j in N)
	    forall (k in K)
	      u[j][k]>=((u[i][k]+d[i]+t[i][j])*x[i][j][k]);
 
	forall (i in N)				//Setting and checking visit time
	  forall (k in K)
	  e[i]<=u[i][k]<=l[i];
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (j in N)
	    forall (k in K)
	      w[j][k]>=((w[i][k]+q[i])*x[i][j][k]);
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (k in K)
	    w[i][k]<=Q[k];
 
	forall (i in P)				//Setting and checking ride time
	  forall(k in K)
	    r[i][k]>=(u[n+i][k]-(u[i][k]+d[i]));
 
	forall (i in P)				//Setting and checking ride time
	  forall (k in K)
	    t[i][n+i]<=r[i][k]<=L;
 
	forall (k in K)
	  u[2*n+1][k]-u[0][k]<=T[k];
}

EDIT : : Bon alors en fait c'est que j'essayais de multiplier une variable int par un boolean. Donc la solution est de tester si le boolean est True mettre la condition en remplaçant le boolean par 1.

Stabilo.

[StabiloHB]

Re-Bonjour tout le monde,

Bon après avoir réglé mes petits soucis ça tourne enfin !!

Mais je pense qu'il y a un problème quand même les résultats ne semblent pas être très bons.

Est ce que quelqu'un qui utiliserai Cplex pourrait m'aider à voir où est le soucis ?

Je remets mon nouveau programme.

data :

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
/*********************************************
 * OPL 12.9.0.0 Data
 * Author: vjeandraud
 * Creation Date: 13 févr. 2020 at 15:04:42
 *********************************************/
 
//Data sheet
 
n=2;
d=[0, 3, 3, 3, 3, 0];
q=[0, 1, 1, -1, -1, 0];
V=2;
T=[1000, 1000];
Q=[3, 3];
e=[0, 0, 0, 0, 0, 0];
l=[480, 480, 480, 480, 480, 480];
c=[[0.0, 4.123105625617661, 1.4142135623730951, 3.1622776601683795, 3.1622776601683795, 3.1622776601683795], [4.123105625617661, 0.0, 3.605551275463989, 3.605551275463989, 3.605551275463989, 2.23606797749979], [1.4142135623730951, 3.605551275463989, 0.0, 4.0, 4.0, 2.0], [3.1622776601683795, 3.605551275463989, 4.0, 0.0, 0.0, 4.47213595499958], [3.1622776601683795, 3.605551275463989, 4.0, 0.0, 0.0, 4.47213595499958], [3.1622776601683795, 2.23606797749979, 2.0, 4.47213595499958, 4.47213595499958, 0.0]];
 
t=[[0.0, 61.84658438426491, 21.213203435596427, 47.434164902525694, 47.434164902525694, 47.434164902525694], [61.84658438426491, 0.0, 54.08326913195984, 54.08326913195984, 54.08326913195984, 33.54101966249685], [21.213203435596427, 54.08326913195984, 0.0, 60.0, 60.0, 30.0], [47.434164902525694, 54.08326913195984, 60.0, 0.0, 0.0, 67.0820393249937], [47.434164902525694, 54.08326913195984, 60.0, 0.0, 0.0, 67.0820393249937], [47.434164902525694, 33.54101966249685, 30.0, 67.0820393249937, 67.0820393249937, 0.0]];

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*********************************************
 * OPL 12.9.0.0 Model
 * Author: vjeandraud
 * Creation Date: 13 févr. 2020 at 13:37:14
 *********************************************/
//Data
int n = ...; 			//Number of clients
int V = ...;			//Number of vehicles
range P = 1..n; 		//Range of pickup
range D = n+1..2*n;		//Range of drop of
range N = 0..2*n+1; 	//Range of all nodes
range PD= 1..2*n;		//Range of nodes whitout depots
range K = 1..V;			//Range of vehicles
int Q[K]=...;			//Vehicle capacity
int q[N]=...;			//Load at node i
int e[N]=...;			//Earliest time bound 
int l[N]=...;			//Lastest time bound
int d[N]=...;			//Duration service at node i
int L=1000;				//Max ride time of a request
int T[K]=...;			//Max duration of route
float c[N][N]=...;		//Cost of traveling from node i to node j
float t[N][N]=...;		//Timde needed from node i to node j
 
//Decision variables
dvar boolean x[N][N][K];	//1 if the kth vehicle goes from i to j
dvar float u[N][K];			//Time at which k starts servicing i
dvar int w[N][K]; 			//Load of vehicle k after node i
dvar float r[N][K];			//the ride time of user i
 
//Objective function
minimize
  sum(k in K, i in N, j in N)
    c[i][j]*x[i][j][k];
 
//Constraints
subject to {
	forall (i in P)				//Every request is served once
		sum(k in K, j in N)
	 	 x[i][j][k]==1;
 
	forall (k in K)				//Every vehicles leaves the start terminal
	  sum(i in N)
	    x[0][i][k]==1;
 
	forall (k in K)				//Every vehicles enters the end terminal
	  sum(i in N)
	    x[i][2*n+1][k]==1;
 
	forall (i in P)				//Same vehicle services pickup and delivery
	  forall (k in K)
	    (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;
 
	forall (i in PD)			//Same vehicle that enters a node leaves the node
	  forall (k in K)
	    (sum(j in N) x[j][i][k])-(sum(j in N)x[i][j][k])==0;
 
	forall (i in N)				//Setting and checking visit time
	  forall (j in N)
	    forall (k in K)
	      (x[i][j][k]==1) => (u[j][k]>=(u[i][k]+d[i]+t[i][j]));
 
	forall (i in N)				//Setting and checking visit time
	  forall (j in N)
	    forall (k in K)
	      (x[i][j][k]==0) => (u[j][k]>=0);
 
	forall (i in N)				//Setting and checking visit time
	  forall (k in K)
	  	e[i]<=u[i][k]<=l[i];
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (j in N)
	    forall (k in K)
	      (x[i][j][k]==1) => (w[j][k]>=(w[i][k]+q[i]));
	forall (i in N)				//Setting and checking vehicle load
	  forall (j in N)
	    forall (k in K)
	      (x[i][j][k]==0) => (w[j][k]>=0);
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (k in K)
	    w[i][k]<=Q[k];
 
	forall (i in P)				//Setting and checking ride time
	  forall(k in K)
	    r[i][k]>=(u[n+i][k]-(u[i][k]+d[i]));
 
	forall (i in P)				//Setting and checking ride time
	  forall (k in K)
	    t[i][n+i]<=r[i][k]<=L;
 
	forall (k in K)
	  u[2*n+1][k]-u[0][k]<=T[k];
}

Merci d'avance et bonne journée,

Stabilo.

[dourouc05]

EDIT : : Bon alors en fait c'est que j'essayais de multiplier une variable int par un boolean. Donc la solution est de tester si le boolean est True mettre la condition en remplaçant le boolean par 1.

En fonction de ce booléen, ça peut être une très bonne solution ou une horreur… Si c'est un paramètre, c'est tout à fait normal (et CPLEX n'aurait jamais dû râler, en fait). Si c'est une variable d'optimisation, tu ne peux pas savoir, lors de la construction de ton modèle, si elle va prendre la valeur 1 ou 0.

Je suppose que la contrainte en question est w[j][k]>=((w[i][k]+q[i])*x[i][j][k]). Soit tu utilises des contraintes indicatrices (https://www.ibm.com/support/knowledg...tors_defn.html), soit tu utilises une formulation à base de M (https://www.ibm.com/support/pages/di...-m-formulation).

[dourouc05]

Non, personne ne va te dire ce qui ne va pas dans ton code . Qu'est-ce que tu remarques qui n'est pas juste a priori ? Quelle serait la contrainte qui n'est pas entièrement appliquée ?

[StabiloHB]

Salut à toi merci pour tes réponses !

Soit tu utilises des contraintes indicatrices, soit tu utilises une formulation à base de M.

Alors c'est la variable qui doit dire si oui ou non l'arc est actif, pour cela qu'une variable booléenne me semblait appropriée.

Code :

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

dvar boolean x[N][N][K];	//1 if the kth vehicle goes from i to j

Du coup je pense avoir utilisé une contrainte indicatrices car j'avais solutionné le problème comme ceci ce qui ressemble vachement avec le site que tu m'as envoyé.

Code :

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

1
2
3
(x[i][j][k]==1) => (w[j][k]>=(w[i][k]+q[i]));
et
(x[i][j][k]==0) => (w[j][k]>=0)

Pour ce qui est de la solution je ne la comprends même pas pour cela qu'il m'est difficile de savoir quelles contraintes sont respectées ou non.

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
x = [[[1
                 1]
                 [0 0]
                 [0 0]
                 [0 0]
                 [0 0]
                 [0 0]]
             [[0 0]
                 [0 0]
                 [0 0]
                 [0 0]
                 [0 1]
                 [0 0]]
             [[0 1]
                 [0 0]
                 [0 0]
                 [0 0]
                 [0 0]
                 [0 0]]
             [[0 0]
                 [0 0]
                 [0 1]
                 [0 0]
                 [0 0]
                 [0 0]]
             [[0 0]
                 [0 0]
                 [0 0]
                 [0 1]
                 [0 0]
                 [0 0]]
             [[0 0]
                 [0 1]
                 [0 0]
                 [0 0]
                 [0 0]
                 [1 1]]];

De plus j'ai un avertissement comme quoi certaines valeurs d'une variable de décision ne sont pas utilisées.

Code :

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

1
2
 
//La variable de décision "r[0][1]" n'a jamais été utilisée par le moteur.

Pour ma part je pense que vu que ces arcs ne sont pas utilisés, la variable associée n'est pas utilisée non plus.

Bonne journée,

Stabilo.

[dourouc05]

Ta solution pour gérer la variable booléenne me semble bonne !

Après, pour ce qui est de l'explication de la solution, je trouve ce format assez peu lisible . CPLEX en ligne de commande est souvent plus compréhensible… mais je ne sais pas si c'est compatible OPL ou pas. Tu peux aussi utiliser des blocs de code pour un truc qui a plus de sens (execute DISPLAY).

[StabiloHB]

Salut !

Bon alors j'ai fais comme tu m'as conseillé un petit execute qui write la solution c'est quand même beaucoup plus lisible :

Code :

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

1
2
3
4
5
6
7
8
execute
{
for(var i in N)
	for(var j in N)
		for(var k in K)
			if (x[i][j][k]!=0)
				writeln("[",i,"]","[",j,"]","[",k,"]","=",x[i][j][k]);
}

Résultat :

Code :

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

1
2
3
4
5
6
7
8
9
[0][0][1]=1
[0][0][2]=1
[1][4][2]=1
[2][0][2]=1
[3][2][2]=1
[4][3][2]=1
[5][1][2]=1
[5][5][1]=1
[5][5][2]=1

Du coup pour l'instant, les contraintes qui sont de sortir de 0 et rentrer à 5 (la dernière node) sont respectées.

Mais pour ce qui est des autres ! Aie

Déjà pour éviter que le bus fasse node i to node i je vais essayer de mettre des pour i!=j partout.

Merci bonne journée !

EDIT : Bon j'ai résolu un soucis et pas des moindres en rajoutant une contrainte :

Code :

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

1
2
3
	forall (k in K)
	  sum(i in N)
	    x[i][i][k]==0;

Elle permet de dire que le bus ne peut pas partir d'une node i pour aller à la node i. Au lieu de rajouter des if i!=j.

PS : Je poste mes questions au fur et à mesure que j'avance, des fois j'arrive à y répondre seul des fois non, mais je pense que c'est important que je les mette toutes ici d'une part pour moi, ça me permet de poser mes questions correctement et de les structurer pour que vous m'aidiez, et d'une autre part pour d'éventuelle future(s) personne(s) qui aurai(en)t la même problématique que moi.

Maintenant je vais essayer de comprendre pourquoi la variable de Cumul de temps n'est pas utilisée.

Stabilo.

[dourouc05]

Elle permet de dire que le bus ne peut pas partir d'une node i pour aller à la node i. Au lieu de rajouter des if i!=j.

Pour ce genre de cas, je préfère souvent utiliser comme indice les arêtes (plutôt que des paires de nœuds) : naturellement, ce genre de problème disparaît.

[StabiloHB]

Ah oui les supprimer directement dans le coût des arcs tu veux dire ?

Bon sinon je sais maintenant pourquoi j'ai des avertissements :

Code :

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

//La variable de décision "r[0][1]" n'a jamais été utilisée par le moteur.

Vu que cette variable est le temps que passe le passager dans le bus, déjà de 0 à i, il n'y a pas de passager donc normal quelle ne soit pas utilisée. Puis pour tous les autres avertissements, ce sont pour des trajets qui n'existe pas.
Donc ça c'est ok.

Cependant reste encore un soucis !
il ne va pas forcément livrer au bon endroit.. Parce que normalement, pickup à i et delivery à i+n
Pour moi c'était cette contrainte qui permettait ça mais finalement non et la je sèche...

Code :

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

1
2
3
	forall (i in P)				//Same vehicle services pickup and delivery
	  forall (k in K)
	    (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;

Stabilo.

[dourouc05]

Ah oui les supprimer directement dans le coût des arcs tu veux dire ?

Non : ne juste pas avoir les variables correspondantes. Par exemple, tu aurais ceci : dvar boolean x[E][K];, avec un E à définir adéquatement. Ainsi, tu as un minimum de variables créées, tu limites le travail en prétraitement de CPLEX. Maintenant, ce n'est peut-être pas aussi facile à implémenter en OPL… Dans des langages de programmation "complets", avec des bibliothèques de graphe, c'est assez facile.

Cependant reste encore un soucis !
il ne va pas forcément livrer au bon endroit.. Parce que normalement, pickup à i et delivery à i+n
Pour moi c'était cette contrainte qui permettait ça mais finalement non et la je sèche...

Code :

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

1
2
3
	forall (i in P)				//Same vehicle services pickup and delivery
	  forall (k in K)
	    (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;

Peut-être ne comprends-je pas bien ton modèle, mais c'est normal que, pour la livraison, tu utilises l'arête n+1 -> j ?

Sinon, pourrais-tu remettre ton modèle corrigé ? De préférence sous forme mathématique, c'est plus facile à lire !

[StabiloHB]

Non : ne juste pas avoir les variables correspondantes.

Ah oui d'accord ne pas créer les trajets impossibles.

Oui c'est le modèle de Jean-François Cordeau et Gilbert Laporte.


Alors où :

P ensemble des pickups de 1 à n.
D ensemble des delivery de n+1 à 2n où n+i est le delivery de i.
V ensemble P+D+0+(2*n+1) donc 0 et 2n+1 sont start et le terminal.
K ensemble des bus
Qk capacité d'un bus
ei et li, chaque node a un temps mini d'entré (early start) et un temps maxi d'entré(late start) (en gros une fenêtre de passage).
L le temps maximum qu'un passager peut passer dans le bus

tij le temps de trajet entre i et j
cij le coût de chaque arc entre i et j
xij est l'arc 1 si il est actif 0 dans l'autre cas.
qi est la charge de chaque passager donc qi+n=-qi. De plus q0=q2n+1=0.

wik la charge du bus k quand il part de la node i
rik le temps propre a i où k part de i donc r doit toujours être inférieur à L (le temps max)
uik est la variable de temps du bus k en fonction des nodes i

J'espère avoir été assez clair j'avoue qu'il n'est pas si simple que ça il faut un petit pour comprendre toutes les équations.

En tout cas merci pour ton aide !

Bonne fin d'après midi.

Stabilo.

[dourouc05]

C'est vrai que le modèle est un peu tordu, surtout je trouve avec la numérotation des points dans le graphe (1 à n pour les départs, n+1 à 2n pour les arrivées)…

Pour ta variable x, ne devrais-tu pas plutôt avoir un x[P][N][K] ?

[StabiloHB]

Pour ta variable x, ne devrais-tu pas plutôt avoir un x[P][N][K] ?

Alors non parce que sinon les trajets entre les n+i et d'autres nodes ne seraient pas pris en charge.

Bon sinon petite update de mon programme.
J'ai linéarisé les contraintes suivantes :


Ce qui nous donne donc avec BigM

Code :

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

1
2
3
4
5
6
7
8
9
	forall (i in N)				//Setting and checking visit time
	  forall (j in N)
	    forall (k in K)
	      u[j][k]>=u[i][k]+d[i]+t[i][j]-M*(1-x[i][j][k]);
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (j in N)
	    forall (k in K)
	      w[j][k]>=w[i][k]+q[j]-M*(1-x[i][j][k]);

Ensuite j'ai réussi en OPL à mettre du min et max (pour le poids dans le bus):

Code :

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

1
2
3
4
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (k in K)
	    maxl(0,q[i])  <=  w[i][k]  <=minl(Q[k], (Q[k]+q[i]));

Cependant, il ne va toujours pas au bon endroit... Il commence par déposer quelqu'un, hors la contrainte juste au dessus doit normalement interdire le poids à l'intérieur du véhicule d'être négatif...
J'ai l'impression que le poids ne s'affecte pas bien.

Voici mon code complet :

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*********************************************
 * OPL 12.9.0.0 Model
 * Author: 
 * Creation Date: 13 févr. 2020 at 13:37:14
 *********************************************/
//Data
int M = 1000000000;		//Big M
int n = ...; 			//Number of clients
int V = ...;			//Number of vehicles
range P = 1..n; 		//Range of pickup
range N = 0..2*n+1; 	//Range of all nodes
range PD= 1..2*n;		//Range of nodes whitout depots
range K = 1..V;			//Range of vehicles
int Q[K]=...;			//Vehicle capacity
int q[N]=...;			//Load at node i
int e[N]=...;			//Earliest time bound 
int l[N]=...;			//Lastest time bound
int d[N]=...;			//Duration service at node i
int L=1000;				//Max ride time of a request
int T[K]=...;			//Max duration of route
float c[N][N]=...;		//Cost of traveling from node i to node j
float t[N][N]=...;		//Timde needed from node i to node j
 
//Decision variables
dvar boolean x[N][N][K];	//1 if the kth vehicle goes from i to j
dvar float u[N][K];			//Time at which k starts servicing i
dvar int w[N][K]; 			//Load of vehicle k after node i
dvar float r[N][K];			//the ride time of user i
 
//Objective function
minimize
  sum(k in K, i in N, j in N)
    c[i][j]*x[i][j][k];
 
//Constraints
subject to {
 
	forall (i in P)				//Every request is served once
	  sum(k in K, j in N)
	    x[i][j][k]==1;
 
	forall (k in K)				//Every vehicles leaves the start terminal
	  sum(i in PD)
	    x[0][i][k]==1;
 
	forall (k in K)				//Every vehicles enters the end terminal
	  sum(i in PD)
	    x[i][2*n+1][k]==1;
 
	forall (i in P)				//Same vehicle services pickup and delivery
	  forall (k in K)
	    (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;
 
	forall (i in PD)			//Same vehicle that enters a node leaves the node
	  forall (k in K)
	    (sum(j in N) x[j][i][k])-(sum(j in N)x[i][j][k])==0;
 
	forall (i in N)				//Setting and checking visit time
	  forall (j in N)
	    forall (k in K)
	      u[j][k]>=u[i][k]+d[i]+t[i][j]-M*(1-x[i][j][k]);
 
	forall (i in N)				//Setting and checking visit time
	  forall (k in K)
	  	e[i]<=u[i][k]<=l[i];
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (j in N)
	    forall (k in K)
	      w[j][k]>=w[i][k]+q[j]-M*(1-x[i][j][k]);
 
	forall (i in N)				//Setting and checking vehicle load
	  forall (k in K)
	    maxl(0,q[i])  <=  w[i][k]  <=minl(Q[k], (Q[k]+q[i]));
 
	forall (i in P)				//Setting and checking ride time
	  forall(k in K)
	    r[i][k]>=(u[n+i][k]-(u[i][k]+d[i]));
 
	forall (i in P)				//Setting and checking ride time
	  forall (k in K)
	    t[i][n+i]<=r[i][k]<=L;
 
	forall (k in K)
	  u[2*n+1][k]-u[0][k]<=T[k];
}
 
//print arc results
execute 					
{
for(var i in N)
	for(var j in N)
		for(var k in K)
			if (x[i][j][k]!=0)
				writeln("[",i,",",j,",",k,"]");
}

Et les data pour le faire tourner avec :

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
/*********************************************
 * OPL 12.9.0.0 Data
 * Author: 
 * Creation Date: 13 févr. 2020 at 15:04:42
 *********************************************/
 
//Data sheet
 
n=5;
d=[0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0];
q=[0, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 0];
V=2;
T=[1000, 1000];
Q=[3, 3];
e=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
l=[480, 480, 480, 480, 480, 480, 480, 480, 480, 480, 480, 480];
c=[[0.0, 4.123105625617661, 2.23606797749979, 1.4142135623730951, 1.4142135623730951, 3.605551275463989, 1.4142135623730951, 2.8284271247461903, 1.0, 4.47213595499958, 4.123105625617661, 2.0], [4.123105625617661, 0.0, 3.1622776601683795, 3.0, 3.0, 1.4142135623730951, 3.0, 3.605551275463989, 4.47213595499958, 1.0, 2.0, 4.123105625617661], [2.23606797749979, 3.1622776601683795, 0.0, 1.0, 1.0, 2.0, 1.0, 4.123105625617661, 3.1622776601683795, 3.0, 4.242640687119285, 1.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [3.605551275463989, 1.4142135623730951, 2.0, 2.23606797749979, 2.23606797749979, 0.0, 2.23606797749979, 4.123105625617661, 4.242640687119285, 1.0, 3.1622776601683795, 3.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [2.8284271247461903, 3.605551275463989, 4.123105625617661, 3.1622776601683795, 3.1622776601683795, 4.123105625617661, 3.1622776601683795, 0.0, 2.23606797749979, 4.47213595499958, 2.23606797749979, 4.47213595499958], [1.0, 4.47213595499958, 3.1622776601683795, 2.23606797749979, 2.23606797749979, 4.242640687119285, 2.23606797749979, 2.23606797749979, 0.0, 5.0, 4.0, 3.0], [4.47213595499958, 1.0, 3.0, 3.1622776601683795, 3.1622776601683795, 1.0, 3.1622776601683795, 4.47213595499958, 5.0, 0.0, 3.0, 4.0], [4.123105625617661, 2.0, 4.242640687119285, 3.605551275463989, 3.605551275463989, 3.1622776601683795, 3.605551275463989, 2.23606797749979, 4.0, 3.0, 0.0, 5.0], [2.0, 4.123105625617661, 1.0, 1.4142135623730951, 1.4142135623730951, 3.0, 1.4142135623730951, 4.47213595499958, 3.0, 4.0, 5.0, 0.0]];
 
t=[[0.0, 61.84658438426491, 33.54101966249685, 21.213203435596427, 21.213203435596427, 54.08326913195984, 21.213203435596427, 42.42640687119285, 15.0, 67.0820393249937, 61.84658438426491, 30.0], [61.84658438426491, 0.0, 47.434164902525694, 45.0, 45.0, 21.213203435596427, 45.0, 54.08326913195984, 67.0820393249937, 15.0, 30.0, 61.84658438426491], [33.54101966249685, 47.434164902525694, 0.0, 15.0, 15.0, 30.0, 15.0, 61.84658438426491, 47.434164902525694, 45.0, 63.63961030678927, 15.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [54.08326913195984, 21.213203435596427, 30.0, 33.54101966249685, 33.54101966249685, 0.0, 33.54101966249685, 61.84658438426491, 63.63961030678927, 15.0, 47.434164902525694, 45.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [42.42640687119285, 54.08326913195984, 61.84658438426491, 47.434164902525694, 47.434164902525694, 61.84658438426491, 47.434164902525694, 0.0, 33.54101966249685, 67.0820393249937, 33.54101966249685, 67.0820393249937], [15.0, 67.0820393249937, 47.434164902525694, 33.54101966249685, 33.54101966249685, 63.63961030678927, 33.54101966249685, 33.54101966249685, 0.0, 75.0, 60.0, 45.0], [67.0820393249937, 15.0, 45.0, 47.434164902525694, 47.434164902525694, 15.0, 47.434164902525694, 67.0820393249937, 75.0, 0.0, 45.0, 60.0], [61.84658438426491, 30.0, 63.63961030678927, 54.08326913195984, 54.08326913195984, 47.434164902525694, 54.08326913195984, 33.54101966249685, 60.0, 45.0, 0.0, 75.0], [30.0, 61.84658438426491, 15.0, 21.213203435596427, 21.213203435596427, 45.0, 21.213203435596427, 67.0820393249937, 45.0, 60.0, 75.0, 0.0]];

Stabilo.

[StabiloHB]

Salut à tous,

Bon je reposte ici, j'ai trouvé le problème mais je n'arrive pas à le résoudre.

CPLEX ne reconnait pas du tout la charge du véhicule, on peut lui mettre n'importe quelle contrainte dessus cela ne changera pas le résultat..
Donc je pense que ça doit être dans la définition de la contrainte où je me trompe puisque aucune contrainte ne fonctionne.

J'ai trouvé ce code pour un CVRP, Capacited Vehicle Routing Problem, j'ai essayé de définir exactement comme lui pour la capacité et ça ne fonctionne pas non plus.

Si vous avez des idées,

En vous souhaitant à tous une très bonne journée.

Stabilo.

[dourouc05]

Es-tu sûr que les contraintes sont bien prises en compte ? Tu peux générer un fichier LP et vérifier à la main (https://www.ibm.com/support/knowledg...to_lpfile.html).

Sinon, dans ton bloc de code, en plus de ta solution, affiche les deux membres des contraintes de capacité. Ça te donnera peut-être des indications…

[StabiloHB]

Bon ! eh bien après de lonnnngues heures j'ai débeugé tout ça !

Alors pour m'expliquer, je n'avais pas vraiment besoin de linéariser, la technique du implique que l'on avait évoqué plus haut fonctionne très bien. Il lui manquait juste des conditions initiales !!! eh oui cplex ne connaissait pas le poids qu'il y avait dans le véhicule à la sortie du dépôt alors il allait où c'était le plus pratique en l’occurrence, dans mon exemple, un delivery.
J'ai donc rajouté 2 contraintes (je ne suis pas sur que la deuxième soit vraiment utile)

Code :

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

1
2
forall (k in K)w[0][k]==0;
forall (k in K)w[2*n+1][k]==0;

Merci à toi de m'avoir aidé, j'ai pu voir tout ça dans le LP sheet. En effet, en plus de cette initialisation manquante, il semblerait que CPLEX n'aime pas trop quand on lui donne 2 contraintes en une je m'explique :
Cela fonctionne, on peut les retrouver dans le LP :

Code :

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

1
2
forall (i in N) forall (k in K) w[i][k]>=0;
forall (i in N)	forall (k in K) w[i][k]<=Q[k];

Mais pas comme ceci :

Code :

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

forall (i in N) forall (k in K) Q[k]>=w[i][k]>=0;

En sachant tout ça j'ai aussi modifié les autres contraintes en conséquence et miracle tout semble fonctionner.

Donc encore une fois je te remercie pour le temps que tu as passé à me répondre pour m'aiguiller et à réfléchir sur le problème.
Je vais maintenant m'amuser, avec un petit logiciel python, à créer un fichier excel de donnée car j'ai cru comprendre que CPLEX pouvait importer ses datas depuis un tableau excel.

Je mets bien évidemment le code OPL du Dial A Ride Problem pour monsieur le petit bonhomme du futur qui chercherait à résoudre ce genre de problème.
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/*********************************************
 * OPL 12.9.0.0 Model
 * Author: vjeandraud
 * Creation Date: 13 févr. 2020 at 13:37:14
 *********************************************/
//Data
int n = ...; 			//Number of clients
int V = ...;			//Number of vehicles
range P = 1..n; 		//Range of pickup
range N = 0..2*n+1; 	//Range of all nodes
range PD= 1..2*n;		//Range of nodes whitout depots
range K = 1..V;			//Range of vehicles
int Q[K]=...;			//Vehicle capacity
int q[N]=...;			//Load at node i
int e[N]=...;			//Earliest time bound 
int l[N]=...;			//Lastest time bound
int d[N]=...;			//Duration service at node i
int L=1000;				//Max ride time of a request
int T[K]=...;			//Max duration of route
float c[N][N]=...;		//Cost of traveling from node i to node j
float t[N][N]=...;		//Timde needed from node i to node j
 
//Decision variables
dvar boolean x[N][N][K];	//1 if the kth vehicle goes from i to j
dvar float u[N][K];			//Time at which k starts servicing i
dvar int+ w[N][K]; 		//Load of vehicle k after node i
dvar float r[P][K];			//the ride time of user i
 
//Objective function
minimize
  sum(k in K, i in N, j in N)
    c[i][j]*x[i][j][k];
 
//Constraints
subject to {
 
//Every request is served once	
	forall (i in P)	sum(k in K)sum(j in N) x[i][j][k]==1;
 
//Every vehicles leaves the start terminal	  	
  	forall (k in K)	sum(i in PD) x[0][i][k]==1;
 
//Every vehicles enters the end terminal	
	forall (k in K)	sum(i in PD) x[i][2*n+1][k]==1;
 
//Same vehicle services pickup and delivery    
	forall (i in P)	forall (k in K) (sum(j in N) x[i][j][k])-(sum(j in N) x[n+i][j][k])==0;
 
//Same vehicle that enters a node leaves the node
	forall (i in PD) forall (k in K) (sum(j in N) x[j][i][k])-(sum(j in N)x[i][j][k])==0;
 
//Setting and checking visit time    
	forall (i in N)	forall (j in N) forall (k in K) (x[i][j][k]==1) => (u[j][k]==(u[i][k]+d[i]+t[i][j]));     
	forall (i in N) forall (k in K) e[i]<=u[i][k];
	forall (i in N) forall (k in K) u[i][k]<=l[i];
	forall (k in K) u[2*n+1][k]-u[0][k]<=T[k];
	//init
	forall (k in K)u[0][k]==0;
 
//Setting and checking visit time
	forall (i in N)forall (k in K)e[i]<=u[i][k]<=l[i];
 
//Setting and checking vehicle load
	forall (i in N) forall (j in N) forall (k in K) (x[i][j][k]==1) => (w[j][k]==(w[i][k]+q[j]));
	forall (i in N) forall (k in K) w[i][k]>=0;
	forall (i in N)	forall (k in K) w[i][k]<=Q[k];
	//init
	forall (k in K)w[0][k]==0;
	forall (k in K)w[2*n+1][k]==0;
 
//Setting and checking ride time	
	forall (i in P)forall(k in K)r[i][k]==(u[n+i][k]-(u[i][k]+d[i]));
	forall (i in P)forall (k in K)t[i][n+i]<=r[i][k]<=L;
 
 
}
 
//print arc results
execute 					
{
for(var i in N)
	for(var j in N)
		for(var k in K)
			if (x[i][j][k]!=0)
				writeln("[",i,",",j,",",k,"]");
}

Datas :

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
/*********************************************
 * OPL 12.9.0.0 Data
 * Author: vjeandraud
 * Creation Date: 13 févr. 2020 at 15:04:42
 *********************************************/
 
//Data sheet
 
n=5;
d=[0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0];
q=[0, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 0];
V=1;
T=[10];
Q=[5];
e=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
l=[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000];
c=[[0.0, 4.123105625617661, 2.23606797749979, 1.4142135623730951, 1.4142135623730951, 3.605551275463989, 1.4142135623730951, 2.8284271247461903, 1.0, 4.47213595499958, 4.123105625617661, 2.0], [4.123105625617661, 0.0, 3.1622776601683795, 3.0, 3.0, 1.4142135623730951, 3.0, 3.605551275463989, 4.47213595499958, 1.0, 2.0, 4.123105625617661], [2.23606797749979, 3.1622776601683795, 0.0, 1.0, 1.0, 2.0, 1.0, 4.123105625617661, 3.1622776601683795, 3.0, 4.242640687119285, 1.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [3.605551275463989, 1.4142135623730951, 2.0, 2.23606797749979, 2.23606797749979, 0.0, 2.23606797749979, 4.123105625617661, 4.242640687119285, 1.0, 3.1622776601683795, 3.0], [1.4142135623730951, 3.0, 1.0, 0.0, 0.0, 2.23606797749979, 0.0, 3.1622776601683795, 2.23606797749979, 3.1622776601683795, 3.605551275463989, 1.4142135623730951], [2.8284271247461903, 3.605551275463989, 4.123105625617661, 3.1622776601683795, 3.1622776601683795, 4.123105625617661, 3.1622776601683795, 0.0, 2.23606797749979, 4.47213595499958, 2.23606797749979, 4.47213595499958], [1.0, 4.47213595499958, 3.1622776601683795, 2.23606797749979, 2.23606797749979, 4.242640687119285, 2.23606797749979, 2.23606797749979, 0.0, 5.0, 4.0, 3.0], [4.47213595499958, 1.0, 3.0, 3.1622776601683795, 3.1622776601683795, 1.0, 3.1622776601683795, 4.47213595499958, 5.0, 0.0, 3.0, 4.0], [4.123105625617661, 2.0, 4.242640687119285, 3.605551275463989, 3.605551275463989, 3.1622776601683795, 3.605551275463989, 2.23606797749979, 4.0, 3.0, 0.0, 5.0], [2.0, 4.123105625617661, 1.0, 1.4142135623730951, 1.4142135623730951, 3.0, 1.4142135623730951, 4.47213595499958, 3.0, 4.0, 5.0, 0.0]];
 
t=[[0.0, 61.84658438426491, 33.54101966249685, 21.213203435596427, 21.213203435596427, 54.08326913195984, 21.213203435596427, 42.42640687119285, 15.0, 67.0820393249937, 61.84658438426491, 30.0], [61.84658438426491, 0.0, 47.434164902525694, 45.0, 45.0, 21.213203435596427, 45.0, 54.08326913195984, 67.0820393249937, 15.0, 30.0, 61.84658438426491], [33.54101966249685, 47.434164902525694, 0.0, 15.0, 15.0, 30.0, 15.0, 61.84658438426491, 47.434164902525694, 45.0, 63.63961030678927, 15.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [54.08326913195984, 21.213203435596427, 30.0, 33.54101966249685, 33.54101966249685, 0.0, 33.54101966249685, 61.84658438426491, 63.63961030678927, 15.0, 47.434164902525694, 45.0], [21.213203435596427, 45.0, 15.0, 0.0, 0.0, 33.54101966249685, 0.0, 47.434164902525694, 33.54101966249685, 47.434164902525694, 54.08326913195984, 21.213203435596427], [42.42640687119285, 54.08326913195984, 61.84658438426491, 47.434164902525694, 47.434164902525694, 61.84658438426491, 47.434164902525694, 0.0, 33.54101966249685, 67.0820393249937, 33.54101966249685, 67.0820393249937], [15.0, 67.0820393249937, 47.434164902525694, 33.54101966249685, 33.54101966249685, 63.63961030678927, 33.54101966249685, 33.54101966249685, 0.0, 75.0, 60.0, 45.0], [67.0820393249937, 15.0, 45.0, 47.434164902525694, 47.434164902525694, 15.0, 47.434164902525694, 67.0820393249937, 75.0, 0.0, 45.0, 60.0], [61.84658438426491, 30.0, 63.63961030678927, 54.08326913195984, 54.08326913195984, 47.434164902525694, 54.08326913195984, 33.54101966249685, 60.0, 45.0, 0.0, 75.0], [30.0, 61.84658438426491, 15.0, 21.213203435596427, 21.213203435596427, 45.0, 21.213203435596427, 67.0820393249937, 45.0, 60.0, 75.0, 0.0]];

[dourouc05]

, c'est vraiment bien que tu aies trouvé ce qui bloque ! Et merci pour les suivants .