Transportation companies such as airlines face daunting problems in setting schedules. A schedule which specifies which vehicles and crew are to make specific trips at specific times must take account of the availability of vehicles to be used in the operation and the crews to operate the vehicles, as well as the availability of fixed resources such as airport gates. Each of these resources typically is governed by complex sets of rules which take account of factors such as the need to set aside times for maintenance of aircraft; the differing qualifications of different pilots and crew member duty time limitations set by government regulations or labor union agreements.
The scheduling system may start with a list of operations, such as a list of flights to be flown at specific times between specific airports, and attempt to find a schedule which will have appropriate aircraft available for all operations, then attempt to schedule the necessary crews, and so on. The process of setting the actual schedule of is generally divorced from the process of determining which routes to fly at which times. This typically leads to sub-optimal use of resources. For example, there typically is no feedback which might lead the airline to recognize that a small change in a departure time of a flight might allow the airline to use an airplane for another flight, so that an airplane sits idle at a cost of thousands of dollars per hour.
It would be desirable to derive an optimized schedule for an airline or other transportation operation, taking into account both financial variables such as the expected revenue from each flight and constraints imposed by resources such as available aircraft. At first consideration, it might seem that one could derive an optimum schedule by applying conventional linear programming techniques to treat all of the variables in the schedule and find the schedule which provides the maximum net financial return. However, it is impossible to determine an optimum schedule for an airline or other transportation company of any size by conventional mathematical techniques. For an airline with 100 airplanes servicing 200 flights per day, even assuming that the flight times are fixed and ignoring the different possible crew arrangements, there are 20,000 possibilities for flying particular aircraft on particular flights the first day. Because the first day's flights reposition the aircraft at different airports, each possibility for the first day yields a different set of 20,000 possibilities for the second day, so that a two-day schedule would include (20,000)2 or 400,000,000 possibilities, and a three-day schedule would include (20,000)3 or 8,000,000,000 possibilities and so on. To select an optimum schedule for a month or two requires examination of an essentially infinite number of possibilities, and is beyond the capability of even the most powerful computers. Stated another way, the problem of deriving an optimum schedule belongs to a class of mathematical problems referred to as “NP-hard,” such that the computational load increases exponentially with the number of aircraft, crew and other elements to be accounted for by the schedule.
Despite the considerable effort devoted to the problem of scheduling for airlines and other transportation companies, no truly satisfactory system has been developed heretofore. In particular, it is estimated that using the best current techniques, airlines waste approximately percent of their revenues due to the inefficiencies resulting from poor scheduling. Thus, prior to the present invention, there has been a substantial unmet need for improvement in scheduling.
USPTO Backgrounds
USPTO Backgrounds