I have to solve this with Octave or Scilab.
There's an airplane company with airplanes flying to 3 different destinations (London, Paris, Rome).
ID From To Depart Arrive
1 London Rome 5:45 7:15
2 Rome London 9:15 10:45
3 London Rome 11:45 13:15
4 Rome London 13:15 14:45
5 London Rome 15:45 17:15
6 Rome London 17:45 19:15
7 London Paris 6:45 9:45
8 London Paris 10:45 13:45
9 London Paris 15:45 18:45
10 Paris London 9:15 12:15
11 Paris London 13:45 16:45
12 Paris London 19:15 22:15
13 Paris Rome 8:45 12:15
14 Rome Paris 9:45 13:15
15 Paris Rome 14:45 18:15
16 Rome Paris 11:45 15:15
Based on this schedule I need to write a program that finds the minimum plane needed. And for each plane to show where is going to fly (IDs).
Professor said that i can use the problem of graph coloring and than with linear programming. But I still don't understand.
If it takes too long to solve I will appreciate any help, because I don't even know where to start.
UPDATE:
So I put the schedule into a table M(i,j)=1 when a plane cant "perform" both flights.
- I got an answer, but when i want to execute I get an error. So i don't even know the solution. Can somebody explain why is not working?
- Anybody knows why he put 304 in the size of a matrix? What a cytpe and vartype mean?
- Thank you :)
M = [
0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0;// 1
0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1;// 2
0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1;// 3
0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1;// 4
0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1;// 5
0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1;// 6
1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1;// 7
0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1;// 8
0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1;// 9
1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1;// 10
0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1;// 11
0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0;// 12
1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1;// 13
0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1;// 14
0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1;// 15
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0 // 16
];
//272 variables, first 16 colors,from 17 to 272 x_ik (i flight, k color)
c = zeros(272,1);
for i = 1:16
c(i) = 1;
end
A = zeros(304,272);
b = zeros(304,1);
c = 1;
ctype = "";
//sum of x_ik = 1
for i = 1:16
for k = 1:16
A(c,16*i+k) = 1;
end
b(c) = 1;
c = c+1;
ctype = strcat(ctype, "S"); // S : sum x_ik = 1
end
// x_ik - y_k <= 0
for i = 1:16
for k = 1:16
A(c,k) = -1;
A(c,16*i+k) = 1;
b(c) = 0;
ctype = strcat(ctype, "U"); // U : <=
c = c+1;
end
end
// x_ik + x_jk <= 1
for i = 1:16
for j = (i+1):16
if (M(i,j) == 1)
for k = 1:16
A(c,16*i+k) = 1;
A(c,16*j+k) = 1;
b(c) = 1;
ctype = strcat(ctype, "U");
c = c+1;
end
end
end
end
lb = zeros(1,272);
ub = ones(1,272);
vartype = "";
for i = 1:272
vartype = strcat(vartype, "I");
end
sense = 1;
param.msglev = 1;
[xmin, fmin, status, extra] = glpk(c, A, b, lb, ub, ctype, vartype, sense, param);
disp(fmin);
disp(extra);
First thing I would do - apart from (as your comment says) finding out how long a relocation flight takes over the three routes, and what the turn-around time is between flights - is lay out the schedule on a time basis to get some ideas of what the key items are to capture in your data model.
You can already see there's another data issue with the last flight from Rome to London, and possibly with the last flight from Rome to Paris. And that (if we believe the data as at present) there are 6 planes in the air at 12:00 midday.