Aircraft routing and charging scheduling for air taxi services with flight pooling

Advances in battery technology and distributed electric propulsion have positioned air taxi as an emerging transportation paradigm. To unlock its potential as an on-demand urban transit solution, mathematical modeling and algorithmic design for aircraft routing and charging scheduling optimization of air taxi services are necessary. This paper investigates an aircraft routing and charging scheduling (AR&CS) problem for air taxi services with flight pooling. We first formulate a mixed-integer linear programming model for the considered AR&CS problem. Subsequently, we develop a tailored adaptive large neighborhood search (ALNS) algorithm to solve the AR&CS problem. In the ALNS algorithm, an efficient two-phase construction heuristic is proposed to generate an initial solution. The first phase employs a four-step procedure to identify service flights and allocate orders, while the second phase adopts a parallel-route-construction approach based on greatest fitness to determine aircraft routing and charging scheduling. Moreover, three types of dedicated destroy-repair operators are designed to improve the solution: service flight selection, order allocation, and aircraft routing and charging scheduling. Finally, extensive numerical experiments are conducted to evaluate the performance of the proposed solution methods, to assess the benefits of flight pooling consideration for air taxi services, and to explore managerial insights for air taxi operators. The results demonstrate that the ALNS algorithm significantly outperforms Gurobi in solving large-scale problems while also delivering highly stable performance. Furthermore, introducing flight pooling in air taxi services enhances both system profitability and service level.