How to formulate fleet Assignment Problem?

Question

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

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

How can I formulate it as a MILP ?

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. — Kuifje, Commented Aug 6, 2022 at 7:39

LINDO Systems · Accepted Answer · 2022-08-08 15:01:51Z

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, [email protected], and I can send you runnable code for your specific data set.

1 Answer 1