2339. A Lagrangian relaxation approach for the extended aircraft routing problem with itinerary-based revenue
Invited abstract in session MB-59: Routing decisions , stream Transportation.
Monday, 10:30-12:00Room: Liberty 1.14
Authors (first author is the speaker)
| 1. | Matteo Petris
|
| École nationale des ponts et chaussées | |
| 2. | Sébastien Deschamps
|
| Ecole des Ponts ParisTech CERMICS | |
| 3. | Frédéric Meunier
|
| LVMT, Ecole Nationale des Ponts et Chaussées | |
| 4. | Axel Parmentier
|
| CERMICS, Ecole des Ponts ParisTech |
Abstract
In the Extended Aircraft Routing Problem with Itinerary-based Revenue (EARP-IR), an airline needs to design a schedule, i.e., the sequences of legs (flights) operated by its planes,
with the aim of maximising the revenues. Estimating the revenue of a schedule relies on the fact that customers look for an itinerary, i.e., a sequence of legs from an origin to a destination, rather than a single leg. The estimation captures the behaviour of the customers and is encoded via an atomic and stochastic model where customers arrive one after the other and choose an itinerary or none of them according to a basic attraction model, a discrete choice model where the probabilities to buy an itinerary depend on attractiveness values.
As the seats of a leg are limited, only itineraries composed of legs with free seats are sold. We show that this model is approximated by a linear program, the so-called Sales Based Linear Program (SBLP). The EARP-IR integrates the operational problem of designing a schedule with the itinerary-based revenue estimation model (the SBLP).
The operational problem is an Aircraft Routing Problem enriched with gate and frequency constraints (NP-hard).
We propose a mixed integer linear programming model for the EARP-IR. We exploit the structure of the model to devise a Lagrangian relaxation approach where we relax the constraints which link the operational problem with the SBLP. A Lagrangian heuristic is also devised to retrieve feasible solutions.
Keywords
- Airline Applications
Status: accepted
Back to the list of papers