![[Challenge Logo]](http://www.challenge.nm.org/archive/00-01/logo2half.jpg)
Team Number: 027
School Name: Albuquerque Academy
Area of Science: Operations Reaearch
Project Title: Profit Maximization Through Flight Scheduling
Challenge Team Interim Report
|
Team Number: 027 School Name: Albuquerque Academy Area of Science: Operations Reaearch Project Title: Profit Maximization Through Flight Scheduling |
|
|
|
|
Problem Definition:
As the deregulated airline industry continues to grow, flights increasingly radiate from a small number of fixed hubs. In some cases, passing through one of these hubs when traveling between two other cities represents a significant extra distance for the passenger as well as wasted resources for the airline. An airline with an abundance of passengers might be able to arrange its fleet in order for passengers to fly more directly. This will save time and money for consumers and airlines by reducing the reliance on hubs. We will also take into account that larger planes allow passengers to fly for a lower cost per mile. Our project is to create a program that will set up the flight routes for an airline which will maximize profit but still accommodate all travelers. By chartering only necessary flights and loading close to the maximum capacity of every flight, we will increase economic efficiency. To convenience the customers, the program will also ensure that no passenger will have to make more than one connecting flight.
Problem Solution:
Our airline scheduling problem can be viewed as a graph theory problem in which each city is a vertex and the flights between cities are edges. The graph theory problem is similar to the Traveling Salesman Problem, a well-known NP-hard problem. If the Traveling Salesman Problem is in fact reducible to our problem as we suspect, it would prove that our problem is also NP-hard. Because exact solutions to NP-hard problems can usually not be feasibly calculated, even on supercomputers, we will attempt to find approximate solutions.
We will try solving the scheduling problem using different algorithms and compare the algorithms to determine which is the most effective. Our current list of algorithms includes hill climbing, greedy search, local search, heuristic search, and genetic algorithms although we are still investigating additional methods. We have coded the heart of the program that will be used by every method of solution and are currently determining which data structures are most appropriate for each of the aforementioned algorithms. Using an adaptation of the well-known network flow problem it may be possible to use more sophisticated representations to obtain results more quickly.
Eventually, some of the algorithms will need to be run in parallel. We expect that genetic algorithms in particular will require a supercomputer. After testing our program running on a single processor, we will parallelize where necessary using MPI (Message Passing Interface).
Progress to date:
We have gathered data regarding the number of people traveling from one city to another daily on certain airlines. The data came from a variety of sources, including the Department of Transportation and specific airlines. Raw information that we were unable to attain was projected based on factors such as population and distance between cities. We will calculate the cost of the flights based on information gathered from the Federal Aviation Administration, Bureau of Transportation Statistics, and airplane manufacturers. The cost will represent a sum of fuel cost, wages, food, landing fees, and other factors. We are experimenting with a variation of the network flow algorithm to set up the flights.
Expected Results:
Once completed, our program will simulate an airline by setting up an ideal, or nearly ideal, system of flights. It will accommodate all of the passengers at the minimum cost, by finding the cheapest combination of flights capable of transporting the passengers to their desired destinations. Besides allowing airlines to increase profits by efficiently scheduling their flights, our program will be able to predict the decrease in costs resulting from a merger. By determining the minimum costs for two airlines separately and then calculating the minimum costs for the two airlines combined, we will be able to approximate the amount of money that would be saved if the two airlines merged.
We anticipate that our program will recommend a decreased reliance on hubs. Mergers will probably be most effective between airlines that are presently too small to fill large capacity planes between many pairs of cities. Genetic algorithms, we hypothesize, will be the most efficient means to approximate the global best flight network.
Team Members
Sponsoring Teachers