How to make subset of set in GAMS (A FLOW BASED FORMULATION of CVRP.

Problems with modeling
Post Reply
figura
User
User
Posts: 1
Joined: 6 years ago

How to make subset of set in GAMS (A FLOW BASED FORMULATION of CVRP.

Post by figura »

Hello,
I've got an issue about adding a constraint (subtour elimination) in GAMS from A FLOW BASED FORMULATION of CVRP.
The binary decision variable x(rij) is defined to indicate if the vehicle r, r ∈ {1, 2, . . . , p} traverses an arc (i, j) in an optimal solution.
I need to define subset S of set {1,...,n} from constraint (6) ->
Σ Σ Σ x(rij) ≤ |S|−1 ∀S ⊆ {1,...,n}
r=1 i∈S j∈S,i≠j

The integer linear programming model of the CVRP: Minimize:
p n n
Σ Σ Σ c(ij) x(rij) -> (1)
r=1 i=0 j=0,i≠j
Subject to
p n
Σ Σ x(rij)=1, ∀j ∈ {1,...,n} ->(2)
r=1 i=0,i≠j

n
Σ x(r0j)=1, ∀r ∈ {1,...,p}, -> (3)
j=1

n n
Σ x(rij)= Σ x(rji), ∀j ∈ {0,...,n}, r ∈ {1,...,p}, -> (4)
i=0, i≠j i=0

n n
Σ Σ d(j)x(rij)≤ Q, ∀r ∈ {1,...,p}, -> (5)
i=0 j=1,i≠j

p
Σ Σ Σ x(rij) ≤ |S|−1 ∀S ⊆ {1,...,n} -> (6)
r=1 i∈S j∈S,i≠j

xrij ∈{0,1}, ∀r ∈ {1,...,p}, i,j ∈ {0,...,n},i≠ j. -> (7)
I hope, that it is possible to make it in GAMS. This is my formulation in GAMS (I tried to make it with adding sets manually), but it doesnt working (because subtour elimination doeasn't working).
$title CRZP (flow based).
Sets
i /0*4/
subi(i) /1*4/
r /1*4/
alias (i,j)
alias (subi,subj);
Sets offdiag0(i,j)
offdiag1(i,j)
offdiag2(i,j)
offdiag3(i,j)
offdiag4(i,j);

offdiag0(i,j)=yes;
offdiag0(i,i)=no;
offdiag1(i,j)=offdiag0(i,j);
offdiag1(i,'0')=no;
offdiag1('0',j)=no;
offdiag2(i,j)=offdiag1(i,j);
offdiag2(i,'1')=no;
offdiag2('1',j)=no;
offdiag3(i,j)=offdiag2(i,j);
offdiag3(i,'2')=no;
offdiag3('2',j)=no;
offdiag4(i,j)=offdiag3(i,j);
offdiag4(i,'3')=no;
offdiag4('3',j)=no;

display offdiag1, offdiag2;
Table d(i,j)
0 1 2 3 4
0 0 1 2 2 4
1 1 0 3 3 5
2 2 3 0 4 6
3 2 3 4 0 2
4 4 5 6 2 0;
Parameters q(j) /1 5,2 5,3 4,4 5/;
parameter g / 20 /;
Binary variables x(i,j,r);
Free variable f;
Equations
ohr1(j),ohr2(r),ohr3(j,r),ohr4(r),ohrx1,ohrx2,ohrx3,ohrx4,ucel;
ucel.. f=e=sum((i,j,r),d(i,j)*x(i,j,r)$offdiag0(i,j));
ohr1(subj(j)).. sum((i,r),x(i,j,r)$offdiag0(i,j))=e=1;
ohr2(r).. sum(j,x('0',j,r))=e=1;
ohr3(j,r).. sum(i,x(i,j,r)$offdiag0(i,j))=e= sum(i,x(j,i,r)$offdiag0(i,j));
ohr4(r).. sum((i,j),q(j)*x(i,j,r)$offdiag0(i,j))=l=g;
ohrx1.. sum((r,i,j)$offdiag1(i,j),x(i,j,r))=l=3;
ohrx2.. sum((r,i,j)$offdiag2(i,j),x(i,j,r))=l=2;
ohrx3.. sum((r,i,j)$offdiag3(i,j),x(i,j,r))=l=1;
ohrx4.. sum((r,i,j)$offdiag4(i,j),x(i,j,r))=l=0;
Model fsvrp /all/;
Solve fsvrp using mip minimizing f;
display x.l,f.l;

Thank you for any help. :)
Post Reply