Journées de l'optimisation 2007 Optimizations days

The objective function of the Fleet Assignment Problem is the profit associated with any prospective FA. While the cost's dependency on the FAP decision variables is quite straightforward, expressing the expected revenue as a function of the FA is a quite tricky business (if not a presumptuous one...). In this talk, we explain how we have used a stochastic demand passenger flow model to improve the revenue component of the objective function of a FAP solver. The model takes into account spill and recapture between itineraries. The linear objective function is improved by iteratively computing FAs and passenger flows. We made tests on a full-scale network, using a leg-based loss of revenue estimation as a comparison. We obtain improvements of profits (on paper) of up to 0.4% of the costs.

In this communication is considered the problem of long term forecasting of an air transportation network. This problem is crucial when planning the necessary investments in airports, fleets and air traffic control resources. The proposed approach makes use of two different optimization models: One model is devoted to demand forecasting while the other one optimizes the air transport supply according with a profit maximization behaviour for the whole sector. The demand forecasting process makes use of an entropy maximization approach to determine origin-destination matrices for a given scenario. The supply optimization model considers simultaneously two classes of flows: aircraft flows providing air transportation capacity and passengers flows generating revenues to the airlines operators. No classical flows in networks optimization technique is available to solve this problem while two level solution techniques considering aircraft flows at the first level and passengers flows at the other can be considered. A proposed solution scheme is composed of an iterative process between the current solutions of the demand and the supply optimization problems: the entropy maximizing problem provides the passengers origin-destination matrix given a fare structure, while the supply optimization problem provides the fare structure given a passengers origin-destination matrix. The problem is illustrated in the case of West Africa.

Given a set of pairings (predetermined sequences of flights) to operate over a month, the bidline scheduling problem consists of determining anonymous monthly work schedules for air crew members (pilots in our case) such that all pairings are covered by the appropriate number of crew members and all work rules are satisfied. The objective aims at constructing schedules that are, as much as possible, similar in terms of the number of days off they contain and the number of work hours credited. This problem is typically modeled as a set partitioning type problem that contains a huge number of variables, one for each feasible schedule. In this talk, we propose to solve it using dynamic constraint aggregation combined with column generation. This recent methodology allows to reduce degeneracy by aggregating some of the master problem constraints. It is embedded in a heuristic branch-and-bound procedure to derive integer solutions. Results on real-data instances involving up to 565 crew members and 2924 pairings will be presented.