Optimizing Airline routes

Thanks to Chad, a Tepper MBA student, who pointed out the the Wall Street Journal of March 6, 2007 has an article on optimizing international airline routes. It turns out that countries have complicated costs for airplanes flying in their space, and rerouting the planes can lead to pretty significant savings (on the order of $1,400/flight, which multiplies out to millions per year). From the article:

The formulas countries use to compute their overflight fees vary widely. Cameroon, in Africa, bases its charges on the maximum takeoff weight, with an international flight passing over the country paying from €102 to €204 ($134 to $267). Canada assesses 3.6 Canadian cents (3 U.S. cents) times the distance flown times the weight of the aircraft, plus C$97 per flight for air-traffic control coverage over the North Atlantic. United Kingdom overfly rates are three times as high as Ireland’s rates, and German rates are at least twice as high as Canada’s, according to international aviation specialists.
The U.S. funds its air-traffic-control system differently. Instead of flyover fees, passengers pay multiple taxes to the airlines, which pass the money on to a trust fund. On domestic flights fliers pay 7.5% of the cost of the ticket, plus $3.40 for each flight segment. Passengers on international flights pay $15.10 in fees for coming into and leaving the U.S. Minimizing overflight fees must be balanced against additional fuel costs if an alternative route is less direct. The software systems track a slew of additional data: weather; airport locations and runways; weight and performance of each airplane in the carrier’s fleet; temporarily blocked airspace and the locations of fixed air routes, which change daily due to winds.
The computers churn through multiple scenarios, including minimum time, minimum fuel and minimum cost, and determine which is the best solution for the maximum payload, given up-tothe-minute wind and weather information.

It is surprising the savings possible:

British Airways in 2003 finished installing such software on its route network, replacing a homemade system that one pilot describes as “a blunt instrument.” As a result, it has drastically changed the routing of its Sao Paulo-London flight. Instead of flying in a straight line and crossing over Portugal, Spain and France before entering U.K. airspace, the airline now takes a northerly track over the Atlantic and enters the U.K. over Cornwall. Capt. Tim de la Fosse, BA’s general manager of flight technical, says the new path saves £3,000 ($5,767) per one-way flight in European overfly fees, uses one fewer ton of fuel and is 18 minutes shorter in duration.