-
Notifications
You must be signed in to change notification settings - Fork 1
/
part-d.gms
118 lines (78 loc) · 5.1 KB
/
part-d.gms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
Sets
i village / 1 * 30 /
alias (i, j)
;
Table d(i,j) distance table
$onDelim
,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
1,0,32,72,55.5,70,86.5,53.5,50.5,44.5,40,36,67,73,65,50,52.5,73.5,84,89,57.5,31.5,41,69.5,74,60.5,62,87,91,59.5,41.5
2,32,0,71.5,47,71,80,48,51.5,61.5,47,60.5,70,58,43.5,75.5,44,64,56.5,47.5,85,66,67.5,70.5,45.5,61.5,88.5,69,65.5,51.5,32
3,72,71.5,0,41,45.5,59,52.5,64,50,60.5,75.5,49,46,94.5,44.5,45.5,78,60,65,83.5,50.5,55.5,66.5,48.5,49.5,54,80,56,54.5,32
4,55.5,47,41,0,44.5,73,46,97,65,51,84,48.5,41.5,82,48.5,63.5,65,42.5,64,39.5,44.5,40.5,31.5,49.5,98.5,58.5,70.5,95,59,64
5,70,71,45.5,44.5,0,45.5,69.5,88,84.5,65.5,92,79.5,69,61.5,73,56.5,91,47.5,33.5,28,56,57.5,58.5,56,71.5,75,93,62,43.5,66.5
6,86.5,80,59,73,45.5,0,64,73.5,75.5,73.5,63,58.5,67.5,36.5,50,61,58,50.5,88,49,96,47.5,69,59,76,90,26.5,46.5,55.5,64.5
7,53.5,48,52.5,46,69.5,64,0,25.5,56,31.5,74,54,36,44,33.5,62.5,61.5,37,52,58,54,34.5,50,64,81,46.5,56.5,75.5,64.5,60.5
8,50.5,51.5,64,97,88,73.5,25.5,0,45,54,86,55,44.5,56,38.5,76,74.5,74.5,89,68.5,79.5,53.5,71.5,61,34.5,70.5,88,76.5,34,61.5
9,44.5,61.5,50,65,84.5,75.5,56,45,0,91,68.5,47.5,33,65.5,48,66.5,86,58,78.5,63.5,41,57,57.5,69,49.5,73.5,31,51.5,57,54.5
10,40,47,60.5,51,65.5,73.5,31.5,54,91,0,71,84,51,58,43,81,72.5,53.5,56,74,79,62,93.5,50.5,63.5,34,95.5,65,45,60
11,36,60.5,75.5,84,92,63,74,86,68.5,71,0,64,70,69.5,58,81,75,77,29,40,35.5,79,79,90,70.5,85,83.5,47,54.5,68.5
12,67,70,49,48.5,79.5,58.5,54,55,47.5,84,64,0,35,79.5,83,51.5,57.5,76,38,58,71,79,86,54,51,63.5,72,51,81,56
13,73,58,46,41.5,69,67.5,36,44.5,33,51,70,35,0,70.5,72.5,51.5,94.5,31.5,77.5,61.5,50,55.5,72,44,37.5,39,63.5,45.5,75.5,77
14,65,43.5,94.5,82,61.5,36.5,44,56,65.5,58,69.5,79.5,70.5,0,45,77,26,96.5,82,40,57.5,60,54,70,39.5,55.5,55,82,66,56
15,50,75.5,44.5,48.5,73,50,33.5,38.5,48,43,58,83,72.5,45,0,79.5,80,79,75.5,63,71,70.5,61.5,52.5,59.5,73,45.5,84.5,92.5,56.5
16,52.5,44,45.5,63.5,56.5,61,62.5,76,66.5,81,81,51.5,51.5,77,79.5,0,63.5,41,50.5,52.5,68,31,56.5,61,62.5,58,68.5,68.5,70.5,70
17,73.5,64,78,65,91,58,61.5,74.5,86,72.5,75,57.5,94.5,26,80,63.5,0,54,71,57,56,33.5,40,52,81,55.5,48.5,47,55.5,49
18,84,56.5,60,42.5,47.5,50.5,37,74.5,58,53.5,77,76,31.5,96.5,79,41,54,0,67,54.5,47.5,23,73,54,84,68.5,88.5,65,87.5,34.5
19,89,47.5,65,64,33.5,88,52,89,78.5,56,29,38,77.5,82,75.5,50.5,71,67,0,44,60.5,93.5,32.5,74,45,28.5,26,34.5,81.5,74
20,57.5,85,83.5,39.5,28,49,58,68.5,63.5,74,40,58,61.5,40,63,52.5,57,54.5,44,0,73.5,68.5,29,76.5,91,75,70.5,51,69.5,82
21,31.5,66,50.5,44.5,56,96,54,79.5,41,79,35.5,71,50,57.5,71,68,56,47.5,60.5,73.5,0,58,59.5,59,58.5,73,57.5,62,68,48
22,41,67.5,55.5,40.5,57.5,47.5,34.5,53.5,57,62,79,79,55.5,60,70.5,31,33.5,23,93.5,68.5,58,0,83,42,81.5,73.5,59,69.5,71,34.5
23,69.5,70.5,66.5,31.5,58.5,69,50,71.5,57.5,93.5,79,86,72,54,61.5,56.5,40,73,32.5,29,59.5,83,0,64,47.5,62.5,67.5,74.5,76.5,55
24,74,45.5,48.5,49.5,56,59,64,61,69,50.5,90,54,44,70,52.5,61,52,54,74,76.5,59,42,64,0,82,84,51,69,48.5,65.5
25,60.5,61.5,49.5,98.5,71.5,76,81,34.5,49.5,63.5,70.5,51,37.5,39.5,59.5,62.5,81,84,45,91,58.5,81.5,47.5,82,0,54.5,48.5,27,66.5,55
26,62,88.5,54,58.5,75,90,46.5,70.5,73.5,34,85,63.5,39,55.5,73,58,55.5,68.5,28.5,75,73,73.5,62.5,84,54.5,0,38.5,59.5,78,58
27,87,69,80,70.5,93,26.5,56.5,88,31,95.5,83.5,72,63.5,55,45.5,68.5,48.5,88.5,26,70.5,57.5,59,67.5,51,48.5,38.5,0,60.5,92,46.5
28,91,65.5,56,95,62,46.5,75.5,76.5,51.5,65,47,51,45.5,82,84.5,68.5,47,65,34.5,51,62,69.5,74.5,69,27,59.5,60.5,0,56,67
29,59.5,51.5,54.5,59,43.5,55.5,64.5,34,57,45,54.5,81,75.5,66,92.5,70.5,55.5,87.5,81.5,69.5,68,71,76.5,48.5,66.5,78,92,56,0,52.5
30,41.5,32,32,64,66.5,64.5,60.5,61.5,54.5,60,68.5,56,77,56,56.5,70,49,34.5,74,82,48,34.5,55,65.5,55,58,46.5,67,52.5,0
$offDelim
;
Scalar
time_limit time limit for to turn back to first village (h). / 10 /
speed speed of the snowplows (h). / 40 /
;
Set eijj(i,j) 'exclude j = 1 for pair (i,j)';
eijj(i,j) = ord(j) > 1;
Set eiji(i,j) 'exclude i = 1 for pair (i,j)';
eiji(i,j) = ord(i) > 1;
Set ei(i) 'exclude i = 1';
ei(i) = ord(i) > 1;
Set ej(j) 'exclude j = 1';
ej(j) = ord(j) > 1;
Free Variables
m
;
Variables
z
y(i,j) the total distance from the origin to the node j traveled by a snowplow when it goes from i to j
;
Binary Variables
x(i,j) if one of the salesman goes from village i to village j
;
x.fx(i,i) = 0;
Equations
eq2, eq3, eq4(j), eq5(i), eq12(i), eq14(i), eq16(i, j), eq17(i), eq18(i,j)
;
eq2 .. sum(i $(not sameas(i, '1')), x('1', i)) =e= m;
eq3 .. sum(i $(not sameas(i, '1')), x(i, '1')) =e= m;
eq4(ej(j)) .. sum(i, x(i,j)) =e= 1;
eq5(ei(i)) .. sum(j, x(i,j)) =e= 1;
eq12(ei(i)) .. sum(j $(not sameas(i,j)), y(i,j)) - sum(j $(not sameas(i,j)), y(j,i)) - sum(j, d(i,j) * x(i,j)) =e= 0;
eq14(ei(i)) .. y('1',i) =e= d('1',i) * x('1',i);
eq16(eijj(i,j)) .. y(i,j) =l= (time_limit * speed - d(j, '1')) * x(i,j);
eq17(ei(i)) .. y(i,'1') =l= time_limit * speed * x(i,'1');
eq18(eiji(i,j)) .. y(i,j) =g= (d('1',i) + d(i,j)) * x(i,j);
option optCr = 0.00;
Model part_d /all/;
Solve part_d using MIP minimizing m;
Display m.l;