Dynamic Programming for the Fixed Route Hybrid Electric Aircraft Charging Problem

Air mobility is rapidly moving towards the development and usage of hybrid electric aircraft in multi-flight missions. Aircraft operators must consider numerous infrastructure and operational constraints in their planning, during which predicting energy usage is critical. We introduce this problem as the Fixed Route Hybrid Electric Aircraft Charging Problem (FRHACP). Given a fixed route, this problem aims to decide how much to refuel/charge at each terminal as well as the energy types to use during each flight leg (hybridization). The objective is to minimize the total energy-related monetary costs while satisfying scheduling and hybridization constraints. We propose a dynamic programming algorithm to solve this problem and show that it is optimal under assumptions usually satisfied in real-life settings. We then propose a gradient descent post-treatment to relax one of these assumptions while maintaining optimality. Results on realistic instances demonstrate that the developed algorithms outperform greedy heuristics, reaching an average cost reduction of up to 19.4%.