Problem of Linear Programming, Scilab or Octave

280 Views Asked by At

I have to solve this with Octave or Scilab.

There's an airplane company with airplanes flying to 3 different destinations (London, Paris, Rome).


Schedule of flights

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);
3

There are 3 best solutions below

0
On

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.

enter image description here

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.

0
On

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);
0
On

Joffan is definitely on the right track.

The different time intervals of his schedule form the vertices of a graph. Add a source linked to all vertices, and link all vertices to a sink. Then, add an edge between two vertices $u$ and $v$ if they correspond to two possible successive flights (i.e., the arrival city of $u$ and the departure city of $v$ are the same, and the the arrival time of $u$ is before the departure time of $v$).

Finally, link the sink to the source, with a unit cost edge.

The problem is now equivalent to finding a minimum cost flow on this graph, where a unit of flow must go through each vertex. A unit of flow represents an airplane, and its path from the source to the sink is its schedule. The unit cost edge from the sink to the source will make sure that a minimum number of planes is used to satisfy all flights.

Note: Alternatively, you can model the problem as a graph coloring problem. The vertices of the graph are the same, but this time two vertices are linked with an edge if and only if they correspond to two flights that cannot be done by the same plane (i.e., it is the complement of the previous graph). Now, the minimum number of airplanes needed is the chromatic number of the graph. Since it is an interval graph, it can be found in polynomial time.