Overbooking on Airlines

Problem Definition

A low-cost airline, OrgaAir, operates four daily flights from Valencia to London at 10:00, 12:00, 14:00 and 16:00 hours. The first two flights hold 100 passengers and the last two can fly up to 150 passengers each. Should overbooking occur, which implies having sold more seats than the plane actually has, the airline can place a passenger on a later flight. Evidently each delayed traveller is compensated by being paid €200 plus €20 for each hour delayed. The firm places delayed travellers on their own operating flights, or on one of the flights from other airlines departing at 20:00 hours, which always have available seats (a capacity of 999 passengers is always considered) at no extra charge. Let us assume that at the beginning of the day we know that OrgaAir has sold 110, 160, 100 and 100 seats on its four daily flights, respectively. Model this problem as a maximal flow model at a minimum cost in order to minimise the airline’s total overbooking cost.