A dynamic programming approach for 4D flight route optimization

摘要

This paper describes our solution for the GE Flight Quest 2 (FQ2) challenge, organized by Kaggle. FQ2 aimed at optimizing flight routes so that the overall cost depending on fuel consumption and delay is as low as possible. The contestants could use several data tables as inputs, including aircraft positions and destinations, weather information and other aviation related data. Their task was to produce a flight plan for each flight, given as a list of (latitude, longitude, altitude, airspeed) quadruplets. The cost of the flight plans was evaluated with an open source simulator. Our proposed method produces an initial solution with the Dijkstra's algorithm to avoid restricted zones, and then refines it using dynamic programming and local search techniques. We can extensively utilize wind forecasts and significantly divert the planes from the the great circle route if necessary. Moreover, our method tries to set the ascending and descending profiles of the flights to further decrease the cost. Our algorithm achieved second place on the public, and fifth place on the private leaderboard of the contest.