MODEL:
! Assignment of calls to paths in an undirected network(NETUND).
Keywords: telephony, route assignment, network design,
call routing, multi-commodity flow;
SETS:
! REQ= max demand available, REV= call's revenue;
CALL: REQ, REV;
! BW is link capacity, COST is unit cost of using;
LINK: BW, COST;
PATH: COSTP;
! X(I,J) is 1 if call I is assigned to path J;
CXP( CALL, PATH): X;
! LXP describes paths in terms of links;
LXP( LINK, PATH):;
ENDSETS DATA:
CALL= CA,CB,CC,CD,CE,CF,CG,CH,CI,CJ,
CK,CL,CM,CN,CO,CP,CQ,CR,CS,CT;
LINK= A,B,C,D,E,F,G,H,I,J,K,L;
PATH= 1..95;
! Possible call to path assignments;
CXP= CA,1 CA,2 CA,3 CA,4
CB,5 CB,6 CB,7 CB,8
CC,9 CC,10 CC,11 CC,12 CC,13 CC,14
CD,15 CD,16 CD,17 CD,18 CD,19
CE,20 CE,21 CE,22 CE,23
CF,24 CF,25 CF,26 CF,27 CF,28 CF,29
CG,30 CG,31 CG,32 CG,33 CG,34
CH,35 CH,36 CH,37 CH,38
CI,39 CI,40 CI,41 CI,42
CJ,43 CJ,44 CJ,45 CJ,46 CJ,47 CJ,48
CK,49 CK,50 CK,51 CK,52 CK,53 CK,54
CL,55 CL,56 CL,57 CL,58 CL,59 CL,60 CL,61
CM,62 CM,63 CM,64 CM,65
CN,66 CN,67 CN,68 CN,69
CO,70 CO,71 CO,72 CO,73
CP,74 CP,75 CP,76 CP,77
CQ,78 CQ,79 CQ,80 CQ,81 CQ,82
CR,83 CR,84 CR,85 CR,86 CR,87 CR,88
CS,89 CS,90 CS,91 CS,92 CS,93 CS,94
CT,95;
! Links and which paths they are on;
LXP= B,1 C,2 G,2 D,3 L,3 G,3 D,4 J,4 I,4 G,4 C,5
D,6 L,6 B,7 G,7 D,8 J,8 I,8 D,9 J,9 D,10 L,10 I,10
B,11 G,11 I,11 C,12 I,12 C,13 L,13 J,13 B,14 G,14 L,14 J,14 D,15 H,15
C,16 L,16 H,16 C,17 I,17 J,17 H,17 B,18 G,18 L,18 H,18
B,19 G,19 I,19 J,19 H,19 A,20 C,20 K,20
A,21 B,21 G,21 K,21 A,22 D,22 L,22 K,22 A,23 D,23 J,23 I,23 K,23
A,24 D,24 J,24 A,25 D,25 L,25 I,25 A,26 C,26 L,26 J,26 A,27 C,27 I,27
A,28 B,28 G,28 I,28 A,29 B,29 G,29 L,29 J,29 A,30 D,30 H,30
A,31 C,31 L,31 H,31 A,32 C,32 I,32 J,32 H,32 A,33 B,33 G,33 L,33 H,33
A,34 B,34 G,34 I,34 J,34 H,34 B,35 E,35 G,36 C,36 E,36
G,37 L,37 D,37 E,37 G,38 J,38 I,38 D,38 E,38 B,39 A,39 F,39
G,40 C,40 A,40 F,40 G,41 L,41 D,41 A,41 F,41 G,42 I,42 J,42 D,42 A,42 F,42
B,43 D,43 H,43 B,44 C,44 L,44 H,44 B,45 C,45 I,45 J,45 H,45
G,46 L,46 H,46 G,47 I,47 J,47 H,47 G,48 C,48 D,48 H,48 F,49 A,49 D,49 J,49
F,50 A,50 D,50 L,50 I,50 F,51 A,51 B,51 G,51 I,51 F,52 A,52 C,52 I,52
F,53 A,53 C,53 L,53 J,53 F,54 A,54 B,54 G,54 L,54 J,54 I,55 G,55
I,56 C,56 B,56 I,57 L,57 D,57 B,57 J,58 D,58 B,58 J,59 E,59 C,59 G,59
J,60 L,60 G,60 J,61 L,61 C,61 B,61 K,62 C,62 E,62 K,63 G,63 B,63 E,63
K,64 L,64 D,64 E,64 K,65 I,65 J,65 D,65 E,65 C,66 A,66 G,67 B,67 A,67
L,68 D,68 A,68 I,69 J,69 D,69 A,69 C,70 E,70 G,71 B,71 E,71
L,72 D,72 E,72 I,73 J,73 D,73 E,73 L,74 H,74 I,75 J,75 H,75
C,76 D,76 H,76 G,77 B,77 D,77 H,77 D,78 A,78 L,79 C,79 A,79
L,80 G,80 B,80 A,80 J,81 I,81 C,81 A,81 J,82 I,82 G,82 B,82 A,82
D,83 B,83 D,84 C,84 G,84 L,85 G,85 L,86 C,86 B,86 J,87 I,87 G,87
J,88 I,88 C,88 B,88 E,89 D,89 J,89 E,90 C,90 I,90 E,91 D,91 L,91 I,91
E,92 C,92 L,92 J,92 E,93 B,93 G,93 I,93 E,94 B,94 G,94 L,94 J,94
E,95 A,95;
REQ = 10, 7, 6, 6, 5, 5, 7, 2, 4, 8,
6, 3, 5, 6, 5, 2, 6, 8, 5, 5;
REV = 420, 380, 400, 390, 500, 490, 400, 150, 450, 500,
850, 200, 370, 500, 340, 120, 460, 450, 360, 170;
BW = 25, 35, 40, 20, 15, 10,
20, 15, 10, 15, 10, 20;
COST = 5, 7, 9, 5, 4, 8
4, 5, 4, 6, 3, 7;
! Laguna/Glover data;
ENDDATA
! Precompute cost of a given path, costp;
@FOR( PATH( H): COSTP( H) = @SUM( LXP( J,H): COST( J)););
!Objective Function;
MAX = @SUM( CXP( I,H):(REV( I) - REQ( I)*COSTP( H)) * X( I,H));
! Demand;
@FOR( CALL( I):
@SUM( CXP( I,H): X( I,H)) < 1;);
!Capacity for each link;
@FOR( LINK( J):
@SUM( CXP( I,H):
@SUM( LXP( J,H): REQ(I)*X(I,H))) < BW(J););
! X Binary;
@FOR( CALL( I):
@FOR( CXP( I,H): @BIN( X( I,H));));
END
|