In [1]: 
import networkx as nx
import matplotlib.pyplot as plt
from IPython.display import SVG
import pygraphviz as pgv

Airline scheduling

Definition Airline scheduling problem

  • Given a set $\cal F$ of $n$ flights and a flights schedule $\cal S$, i.e., origin $o_i$, destination $d_i$, departure $s_i$ and arrival time $a_i$ of each flight in $F$
  • Find the minimum number of aircrafts needed to realize the schedule

Observation $|\cal S|$ aircrafts is always a feasible (trivial) solution

Example

Flight Origin Destination Departure Arrival
1 Roma Milano 6:00 a.m. 7:00 a.m.
2 Venezia Palermo 7:00 a.m. 8:35 a.m.
3 Milano Napoli 8:00 a.m. 9:15 a.m.
4 Venezia Catania 9:30 a.m. 11:15 p.m.
5 Catania Firenze 1:15 p.m. 3:00 p.m.
6 Torino Bari 5:00 p.m. 6:30 p.m.

The sequence of flights $1 \rightarrow 3 \rightarrow 5$ can be realized with the same aircraft. In fact, between arrival time of flight $1$ and departure time of flight $3$ there is enough slack for aircraft maintaince. Then, from Napoli airport the aircraft can flight to Catania on time for the flight $6$

The graph model

Define a graph $G$ with the following structure:

Each flight is $i$ is represented by a pair of nodes $u_i, b_i$ and an arc directed from $u_i$ to $v_i$ with capacity $1$ and minimum flow requirement $1$

In [2]: 
flights = [1,2,3,4,5,6]

m=3

G = nx.DiGraph()

G.add_nodes_from (['u'+str(i) for i in flights])
G.add_nodes_from (['v'+str(i) for i in flights])

for i in flights:
    G.add_edge ('u'+str(i), 'v'+str(i), lb=1, ub=1)

An arc from node $v_h$ and node $u_k$ with capacity $1$ is added to $G$ if an aircraft can perform flight $k$ after flight $h$

In our example:

  1. An aircraft performing flight $1$ may perform flight $3$, flights $5$ and $6$
  2. An aircraft performing flight $2$ may perform flights $5$ and $6$
  3. An aircraft performing flight $3$ may perform flights $5$ and $6$
  4. An aircraft performing flight $4$ may perform flight $6$
In [3]: 
# 1
G.add_edge ('v1','u3', lb=0, ub=1)
G.add_edge ('v1','u5', lb=0, ub=1)
G.add_edge ('v1','u6', lb=0, ub=1)

#2 
G.add_edge ('v2','u5', lb=0, ub=1)
G.add_edge ('v2','u6', lb=0, ub=1)

#3
G.add_edge ('v3','u5', lb=0, ub=1)
G.add_edge ('v3','u6', lb=0, ub=1)

#4
G.add_edge ('v4','u6', lb=0, ub=1)

Nodes $s$ and $t$ are added to G. $s$ is connected to all nodes $u$ with an arc of capacity 1. All $v$ nodes are connected to $t$ with an arc of capacity 1

In [4]: 
G.add_node('s')
G.add_node('t')

for i in flights:
    G.add_edge ('s','u'+str(i), lb= 0, ub=1)
    G.add_edge ('v'+str(i), 't', lb= 0, ub=1)

Add an arc with capacity $m$ and flow requirement $m$ from $t$ to $s$

In [5]: 
G.add_edge('t','s', lb=m,ub=m)
In [6]: 
count = 0
offsetcol = 140

lenghtcol = offsetcol * float(len(flights))

for i in flights:
    G.node['u'+str(i)]['pos'] = "%f,%f"%(150, offsetcol * count)
    G.node['v'+str(i)]['pos'] = "%f,%f"%(450, offsetcol * count)
    count += 1
    
G.node['s']['pos'] = "%f,%f"%(0.0, lenghtcol / 2.0)
G.node['t']['pos'] = "%f,%f"%(600, lenghtcol /2.0)

for i in G.edges():
    if i[0][0] != 'u':
        G[i[0]][i[1]]['xlabel'] = '[%d,%d]'%(G[i[0]][i[1]]['lb'],G[i[0]][i[1]]['ub']) 
    else:
        G[i[0]][i[1]]['taillabel'] = '[%d,%d]'%(G[i[0]][i[1]]['lb'],G[i[0]][i[1]]['ub'])

d = nx.to_agraph(G)
d.node_attr.update (fontsize='12', width=0.4, shape='circle')
d.edge_attr.update(fontsize='10', arrowhead='vee', penwidth=0.2)
d.graph_attr.update(splines='true')
d.draw ('img.svg', prog='neato', args='-n2')

SVG(filename='img.svg')
Out[6]:
%3 u5 u5 v5 v5 u5->v5 [1,1] t t v5->t [0,1] u4 u4 v4 v4 u4->v4 [1,1] u6 u6 v4->u6 [0,1] v4->t [0,1] v6 v6 u6->v6 [1,1] v6->t [0,1] u1 u1 v1 v1 u1->v1 [1,1] v1->u5 [0,1] v1->u6 [0,1] u3 u3 v1->u3 [0,1] v1->t [0,1] s s s->u5 [0,1] s->u4 [0,1] s->u6 [0,1] s->u1 [0,1] s->u3 [0,1] u2 u2 s->u2 [0,1] v3 v3 u3->v3 [1,1] v2 v2 u2->v2 [1,1] v3->u5 [0,1] v3->u6 [0,1] v3->t [0,1] v2->u5 [0,1] v2->u6 [0,1] v2->t [0,1] t->s [3,3]

If a feasible flow exists in $G$ then the schedule can be realized with $m$ aircraft

In [7]: 
H = G.copy()

for j in H.edges():
    H[j[0]][j[1]]['capacity'] = \
    H[j[0]][j[1]]['ub'] -  H[j[0]][j[1]]['lb']
In [8]: 
H.add_node('s1')
H.add_node('t1')

unbalance = {}

for i in G.nodes():
        auxunb = 0
        for j in G.in_edges(i):
            auxunb += G[j[0]][j[1]]['lb']
        
        for j in G.out_edges(i):
            auxunb -= G[j[0]][j[1]]['lb']
        
        unbalance[i] = auxunb

for i in unbalance:

    if unbalance[i] > 0:
        H.add_edge ('s1',i,capacity = unbalance[i])
    if unbalance[i] < 0:
        H.add_edge (i,'t1',capacity =- unbalance[i])
In [9]: 
value, flow = nx.maximum_flow(H,'s1','t1', 'capacity')

valid_circulation = True

for i in H.out_edges('s1'):
    print "Flow and capacity of arc (%s,%s):" % (i[0],i[1]), H[i[0]][i[1]]['capacity'], flow[i[0]][i[1]]
    if H[i[0]][i[1]]['capacity'] != flow[i[0]][i[1]]:
        print 
        print "\x1b[1;31mValid circulation not found\x1b[0m"
        valid_circulation = False
        break
   

Flow and capacity of arc (s1,s): 3 3
Flow and capacity of arc (s1,v1): 1 1
Flow and capacity of arc (s1,v2): 1 1
Flow and capacity of arc (s1,v3): 1 1
Flow and capacity of arc (s1,v4): 1 1
Flow and capacity of arc (s1,v5): 1 1
Flow and capacity of arc (s1,v6): 1 1
In [10]: 
for i in G.edges ():
    G[i[0]][i[1]]['xlabel'] = ''
    G[i[0]][i[1]]['taillabel'] = ''
    if flow[i[0]][i[1]] > 0 or G[i[0]][i[1]]['lb'] == 1:
            G[i[0]][i[1]]['color'] = 'red'
            G[i[0]][i[1]]['penwidth'] = '2'
    else:
        G[i[0]][i[1]]['penwidth'] = '0.2'

d = nx.to_agraph(G)
d.graph_attr.update(splines='true')
d.node_attr.update (fontsize='12', shape='circle')
d.edge_attr.update(fontsize='10', arrowhead='vee')

d.draw ('img.svg', prog='neato', args='-n2')

SVG(filename='img.svg')
Out[10]:
%3 u5 u5 v5 v5 u5->v5 t t v5->t u4 u4 v4 v4 u4->v4 u6 u6 v4->u6 v4->t v6 v6 u6->v6 v6->t u1 u1 v1 v1 u1->v1 v1->u5 v1->u6 u3 u3 v1->u3 v1->t s s s->u5 s->u4 s->u6 s->u1 s->u3 u2 u2 s->u2 v3 v3 u3->v3 v2 v2 u2->v2 v3->u5 v3->u6 v3->t v2->u5 v2->u6 v2->t t->s