1
$\begingroup$

I do want to formulate a fleet assignment problem. The following table is available

enter image description here

It shows the departure/arrival location and time

I am trying to find the min number of required planes to assign to each route.

I first visualised the table to get some Idea

enter image description here

How can I formulate it as a MILP ?

$\endgroup$
1
  • 2
    $\begingroup$ Consider the lines of your diagram as nodes of a graph, and link two such nodes $u$, $v$ if 1/ $u$, $v$ are in the same location 2/ arrival time at $u$ is smaller than departure time at $v$. Add a source and sink and connect to all nodes, and connect the sink to the source. You could then minimize the cost from sink to source, while imposing a unit of flow (or possibly more if capacity is met) on each flight. $\endgroup$
    – Kuifje
    Aug 6 at 7:39

1 Answer 1

1
$\begingroup$

You may want to have the 2 primitive sets:

CITY

e.g. CHI MNN KC_

and PERIOD or event points

e.g. P0600 P0630 P0700 etc.

The nodes of the network will be the 2-tuples (i,p) or (CITY, PERIOD)

The arcs/decision variables will be:

x(i,p,j,q) = planes flying from (i,p) to (j, q)

Additionally you want the idle on ground arcs:

idle( i, p) = planes idle on ground at i just after point p,

The flow balance constraints will be essentially, for each (i, p):

idle( i, p-1) + planes arriving at (i,p) = idle( i, p) + planes departing (i,p)

The demand constraints for each (i,p,j,q) will be something like:

capacity flown on (i,p,j,q) >= demand( i,p,j,q).

Send me an email, linus.schrage@chicagobooth.edu, and I can send you runnable code for your specific data set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.