CN101421753A - Transportation Scheduling System - Google Patents

Abstract

Methods for scheduling a transportation operation such as the operation of an airline. The method desirably selects a demand (100) for transportation specifying an origin, destination, and time of arrival or departure, and selects resources from a database of available resources such as aircraft (508), crew, and departure gates. The resource selection desirably is conducted so as to optimize a result function such as contribution to margin or other financial result from the particular operation specified in the demand. Upon developing a schedule fragment (108), the specified resources are committed, and the database of available resources is modified (110) to indicate that the resources are no longer available at the relevant times. The system then treats another demand and repeats the process so as to develop a full schedule. The system can develop a feasible schedule, even for a complex transportation operation in a brief time, typically in minutes or less. Schedules can be developed using alternative strategies and assumptions, and tested against one another.

Description

Transportation Scheduling System

Cross References to Related Applications

This application claims U.S. Provisional Patent Application No. 60/774,623, filed February 21, 2006, U.S. Provisional Patent Application No. 60/797,413, filed May 3, 2006, and U.S. Provisional Patent Application No. 60/797,413, filed January 11, 2007 Priority as of the filing date of Application No. 60/879,831, the disclosure of which is hereby incorporated by reference.

technical field

The present application relates to methods and systems for scheduling transportation operations.

Background technique

Transportation companies such as airlines face the daunting problem of setting up schedules. A schedule specifying which vehicles and crews to make a particular trip at a particular time must take into account the availability of the vehicles to be used in operation and the crews to operate the vehicles as well as the availability of fixed resources such as airport gates. Typically, each of these resources is governed by a complex set of rules that take into account factors such as the need to allow time for aircraft maintenance, the different qualifications of different pilots, and the duties of flight attendants set by government regulations or union agreements. time limit.

A dispatch system may start with a list of operations such as a list of flights to be flown at a specific time between specific airports, and try to find a schedule with the appropriate aircraft available for all operations, then try to dispatch the necessary flight attendants, and so on. The process of setting up the actual schedule is generally separate from the process of determining which routes will be flown at which times. This often results in a sub-optimal use of resources. For example, there is often no feedback that would allow an airline to recognize that a small change in a flight's departure time could allow the airline to use the plane for another flight, without which the plane would sit idle at the cost of thousands of dollars an hour.

It is desirable to obtain an optimized schedule for an airline or other transportation operation taking into account financial variables such as expected revenue from each flight and constraints imposed by resources such as available aircraft. As a first consideration, it appears that an optimal schedule can be obtained by applying conventional linear programming techniques to process all variables in the schedule and find the schedule that provides the greatest net financial return. It is however not possible to determine an optimal schedule for any size airline or other transportation company by conventional mathematical techniques. For an airline with 100 aircraft servicing 200 flights per day, even assuming fixed flight times and ignoring different possible crew arrangements, there are 20,000 possibilities to fly a particular aircraft on a particular flight on the first day. Because the first day's flight relocated the aircraft to a different airport, a different set of 20,000 possibilities is generated for the second day for each possibility for the first day, so a two-day schedule would consist of (20,000) ² or 400,000,000 possibilities, and a three-day schedule would include (20,000) ³ or 8,000,000,000 possibilities and so on. To choose the optimal schedule for a month or two requires examining an essentially infinite number of possibilities and is beyond the capabilities of even the most powerful computer. In other words, the problem of obtaining an optimal schedule belongs to a class of mathematical problems known as "NP-hard", whereby the computational load increases exponentially with the number of aircraft, crew and other factors to be considered by the schedule.

Although considerable effort has been devoted to the scheduling problem of airlines and other transportation companies, no truly satisfactory system has been developed so far. Specifically, it is estimated that even with the best current technology, airlines waste about _ percent of their revenues due to inefficiencies due to poor scheduling. There is therefore a substantially unmet need for scheduling improvements prior to the present invention.

Contents of the invention

One aspect of the invention provides a computer-implemented method of generating a schedule for a transportation operation. The method according to this aspect of the invention contemplates using an ordered list of multiple demands for transportation between multiple origins and multiple destinations, each demand associated with an origin, a destination, and a time of departure or arrival Associated. The method expects to use the computer to set up the schedule segments to satisfy one of the requirements in the ordered list. The step of setting up a schedule segment includes allocating resources from one or more lists of available resources. In the case of an airline, for example, the step of setting up a schedule segment most often involves assigning specific aircraft, flight attendants, and airport gates. A method according to this aspect of the invention desirably includes modifying one or more lists of available resources based on resource usage in the schedule setting step to indicate a revision status. The method most preferably also includes the steps of repeating the step of setting schedule segments and modifying the list of available resources, performing these steps for a plurality of demands according to the order of the demands in the list, and thereby using the modifying steps from the immediately preceding demand The resulting status is used to execute the set schedule staging steps for each requirement.

Another aspect of the invention provides additional methods of generating schedules for shipping operations. The method according to this aspect of the invention contemplates using a list of multiple demands for transportation between multiple origins and multiple destinations, each demand being associated with an origin, a destination, and a time of departure or arrival and the method also uses one or more vehicle lists that include identifications of a plurality of vehicles and information indicating the location and temporal relationship of each vehicle. The method according to this aspect of the invention contemplates using a computer to select a vehicle from one or more of the vehicles identified in the vehicle list, to select one of the demands from the demand list, and to set up the schedule segmentation so that by combining the The selected vehicle is assigned to the selected demand to satisfy the selected demand. Additionally, the method desirably includes modifying one or more of the vehicle lists and demand lists based on the vehicle usage and demand in the step of setting the schedule segment to indicate a revision status. The method according to this aspect of the invention desirably includes repeating these steps, thereby performing the selection and schedule segment setting steps for multiple requirements, and thereby performing these steps for each iteration using the state derived from the modification steps of adjacent previous iterations. step.

As discussed further below, preferred embodiments of methods according to these aspects of the invention are capable of rapidly generating realistic and useful schedules, even for complex transportation operations such as large airlines.

Further aspects of the invention provide computer systems and computer programming elements for implementing the dispatching methods discussed above and transportation systems using such dispatching methods.

Description of drawings

Fig. 1 is a flowchart schematically depicting some units in a method according to one embodiment of the present invention.

FIG. 2 is a partial flow diagram depicting other elements in the method of FIG. 1 .

Figure 3 is a graph of historical ridership data.

FIG. 4 is a schematic diagram of certain forecasted passenger capacity data abstracted from the data in FIG. 3 .

FIG. 5 is a partial flowchart depicting further steps of the method shown in FIGS. 1 and 2 .

FIG. 6 is another partial flowchart depicting one of the steps of FIG. 5 in more detail.

FIG. 7 is another partial flowchart depicting in more detail another step shown in FIG. 5 .

FIG. 8 is another partial flowchart depicting in more detail another step shown in FIG. 5 .

Figure 9 is a graph of expected ridership versus departure time.

Figure 10 is a schematic illustration of a process used in the methods of Figures 1-9.

11 is another partial flowchart depicting certain steps used in the methods of FIGS. 1-10.

FIG. 12 is another partial flowchart depicting one of the steps shown in FIG. 11 .

Figure 13 is a schematic flowchart depicting a process according to another embodiment of the invention.

Figure 14 is a schematic diagram of a computer system and transport system used in an embodiment of the invention.

Detailed ways

A process according to one embodiment of the invention is shown in general form in FIG. 1 . The process begins by formulating a demand node set, a set of requirements for shipping operations associated with a specific date and time in the future. In the example discussed here, the demand node represents demand for passenger airline flights, but other transportation operations could be handled similarly. In addition to the date, time of departure, origin, destination, and expected number of passengers of each type, the data defining each demand node will most desirably include additional data associated with the outcome achieved by satisfying the demand, such as: ideal operations profit contribution ("CTM": contribution to operating margin) or other financial result of an airline from an operation that uses the best possible aircraft to meet demand at the exact time specified in the demand; expected revenue per passenger per service category ; Indicates whether the operation represented by the demand node works as a feeder for routing traffic to other operations in the system; and other factors discussed below. The system can provide usable results with demand nodes formulated according to any reasonable scheme. However, it is highly desirable to formulate requirements according to a process such as the requirements node formulation process discussed further below.

In the next stage 102 of the process, the requirements are arranged into an order referred to herein as a "topological order". The order defines the order in which the system processes requests in a scheduling operation. The sorting step is primarily performed by sorting the requirements according to one or more sorting keys, wherein such sorting keys are respectively based on one or more units of data associated with a requirement node. For example, demand nodes may be sorted by departure date and time with or without other factors such as expected contribution to CTM. Alternatively, the demand node's origin and destination could be used as sort keys, so that flights between certain cities are higher in the order.

Once the requirements have been sequenced at step 102, the system starts with an assumed initial system state. The system state includes data defining the availability of resources required to perform transport operations. These resources include: mobile resources, such as aircraft or other vehicles used in operations; and flight attendants, and stationary resources, such as airport gates, which may be associated with points of origin or destination. The system then processes the requirements in order according to the topological order assigned at step 102 . So at step 106 the system just picks the first demand at the top of the ordered list and works on that demand in step 108 to calculate the schedule segment for that particular demand. The process of computing a schedule segment involves selecting the resources to be applied to satisfy the demand in a manner that produces a feasible result, and hopefully the best achievable result given the state of the system. For example, for a particular segment the system may seek to select the particular aircraft and crew that will produce the best operational outcome (eg, best CTM). It should be appreciated that optimization of schedule segments for a particular operation is a relatively simple problem; the number of possibilities for a given demand node is bounded by the number of resources available in the system, and does not grow with the number of demand nodes. The process of computing schedule segments may include adaptation. As discussed below, the term "adaptive" as used herein refers to adjusting initial assumptions applied during a selection or optimization process. For example, where demand might specify a 6 p.m. flight out of Cleveland with a capacity of 150 passengers, the process of setting up a schedule segment involves examining what can be achieved by departing at a later time or utilizing a smaller aircraft, or both. the result of.

Once the system has selected the feasible and most preferred optimal set of resources to be applied to the particular requirement under consideration, the resources are committed to the particular requirement under consideration. This causes a new system state to be set in step 110 . Accordingly, the list of which aircraft are available at what times is modified to indicate that the aircraft assigned to the demand processed in step 108 are no longer considered available on the date and time considered in step 108 . Similarly, the flight attendant assigned to the particular need handled in step 108 is no longer available, and so on. The system then loops back to step 106, whereupon the system processes the next requirement, now at the top of the list. Thus in each cycle the system considers a demand and tries to find a feasible set of resources for that demand and most hopefully an optimal set of resources. The process continues until all demand nodes have been processed at step 112 .

As noted above, during the computation of the schedule segment for each demand, the system evaluates the resulting function, most commonly a financial result such as CTM, associated with the set of resources allocated to satisfy the demand node. The system will also record this result as the expected result for that schedule segment and aggregate this result with results associated with all other previously calculated schedule segments to produce an aggregate expected result, such as the aggregate CTM for the schedule as a whole . The expected outcome at this stage of the operation, such as the CTM, is more accurate than the ideal CTM of the original demand node. The expected results after computing the schedule segments reflect what can be achieved with the available resources. In some cases, the system may not be able to find a feasible set of resources, and in this case, the system may return a result indicating that the requirement is not met. The system can also keep track of these instances.

When the system has processed the last demand at step 112, the system has produced a complete schedule that defines for all demand or at least demand that can be serviced by available resources and not excluded by other criteria discussed below Resource allocation for subsets. The number of computations to be performed in a complete loop of steps 106-112 to generate a complete schedule is finite and does not increase exponentially with the size of the operations to be scheduled. All calculations required to complete a complete schedule can be performed in minutes or less on a conventional personal computer programmed to perform the operations discussed herein. Since scheduling operations can be performed rapidly, the assumptions used in developing the schedule can be changed and the scheduling process can be repeated. As shown at step 114, a computer system or human operator may observe the aggregated results from the scheduling operation and make a decision to repeat the scheduling process, eg, by evaluating the aggregated CTM, the number of unmet demands, and the like. This decision may include deciding at step 116 to adjust the level of resources available for the scheduling operation, such as the number of aircraft or flight attendants, and repeating the scheduling operations beginning at step 104 and continuing until the entire additional scheduling has been completed.

Since it is possible to compute the schedule quickly, the cycle can be repeated iteratively until an optimal resource level is found that returns the best result, such as the highest CTM or the fewest unmet needs. Alternatively or additionally, the system or a human operator may order the system to change the assumptions used in formulating the requirements in step 100 , or the order of sorts applied in the topological sort step 102 . For example, a dispatch system can be used in conjunction with a revenue forecasting module that applies game theory to test the performance of various fare classes, classes, or supplementary services (such as baggage allowances or meal services associated with a flight) or against known information about competition. other factors. Different assumptions applied in game theory produce different market share estimates in demand nodes, and thus different expected number of passengers and different expected revenue per passenger. In a change strategy step 118, a game theory system (not shown) may be ordered to try different hypotheses regarding the fares that will be charged or the services that the airline will provide using the dispatch system and the responses of competitors to those fares, and This results in different ridership forecasts and thus different demand at step 100 . Different market share estimates can be applied for various parts of the demand calculation, for example different market shares along different competitors' service routes. The classification key and classification order applied in the topological sort step 102 may also vary. Thus, basically any element of the strategy used by the airline can be changed. Furthermore, since the scheduling system can generate a complete schedule for months of operation in minutes, it is feasible to calculate the schedule for multiple policy assumptions and thus find the best one.

The process for formulating requirements (step 100 of FIG. 1 ) is shown in detail in FIGS. 2-9 . The process begins by loading historical data describing ticket sales for all carriers serving the cities the airline will serve. Passenger data is typically provided in the form of passenger name records, or "PNRs," which each reflect an individual passenger itinerary. Each PNR typically reflects the passenger's origin and destination; the price paid for carriage between the origin and destination; and the class of service defined by the carrier carrying the passenger. PNR data is commercially available in the aviation industry. Expect to use at least one year of historical data.

In the next stage 152 of the process, the system compiles historical data for each pair of origin and destination cities. The system allows separate editing of different sets of days during processing. For example, the system can compile the data set for each origin and destination for all weekdays; or alternatively, a data set for all Mondays in the historical period in question, another data set for all Tuesdays in the same period. datasets and more. It is desirable that each historical period is smaller than a full year, such as a month, so that datasets compiled for different periods, such as different months, can be compared to each other to detect seasonal patterns. Data sets compiled for different historical periods can also be compared to each other to detect increasing trends in travel between particular origin and destination cities. For example, the number of passengers transported between a particular origin city and destination city on weekdays in February of the most recent year can be compared to February of the previous year, if data equivalent to more than one year is available. The numbers are compared to obtain estimates of annual growth. The compilation for each day set in the historical period includes data related to the number of passengers departing at a particular departure time in each class of service offered by the multiple carriers serving the city for the historical period in question, and also includes data related to the passenger Data on the average fare paid for each type of service.

Departure time data reflect passenger behavior using schedules provided by airlines serving the origin and destination during the historical period in question. This data is graphically depicted in FIG. 3 . For example, bar 154 represents the number of passengers traveling in economy class on airline flight A departing at 8:30 am, while bar 156 represents the average number of passengers carried in first class on the same airline flight A, and bar 158 represents the average number of passengers carried in a single cabin on the airline's Flight B departing at 8:45 am.

In a further step 160 of the process, historical information is abstracted by aggregating passengers departing within a defined time interval, such as a specific one-hour or two-hour window of the day, referred to here as a window, and different airlines The offered class of service maps to the closest relative class of service offered by the airline being scheduled. The system thus forms a demographic of historical city pairs for each class of airlines dispatched for each window. For example, as shown in the graph in FIG. 4 , bar 162 represents the average number of passengers who depart on a typical weekday from a particular origin to a particular destination and whose purchases roughly correspond to the category of economic carrier being dispatched. All carrier service classes for tickets. Similarly, bar 164 represents the average number of first class passengers in the same window on a typical weekday. Although the editing process 152 and the refining process 160 are shown as separate processes for clarity of illustration, these processes may overlap. For example, when checking each PNR record, the class of service may be shifted from that of the actual carrier used to the class of service of the dispatched carrier.

In effect, each window represents a somewhat different market of potential travelers from the markets represented by the other windows of the day. The size of the window can be varied for different city pairs by manual or automatic selection based on factors such as the number of flights serving the city pair. For example, when two cities are connected by only two flights per day, the window size can be 12 hours; when cities are connected by dozens of flights per day (such as New York and Chicago), the window size can be less than one hour.

The system can assign arbitrary departure times within the window used in the abstraction process, such as the center of the window. More preferably, the system calculates an average departure time for passengers included in the demographic based on historical departure times incorporated in the demographic and assigns the average time as the city-to-demographic departure time. The system can also obtain measures of temporal variation in demographics, ie, measures of the relationship between time within a window and number of passengers.

The system also calculates an average historical fare by the class of service offered by the carrier being dispatched. Thus, when the travel class of the respective passenger name record matches the relative class of the carrier being dispatched, then the historical fare paid by the passenger in question will be paid for the same passenger for the relative class of travel on the carrier being dispatched. fare paid. These fares are averaged over all travelers included in the demographic to produce an average historical fare associated with the class and window.

Thus, at the end of the editing process and the abstraction process, the system has historical demographics for each pair of origin and destination city pairs. Such historical city-pair demographics include departure times, number of passengers, and average fares, respectively, for each class of service of the dispatched carrier, and may include additional data, such as measurements of changes in departure times.

Then in another step 168 of the process, these historical city-pair demographics are converted into predicted city-pair demographics. As discussed above, the historical demographics for each city pair represent passengers carried by all carriers. The number of passengers in each historical city-pair demographic is multiplied by the forecasted market share of the airline dispatching in the particular market represented by the demographic. For example, if the historical city-to-demographics indicate that 600 economy class passengers and 100 first class passengers depart Seattle for New York between 6:00 and 8:00 pm With a forecasted market share of 20% achieved, the forecasted city-to-demographics will indicate that the airline can expect 120 economy class passengers and 20 first class passengers. Similarly, a growth factor may be applied to account for the year-to-year increase (or decrease) in traffic between the origin city and the destination city. Additionally, the predicted average fare for each service category that the airline will fulfill is included in each forecasted city-pair demographic. Market share predictions can be made intuitively based on average ticket prices, but are preferably made by applying techniques that take into account competitive behavior in the market, such as theory. Alternatively, historical market share and historical fare data can be used based on the assumption that none of the airlines serving the market will change its pricing strategy.

The predicted city-pair demographics obtained from step 168 are converted into demand nodes, i.e., for transportation between origin and destination on routes served by airlines scheduled along the process outlined in FIG. 5 individual needs. In a first step 180 of the process, the city-pair demographics are converted into route demographics by the steps shown in detail in FIG. 6 . The process of FIG. 6 assumes that the airline has already determined which city pairs it will provide nonstop service between cities, and therefore has a list of directly connected cities. Each pair of directly connected cities is referred to herein as a "route". The system takes a list of city-pair demographics and then processes each city-pair demographic in sequence. At step 185, the system selects the shortest route through all available routes connecting the origin and destination cities of the city-pair demographic list. For example, the system may examine all routes that originate in the departure city of the city-pair demographic and determine whether any of these routes are destined for the destination city of the city-pair demographic. If so, the route is a non-stop direct route and is therefore the shortest. If not, the system can examine the destination cities for each route originating from the city-pair demographic's origin city and select the set of cities that make up the destination cities for these routes. The system then considers these destinations individually in turn and sees if there is a route that originates in the destination city and ends at the destination of the city-pair demographic. If so, the system records the combined length of the two route combinations and continues this check until all such two route combinations have been found. The system then considers the available combinations of the two routes and chooses the combination with the smallest total length. If no two-way combination is found, the system can search for a three-way combination in a directly analogous manner.

In a variation of this approach, the system may consider certain cities to be central cities, so that if there are no direct one-route paths, the system will seek to construct two-route paths and three The path of the route. This greatly reduces the number of possibilities to be considered when specifying two-way and three-way paths.

In another variation, the system may exclude routes extending in the wrong direction from the origin city or from the center city, i.e. the route's destination city is farther from the city-to-demographic destination than the route's origin city Cities are farther away. This also limits the number of routes that will be considered when finding two-way and three-way paths. The length of each route considered in this process may be actual geographic miles between cities or may be a fraction based on geographic miles and other factors, such as landing fees or congestion at particular airports.

Once the system has found the shortest route route for the demographics of a particular city pair, the system creates route demographics at step 187 for each route in the shortest route. If the shortest route happens to be a one-route route, that is, a direct route with no stops, the route demographics are the same as the original city-pair demographics. However, if the route is a multi-route route, the system constructs a first route demographic with the origin city of the city-pair demographic as its origin, with the first route's destination as its destination, and with The departure time of the city to the demographic is the departure time. The expected revenue per passenger for the first route demographic is a fraction of the expected revenue per passenger. Part of the expected revenue can be achieved based on route length, ie the expected revenue for the first route can be the city-to-demographic expected revenue divided by the total length of all routes in the route and multiplied by the length of the first route itself. The system also creates route demographics for the second route in the route. The route demographic has the destination city of the first route as its departure city, the destination city of the second route as its destination city, and its departure time is equal to the departure time of the city-to-demographic plus the expected along the first route Flight time and time allowed for transfers. Furthermore, the expected revenue for the second route is a fraction of the expected revenue per passenger for the city-pair demographic as a whole, calculated by length as discussed above for the first route. In the case of a route with multiple routes, the route demographics of each route in the route can be marked to indicate whether the route is a feeder route (where there is a subsequent route in the route) or a receiver route (where there is a previous route in the route) or Both.

Once the route demographics have been set for all routes in the route, the system returns to step 181 and repeats the process of steps 185 and 187 for the next city pair demographics until all city pair demographics have been processed and converted to route demographics . Each route census identifies its applicable date in the same way as a city-to-demographic. For example, a route demographic derived from a city-pair demographic that applies only to Mondays in February will likewise only apply to Mondays in February.

After the route demographics have been formed, they are used in the next step 190 of the process shown in FIG. 5 to create an initial list of demand nodes. Get each route in turn. For each route, based on the route demographics formed in step 180, a route demographics list is compiled with origins and destinations corresponding to the route in question. The list of route demographics for each route is converted into a demand node set for each applicable day of the route demographic in question. For example, convert route demographics for Mondays in February into demand nodes for dates corresponding to the first Monday in February, demand nodes for dates corresponding to the second Monday in February, and so on. The system can also take into account a priori or intuitive knowledge available to the operator. For example, if historical data is compiled for weekday flights, and the operator knows that a particular date will be a religious holiday at the origin or destination, the system can reduce the expected number of passengers for that particular date. After processing the demographics of all routes corresponding to a particular route, the system picks the next route and processes the route demographics for that route in the same manner. This process continues until all route demographics for all routes have been processed. At this time, an initial list of demand nodes for each route is obtained. Such demand nodes include all characteristics of route demographics, such as origin, destination, departure date and time, expected revenue per passenger in each category, and expected number of passengers in each category, respectively.

In the next stage 200 of the process, as shown in detail in Figure 7, the system checks the demand nodes in the initial list. The check starts at step 202 with a list of routes, and at step 204 each route is obtained in turn. For each route, at step 206 the system obtains a list of demand nodes for that route. The list does not need to be in a particular order. Once the list of demand nodes for a particular route has been retrieved, the system starts with the first demand node in the list. At step 208 the system takes the first demand node in the list and processes the demand node to select the best aircraft to use in the flight that satisfies that demand node, i.e. the flight has the expected number of passengers from origin to destination flight. The system examines all aircraft types used by the scheduled airline and selects the aircraft type that will produce the greatest profit contribution if it has the expected number of passengers specified in the demand node to fly from the origin to the destination city. At this stage of the process, without regard to whether this type of aircraft is actually available at the time and date specified by the demand node, nor when making the aircraft available at that time and date (such as transporting the aircraft from a distance) The selection of the "best" aircraft type is made without possible costs incurred. Thus, the profit contribution characterized at this stage of the process gives an upper bound on the expected return to nodes that satisfy demand.

In the next stage 212 of the process, the system compares the number of passengers specified in the demand node with the number of passengers that the best aircraft selected at step 210 can carry. If the number of passengers specified in the demand node is less than or equal to the capacity of the selected best aircraft, the system marks the demand node as processed, marks the demand node with the expected profit contribution and returns to step 208 to process the next demand node . However, if the number of passengers specified in the demand node is greater than the capacity of the selected best aircraft, the system deletes the original demand node from the list and splits the demand node into two smaller demand nodes at step 214 and divides the These smaller demand nodes are added to the list of demand nodes for the route, whereupon the system again returns to step 208 to obtain the next unprocessed demand node. One of the new smaller demand nodes may constitute the next demand node to be processed. The smaller demand nodes created by the larger demand nodes are identical to the original demand nodes, but the new smaller demand nodes each have half the number of passengers specified in the original demand nodes. The additional demand node has the same departure time as the original demand node. Additional requirement nodes are handled in the same way as other requirement nodes in the list. Therefore, a very large demand node can be split into two demand nodes on the first pass through step 212 . As each of these smaller requirement nodes is processed, one or more requirement nodes may be split again into smaller requirement nodes. Additionally, when processing such a split smaller demand node at step 210, the optimal aircraft selected for that demand node may be different than the optimal aircraft selected for the original larger demand node.

The process continues in this manner until all demand nodes for the route (including any smaller demand nodes obtained in the split at step 214) have been processed, whereupon the system obtains the next route at step 204 and the new list of demand nodes associated with the route and repeat the same process. This continues until all routes are finished processing in the same manner.

The resulting list of output demand nodes is passed to a further step 220 (FIGS. 5 and 8). In this step, the system checks the list of demand nodes for each route and determines if a better expected CTM can be found by combining the demand nodes with each other. This step selects a particular route from the route list and sorts all demand nodes from step 200 (FIG. 5) by departure time. At step 224 (FIG. 8) of step 220, the system selects the first three demand node sets in the sorted list. The system then attempts in step 226 to create a combined node from the first two of the three selected nodes.

The procedure calculates time horizons separately for the two demand nodes. This time range for each demand node is based on an estimate of how passenger load will change over time if the flight deviates in time from the time specified in the demand node. As shown graphically in FIG. 9 , the change in passenger capacity over time for demand node 250 can be represented by a step function as shown by the mesh bars. The step function has a maximum value N ₂₅₀ equal to the number of passengers in the demand node at the original departure time T ₂₅₀ of the demand node, and progressively smaller values for earlier and later departure times. Valid ranges for demand nodes may be the earliest and latest times for which the time step function has a value greater than some arbitrary number of passengers. The step function can be based on general assumptions about the system as a whole, or alternatively can be chosen based on a priori knowledge associated with a particular route. For example, a demand node serving a well-known business destination such as New York City or the Washington D.C. area could be assigned a narrow, steeply descending step function to reflect the assumption that business travelers generally have tightly constrained schedules, while vacation travelers could be assigned The assumption that the schedule is relatively insensitive assigns relatively wide variations to demand nodes destined to or originating from resorts such as Orlando, Florida.

In another embodiment, based on the historical data used to generate historical passenger data and city-to-demographics, an estimate of passenger load variation with departure time can be derived. For example, if the historical passenger data shows that the number of passengers departing at different times with a wide space around the midpoint of the window used in the abstraction process (step 150) is substantially equal, a large variation may be assigned to the city versus demographic, and This large change can be assigned to each route demographic obtained from the city pair demographic in step 180 and forwarded to each demand node created from the route demographic. Furthermore, changes to a particular demand node can be unilateral or symmetrical about the departure time of the demand node. For example, if a particular demand node is marked with a flag indicating that this demand node is derived from route demographics representing the second or subsequent route demographics in the multipath route (step 180), the variation or step function Set to drop gradually for departure times after the demand node's original departure time, but can drop to zero passengers for all departure times before the demand node's original departure time, reflecting the The reality is that there are no passengers from earlier flights in the path.

The function relating each demand node time to the number of passengers has a valid range bounded by the earliest and latest times at which any significant number of passengers represented by the demand node will be willing to travel along the route. For example, the step function for demand node 250 has an effective range from time T _250E to time T _250L . Another demand node 252 with departure time T ₂₅₀ has a variation function represented by the unshaded bar in FIG. 9 with a finite range from T _252E to T _252L . The system checks the live ranges of two demand nodes and determines if the live ranges overlap. If they do not coincide, then the attempt to combine the two demand nodes is discarded and step 226 is done. However, if these valid ranges overlap, the system selects a set of possible departure times for the combined demand node. The earliest possible departure time is the earliest time in the time range encompassed by the overlapping live range or the later time in the original departure time of the earlier demand node. The latest possible departure time is the earlier time included in the overlapping effective range of two demand nodes or the departure time of the later demand node. For example, the live ranges of demand nodes 250 and 252 overlap from time T _252E to time T _250L . Therefore, the earliest possible departure time of the combined node will be T _252E and the latest possible departure time will be T _250L . In fact, the overlapping range of two demand nodes on the same route and on the same day means that flights along that route departing in the overlapping range will attract some passengers associated with the earlier demand node and some passengers associated with the later demand node . The system also calculates one or more intermediate possible departure times between the earliest possible departure time and the latest possible departure time. For example, the system calculates one such intermediate departure time as the midpoint between the earliest possible departure time and the latest possible departure time.

For each possible departure time, the system determines the expected number of passengers for that departure time. The system evaluates the step function of each demand node for a possible departure time and adds the values of the step functions of the two demand nodes for a particular departure time to arrive at a combined node operating at that possible departure time expected number of passengers. For example, the expected number of passengers for a flight departing at time T _252E is the sum of _NA and _NB (FIG. 9).

The system then calculates the best aircraft for the demand node at each possible departure time and calculates the CTM for that possible departure time. In the combining step, if the expected number of passengers exceeds the capacity of the optimal aircraft, the expected number of passengers is set to the capacity of the aircraft. The system compares the CTMs of the possible departure times and chooses the best CTM as a result of combining the first two demand nodes, whereupon step 226 terminates. The system then attempts to combine the next two demand nodes at step 240 and all three selected demand nodes at step 242 in exactly the same way. The process of combining three demand nodes may assume combining these demand nodes into two demand nodes with two different departure times, and using multiple possible departure times within a range of times, and based on a step function of the three selected demands, the combined passenger capacity at each possible departure time is calculated, and again the best aircraft is selected and the optimal The aircraft calculates the CTM. The best aggregate CTM of the two demand nodes is output as a result of step 242 .

At step 244, the system compares the CTM of the two-node combination derived from steps 226 and 240 with the CTM derived from the three-node combination of step 242, and selects the best CTM among these CTMs, and outputs the result, The results include likely departure times, expected CTMs of the combined nodes, and node identities that will be combined to produce the combined node, ie the first two, last two or all three of the considered nodes. At step 246, the system compares the CTM of the combined node output by step 244 to the sum of the CTMs of the individual nodes used to form the combined node. If so, the system proceeds to step 248 and replaces the single node used to form the combined output node with the combined one or more nodes, then returns to step 224 . If the CTM produced by the combined node is not higher than the sum of the CTMs of the individual nodes, the system returns directly to step 244 without replacing the individual nodes. At step 224, the system obtains another set of three demand nodes including the latest demand node and the two successor demand nodes in the previously processed set. The system then processes this new set of demand nodes in the same manner. This continues until there are no more demand nodes to process, whereupon the system returns to step 221 and selects the next route, which is processed in the same manner. This continues until all routes have been processed.

During this combining process, the system may reverse some of the splitting processing performed at sub-step 214 (FIG. 7) of residual requirements processing 200. For example, if a very large demand node is split into two demand nodes, the two demand nodes can be recombined back into the larger demand node at step 226 or step 240 .

At this point in the process, the step of formulating requirements (step 100 in Figure 1) is complete. The system then arranges the demand nodes into an order referred to herein as a topological order. This is done by classifying requirements according to one or more classification keys. Classification keys can include any characteristic of a requirement. A simple sort key includes the date and departure time specified in the request, thereby ordering the request in chronological order. However, other sorting keys may be used, such as sorting by expected CTM so that the most profitable flight is at the top of the topological order, or sorting by route length so that long-distance demand is prioritized or short-distance demand is prioritized. An airline may also wish to prioritize flights between designated central cities such that demand nodes with central cities as origin and destination cities are processed first. As described above, route demands can be marked as feeder route demands of a multi-route path, and demand nodes derived from feeder route demands similarly marked. This flag can be used as a sort key such that feeder demand nodes are processed first. In another variation, weighting factors may be assigned to these and other characteristics of the requirement nodes, and a composite classification key may be calculated based on the characteristics of the respective requirement nodes weighted by these factors. The choice of classification key will to some extent affect the results achieved in scheduling. However, it has been found in practice that simple sorting by departure date and time works as well or nearly as well as more complex schemes.

The system maintains a database of resources needed to perform operations to be scheduled. For airlines, these resources include aircraft and flight attendants, both of which are mobile, and passenger gates at specific airports. The database includes information about the characteristics of each resource and also includes information about the state of each resource at future times during the duration of generation of the schedule. For an aircraft, characteristics will typically include the aircraft type, its seat capacity in each service class; its maximum range (which may be referred to as maximum block time); and the cost of operating the aircraft, often referred to as cost per flight hour. Information about the status of the aircraft at various times in the schedule will include, for example, where it is parked at a particular airport or en route; an indication as to whether the aircraft is grounded for maintenance; and information about the operational history of the aircraft, such as since the last scheduled maintenance check and operating hours and calendar days since the last major inspection. For flight attendants, characteristics would include qualifications to serve at specific types of airports and headquarters. The status information at each time will include information such as: whether the flight attendant is on or off duty; the location of the flight attendant at their headquarters or at some other airport or en route; Monthly and yearly cumulative hours of service and any other data related to calculations regarding flight attendant availability for flights based on government regulations, union contracts, or airline staffing policies. Gate characteristics include the identity of the airport where the gate is located, and may also include the types of aircraft that can be accommodated at a particular gate. A gate can also have an occupancy cost associated with it, such as that caused by a delayed departure of an aircraft. The status of the gate usually simply indicates whether the gate was occupied or not occupied for the various time intervals in the schedule.

The database is set to an initial state representing the expected state of the various resources at the start of the schedule.

The system fetches demand nodes in the order set by the topological sort step and attempts to compute a schedule segment for each demand node. Each schedule segment includes the origin and destination of the demand node and the specified conditions for satisfying the demand node's flight operations. These conditions include specific aircraft, specific crew and specific gates. The specified conditions are chosen such that they are feasible, ie, the aircraft is present and not otherwise occupied; the aisle or gate is available; and the flight crew is qualified and available. The system also attempts to specify conditions for the schedule segments such that an outcome function representing the expected outcome of flying a flight meeting those conditions satisfies the criteria. The most common outcome function is the expected operating profit contribution, and the system attempts to maximize this expected operating profit contribution.

The problem of selecting the conditions specified in the schedule section can be understood with reference to FIG. 10 . The distance D ₁ between the aircraft and the specified conditions represents the negative profit contribution or cost associated with flying the aircraft from the origin specified in the demand to the destination specified in the demand and, if applicable, is also included for use in accordance with The cost of needing to relocate the aircraft from another airport. The distance _D2 represents the cost of providing the crew, including direct hourly costs and idiosyncratic costs such as crew relocation, overtime payments to the crew, etc. The distance _D3 between the specified condition and the demographic incorporated in the demand node represents the negative impact on revenue due to specifying a departure time different from that specified in the demand node, e.g. specifying the aircraft in demand The time and departure gate specified in the node are not available. Distance _D3 also includes any loss of revenue due to the designation of aircraft that are too small to accommodate the expected passenger load. The distance D ₄ represents the costs associated with using the corridor or gate at the airport of origin and the airport of destination. The system attempts to choose conditions such that the sum of D ₁ -D ₄ is a minimum given the current state of the resource database, ie the constraints imposed by the resource availability indicated in the database. The minimization or maximization need not be a strictly mathematical minimization or maximization. In other words, the system does not need to consider every possible alternative, but can in fact only consider some alternatives consistent with available resources in order to reach a local minimum or maximum. However, it is usually feasible to consider most or all available resources.

One implementation of the process for selecting conditions for scheduling segments is shown diagrammatically in FIG. 11 . At step 300, the process begins by inputting an ordered list of demand nodes resulting from the topological ordering steps discussed above. At step 302, the system checks to determine if all demand nodes have been processed. Assuming there are unprocessed demand nodes, the system picks the first unprocessed demand node in the ordered list at step 304 . In steps 306 and 308, the system attempts to select the best aircraft from among the aircraft available to fly the flight specified by the request's origin, destination, and departure time. In these steps, given the current state of the resource database, the system attempts to find an aircraft indicating availability at the airport of origin of the flight or an aircraft that can fly to the airport of origin and is available for the flight. Among these aircraft, the system looks for the specific aircraft that has the least negative impact on the CTM. Since it is almost always better to use aircraft that are already parked at the origin airport, in step 306 the system first checks for aircraft that will be at the origin airport at the time of departure. If a satisfactory aircraft is found, the system ignores step 308 and therefore does not check the possibility of using an aircraft that is elsewhere in operation.

The selection process available in step 306 is schematically shown in FIG. 12 . At step 309, the process selects an aircraft from the fleet. If the resource database indicates that the aircraft will park at the origin airport indicated in the demand node at the departure time indicated in the demand node or within some predetermined window, such as one hour after the departure time, the system proceeds to the next step 312 . Otherwise, the system abandons the aircraft and returns to aircraft selection step 309 . At step 312 , the system checks the resource database to determine if the aircraft has been committed to another flight or for maintenance within the time required for the flight specified in the demand node. If the aircraft is not available, the system again abandons the aircraft and returns to step 309 . If an aircraft is available, the system also checks whether the aircraft is an aircraft available for use in the flight specified in the demand node. For example, the system checks a range of aircraft types in terms of flight length between origin and destination airports. If the aircraft does not have sufficient range, it is not a viable aircraft for the flight. Other factors may be considered in determining feasibility. For example, if a destination airport does not have a runway length sufficient to accommodate a particular type of aircraft, any aircraft of that type may be excluded. Assuming no aircraft are excluded, the system determines in step 316 the difference or "delta" between the time the aircraft will become available at the gate according to the resource database and the departure time specified in the demand node. Of course, if the database indicates that the aircraft will be available at the requested departure time, the delta will be 0.

In another step 318, the system calculates a scoring factor for use of the selected aircraft in the demand node. A scoring factor is based on the delta in availability time calculated in step 316 . This scoring factor can be based on any per-minute value set by the airline. Alternatively, the scoring factor may be calculated based on a measure of demand node change, such as the step function relating passenger numbers to departure times discussed above with reference to FIG. 9 . Thus, if the demand node includes a function that relates passenger numbers to departure times, such as the step function of FIG. Effect. The difference between the number of passengers in a demand node and the number of passengers obtained by evaluating the change over time can be multiplied by the expected revenue per passenger to obtain a score or cost associated with delayed availability.

Additionally, the system calculates a score or cost based on the hourly flight cost of the currently selected aircraft. The system also calculates the seat delta, the amount by which the number of expected passengers exceeds the number of seats in the aircraft. This cost is simply the product of the difference between the number of seats and the number of passengers multiplied by the expected revenue per passenger in a particular category. The system adds the various scores and calculates the total score. This total score represents the negative impact on CTM of a particular aircraft flight and thus represents _D1 of FIG. . The system adds the aircraft to the list of feasible aircraft. The aircraft's position in the list is based on points. Therefore, the list is topologically ordered according to the scores of the various aircraft. The system returns to step 309 to process the next aircraft. If there are no more aircraft to process, the system moves to step 322 and picks the aircraft with the lowest score in the list, and moves to flight attendant selection step 324 (FIG. 11). If no aircraft is found in the list, this indicates that no feasible aircraft is available at the origin airport specified in the demand node, and the system moves to step 308 .

Step 308 is substantially the same as step 306, except that step 308 only considers that the aircraft is not indicated to be parked at the origin airport and includes additional sub-steps that determine whether the aircraft can meet the departure time based on information in the resource database. Fly to the departure airport within the specified time or within a specified window, such as one hour after the departure time. Also in step 308, the score for each aircraft includes the cost to fly from the airport where the aircraft was at the relevant time to the airport of origin. If no aircraft are found in step 308, this indicates that the demand node cannot be satisfied with the resources in the state indicated by the database. Therefore no schedule segments are generated for demand nodes. Instead, the demand node is simply marked in step 326 to indicate that this particular demand node was ignored due to no feasible aircraft.

When an aircraft has been selected in step 306 or 308, if the aircraft is available at a different time than specified in the demand node, the departure time of the flight operation serving the demand node is adjusted to the aircraft's available time. In other words, the system adapts the schedule segments to meet the available aircraft resources.

If an aircraft is selected in step 306 or 308, the system goes to a flight attendant selection step 324. The flight attendant selection step is performed in a similar manner to the aircraft selection steps 306 and 308 . Thus, the system checks available flight attendants, selects available flight attendants, and finds the lowest cost available flight attendant. The system also wants to take into account the balancing of flight attendants so that flight attendants do not exceed the maximum number of hours per month or year. For example, an additional cost may be assigned to any flight attendant that is directly related to the number of hours previously scheduled for that flight attendant in the month under consideration. The flight attendant selection step uses the departure time and aircraft type found in the aircraft selection step. Thus to be feasible, the flight attendant must be eligible to board on the type of aircraft selected in 306 or 308 and must be available at the origin airport at the departure time established in step 306 or 308 . The flight attendant must also have sufficient hours remaining at the time of departure to allow the flight attendant to complete the flight. The flight attendant selection step may first search for flight attendants at the departure airport according to the resource database, and then find flight attendants who can be relocated to the departure airport. The crew selection step may also deal with a full crew for that aircraft type, and then if a full crew cannot be found, the crew selection step may attempt to find individual crew members to form a full crew. Alternatively or additionally, the flight attendant selection step may also process first those flight attendants who have no employment history, and then those flight attendants who have had an on-duty history since their most recent previous departure day. This may be helpful because the calculations required to determine whether a particular flight attendant has sufficient hours remaining given all the hours constraints may be time consuming.

If no flight attendant can be found, the system does not form a schedule segment but instead moves to step 328 and marks the node as being ignored because no flight attendant is available. In a variation, if a flight attendant cannot be found due to a lack of flight attendants with some specific qualification, for example a pilot qualified on a Boeing 747 cannot be found, the system may mark the node with that specific indication.

Assuming a flight attendant is found, the system calculates a score reflecting the cost of the flight attendant, eg, a score reflecting the flight attendant's base salary and any additional payments associated with the flight attendant such as overtime pay, perks costs, and flight attendant relocation. This fraction represents D ₂ in FIG. 10 . If a flight attendant is found, the system transfers to step 330 and searches for available gates at the origin and destination. Furthermore, if no gate is found, the system does not form a schedule segment but instead marks the node as ignored because no gate is available at the particular airport.

Assuming a gate is found, the system forms a schedule segment and implements it by marking the database resource to submit the aircraft, flight attendant and gate found in the previous step. These resources are therefore represented as being occupied for the time required to complete the flight. The system also flags the database to indicate that the mobile resource, including the aircraft and flight attendant, will be placed at the destination airport at a time corresponding to the end of the flight. The system also updates the status of the aircraft to indicate the additional flight time since the last maintenance and the status of the flight attendants to indicate the additional man hours they will devote to the flight.

At this point a single schedule segment is complete. At step 336, the system may also record the expected profit contribution of the flight if the flight is segmented according to the schedule.

In one variation, the system may test the proposed schedule segment against one or more waiver criteria before committing resources at step 334 . For example, if the proposed schedule segment would result in a negative profit contribution, the system may not commit the resource but may mark the demand node as ignored due to a negative CTM and return to step 302 . In another variation, the system may override the waiver criteria if one or more of the retention criteria are met. For example, the system may be arranged to retain schedule segments if a demand node is marked as a feeder for another demand. In yet another variation, the reservation criteria may include serving certain cities of particular importance to the airline. In another variant, the system may recheck some previous resource allocations. For example, if the results of the aircraft selection steps 306 and 308 indicate that no aircraft are available to satisfy the demand or that the only aircraft available to satisfy the demand would produce adverse results because those aircraft are much smaller or larger than the expected number of passengers, the system It is possible to examine aircraft previously assigned to flights that will arrive at the origin airport within hours of the departure time of the demand being processed, and determine whether it is feasible to reschedule these flights so that the aircraft arrive earlier, and if so, to What would be the impact of CTM or other outcomes. The system may also attempt to reschedule previously scheduled flights if the first step indicates that the selected aircraft will be available after the departure time in the demand under consideration and such a delay would reduce the CTM of the demand under consideration. In another variation, the system can test the effect of splitting or combining requirements at this stage. For example, if a first demand has a first departure time and 100 expected passengers, and the best available aircraft has 200 seats, the system can look for a demand with another departure time and determine whether it would be more profitable to combine the two demands picture. This stage may use a process similar to that discussed above with reference to FIGS. 7 and 8 . In this case, however, the check of possible combinations and splits is performed based on those aircraft that will actually be available at the departure time of the combination or split requirement in question, rather than the best possible aircraft.

After a schedule segment has been completed for a demand node or a demand node has been ignored, the system checks at step 302 whether there are more demand nodes to process. If so, the system picks the next demand node at step 304 and repeats the steps discussed above. If there are no more demand nodes, the schedule is complete. The system can output a total expected CTM by summing all CTMs associated with a single schedule segment.

As shown above with reference to FIG. 1 , the system can adjust resources and repeat the entire scheduling process or a portion of the scheduling process. Adjustments to resources may be based on information related to requirement ignorance reasons obtained when the requirement was marked at steps 324 , 328 , and 332 . For example, if flags indicate that many needs were overlooked due to a lack of qualified flight attendants at Embraer Airport and these neglects occurred primarily on and after March 31, the system could adjust the resource database to indicate that additional flight attendants with such qualifications exist and Instructions issued: Such additional flight attendants should be hired and trained to be available on March 31. The system can recalculate the entire schedule based on the assumption that a certain number of additional flight attendants will be available after March 31. Optionally, if the demand has been sorted by departure time and date, the system can recalculate the part of the schedule from March 31 onwards and compare the recalculated schedule to the The earlier calculated schedules are concatenated to form a composite schedule. The total CTM of the recalculated schedule can be compared to the CTM of the original schedule to determine whether the proposed resource changes are economically satisfactory. Similarly, if an ignored node indicates that it is recommended that additional aircraft of a particular type should be made available, the system can alter the resource database to indicate that such additional aircraft are available, recalculate the schedule or a portion of the schedule as indicated and compare the recomputed The CTM of the current schedule is compared with the CTM of the original schedule to determine the advantage that can be obtained by acquiring or leasing more aircraft.

A process according to another embodiment of the invention, shown schematically in Figure 13, utilizes similar requirements to those discussed above. In step 400, requirements may be developed through substantially the same process as discussed above with reference to FIGS. 2-9. In the same way here, each requirement can include: origin, destination, and desired departure time or arrival time, and it is also desirable to include information specifying an estimated load, such as the number of passengers in each fare class in the case of a passenger airline . Here, too, individual demands may include information relating loads (such as passenger loads or passenger loads in individual fare classes) to departure or arrival times. Here again, the system maintains a resource database that includes at least a list of vehicles and hopefully includes a list of vehicles with information as discussed above, such as the status of each vehicle at each time in the future interval that the schedule will contain, e.g. Set at a specific destination, such as an airport or gate. The database is also expected to include other resources such as terminal gates and flight attendants, and is expected to include the same information as discussed above. In the same way, the database is in the initial state at the beginning of the scheduling process.

At step 404 the system selects a particular vehicle from the database. The selection may be based on the ordering of the vehicles by type or even by vehicle identification. For example, an airline may choose to dispatch its most expensive planes first in order to best utilize those particular planes, in which case the most expensive planes will be prioritized in the vehicle list, and thus one of these most expensive planes will be preferred.

Having completed selecting a particular vehicle, the system evaluates the state of the vehicle at step 406, finds the next time the vehicle will be available, and selects a set of feasible needs that it believes can be met by using the selected vehicle. For example, if the selected vehicle is listed in the database as being under maintenance or occupied in a previously scheduled operation past a specific date and time, the system can determine the specific date and time the vehicle will become available by excluding departure times The set of feasible requirements is selected from those requirements long before time. The system can also exclude at this stage requirements that are not feasible for the particular vehicle, such as those that require runway lights that are smaller than required by the aircraft in question or have a longer flight range than the aircraft in question. The needs of the destination airport. The system can also exclude requirements that may be technically feasible but have a low probability of yielding a profitable outcome if serviced by that particular vehicle, such as where the origin is located at a greater distance from the location of the vehicle than indicated in the database distance requirements. It is possible to ignore this step and use all the demand seat demand sets in the database; infeasible demands can be excluded at a later stage. However, selecting a feasible demand set reduces the number of calculations.

At step 408, the system selects one of the demands in the set from step 406, and then at step 410 calculates a schedule score for the demand based on the assumption that the particular vehicle selected at step 404 will be used to satisfy the demand. part. The step of calculating the schedule segment can be performed using steps similar to those discussed above in order to select the best resources such as flight attendants and gates, complete the schedule segment and adjust the departure time to be on the aircraft if necessary. A departure time on or after the available time. The same here, at step 412 , the system computes a result function for the possible schedule segments obtained from step 410 . As discussed above, the outcome function may include financial outcomes for possible schedule segments, such as CTMs. Optionally, the outcome function may include a penalty for the idle time the aircraft spends from its availability time to its departure time. At step 414, the system can determine whether all requirements in the requirements set from step 406 have been processed to completion. If not, the system returns to step 408, selects another requirement from the set and repeats steps 410 and 412 for that requirement to provide a feasible time period and associated result function for the next requirement. The process continues until all feasible demands have been processed to produce possible schedule segments and associated result functions. The system then moves to step 416 where the system selects the particular requirement that produces the highest result function, such as the highest CTM, among all requirements in the set from step 406 . In this regard, if step 406 is ignored or step 406 uses such broad criteria that the set includes infeasible requirements, the system will determine feasibility in the step of computing possible schedule segments (step 410) and learn from step 416 Any requirements that make it infeasible are excluded from the selection.

Once the selection of the best outcome is complete, the schedule fragment is set by taking the conditions specified in the possible schedule section associated with the best outcome and submitting the resources including the selected vehicles and other resources to the schedule fragment . Accordingly, the database is updated at step 418 with a new state indicating that the selected vehicle and any other resources used in the set schedule segment are committed. Once the new state has been set, the system again returns to step 406 and selects a set of feasible requirements for the selected aircraft based on the new state. For example, if the most recent pass through steps 406-416 resulted in the setting of a schedule segment that took an aircraft destined for San Francisco and made the aircraft available for use at 3:00 pm on a particular day, the next time Going through steps 406-415 will result in selecting the demand that best utilizes the aircraft based on the aircraft's location in San Francisco and its available time at 3:00 pm for the day. The process continues until at step 420 the system determines that the vehicle is fully scheduled for the time interval to be covered by the generated schedule. If the vehicle has been fully dispatched, then at step 424 the system checks to determine if this was the last vehicle to be dispatched. If not, the system transfers back to step 404, selects the next vehicle and repeats steps 406-420 for that vehicle to plan a full schedule for the next vehicle in the same way; and the process repeats until all vehicles have been dispatched. means of transport, thereby completing the schedule.

Scheduling in this manner uses the same general approach as discussed above with reference to Figure 10, namely picking the condition that minimizes cost or maximizes some other outcome of a particular flight operation. In this embodiment, however, the requirements are selected in the order in which they become feasible for a particular aircraft. In other words, this embodiment has an aircraft traverse the schedule and find the best use of that aircraft at any time in the schedule, repeating the process until the aircraft has been fully scheduled for the desired time interval. In a variation of this process, the system may not calculate the entire schedule for each vehicle before selecting the next vehicle. For example, after setting a new state of record schedule segment for a particular vehicle, the system may transition back to step 404 and select another vehicle. The step of selecting a vehicle may in this embodiment be configured to select a vehicle from among all vehicles of a particular type based on the number of times the vehicle has been selected, whereby the vehicle that has been previously selected the least number of times will be picked. In this way, the system essentially finds the optimal use for each vehicle in a first operation from an initial state. Then, when the status of the system indicates that the vehicles have been dispatched for the first operation, the system again seeks the optimal use of the vehicles for the second operation. This process continues until all vehicles have been dispatched for all time intervals covered by the schedule.

In each of these embodiments, after the full schedule has been developed, the human operator or the system may decide to adjust resources as indicated schematically at step 428, or to change resources as indicated schematically at step 430 A strategy is used to formulate demand, and the process is repeated to generate another schedule. In the same way, schedules planned using various resource sets and different strategies can be quickly generated and compared with each other.

In another variation, the system may set a portion of the schedule using the vehicle order scheduling method discussed above with reference to FIG. 13 and may set parts of the schedule using the demand order method discussed above with reference to FIG. 11. other parts. In the embodiments discussed above, the scheduling process included resources other than vehicles, namely flight attendants and airport gates. In a more limited variation, the scheduling process discussed here can be used to schedule vehicles only, while external processes can be used to schedule other resources. In this more limited variant, the database may only contain information about vehicles.

It is desirable that the systems discussed above provide time for vehicle maintenance. For example, aircraft typically must be serviced at the end of each flight. This type of maintenance usually requires regular intervals and can be performed at any location. Therefore, it is desirable for the system to simply add the intervals maintained at the end of each flight. Other maintenance, often referred to as "C" and "D" maintenance, must be performed at designated maintenance centers, which may or may not be at the terminals served by the airline. This type of maintenance must be performed at intervals set by rules that may include, for example, a specified number of flight hours, takeoffs or landings, or calendar days, or some combination of these rules. As given above, the resource database maintained by the system contains status information for each aircraft that includes these factors. Whenever a particular aircraft is incorporated into a schedule segment, the system may review the database or portion of the database related to that aircraft. If the state of the aircraft at the end of the new schedule segment is that the aircraft requires maintenance, the system can simply pre-schedule the aircraft for the specific maintenance required, flag the resource database to indicate that the aircraft will be stopped during the desired interval (usually days or weeks) fly and pass a signal to a maintenance control system or human operator indicating when the aircraft will be available for maintenance and the type of maintenance required. In yet another variation, if the status information for a particular aircraft indicates that it is approaching a maintenance deadline, the system may set the aircraft to a destination at or near an appropriate maintenance base with lower labor costs, thereby increasing the cost of the next scheduled aircraft. Possibility to send aircraft to maintenance base or nearby. The ability to interface with the maintenance system and actually dispatch the aircraft with full knowledge of the maintenance required provides significant advantages.

Each of the systems discussed above begins the scheduling process based on the initial state of the aircraft and other resources, and builds a database of future states that the aircraft can be expected to be in at extrinsic times by generating schedule segments. Most typically, the initial state is the predicted state some time after execution of the scheduled operation. For example, an airline may use the system in January to generate a schedule for operations in July and August based on the assumed initial state of the aircraft on July 1. However, because the scheduling process is extremely fast, it can be used as a real-time scheduling tool, where the initial state is the observed state on the day of scheduling. Thus, the scheduling process may allow airlines to react to practical events such as weather disruptions by picking the most efficient schedule to fly from that date.

In the above discussion, outcome functions have been stated for financial outcomes such as CTM. However, non-financial results can also be assessed. For example, an outcome function for a particular demand could include the time a passenger waits to connect from a feeder flight. Wait times can be assessed independently or can be translated into a financial cost that reflects an airline's expectation that passengers inconvenienced by longer layover times will turn into less loyal customers. Such costs can be subtracted from the CTM to produce the final result function.

The calculations discussed above can be performed using a conventional general purpose computer 500 (FIG. 14), which includes the usual elements of a computer, such as a processor and memory to accommodate resource databases and schedule segments. The computer also includes programming elements comprising a computer readable medium 501 and a program stored on the medium, the program being executed to cause the computer to perform the steps discussed above. The medium 501 may be separate from or may be integrated with the memory used to store the resource database and schedule segments. For example, medium 501 may be a magnetic disk, magnetic disk, or solid-state memory incorporated into a computer. As shown schematically in Figure 14, one system for performing these calculations includes a computer 500 programmed to perform the operations discussed above; and also includes one or more input nodes 502 for providing input information, the The input information defines at least in part the services to be provided in the transport operation to be performed. In the illustrated embodiment, input nodes 502 are shown as input terminals, and these nodes may be used to provide any element with information to be processed in a method as discussed above. The system also includes at least one output node 506 configured to receive information representing at least a portion of the resources allocated to the schedule segments of the computer 500 . Output nodes 506 are desirably arranged to display or output this information in a human readable form, such as on a screen display or a printout. Although input node 502 and output node 506 are shown separately, these nodes may be combined with one another. Input and output nodes can be directly connected to computer 500 if these are in the same location as the computer. Nodes 502 and 506 may be located remotely from computer 500 and may be connected to the computer by any suitable communication means, for example by a local connection via the Internet 504 as schematically shown in FIG. 14 . Although computer 500 is shown in FIG. 14 as a single element, elements of computer 500 may be distributed at various locations and interconnected by any suitable means of communication. Additionally, while it is desirable that the input and output nodes be linked to the computer 500 via a network or other form of instant communication, this is not required; the input and output nodes may be arranged to provide input information and receive output information in hard copy or suitable electronic media, These hard copies or appropriate electronic media may be physically transferred between multiple nodes and computers.

The computer input nodes and output nodes form part of a larger transportation system including vehicles, such as aircraft 508, and terminals 510, such as airports. As discussed above, the schedule defines routes between terminals 510 , which correspond to physical routes 512 . Input and output nodes may be located at one or more terminals 510, or at another location.

While the invention is described herein with reference to specific embodiments, it should be understood that these embodiments are merely illustrative of the principles and applications of the invention. It is therefore to be understood that numerous modifications may be made to the exemplary embodiments and that other arrangements may be devised without departing from the spirit and scope of the invention as defined by the appended claims.

Claims (50)

1, a kind of for transport operation generate dispatch list by computer-implemented method, comprising:

A) provide ordered list for a plurality of demands of transporting between a plurality of origins and a plurality of destination, each demand is related with origin, destination and departure time or arrival time;

Use a computer and be used for:

B) schedule fragment is set, to satisfy a described demand in the described ordered list, the described step that described schedule fragment is set comprises the resource of distribution from one or more list of available resources, and

C) be used for revising described one or more list of available resources based on making of resource in step (b), revised state with indication; And

D) repeating step (b) and (c), make that according to the order of described demand in described tabulation be described a plurality of demand execution in step (b) and (c), and make and use the state that draws by step (c) to be each demand execution in step (b) at the previous demand of being close to.

2, the method for claim 1, the wherein said step that schedule fragment is set for demand comprises: with described demand in adjacent time range of departure time in adjust the departure time.

3, method as claimed in claim 2, the wherein said step that schedule fragment is set comprises: determine at least one result based on the departure time information relevant with load that makes that is used for described demand.

4, method as claimed in claim 2 wherein is based upon the before definite schedule fragment of other demand to small part and selects described time range.

5, the method for claim 1 is wherein carried out the described step that schedule fragment is set, and makes the result function of described schedule fragment satisfy one or more standards.

6, method as claimed in claim 5, wherein said one or more standards comprise: the maximization of the described result function of described schedule fragment or minimize.

7, method as claimed in claim 5, wherein said result function comprises: one or more finance values of described schedule fragment.

8, method as claimed in claim 7 also comprises: the described finance value that adds up to described schedule fragment is to obtain the total finance value of described dispatch list.

9, method as claimed in claim 7, wherein said each demand comprise the prediction load, and described method is further comprising the steps of: the described prediction load that obtains described demand to small part based on the one or more estimations to the market behavior.

10, method as claimed in claim 9, further comprising the steps of: as to adjust described one or more estimations to the market behavior; And use described adjusted estimation to come the repetition abovementioned steps to the market behavior.

11, the method for stating as claim 10, wherein said adjustment comprises the step of one or more estimations of the market behavior: adjust aspect at least one in price of charging at transportation and the value that provides in described transportation; And use at least one aspect of described price and value and the estimated relation between the transportation demand.

12, the method for stating as claim 11, at least one aspect of wherein said price and value comprises: the total value that the client pays for transportation.

13, method as claimed in claim 11, at least one aspect of wherein said price and value comprises: the Additional Services level that provides to the client in the transportation that exchange is bought.

14, method as claimed in claim 8, further comprising the steps of: as to revise resource; Use the described resource of having revised to repeat abovementioned steps at least some described demands.

15, method as claimed in claim 14, further comprising the steps of: the described total finance value of relatively utilizing the different resource collection to be realized.

16, the method for claim 1, the wherein said step that schedule fragment is set for demand comprises: to described need assessment result function; And if described result function satisfies one or more mark standards of abandoning for described demand dispatch service.

17, method as claimed in claim 16, wherein said one or more standards of abandoning comprise: lack one or more retention criteria.

18, the method for claim 1, the wherein said step that provides sequence table comprises: set up a plurality of sorting key wories; And described demand is sorted according to described a plurality of sorting key wories.

19, method as claimed in claim 18, wherein said sorting key word comprises: whether continuity value, described continuity value indication particular demands are one of them of a succession of demand of successfully being served by the single vehicles.

20, method as claimed in claim 18, wherein said sorting key word comprises: at least one finance value of described demand.

21, method as claimed in claim 18, wherein said sorting key word comprises: at least one in departure time and arrival time.

22, method as claimed in claim 18, the wherein said step that provides sequence table is further comprising the steps of: concern based on the one or more continuitys between the demand and revise the described tabulation of sorting according to described a plurality of sorting key wories.

23, method as claimed in claim 18, further comprising the steps of: revise described demand or described sorting key word at least one of them; And repetition abovementioned steps.

24, the method for claim 1, wherein said the Resources list is included in the resource database that ad-hoc location and time can use, and the wherein said step that schedule fragment is set for particular demands comprise from described origin can with described resource reduce resource.

25, method as claimed in claim 24, wherein said that the step of schedule fragment is set is further comprising the steps of for particular demands: for the time after the expection deadline of the described operation related with described demand, mobile resources is added to the described resource database that can use in the described destination related with described demand.

26, method as claimed in claim 24, further comprising the steps of: determine for the hope departure time related with described demand, in the described origin related with described demand can with described resource whether be not enough to allow to carry out the described operation related with described demand; And, then determine according to described database whether mobile resources is present in the another location and can describedly wishes that the operation of departure time in time relocates to the origin for having if like this.

27, method as claimed in claim 26, it is further comprising the steps of: if mobile resources can not describedly wish that the operation of departure time in time relocates to described origin for having, but then determine in described all resources after wishing the departure time feasible departure time the earliest of time spent all, and the departure time is set to the described feasible departure time the earliest.

28, method as claimed in claim 27, also comprise: can accept the feasible departure time the earliest in the departure time scope then return error message if can not find, described error message indication specific resources unavailable got rid of for particular demands schedule fragment has been set.

29, method as claimed in claim 28 also comprises: accumulation comes the information of a plurality of described error messages of the described transportation system of which resource constraint of self-indication operation.

30, method as claimed in claim 29 also comprises: adjust described resource according to the information of described accumulation; And use the resource of described adjustment to repeat abovementioned steps at least some described demands.

31, method as claimed in claim 25, wherein said mobile resources comprises the vehicles.

32, method as claimed in claim 28, wherein said mobile resources comprises the steward.

33, the method for claim 1 also comprises: edit described schedule fragment so that form dispatch list; And operate described transportation system according to described dispatch list.

34, method as claimed in claim 33, wherein said transportation system is an airline.

35, a kind of for transport operation generate dispatch list by computer-implemented method, comprising:

A) provide tabulation and the Resources list for a plurality of demands of between a plurality of origins and a plurality of destination, transporting, each demand and origin, destination and with departure time and arrival time at least one is related, and described the Resources list comprises a plurality of vehicles and the position of each vehicles of explanation and the information of time relation;

Use a computer and be used for:

B) from the described vehicles that described the Resources list, identify, select the vehicles;

C) from described list of requirements, select described a plurality of demands one of them, and schedule fragment is set satisfying selected demand by the selected vehicles being distributed to selected demand, and

D), revise described the Resources list and list of requirements and revised state with indication based on use and demand at the vehicles described in the step (c); And

E) repeating step (b) is to (d), makes to be described a plurality of demand execution in step (b) to (d), and makes the described state that uses the step (d) by contiguous previous repetition to draw carry out the step (c) that each repeats.

36, method according to claim 35, one of them step of the described a plurality of demands of wherein said selection comprises: based on using the selected vehicles that satisfy the demands, be each need assessment result function that demand is concentrated.

37, method according to claim 36, wherein for each concentrated demand of described demand, the step of described assessment result function comprises to the pot life of small part based on the selected vehicles, with described demand in adjacent time range of departure time in adjust the departure time, and the step of wherein said assessment result function to small part makes the departure time information relevant with load based on what be used for described demand.

38, method according to claim 36, the step of wherein said selection demand comprises: concentrate the demand of selecting to produce best described result function from described demand.

39, method according to claim 36, wherein said result function comprise one or more finance values.

40, according to the described method of claim 39, also comprise: add up to the described finance value of described schedule fragment, to obtain the total finance value of described dispatch list.

41, according to the described method of claim 39, wherein each demand comprises the prediction load, and described method is further comprising the steps of: the described prediction load that obtains described demand to small part based on the one or more estimations to the market behavior.

42, according to the described method of claim 41, further comprising the steps of: as to adjust one or more estimations to the market behavior; And use the estimation of being adjusted to come the repetition abovementioned steps to the market behavior.

43, according to the described method of claim 42, wherein said adjustment comprises the step of one or more estimations of the market behavior: adjust aspect at least one in price of charging at transportation and the value that provides in described transportation; And be applied in described price and be worth at least one aspect and the estimated relation between the transportation demand.

44, a kind of dispatching system that is used for transport operation comprises:

A) at least one input node can be operated the input information that has defined the service that provides at least in part in order to receive in described transport operation;

B) computing machine is connected to described at least one input node, and the input information that makes described input node be received can offer described computing machine, and described computing machine is carried out following operation according to described input information:

1) safeguard ordered list for a plurality of demands of transporting between a plurality of origins and a plurality of destination, each demand is specified specific origin, specific purpose ground and is specified from time of described specific origin and arrive time on described specific purpose ground at least one;

2) be provided with schedule fragment with satisfy in the described ordered list described demand one of them, the described step that schedule fragment is set comprises the resource of distribution from one or more list of available resources, carry out the described step that schedule fragment is set, make the result function of described schedule fragment satisfy one or more standards; And

3) based on the use of resource in step (2), revise described one or more list of available resources, revised state with indication; And

4) repeating step (2) and (3), feasible order according to demand in the described tabulation is described a plurality of demand execution in step (2) and (3), and makes use come to be each demand execution in step (2) by the state of step (3) acquisition of contiguous previous demand; And

C) at least one output node is connected to described computing machine, makes expression can be provided for described at least one output node to the output information of at least some described resources of schedule fragment distribution.

45, system as claimed in claim 44, wherein said computing machine is connected with described at least one input node with described at least one output node by electronic communication network.

46, a kind of dispatching system that is used for transport operation comprises:

A) at least one input node can be operated the input information that has defined the service that provides at least in part in order to receive in described transport operation;

B) computing machine is connected to described at least one input node, and the input information that makes described input node be received can be provided for described computing machine, and described computing machine is carried out following operation according to described input information:

1) maintenance is for tabulation and one or more the Resources list of a plurality of demands of transporting between a plurality of origins and a plurality of destination, each demand is related with origin, destination and departure time or arrival time, and described the Resources list comprises a plurality of vehicles and the position of each vehicles of explanation and the information of time relation;

2) from the described one or more vehicles that described list of vehicles, identify, select the vehicles;

3) from described list of requirements, select described a plurality of demands one of them, and schedule fragment is set to satisfy selected demand by the selected vehicles being distributed to selected demand; And

4) based on the use of the vehicles in step (3) with demand is revised described one or more list of vehicles and list of requirements has been revised state with indication; And

5) repeating step (2) makes to be described a plurality of demand execution in step (2) to (4) to (4), and makes use carry out the step (3) that each repeats by the state of step (4) acquisition of previous repetition.

47, system as claimed in claim 44, wherein said computing machine is connected with described at least one input node with described at least one output node by electronic communication network.

48, a kind of transportation system comprises:

A) a plurality of vehicles;

B) a plurality of final positions;

C) at least one input node can be operated in order to receive to the input information that the service that provides has been provided small part in described transport operation;

D) computing machine is connected to described at least one input node, and the input information that makes described input node be received can be provided for described computing machine, and described computing machine is carried out as claim 1 or 36 described processes according to described input information; And

E) at least one output node is deployed in one or more described terminal locations and is connected to described computing machine, makes representative can offer described at least one output node by described process to the output information of the resource of schedule fragment distribution.

49, transportation system as claimed in claim 46, the wherein said vehicles comprise aircraft, and described final position comprises the airport.

50, a kind of programmed element that is used for computing machine comprises computer-readable medium, has program stored therein on the described computer-readable medium, and described program run is used to make computing machine to carry out as claim 1 or 36 described methods.

Images