Aircraft routing under uncertainty via robust optimization

Abstract

We address the robust vehicle routing problem (RVRP), focusing on the development of mathematical models and solution methods to incorporate uncertainties regarding travel times and demand, in traditional and practical variants. We are particularly interested in a practical variant, the aircraft routing problem, motivated by the real case of an on-demand airline company. Features such as heterogeneous fleet, time windows and maintenance requests are incorporated into robust optimization models that allow for the variability of uncertain parameters to be addressed. In particular, a new type of commodity flow model formulation, not yet explored in the robust optimization literature, even in classical variants, was developed for both the traditional RVRP and the aircraft routing problem. Moreover, we propose new compact models and tailored branch-and-cut methods considering different types of uncertainty sets, namely the cardinality constrained set and the single and multiple knapsack sets, using a recent approach based on dynamic programming to obtain the robust counterparts. The developed approaches were implemented and analyzed through computational experiments using instances from the literature as well as real-world data related to aircraft routing.