param n integer > 2; 			      # number of nodes

param m; 				      # number of vehicles

param u >=0; 				      # homogeneous vehicle capacity



set Vehicles ordered := {1..m}; 	      # fleet of vehicles

set Nodes ordered := {0..(n-1)};	      # customer sites

set Arcs := {i in Nodes, j in Nodes: i<>j};



#---[Subtours]---

set S ordered := 1 .. (2^(n-1) - 1);

set Cutset {k in S} := {i in 1..last(Nodes): (k div 2^(ord(i)-1)) mod 2 = 1};



param demand{j in Nodes};                     # customer-specific demand

param xcoord {Nodes};

param ycoord {Nodes};



#---[distance matrix]---cost of travelling from i to j

param DistMatrix {(i,j) in Arcs} := sqrt((xcoord[i] - xcoord[j])^2 + (ycoord[i] - ycoord[j])^2);







var x {i in Nodes, j in Nodes, k in Vehicles} binary; 		# 1 if vehicle k travels from i to j, 0 otherwise

var y {i in Nodes, j in Nodes} binary; 			        # 1 if any vehicle travels from i to j, 0 otherwise



minimize Total_Cost: sum { k in Vehicles,(i,j) in Arcs} DistMatrix[i,j] * x[i,j,k];



subject to c1 {(i,j) in Arcs}: sum {k in Vehicles} x[i,j,k] = y[i,j];  # arc(i,j) is traversed exactly one vehicle



subject to c2 {i in 1..last(Nodes)}: sum {j in Nodes: i<>j} y[i,j] = 1;		      # 1 arc leaving each customer



subject to c3 {j in 1..last(Nodes)}: sum {i in Nodes: i<>j} y[i,j] = 1;		      # 1 arc entering each customer



subject to c4: sum {j in 1..last(Nodes)} y[0,j] = m;



subject to c5: sum {i in 1..last(Nodes)} y[i,0] = m;



subject to c6 {k in Vehicles}: sum {i in 1..last(Nodes)} (sum {j in Nodes: i<>j} demand[i] * x[i,j,k]) <= u;



subject to c7 {k in S: card(Cutset[k]) >= 2}:

	sum {(i,j) in Arcs: (i in Cutset[k]) and (j in Cutset[k])} y[i,j] <= card(Cutset[k])-1;



subject to c8 {j in Nodes, k in Vehicles}: sum {i in Nodes: i<>j} x[i,j,k] = sum {i in Nodes: i<>j} x[j,i,k];



subject to c9 {k in Vehicles}: sum{j in 1..last(Nodes)} x[0,j,k] = 1;



subject to c10 {k in Vehicles}: sum{i in 1..last(Nodes)} x[i,0,k] = 1;



data;



param n := 20;  #Number of nodes

param m := 2;   #Number of vehicles

param u := 10;  #homogeneous vehicle capacity u



param: xcoord ycoord:=

0	30	40

1 	37	52

2 	49 	49

3 	52 	64

4 	20 	26

5 	40 	30

6 	21 	47

7 	17 	63

8 	31 	62

9 	52 	33

10 	51 	21

11 	42 	41

12 	31 	32

13 	5 	25

14 	12 	42

15 	36 	16

16 	52 	41

17 	27 	23

18 	17 	33

19 	13 	13;


param demand:=

0	0

1 	1

2 	1

3 	1

4 	1

5 	1

6 	1

7 	1

8 	1

9 	1

10 	1

11 	1

12 	1

13 	1

14 	1

15 	1

16 	1

17 	1

18 	1

19 	1;



display ctime();



option gentimes 1;

option show_stats 1;


option cplex_options

'timing=1'

'threads=32'

'mipdisplay=2'		

'mipinterval=1000'

'mipemphasis=2'

'iisfind=1'

'timelimit=14400'

;

solve;

display x;
display y;
display Total_Cost;

display x,y,Total_Cost > c:\AMPL\VRPout.txt;