Pinned topic VRP model
I am trying to model a VRP for solving the en13 instance. I am new in this, so sorry if the question is BASIC.
I wanna to create the constraint for maximum load.
cap = 600000;
demand = 0, 1200, 1700, 1500, 1400, 1700, 1400, 1200, 1900, 1800, 1600, 1700, 1100;
With this data I wanna do something like that:
// Cities
int n = ...;
range Cities = 1..n;
int demandCities= ...;
// Edges  sparse set
tuple edge {int i; int j;}
{edge} Edges = {<i,j>  ordered i,j in Cities};
int distEdges = ...;
// Vehicles
int cap = ...;
// Decision variables
dvar boolean xEdges;
forall (j in Cities)
total_load = sum (<i,j> in Edges) x<i,j>*d[i] <= cap;
// The vehicle is not overload
total_load <= cap;
But I am really lost with the last part, I want to have an int which sum every demand of each city I use for the route, and then compare this with the maximum load.
Thank you!

Re: VRP model
20130225T15:51:15ZThis is the accepted answer. This is the accepted answer.I think I have almost the model, but I don't know how to do the max.capacity constraint and if the k vehicles will run ok with this model, if someone could give me someadvice for that it would be great!
This is the data:
/*********************************************
* OPL 12.4 Data
* Author: Iván
* Creation Date: 25/02/2013 at 14:16:04
*********************************************/
n = 13;
v = 5;
cap = 6000;
demand = 0, 1200, 1700, 1500, 1400, 1700, 1400, 1200, 1900, 1800, 1600, 1700, 1100;
dist =[
9 14 21 23 22 25 32 36 38 42 50 52
5 12 22 21 24 31 35 37 41 49 51
7 17 16 23 26 30 36 36 44 46
10 21 30 27 37 43 31 37 39
19 28 25 35 51 29 31 29
9 10 16 22 20 28 30
7 11 13 17 25 27
10 16 10 18 20
6 6 14 16
12 12 20
8 10
10
];Attachments

Re: VRP model
20130226T08:47:53ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130225T15:51:15Z
I think I have almost the model, but I don't know how to do the max.capacity constraint and if the k vehicles will run ok with this model, if someone could give me someadvice for that it would be great!
This is the data:
/*********************************************
* OPL 12.4 Data
* Author: Iván
* Creation Date: 25/02/2013 at 14:16:04
*********************************************/
n = 13;
v = 5;
cap = 6000;
demand = 0, 1200, 1700, 1500, 1400, 1700, 1400, 1200, 1900, 1800, 1600, 1700, 1100;
dist =[
9 14 21 23 22 25 32 36 38 42 50 52
5 12 22 21 24 31 35 37 41 49 51
7 17 16 23 26 30 36 36 44 46
10 21 30 27 37 43 31 37 39
19 28 25 35 51 29 31 29
9 10 16 22 20 28 30
7 11 13 17 25 27
10 16 10 18 20
6 6 14 16
12 12 20
8 10
10
];
subject to {
forall (j in Cities)
sum (e in Edges : e.j == j) x[e]*d[e] <= cap;
} 
Re: VRP model
20130226T19:23:09ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130226T08:47:53Z
Not sure I understand exactly what you are trying to model... may be try in this direction
subject to {
forall (j in Cities)
sum (e in Edges : e.j == j) x[e]*d[e] <= cap;
}
I am trying to modelize a CVRP. 5 (as maximum) vehicles with 6000 of capacity. Each vehicle travels nodes til you have to avoid exceeding its capacity, then they return to the depot and starts the next.
Clarify this the model I am trying?
Your sugestion gives me an error. What is e.j==j exactly meaning? 
Re: VRP model
20130227T08:59:40ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130226T19:23:09Z
Thank you for your answer.
I am trying to modelize a CVRP. 5 (as maximum) vehicles with 6000 of capacity. Each vehicle travels nodes til you have to avoid exceeding its capacity, then they return to the depot and starts the next.
Clarify this the model I am trying?
Your sugestion gives me an error. What is e.j==j exactly meaning? 
Re: VRP model
20130227T18:34:57ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130227T08:59:40Z
Check that your variables names are the same. e.g. "d" against "dist". Expression e.j == j means that the sum is only by e which fits that criterion.
I fix that, but I get an error CPLEX status = 5002.
I think my main problem is model the utilitation of vehicles, as a vehicle return tu depot when it is plenty and then k=k++.
Noone has an example of VRP with cplex? http://en.wikipedia.org/wiki/Vehicle_routing_problem . I just wanna the simple one, with capacity constraint, and I see people asking about problems with VRP more complex than this.
Thank you! 
Re: VRP model
20130228T08:04:54ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130227T18:34:57Z
Ok, I understand.
I fix that, but I get an error CPLEX status = 5002.
I think my main problem is model the utilitation of vehicles, as a vehicle return tu depot when it is plenty and then k=k++.
Noone has an example of VRP with cplex? http://en.wikipedia.org/wiki/Vehicle_routing_problem . I just wanna the simple one, with capacity constraint, and I see people asking about problems with VRP more complex than this.
Thank you!
http://en.wikipedia.org/wiki/Travelling_salesman_problem
int NCity = ...;
range RCity = 1..NCity;
int MAX_LOOPS = ...;
tuple Edge {key int src; key int tgt; int weight;}
{Edge} raw_edges = ...;
int edges src in RCitytgt in RCity;
execute {
for (var e in raw_edges) {
edgeshttp://e.srchttp://e.tgt = e.weight;
}
}
assert
forall (t in RCity)
forall (s in 1..t)
edges[t][s] == edges[s][t];
dvar int uhttp://2..NCity in 2..NCity;
dvar boolean actRCityRCity;
minimize sum(t in RCity, s in RCity) edges[t][s] * act[t][s];
subject to {
forall (t in RCity) {
sum (s in RCity) act[t][s] == 1;
sum (s in RCity) act[s][t] == 1;
act[t][t] == 0;
}
forall (t in 2..NCity) {
forall (s in 2..NCity) {
u[t]  u[s] + 1 <= (NCity  1) * (1  act[t][s]);
}
}
}
Regards,
Zahar 
Re: VRP model
20130228T14:01:23ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130228T08:04:54Z
I have a TSP model, it is related. You may start from it and make the necessary changes.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
int NCity = ...;
range RCity = 1..NCity;
int MAX_LOOPS = ...;
tuple Edge {key int src; key int tgt; int weight;}
{Edge} raw_edges = ...;
int edges src in RCitytgt in RCity;
execute {
for (var e in raw_edges) {
edgeshttp://e.srchttp://e.tgt = e.weight;
}
}
assert
forall (t in RCity)
forall (s in 1..t)
edges[t][s] == edges[s][t];
dvar int uhttp://2..NCity in 2..NCity;
dvar boolean actRCityRCity;
minimize sum(t in RCity, s in RCity) edges[t][s] * act[t][s];
subject to {
forall (t in RCity) {
sum (s in RCity) act[t][s] == 1;
sum (s in RCity) act[s][t] == 1;
act[t][t] == 0;
}
forall (t in 2..NCity) {
forall (s in 2..NCity) {
u[t]  u[s] + 1 <= (NCity  1) * (1  act[t][s]);
}
}
}
Regards,
Zahar
Thank you for your answer and model.
I have already a TSP model working, and with good optimal results with instances, but I still don't know how to obtain a basic CVRP. The main problem, I think, is make an if, or something similar, that allow the model to use a vehicle til is is plenty, and then add 1 to the counter and start again from depot, but remembering the nodes already visited, of course. If someone has one of this or anyone wanna try to modelize one with me would be great!!
I like your model for tsp but I get an error in your subtour elimination ecuation :
u[t]  u[s] + 1 <= (NCity  1) * (1  act[t][s]);
maybe because the writing fails os this forum and misstranslate something bad.
Have you got some data for lunch it and see if it faster than mine? Thank you :D 
Re: VRP model
20130228T14:14:06ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130228T14:01:23Z
Hi zahar,
Thank you for your answer and model.
I have already a TSP model working, and with good optimal results with instances, but I still don't know how to obtain a basic CVRP. The main problem, I think, is make an if, or something similar, that allow the model to use a vehicle til is is plenty, and then add 1 to the counter and start again from depot, but remembering the nodes already visited, of course. If someone has one of this or anyone wanna try to modelize one with me would be great!!
I like your model for tsp but I get an error in your subtour elimination ecuation :
u[t]  u[s] + 1 <= (NCity  1) * (1  act[t][s]);
maybe because the writing fails os this forum and misstranslate something bad.
Have you got some data for lunch it and see if it faster than mine? Thank you :D 
Re: VRP model
20130303T09:30:05ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130228T14:14:06Z
Oh, and the error was that it is a not matrix :) 
Re: VRP model
20130630T15:31:50ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130303T09:30:05Z
This constraint in TSP is called MTZ constraint (initials of the people who first found it). I think it is the fastest model for TSP, you can check on your data.please i need your help, i am trying to resolve pickup and delivery problem with preemption and i can't do it
/********************************************** OPL 12.3 Model* Author: HENI* Creation Date: 13 juin 2013 at 12:01:47*********************************************/int M=30000;//tuplestuple indnoeud{float i;}tuple inddepot{float i;}tuple indcltfrs{float i;}tuple indfrs{float i;}tuple indclt{float i;}tuple indveh{float v;}tuple inddek{float k;}tuple oriddek{float k;float i;}tuple desddek{float k;float i;}tuple qtiteddek{float k;float quantite;}tuple coutveh{float v;float coutvehicule;}tuple capv{float v;float capacite;}tuple distance{float i;float j;float valeur;}tuple time{float i;float j;float temp;}tuple segplus{float n;float s;}tuple segmoins{float n;float e;}{indnoeud}I=...;//{indnoeud2}J=...;{inddepot}ID=...;{indcltfrs}ICF=...;{indfrs}IFR=...;{indclt}ICL=...;{indveh}V=...;{inddek}K=...;{oriddek}OK=...;{desddek}DK=...;{qtiteddek}qK=...;{coutveh}CV=...;{capv}QV=...;{distance}DIJ=...;{time}TIJ=...;{segplus}SEGP=...;{segmoins}SEGM=...;//définition des indices{float} Is={i<i> in I};{float} Js={j<j> in I};{float} Ss={s<s> in I};{float} IDs={i<i> in ID};{float} Ks={k<k> in K};{float} Vs={v<v> in V};{float} ICFs={i<i> in ICF};{float} IFRs={i<i> in IFR};{float} ICLs={i<i> in ICL};//{string} OKs={i<i> in OK};//{string} DKs={i<i> in DK};//définition des paramètresfloat qKs[Ks];float QVs[Vs];float SEGPs[Is];float SEGMs[Is];float F0v[Vs]=0;float CVs [Vs];float OKs [Ks];float DKs [Ks];float DIJs [Is][Js];float TIJs [Is][Js];//float TPs[Ps];//float QVs[Vs];// float CTkpjs[Js][Kps];//lire les paramètresexecute {for (var ook in OK){OKs[ook.k]=ook.i;}}execute {for (var ddk in DK){DKs[ddk.k]=ddk.i;}}execute {for (var nnn in SEGP){SEGPs[nnn.n]=nnn.s;}}//execute {//for (var mmm in SEGM){//SEGMs[mmm.n]=mmm.e;//}//}execute {for (var jjj in TIJ){TIJs[jjj.i][jjj.j]=jjj.temp;}}execute {for (var iii in DIJ){DIJs[iii.i][iii.j]=iii.valeur;}}execute {for (var Ks in qK){qKs[Ks.k]=Ks.quantite;}}execute {for (var Vs in QV){QVs[Vs.v]=Vs.capacite;}}execute {for (var Vs in CV){CVs[Vs.v]=Vs.coutvehicule;}}//*************************************decision variables*********************************************************dvar int+ Yijvk[Is,Vs,Ks] in 0..1;dvar int+ Xijv[Is,Vs] in 0..1;//*****************************************constraint naming**************************************.constraint c1;constraint c2;constraint c3;constraint c4;constraint c5;constraint c6;constraint c7;constraint c8;constraint c9;constraint c10;constraint c11;constraint c12;constraint c13;constraint c14;//*******************************MODEL*********************************************************dexpr float Cobj= sum (v in Vs, i in Is, j in Js)(CVs[v]*DIJs[i,j]*Xijv[i,j,v]);//fonction objectif : min coût de transportminimize sum (v in Vs, i in Is, j in Js)(CVs[v]*DIJs[i,j]*Xijv[i,j,v]);subject to{// contraintes de gestion de stocksc1= forall (i in ICFs)sum (v in Vs, j in SEGPs[i][2])Xijv[i,j,v]==1;c2 = forall (i in ICFs)sum (v in Vs, j in SEGMs[i][2])Xjiv[i,j,v]==1;// contrainte des veh au depotc3 = forall (v in Vs)sum(i in SEGPs [0][2])Xi0v[i,0,v]==1;c4= forall (v in Vs)sum (i in SEGMs[0][2])X0iv[o,i,v]==1;/// sommet visité doit imperativement etre quittéc5= forall (i in ICFs, v in Vs)sum (j in SEGPs[i][2]) Xijv[i,j,v]  sum (j in SEGMs[i][2]) Xjiv[i,j,v] ==0;// conservation des flot: permet transbordement//c6= forall ((k in Ks ,i in ICFs: i!= OKs) AND (i!= DKs))c6= forall (k in Ks ,i in ICFs: i!= OKs, i in ICFs:i!= DKs)sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] ==0;c7= forall (k in Ks, i in OKs)sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] == 1;c8= forall (k in Ks, i in DKs)sum (v in Vs, j in SEGPs[i][2]) Yijvk[i,j,v,k]sum (v in Vs, j in SEGMs[i][2])Yjivk[i,j,v,k] == 1;/// respect capacitec9= forall (i in Is, j in Js, v in Vs)sum (k in Ks) Yijvk[i,j,v,k]*qKs[k] <= QVs[v]*Xijv[i,j,v];c10= forall (i in ICFs, v in Vs, k in Ks)Y0iv[i,j,v] == Yi0v[i,j,v] ==0;// passage sur un arc sans transporter une demandec11= forall (i in Is, j in Js, v in Vs, k in Ks)Yijvk[i,j,v,k]<= Xijv[i,j,v];// contrainte elemination des sous toursc12 = forall (i in Is, j in Js, v in Vs)Xijv[i,j,v] == 1 => Fiv[i,v] + TIJs[i,j,v] <= Fjv[j,v];c13= forall (v in Vs, i in IFRs, j in ICLs)Fiv[i,v] <= Fjv[j,v];c14 = forall ( v in Vs)F0v[v] == 0;}}execute {writeln ("objectif=", Cobj)} 
Re: VRP model
20150112T16:01:13ZThis is the accepted answer. This is the accepted answer. nazkose
 20150110T22:43:37Z
Hello,
I am trying to model capacitated vehicle routing problem like you did, I stuck at the same part, did you find any solution for it ?
Thank you.
Hi
have you had a look at https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777000000000000000014931542
?

Re: VRP model
20160509T11:21:20ZThis is the accepted answer. This is the accepted answer. AlexFleischer
 20150112T16:01:13Z
Hi
have you had a look at https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777000000000000000014931542
?
Hello everyone.
I am trying to model capacitated vehicle Routing Problem with cplex. I am new in this, so I have got a lot of Problems ....
Has anyone CVRP model for cplex???
Thanks for your help