FlightPlanningForFuelStops

Derrell Lipman
December 10, 2010

Overview

Small aircraft require fuel stops in order to fly long distances. This project demonstrates one method of automatic determination of a "best route" for least time from starting airport to destination.

Screenshot

Concepts Demonstrated

A* search is used to find an optimum set of fuel stops enroute from the user-selected starting point to the destination.

Innovation

Innovation? Nah, from a broad perspective, there's nothing terribly innovative here, I don't think. Flight planning software has been around for a long time, and there are various publicly-available flight planners on the web. The "innovation" for me was working with the FAA's database of nearly 20,000 air fields, and determining how to organize the data and implement a search of the state space to find an efficient route. I also learned some limits of the capability of the A* algorithm.

Technology Used Block Diagram

Evaluation of Results

Routes can be viewed in the browser-based visualization tool. The user interface represents lines of longitude and latitude as an equally-spaced grid, which causes the airports to display a depiction of the United States that is stretched horizontally and flattened vertically. Routes are built using great-circle distances, so should follow a curve over long distances when drawn on the visualizer. Most routes tested to date have shown the requisite shape. A few longer routes have shown anomalies which I have been unable to track to a cause.

The visual depiction shows that the algorithmically-determined route is not grossly incorrect. For a more detailed analysis, I have also entered a number of routes ascertained by this program into other flight planning software. What I expect to find is a total route distance that nearly approximates the great circle route from the starting point to the destination. The distance is not expected to be exact. In fact, the search heuristic looks for best "time" for a flight, where "time" is calculated as actual flight time based on distance, plus a 1/2 hour penalty for landing as a result of the time to fuel the plane. This heuristic forces shorter time routes (fewer stops) at the expense of possibly taking a path less directly on the great circle route from starting point to destination.

Finally, I have evaluated the calculated routes of some short paths to ensure that I manually obtain the same route as the algorithm calculates.

Additional Remarks

This entire application is written in JavaScript. The time required to find a long route, between airports on opposite sides of the country for example, is currently excessive (measured in minutes). For comparison, it would be interesting to have a C program that implemented the same graph search, to see how much the interpreted environment really is slowing this down.