A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem

Mohamed Haouari (), Shengzhi Shao () and Hanif D. Sherali ()
Additional contact information
Mohamed Haouari: Department of Mechanical and Industrial Engineering, Qatar University, Doha, Qatar
Shengzhi Shao: Grado Department of Industrial and Systems Engineering (0118), Virginia Tech, Blacksburg, Virginia 24061
Hanif D. Sherali: Grado Department of Industrial and Systems Engineering (0118), Virginia Tech, Blacksburg, Virginia 24061

Transportation Science, 2013, vol. 47, issue 4, 508-525

Abstract: Given a set of flights for a specific fleet type, the aircraft routing problem (ARP) determines the flying sequence for each individual aircraft while incorporating specific considerations of minimum turn time, maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenances. This stage is significant to airline companies as it directly assigns operational routes and maintenance breaks for each aircraft in service. Most approaches related to the problem adopt set partitioning formulations that include exponentially many variables, which requires the design of specialized column generation or branch-and-price algorithms and codes. In this paper, we present a compact polynomial-sized representation for the ARP, which is then linearized and lifted using the reformulation-linearization technique. In addition, we propose two root-node strategies for further augmenting the model formulation. The resulting formulations remain polynomial in size, and we show that they can be solved very efficiently by commercial software without complicated algorithmic implementations. The numerical experiments demonstrate high-quality solutions and significant savings in computational time.

Keywords: aircraft routing problem; reformulation-linearization technique (RLT); compact formulations; airline operations (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0433 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:47:y:2013:i:4:p:508-525

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().