i hope you are all doing good, i have a problem in modelisation of the MDCVRP ( Multi Depot Capacitated Vehicle Routing Problem ) in the CPLEX Studio IDE 22.1.0, can anyone help me on that please ?
here is my mod and dat, when i click run the results appears, but the problem is that the used vehicule does not go back to their warehouses of origin, can anyone help me to fix that ?
Dat :
n = 9; // Total de clients + entrepôts
m = 3; // Nombre d'entrepôts
v = 4; // Nombre de véhicules disponibles
// Poids des commandes pour chaque client (inclut les entrepôts, avec ou sans commande)
PO = [0, 0, 0, 20, 30, 25, 15, 35, 40 ];
// Volume des commandes pour chaque client
VO = [0, 0, 0, 40, 50, 45, 35, 55, 60 ];
// Montant des commandes pour chaque client (0 indique pas de commande ou un entrepôt)
M = [0, 0, 0, 100, 150, 120, 130, 160, 180 ];
// Capacité de poids des véhicules
CPO = [100, 100, 80, 120 ];
// Capacité de volume des véhicules
CVO = [200, 220, 180, 240 ];
// Montant minimal des commandes pour démarrer les véhicules
MO = [300, 250, 200, 350 ];
// Distances entre les points (clients + entrepôts)
D = [
[0, 5, 8, 10, 15, 20, 25, 30, 35 ],
[5, 0, 7, 10, 15, 20, 25, 30, 35 ],
[8, 7, 0, 3, 8, 13, 18, 23, 28 ],
[10, 10, 3, 0, 5, 10, 15, 20, 25 ],
[15, 15, 8, 5, 0, 5, 10, 15, 20 ],
[20, 20, 13, 10, 5, 0, 5, 10, 15],
[25, 25, 18, 15, 10, 5, 0, 5, 10 ],
[30, 30, 23, 20, 15, 10, 5, 0, 5 ],
[35, 35, 28, 25, 20, 15, 10, 5, 0 ],
];
`Mod :
// Déclarations des ensembles et indices
int n = ...;
int m = ...;
int v = ...;
// Définition des ensembles et des plages
range Clients = 1..n; // Inclut les entrepôts et les clients
range Entrepots = 1..m; // Les premiers indices sont les entrepôts
range Vehicules = 1..v;
// Paramètres
int PO[Clients] = ...; // Poids des commandes pour chaque client
int VO[Clients] = ...; // Volume des commandes pour chaque client
int M[Clients] = ...; // Montant des commandes pour chaque client (0 pour ceux sans commande)
int CPO[Vehicules] = ...; // Capacité de poids des véhicules
int CVO[Vehicules] = ...; // Capacité de volume des véhicules
int MO[Vehicules] = ...; // Montant minimal des commandes pour le démarrage des véhicules
float D[Clients][Clients] = ...; // Distances entre les points
// Variables de décision
dvar boolean X[Clients][Clients][Vehicules]; // Si le véhicule k emprunte l'arc de i à j
dvar boolean U[Vehicules]; // Si le véhicule k est utilisé
dvar float+ W[Clients]; // Pour l'élimination des sous-tours
// Objectifs: Minimiser la distance totale parcourue et le nombre de véhicules utilisés
minimize
sum(i in Clients, j in Clients, k in Vehicules) D[i][j] * X[i][j][k];
Contraintes
// Contraintes
subject to {
// Capacité de poids et volume pour chaque véhicule
forall(k in Vehicules)
sum(i in Clients, j in Clients) PO[j] * X[i][j][k] <= CPO[k];
forall(k in Vehicules)
sum(i in Clients, j in Clients) VO[j] * X[i][j][k] <= CVO[k];
// Chaque client est servi exactement une fois, si il a une commande
forall(j in Clients : M[j] > 0)
sum(i in Clients, k in Vehicules) X[i][j][k] == 1;
// Coordination entre X[ijk] et U[k]
forall(i in Clients, j in Clients, k in Vehicules)
X[i][j][k] <= U[k];
// Élimination des sous-tours
forall(i in Clients, j in Clients : i != j, k in Vehicules)
W[i] - W[j] + n * X[i][j][k] <= n - 1;
// Chaque véhicule retourne à son entrepôt d'origine après les livraisons
forall(k in Vehicules)
sum(e in Entrepots) sum(i in Clients) X[i][e][k] == U[k];
// Empêcher les véhicules de se "servir eux-mêmes"
forall(i in Clients, k in Vehicules)
X[i][i][k] == 0;
// Contraintes de Flux
forall(j in Clients : j > m, k in Vehicules) // Pour tous les clients (sauf les entrepôts)
sum(i in Clients) X[i][j][k] == sum(i in Clients) X[j][i][k];
// s'assurer que chaque véhicule utilisé atteint le montant minimal des commandes avant de démarrer.
forall(k in Vehicules)
sum(i in Clients, j in Clients : M[j] > 0) M[j] * X[i][j][k] >= MO[k] * U[k];
}
Display function
// Affichage des résultats
execute {
for(var k in Vehicules) {
if (U[k].solutionValue > 0.5) {
writeln("Parcours pour le véhicule ", k, " :");
var distanceTotale = 0;
for(var i in Clients) {
for(var j in Clients) {
if (X[i][j][k].solutionValue > 0.5) {
writeln(" De ", i, " à ", j, ", distance : ", D[i][j]);
distanceTotale += D[i][j];
}
}
}
writeln("Distance totale parcourue par le véhicule ", k, " : ", distanceTotale, " unités.");
}
}
}
What I would do is use artificial nodes for arrival depots.
// Déclarations des ensembles et indices
int n = ...;
int m = ...;
int v = ...;
// Définition des ensembles et des plages
range Clients = 1..n; // Inclut les entrepôts et les clients
range Entrepots = 1..m; // Les premiers indices sont les entrepôts
range Vehicules = 1..v;
// Paramètres
int PO[Clients] = ...; // Poids des commandes pour chaque client
int VO[Clients] = ...; // Volume des commandes pour chaque client
int M[Clients] = ...; // Montant des commandes pour chaque client (0 pour ceux sans commande)
int CPO[Vehicules] = ...; // Capacité de poids des véhicules
int CVO[Vehicules] = ...; // Capacité de volume des véhicules
int MO[Vehicules] = ...; // Montant minimal des commandes pour le démarrage des véhicules
int D[Clients][Clients] = ...; // Distances entre les points
int n2=n+m;
int m2=2*m;
range Clients2=1..n2;
range Entrepots2=1..m2;
int PO2[c in Clients2]=(c <=m)?PO[c]:PO[c -m];
int VO2[c in Clients2]=(c <=m)?VO[c]:VO[c -m];
int D2[c1 in Clients2][c2 in Clients2] = D[(c1 <=m)?c1:(c1-m)][(c2 <=m)?c2:(c2-m)];
int M2[c in Clients2] = (c <=m)?M[c]:M[c -m];
// Variables de décision
dvar boolean X[Clients2][Clients2][Vehicules]; // Si le véhicule k emprunte l'arc de i à j
dvar boolean U[Vehicules]; // Si le véhicule k est utilisé
dvar int+ W[Clients2]; // Pour l'élimination des sous-tours
// Objectifs: Minimiser la distance totale parcourue et le nombre de véhicules utilisés
minimize
sum(i in Clients2, j in Clients2, k in Vehicules) D2[i][j] * X[i][j][k];
// Contraintes
subject to {
// Capacité de poids et volume pour chaque véhicule
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) PO2[j] * X[i][j][k] <= CPO[k];
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) VO2[j] * X[i][j][k] <= CVO[k];
// Chaque client est servi exactement une fois, si il a une commande
forall(j in Clients2 : M2[j] > 0)
sum(i in Clients2, k in Vehicules) X[i][j][k] == 1;
// Coordination entre X[ijk] et U[k]
forall(i in Clients2, j in Clients2, k in Vehicules)
X[i][j][k] <= U[k];
// Élimination des sous-tours
forall(i in Clients2, j in Clients2 : i != j, k in Vehicules)
W[i] - W[j] + n2 * X[i][j][k] <= n2 - 1;
// Chaque véhicule retourne à son entrepôt d'origine après les livraisons
forall(k in Vehicules)
sum(e in m+1..2*m) sum(i in Clients2) X[i][e][k] == U[k];
forall(k in Vehicules)
sum(e in 1..m) sum(i in Clients2) X[e][i][k] == U[k];
forall(k in Vehicules) forall(e in 1..m)
sum(i in 2*m+1..n2) X[i][e+m][k]==sum(i in Clients2) X[e][i][k];
// Empêcher les véhicules de se "servir eux-mêmes"
forall(i in Clients2, k in Vehicules)
X[i][i][k] == 0;
// Contraintes de Flux
forall(j in Clients2 : j > m2, k in Vehicules) // Pour tous les clients (sauf les entrepôts)
sum(i in Clients2) X[i][j][k] == sum(i in Clients2) X[j][i][k];
// s'assurer que chaque véhicule utilisé atteint le montant minimal des commandes avant de démarrer.
forall(k in Vehicules)
sum(i in Clients2, j in Clients2 : M2[j] > 0) M2[j] * X[i][j][k] >= MO[k] * U[k];
}
// Affichage des résultats
execute {
for(var k in Vehicules) {
if (U[k].solutionValue > 0.5) {
writeln("Parcours pour le véhicule ", k, " :");
var distanceTotale = 0;
for(var i in Clients2) {
for(var j in Clients2) {
if (X[i][j][k].solutionValue > 0.5) {
writeln(" De ",(i<=m)? i:(i-m), " à ", (j<=m)? j:(j-m), ", distance : ", D2[i][j]);
distanceTotale += D2[i][j];
}
}
}
writeln("Distance totale parcourue par le véhicule ", k, " : ", distanceTotale, " unités.");
}
}
}
which gives
// solution (optimal) with objective 72
Parcours pour le véhicule 3 :
De 3 à 5, distance : 8
De 4 à 3, distance : 3
De 5 à 4, distance : 5
Distance totale parcourue par le véhicule 3 : 16 unités.
Parcours pour le véhicule 4 :
De 3 à 6, distance : 13
De 6 à 9, distance : 15
De 7 à 3, distance : 18
De 8 à 7, distance : 5
De 9 à 8, distance : 5
Distance totale parcourue par le véhicule 4 : 56 unités.
Suppose you do not want to use depot 3
You can add
sum(j in Clients2, k in Vehicules) X[3][j][k] ==0;
sum(j in Clients2, k in Vehicules) X[j][3][k] ==0;
sum(j in Clients2, k in Vehicules) X[3+m][j][k] ==0;
sum(j in Clients2, k in Vehicules) X[j][3+m][k] ==0;
and then you get a cost that is not as good as the one before
// solution (optimal) with objective 100
Parcours pour le véhicule 3 :
De 1 à 4, distance : 10
De 4 à 5, distance : 5
De 5 à 1, distance : 15
Distance totale parcourue par le véhicule 3 : 30 unités.
Parcours pour le véhicule 4 :
De 1 à 6, distance : 20
De 6 à 9, distance : 15
De 7 à 1, distance : 25
De 8 à 7, distance : 5
De 9 à 8, distance : 5
Distance totale parcourue par le véhicule 4 : 70 unités.
And with your "one depot for each truck" you can add
forall(i in 1..n) sum(v in Vehicules,j in Clients2) X[i][j][v]<=1;
to the previous model and then you get
// solution (optimal) with objective 100
Parcours pour le véhicule 2 :
De 2 à 4, distance : 10
De 4 à 5, distance : 5
De 5 à 2, distance : 15
Distance totale parcourue par le véhicule 2 : 30 unités.
Parcours pour le véhicule 4 :
De 1 à 9, distance : 35
De 6 à 1, distance : 20
De 7 à 6, distance : 5
De 8 à 7, distance : 5
De 9 à 8, distance : 5
Distance totale parcourue par le véhicule 4 : 70 unités.
And with your new .dat
.mod
// Déclarations des ensembles et indices
int n = ...;
int m = ...;
int v = ...;
// Définition des ensembles et des plages
range Clients = 1..n; // Inclut les entrepôts et les clients
range Entrepots = 1..m; // Les premiers indices sont les entrepôts
range Vehicules = 1..v;
// Paramètres
int PO[Clients] = ...; // Poids des commandes pour chaque client
int VO[Clients] = ...; // Volume des commandes pour chaque client
int M[Clients] = ...; // Montant des commandes pour chaque client (0 pour ceux sans commande)
int CPO[Vehicules] = ...; // Capacité de poids des véhicules
int CVO[Vehicules] = ...; // Capacité de volume des véhicules
int MO[Vehicules] = ...; // Montant minimal des commandes pour le démarrage des véhicules
int D[Clients][Clients] = ...; // Distances entre les points
int n2=n+m;
int m2=2*m;
range Clients2=1..n2;
range Entrepots2=1..m2;
int PO2[c in Clients2]=(c <=m)?PO[c]:PO[c -m];
int VO2[c in Clients2]=(c <=m)?VO[c]:VO[c -m];
int D2[c1 in Clients2][c2 in Clients2] = D[(c1 <=m)?c1:(c1-m)][(c2 <=m)?c2:(c2-m)];
int M2[c in Clients2] = (c <=m)?M[c]:M[c -m];
// Variables de décision
dvar boolean X[Clients2][Clients2][Vehicules]; // Si le véhicule k emprunte l'arc de i à j
dvar boolean U[Vehicules]; // Si le véhicule k est utilisé
dvar int+ W[Clients2]; // Pour l'élimination des sous-tours
// Objectifs: Minimiser la distance totale parcourue et le nombre de véhicules utilisés
minimize
sum(i in Clients2, j in Clients2, k in Vehicules) D2[i][j] * X[i][j][k];
// Contraintes
subject to {
sum(j in Clients2, k in Vehicules) X[3][j][k] ==0;
sum(j in Clients2, k in Vehicules) X[j][3][k] ==0;
sum(j in Clients2, k in Vehicules) X[3+m][j][k] ==0;
sum(j in Clients2, k in Vehicules) X[j][3+m][k] ==0;
forall(i in 1..n) sum(v in Vehicules,j in Clients2) X[i][j][v]<=1;
// Capacité de poids et volume pour chaque véhicule
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) PO2[j] * X[i][j][k] <= CPO[k];
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) VO2[j] * X[i][j][k] <= CVO[k];
// Chaque client est servi exactement une fois, si il a une commande
forall(j in Clients2 : M2[j] > 0)
sum(i in Clients2, k in Vehicules) X[i][j][k] == 1;
// Coordination entre X[ijk] et U[k]
forall(i in Clients2, j in Clients2, k in Vehicules)
X[i][j][k] <= U[k];
// Élimination des sous-tours
forall(i in Clients2, j in Clients2 : i != j, k in Vehicules)
W[i] - W[j] + n2 * X[i][j][k] <= n2 - 1;
// Chaque véhicule retourne à son entrepôt d'origine après les livraisons
forall(k in Vehicules)
sum(e in m+1..2*m) sum(i in Clients2) X[i][e][k] == U[k];
forall(k in Vehicules)
sum(e in 1..m) sum(i in Clients2) X[e][i][k] == U[k];
forall(k in Vehicules) forall(e in 1..m)
sum(i in 2*m+1..n2) X[i][e+m][k]==sum(i in Clients2) X[e][i][k];
// Empêcher les véhicules de se "servir eux-mêmes"
forall(i in Clients2, k in Vehicules)
X[i][i][k] == 0;
// Contraintes de Flux
forall(j in Clients2 : j > m2, k in Vehicules) // Pour tous les clients (sauf les entrepôts)
sum(i in Clients2) X[i][j][k] == sum(i in Clients2) X[j][i][k];
// s'assurer que chaque véhicule utilisé atteint le montant minimal des commandes avant de démarrer.
forall(k in Vehicules)
sum(i in Clients2, j in Clients2 : M2[j] > 0) M2[j] * X[i][j][k] >= MO[k] * U[k];
}
// Affichage des résultats
execute {
for(var k in Vehicules) {
if (U[k].solutionValue > 0.5) {
writeln("Parcours pour le véhicule ", k, " :");
var distanceTotale = 0;
for(var i in Clients2) {
for(var j in Clients2) {
if (X[i][j][k].solutionValue > 0.5) {
writeln(" De ",(i<=m)? i:(i-m), " à ", (j<=m)? j:(j-m), ", distance : ", D2[i][j]);
distanceTotale += D2[i][j];
}
}
}
writeln("Distance totale parcourue par le véhicule ", k, " : ", distanceTotale, " unités.");
}
}
}
and
.dat
n = 12; m = 3; v = 6;
PO = [0, 0, 0, 15, 25, 20, 10, 30, 35, 5, 15, 20];
VO = [0, 0, 0, 30, 40, 35, 25, 45, 50, 15, 30, 35];
M = [0, 0, 0, 80, 120, 100, 110, 140, 160, 60, 90, 100];
CPO = [90, 110, 100, 120, 130, 80];
CVO = [180, 200, 190, 220, 240, 150];
MO = [200, 150, 180, 250, 220, 170];
D = [[ 0, 42, 55, 60, 60, 8, 72, 18, 30, 50, 75, 80], [42, 0, 68, 68, 10, 50, 55, 30, 70, 45, 30, 35], [55, 68, 0, 30, 20, 65, 60, 8, 15, 65, 75, 10], [60, 68, 30, 0, 55, 70, 68, 40, 25, 20, 60, 40],[60, 10, 20, 55, 0, 50, 8, 58, 33, 70, 15, 20],[8, 50, 65, 70, 50, 0, 25, 30, 5, 60, 80, 65],[72, 55, 60, 68, 8, 25, 0, 5, 45, 25, 15, 25],[18, 30, 8, 40, 58, 30, 5, 0, 42, 68, 10, 25],[30, 70, 15, 25, 33, 5, 45, 42, 0, 50, 85, 80],[50, 45, 65, 20, 70, 60, 25, 68, 50, 0, 60, 45],[75, 30, 75, 60, 15, 80, 15, 10, 85, 60, 0, 35],[80, 35, 10, 40, 20, 65, 25, 25, 80, 45, 35, 0]];
gives
// solution (optimal) with objective 191
Parcours pour le véhicule 2 :
De 2 à 12, distance : 35
De 5 à 2, distance : 10
De 12 à 5, distance : 20
Distance totale parcourue par le véhicule 2 : 65 unités.
Parcours pour le véhicule 5 :
De 1 à 6, distance : 8
De 4 à 10, distance : 20
De 6 à 9, distance : 5
De 7 à 11, distance : 15
De 8 à 1, distance : 18
De 9 à 4, distance : 25
De 10 à 7, distance : 25
De 11 à 8, distance : 10
Distance totale parcourue par le véhicule 5 : 126 unités.
If you allow the warehouse 3 then you have .mod
// Déclarations des ensembles et indices
int n = ...;
int m = ...;
int v = ...;
// Définition des ensembles et des plages
range Clients = 1..n; // Inclut les entrepôts et les clients
range Entrepots = 1..m; // Les premiers indices sont les entrepôts
range Vehicules = 1..v;
// Paramètres
int PO[Clients] = ...; // Poids des commandes pour chaque client
int VO[Clients] = ...; // Volume des commandes pour chaque client
int M[Clients] = ...; // Montant des commandes pour chaque client (0 pour ceux sans commande)
int CPO[Vehicules] = ...; // Capacité de poids des véhicules
int CVO[Vehicules] = ...; // Capacité de volume des véhicules
int MO[Vehicules] = ...; // Montant minimal des commandes pour le démarrage des véhicules
int D[Clients][Clients] = ...; // Distances entre les points
int n2=n+m;
int m2=2*m;
range Clients2=1..n2;
range Entrepots2=1..m2;
int PO2[c in Clients2]=(c <=m)?PO[c]:PO[c -m];
int VO2[c in Clients2]=(c <=m)?VO[c]:VO[c -m];
int D2[c1 in Clients2][c2 in Clients2] = D[(c1 <=m)?c1:(c1-m)][(c2 <=m)?c2:(c2-m)];
int M2[c in Clients2] = (c <=m)?M[c]:M[c -m];
// Variables de décision
dvar boolean X[Clients2][Clients2][Vehicules]; // Si le véhicule k emprunte l'arc de i à j
dvar boolean U[Vehicules]; // Si le véhicule k est utilisé
dvar int+ W[Clients2]; // Pour l'élimination des sous-tours
// Objectifs: Minimiser la distance totale parcourue et le nombre de véhicules utilisés
minimize
sum(i in Clients2, j in Clients2, k in Vehicules) D2[i][j] * X[i][j][k];
// Contraintes
subject to {
// sum(j in Clients2, k in Vehicules) X[3][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][3][k] ==0;
// sum(j in Clients2, k in Vehicules) X[3+m][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][3+m][k] ==0;
forall(i in 1..n) sum(v in Vehicules,j in Clients2) X[i][j][v]<=1;
forall(i in 1..m,k in Vehicules) forall(j in Clients2) X[i][j][k]+X[j][i+m][k]<=1;
// Capacité de poids et volume pour chaque véhicule
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) PO2[j] * X[i][j][k] <= CPO[k];
forall(k in Vehicules)
sum(i in Clients2, j in Clients2) VO2[j] * X[i][j][k] <= CVO[k];
// Chaque client est servi exactement une fois, si il a une commande
forall(j in Clients2 : M2[j] > 0)
sum(i in Clients2, k in Vehicules) X[i][j][k] == 1;
// Coordination entre X[ijk] et U[k]
forall(i in Clients2, j in Clients2, k in Vehicules)
X[i][j][k] <= U[k];
// Élimination des sous-tours
forall(i in Clients2, j in Clients2 : i != j, k in Vehicules)
W[i] - W[j] + n2 * X[i][j][k] <= n2 - 1;
// Chaque véhicule retourne à son entrepôt d'origine après les livraisons
forall(k in Vehicules)
sum(e in m+1..2*m) sum(i in Clients2) X[i][e][k] == U[k];
forall(k in Vehicules)
sum(e in 1..m) sum(i in Clients2) X[e][i][k] == U[k];
forall(k in Vehicules) forall(e in 1..m)
sum(i in 2*m+1..n2) X[i][e+m][k]==sum(i in Clients2) X[e][i][k];
// Empêcher les véhicules de se "servir eux-mêmes"
forall(i in Clients2, k in Vehicules)
X[i][i][k] == 0;
// Contraintes de Flux
forall(j in Clients2 : j > m2, k in Vehicules) // Pour tous les clients (sauf les entrepôts)
sum(i in Clients2) X[i][j][k] == sum(i in Clients2) X[j][i][k];
// s'assurer que chaque véhicule utilisé atteint le montant minimal des commandes avant de démarrer.
forall(k in Vehicules)
sum(i in Clients2, j in Clients2 : M2[j] > 0) M2[j] * X[i][j][k] >= MO[k] * U[k];
}
// Affichage des résultats
execute {
for(var k in Vehicules) {
if (U[k].solutionValue > 0.5) {
writeln("Parcours pour le véhicule ", k, " :");
var distanceTotale = 0;
for(var i in Clients2) {
for(var j in Clients2) {
if (X[i][j][k].solutionValue > 0.5) {
writeln(" De ",(i<=m)? i:(i-m), " à ", (j<=m)? j:(j-m), ", distance : ", D2[i][j]);
distanceTotale += D2[i][j];
}
}
}
writeln("Distance totale parcourue par le véhicule ", k, " : ", distanceTotale, " unités.");
}
}
}
which gives
// solution (optimal) with objective 176
Parcours pour le véhicule 1 :
De 3 à 5, distance : 20
De 5 à 12, distance : 20
De 12 à 3, distance : 10
Distance totale parcourue par le véhicule 1 : 50 unités.
Parcours pour le véhicule 5 :
De 1 à 8, distance : 18
De 4 à 9, distance : 25
De 6 à 1, distance : 8
De 7 à 10, distance : 25
De 8 à 11, distance : 10
De 9 à 6, distance : 5
De 10 à 4, distance : 20
De 11 à 7, distance : 15
Distance totale parcourue par le véhicule 5 : 126 unités.
To end the discussion
.mod
// Déclarations des ensembles et indices
int n = ...;
int m = ...;
int v = ...;
// Définition des ensembles et des plages
range Clients = 1..n; // Inclut les entrepôts et les clients
range Entrepots = 1..m; // Les premiers indices sont les entrepôts
range Vehicules = 1..v;
// Paramètres
int PO[Clients] = ...; // Poids des commandes pour chaque client
int VO[Clients] = ...; // Volume des commandes pour chaque client
int M[Clients] = ...; // Montant des commandes pour chaque client (0 pour ceux sans commande)
int CPO[Vehicules] = ...; // Capacité de poids des véhicules
int CVO[Vehicules] = ...; // Capacité de volume des véhicules
int MO[Vehicules] = ...; // Montant minimal des commandes pour le démarrage des véhicules
int D[Clients][Clients] = ...; // Distances entre les points
int n2=n+m;
int m2=2*m;
range Clients2=1..n2;
range Entrepots2=1..m2;
int PO2[c in Clients2]=(c <=m)?PO[c]:PO[c -m];
int VO2[c in Clients2]=(c <=m)?VO[c]:VO[c -m];
int D2[c1 in Clients2][c2 in Clients2] = D[(c1 <=m)?c1:(c1-m)][(c2 <=m)?c2:(c2-m)];
int M2[c in Clients2] = (c <=m)?M[c]:M[c -m];
// Variables de décision
dvar boolean X[Clients2][Clients2][Vehicules]; // Si le véhicule k emprunte l'arc de i à j
dvar boolean U[Vehicules]; // Si le véhicule k est utilisé
dvar int+ W[Clients2]; // Pour l'élimination des sous-tours
// Objectifs: Minimiser la distance totale parcourue et le nombre de véhicules utilisés
minimize
sum(i in Clients2, j in Clients2, k in Vehicules) D2[i][j] * X[i][j][k];
// Contraintes
subject to {
// sum(j in Clients2, k in Vehicules) X[3][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][3][k] ==0;
// sum(j in Clients2, k in Vehicules) X[3+m][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][3+m][k] ==0;
//
// sum(j in Clients2, k in Vehicules) X[2][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][2][k] ==0;
// sum(j in Clients2, k in Vehicules) X[2+m][j][k] ==0;
// sum(j in Clients2, k in Vehicules) X[j][2+m][k] ==0;
forall(j in Clients2 : (M2[j] == 0) && (j>2*m)) sum(i in Clients2, k in Vehicules) X[i][j][k] == 0;
//forall(i in 1..n) ct1:sum(v in Vehicules,j in Clients2) X[i][j][v]<=1;
//forall(i in 1..m,k in Vehicules) forall(j in Clients2) ct2:X[i][j][k]+X[j][i+m][k]<=1;
//forall(k in Vehicules) sum(i in 1..m,j in Clients2)
// X[i][j][v]<=1;
// Capacité de poids et volume pour chaque véhicule
forall(k in Vehicules)
ct3:sum(i in Clients2, j in Clients2) PO2[j] * X[i][j][k] <= CPO[k];
forall(k in Vehicules)
ct4:sum(i in Clients2, j in Clients2) VO2[j] * X[i][j][k] <= CVO[k];
// Chaque client est servi exactement une fois, si il a une commande
forall(j in Clients2 : M2[j] > 0)
ct5:sum(i in Clients2, k in Vehicules) X[i][j][k] == 1;
// Coordination entre X[ijk] et U[k]
forall(i in Clients2, j in Clients2, k in Vehicules)
ct6:X[i][j][k] <= U[k];
// Élimination des sous-tours
forall(i in Clients2, j in Clients2 : i != j, k in Vehicules)
ct7:W[i] - W[j] + n2 * X[i][j][k] <= n2 - 1;
// Chaque véhicule retourne à son entrepôt d'origine après les livraisons
forall(k in Vehicules)
ct8:sum(e in m+1..2*m) sum(i in Clients2) X[i][e][k] == U[k];
forall(k in Vehicules)
ct9:sum(e in 1..m) sum(i in Clients2) X[e][i][k] == U[k];
forall(k in Vehicules) forall(e in 1..m)
ct10:sum(i in 2*m+1..n2) X[i][e+m][k]==sum(i in Clients2) X[e][i][k];
// Empêcher les véhicules de se "servir eux-mêmes"
forall(i in Clients2, k in Vehicules)
ct11:X[i][i][k] == 0;
// Contraintes de Flux
forall(j in Clients2 : j > m2, k in Vehicules) // Pour tous les clients (sauf les entrepôts)
ct12:sum(i in Clients2) X[i][j][k] == sum(i in Clients2) X[j][i][k];
// s'assurer que chaque véhicule utilisé atteint le montant minimal des commandes avant de démarrer.
forall(k in Vehicules)
ct13:sum(i in Clients2, j in Clients2 : M2[j] > 0) M2[j] * X[i][j][k] >= MO[k] * U[k];
}
// Affichage des résultats
execute {
for(var k in Vehicules) {
if (U[k].solutionValue > 0.5) {
writeln("Parcours pour le véhicule ", k, " :");
var distanceTotale = 0;
for(var i in Clients2) {
for(var j in Clients2) {
if (X[i][j][k].solutionValue > 0.5) {
writeln(" De ",(i<=m)? i:(i-m), " à ", (j<=m)? j:(j-m), ", distance : ", D2[i][j]);
distanceTotale += D2[i][j];
}
}
}
writeln("Distance totale parcourue par le véhicule ", k, " : ", distanceTotale, " unités.");
}
}
}
.dat
n = 12; m = 3; v = 6;
PO = [0,0,0,15,25,20,10,12,0,0,0,0];
VO=[0,0,0,30, 40,35,20,13,0,0,0,0]; M=[0,0,0,80,120,100,30,14,0,0,0,0];CPO=[15,25,20,10,12,0]; CVO = [30,40,35,20,13,0];
MO=[80,120,100,30,14,0];
D = [[ 0, 42, 55, 60, 60, 8, 72, 18, 30, 50, 75, 80], [42, 0, 68, 68, 10, 50, 55, 30, 70, 45, 30, 35], [55, 68, 0, 30, 20, 65, 60, 8, 15, 65, 75, 10], [60, 68, 30, 0, 55, 70, 68, 40, 25, 20, 60, 40],[60, 10, 20, 55, 0, 50, 8, 58, 33, 70, 15, 20],[8, 50, 65, 70, 50, 0, 25, 30, 5, 60, 80, 65],[72, 55, 60, 68, 8, 25, 0, 5, 45, 25, 15, 25],[18, 30, 8, 40, 58, 30, 5, 0, 42, 68, 10, 25],[30, 70, 15, 25, 33, 5, 45, 42, 0, 50, 85, 80],[50, 45, 65, 20, 70, 60, 25, 68, 50, 0, 60, 45],[75, 30, 75, 60, 15, 80, 15, 10, 85, 60, 0, 35],[80, 35, 10, 40, 20, 65, 25, 25, 80, 45, 35, 0]];
gives
// solution (optimal) with objective 222
Parcours pour le véhicule 1 :
De 3 à 4, distance : 30
De 4 à 3, distance : 30
Distance totale parcourue par le véhicule 1 : 60 unités.
Parcours pour le véhicule 2 :
De 2 à 5, distance : 10
De 5 à 2, distance : 10
Distance totale parcourue par le véhicule 2 : 20 unités.
Parcours pour le véhicule 3 :
De 1 à 6, distance : 8
De 6 à 1, distance : 8
Distance totale parcourue par le véhicule 3 : 16 unités.
Parcours pour le véhicule 4 :
De 2 à 7, distance : 55
De 7 à 2, distance : 55
Distance totale parcourue par le véhicule 4 : 110 unités.
Parcours pour le véhicule 5 :
De 3 à 8, distance : 8
De 8 à 3, distance : 8
Distance totale parcourue par le véhicule 5 : 16 unités.