Transportation scheduling system

• US 8,260,650 B2
• Filed: 02/21/2007
• Issued: 09/04/2012
• Est. Priority Date: 02/21/2006
• Status: Active Grant

• Current Assignee: Intelligent IP Corp.
• Original Assignee: Intelligent IP Corp.
• Inventors: Miller, H. Roy
• Primary Examiner(s): FLYNN, KEVIN H
• Application Number:
  US11/709,302
• Publication Number:
  US 20070214033A1
• Time in Patent Office: 2,022 Days
• Field of Search: 705/7.22, 705/7.23, 705/7.25, 705/7.31
• US Class Current: 705/7.22
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

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.

Claims

1. A computer-implemented method of generating a schedule for a transportation operation, comprising:

a) providing one or more lists of available resources and an ordered list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations in a memory of a computer, each demand being associated with an origin, a destination and a departure time;

b) using a processor of the computer to set a schedule fragment to satisfy one of the demands in the ordered list, the step of setting the schedule fragment including assigning a resource from the one or more lists of available resources by;

(i) selecting a resource from the one or more lists of available resources and determining whether the selected resource will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected resource to satisfy the demand, such evaluation including, based on a determination that the selected resource is not available at the departure time associated with the demand, modifying the departure time associated with the demand so that the selected resource is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time;

(iii) repeating steps (i)-(ii) for a plurality of resources; and

(iv) assigning to the demand that resource which yields a minimum value or a maximum value of the result function of the resources selected in steps (i)-(iii), and

c) using the processor of the computer to modify the one or more lists of available resources in the memory to indicate a revised state based on the assignment of resources in step (b); and

d) using the processor of the computer to repeat steps (b) and (c) so that steps (b) and (c) are performed for the plurality of demands according to the order of the demands in the list and so that step (b) for each demand is performed using the state resulting from step (c) for the immediately previous demand.

2. A method as claimed in claim 1 wherein the resources include vehicles.

3. A method as claimed in claim 1 wherein the step of modifying the departure time is performed within a range of times selected based at least in part upon previously-determined schedule fragments for other demands.

4. A method as claimed in claim 1 wherein the step of setting a schedule fragment is performed so that the result function for the schedule fragment meets one or more criteria.

5. A method as claimed in claim 4 wherein the one or more criteria includes maximization or minimization of the result function for the schedule fragment.

6. A method as claimed in claim 1 wherein the result function includes one or more financial values for the schedule fragment.

7. A method as claimed in claim 6 further comprising aggregating the financial values for the schedule fragments to derive an aggregate financial value for the schedule.

8. A method as claimed in claim 7 wherein each demand includes a predicted load, the method further including the step of deriving the predicted loads for the demands based at least in part on one or more estimates of market behavior.

9. A method as claimed in claim 8 further comprising the steps of adjusting the one or more estimates of market behavior, and repeating the aforesaid steps using the adjusted estimates of market behavior.

10. A method as claimed in claim 9 wherein the step of adjusting the one or more estimates of market behavior includes adjusting at least one aspect of a price to be charged for transportation and value to be offered in such transportation and applying an estimated relationship between the at least one aspect of the price and value and demand for transportation.

11. A method as claimed in claim 10 wherein the at least one aspect of price and value includes the amount to be paid by a customer for transportation.

12. A method as claimed in claim 10 wherein the at least one aspect of price and value includes a level of an ancillary service supplied to a customer in exchange for purchase of transportation.

13. A method as claimed in claim 7 further comprising the steps of modifying resources, repeating the aforesaid steps for at least some of the demands using the modified resources.

14. A method as claimed in claim 13 further comprising the step of comparing the aggregate financial values achieved with different sets of resources.

15. A method as claimed in claim 1 wherein the step of setting a schedule fragment for a demand includes scheduling no service for the demand if the result function for the demand with the assigned resource meets one or more drop criteria.

16. A method as claimed in claim 15 wherein the one or more drop criteria include the absence of one or more retention criteria.

17. A method as claimed in claim 1 wherein the step of providing an ordered list includes establishing a plurality of sort keys and ordering the demands according to the plurality of sort keys.

18. A method as claimed in claim 17 wherein the sort keys include a continuity value indicative of whether a particular demand is one of a series of demands to be served successfully by a single vehicle.

19. A method as claimed in claim 17 wherein the sort keys include at least one financial value for the demand.

20. A method as claimed in claim 17 wherein the sort keys include at least one of departure time and arrival time.

21. A method as claimed in claim 17 wherein the step of providing an ordered list further includes a step of modifying the list ordered according to the plurality of sort keys based upon one or more continuity relationships between demands.

22. A method as claimed in claim 17 further comprising a step of modifying at least one of the demands or the sort keys and repeating the aforesaid steps.

23. A method as claimed in claim 1 wherein the list of resources includes a database of resources available at particular locations and times and wherein the step of setting a schedule fragment for a particular demand includes deducting resources from the resources available at the origin.

24. A method as claimed in claim 23 further wherein the step of setting a schedule fragment for a particular demand further includes the step of adding mobile resources to the database of resources available at the destination associated with the demand for a time following an expected completion time of the operation associated with the demand.

25. A method as claimed in claim 23 further comprising the step of:

(x) determining that the resources available at the origin associated with the demand for a desired departure time associated with the demand are insufficient to allow the operation associated with the demand and,

(y) in response to the determination in (x), determining from the database whether mobile resources exist at another location and can be relocated to origin in time for an operation with the desired departure time.

26. A method as claimed in claim 25 further comprising the step, if mobile resources cannot be relocated to the origin in time for an operation with the desired departure time, determining the earliest feasible departure time after the desired departure time when all resources can be made available and setting a departure time at the earliest feasible departure time.

27. A method as claimed in claim 26 further comprising returning an error message indicating that unavailability of a particular resource precludes setting a schedule fragment for a particular demand if no earliest feasible departure time within a range of acceptable departure times can be found.

28. A method as claimed in claim 27 further comprising accumulating information from a plurality of the error messages indicative of which resources constrain operation of the transportation system.

29. A method as claimed in claim 28 further comprising adjusting the resources responsive to the accumulated information and repeating the aforesaid steps using the adjusted resources for at least some of the demands.

30. A method as claimed in claim 24 wherein the mobile resources include vehicles.

31. A method as claimed in claim 27 wherein the mobile resources include crews.

32. A method as claimed in claim 1 further comprising compiling the schedule fragments to form a schedule and operating the transportation system according to the schedule.

33. A method as claimed in claim 32 wherein the transportation system is an airline.

34. A computer-implemented method of generating a schedule for a transportation operation, comprising:

a) providing in a memory of a computer a list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations, each demand being associated with an origin, a destination and a departure time, and a list of resources including a plurality of vehicles and information specifying location of each vehicle versus time;

b) using a processor of the computer to select a vehicle from the vehicles identified in the list of resources;

c) using the processor of the computer to set a schedule fragment, the step of setting a schedule fragment including assigning the selected vehicle to a demand by;

(i) selecting a demand from the list of demands and determining whether the selected vehicle will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the selected demand, modifying the departure time associated with the demand so that the selected resource is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time;

(iii) repeating steps (i)-(ii) for a plurality of demands; and

(iv) assigning the selected vehicle to the demand which yields a minimum value or a maximum value of the result function of the demands selected in steps (i)-(iii), and

d) using a processor of the computer to modify the list of resources and list of demands in the memory to indicate a revised state based on the use of vehicles and demands in step (c); and

e) using a processor of the computer to repeat steps (b) through (d) so that steps (b) through (d) are performed for the plurality of demands and so that step (c) for each repetition is performed using the state resulting from step (d) for the immediately previous repetition.

35. A method as claimed in claim 34 wherein the result function includes one or more financial values.

36. A method as claimed in claim 35 further comprising aggregating the financial values for the schedule fragments to derive an aggregate financial value for the schedule.

37. A method as claimed in claim 35 wherein each demand includes a predicted load, the method further including the step of deriving the predicted loads for the demands based at least in part on one or more estimates of market behavior.

38. A method as claimed in claim 37 further comprising the steps of adjusting the one or more estimates of market behavior, and repeating the aforesaid steps using the adjusted estimates of market behavior.

39. A method as claimed in claim 38 wherein the step of adjusting the one or more estimates of market behavior includes adjusting at least one aspect of a price to be charged for transportation and value to be offered in such transportation and applying an estimated relationship between the at least one aspect of the price and value and demand for transportation.

40. A scheduling system for a transportation operation, comprising:

a) at least one input node operable to receive input information at least partially defining services to be provided in the transportation operation;

b) a computer connected to the at least one input node so that input information received by the input node will be supplied to the computer, the computer being operable in response to the input information to;

(1) maintain one or more lists of available resources and an ordered list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations, each demand specifying a particular origin, a particular destination and a time for departure from the particular origin;

(2) set a schedule fragment to satisfy one of the demands in the ordered list, the step of setting the schedule fragment including assigning a resource from the one or more lists of available resources, by;

(i) selecting a resource from the one or more lists of available resources and determining whether the selected resource will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected resource to satisfy the demand, such evaluation including, based on a determination that the selected resource is not available at the departure time associated with the demand, modifying the departure time associated with the demand so that the selected resource is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time; and

(iii) repeating steps (i)-(ii) for a plurality of resources; and

(iv) assigning to the demand that resource which yields the best value of the result function of the resources selected in steps (i)-(iii);

(3) modify the one or more lists of available resources to indicate a revised state based on the use of resources in step (2); and

(4) repeating steps (2) and (3) so that steps (2) and (3) are performed for the plurality of demands according to the order of the demands in the list and so that step (2) for each demand is performed using the state resulting from step (3) for the immediately previous demand; and

c) at least one output node connected to the computer so that output information representing at least some of the resources assigned to schedule fragments will be supplied to the at least one output node.

41. A system as claimed in claim 40 wherein the computer is connected with at least one output node and the at least one input node through an electronic communications network.

42. A scheduling system for a transportation operation, comprising:

a) at least one input node operable to receive input information at least partially defining services to be provided in the transportation operation;

b) a computer connected to the at least one input node so that input information received by the input node will be supplied to the computer, the computer being operable in response to the input information to;

(1) maintain a list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations, each demand being associated with an origin, a destination and a departure time and one or more lists of resources including a plurality of vehicles and information specifying location of each vehicle versus time;

(2) select a vehicle from the one or more vehicles identified in the list of vehicles;

(3) set a schedule fragment by assigning the selected vehicle to one of the demands from the list, the step of assigning the selected vehicle including;

(i) selecting a demand from the list of demands and determining whether the selected vehicle will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the selected demand, modifying the departure time associated with the demand so that the selected resource is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time;

(iii) repeating steps (i)(ii) for a plurality of demands; and

(iv) assigning the selected vehicle to the demand which yields the best value of the result function of the demands selected in steps (i)-(iii);

(4) modify the one or more lists of vehicles and list of demands to indicate a revised state based on the use of vehicles and demands in step (3); and

(5) repeat steps (2) through (4) so that steps (2) through (4) are performed for the plurality of demands and so that step (3) for each repetition is performed using the state resulting from step (4) for the immediately previous repetition.

43. A system as claimed in claim 42 wherein the computer is connected with at least one output node and the at least one input node through an electronic communications network.

44. A transportation system comprising:

a) a plurality of vehicles;

b) a plurality of terminal locations;

c) at least one input node operable to receive input information at least partially defining services to be provided in the transportation operation;

d) a computer connected to the at least one input node so that input information received by the input node will be supplied to the computer, the computer being operable in response to the input information to perform either;

A. a method including steps

     1) through

     4) of;

1) providing one or more lists of available vehicles and an ordered list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations in a memory of the computer, each demand being associated with an origin, a destination and a departure time;

using a processor of the computer to;

2) set a schedule fragment to satisfy one of the demands in the ordered list, the step of setting the schedule fragment including assigning a vehicle from the one or more lists of available resources by;

(i) selecting a vehicle from the one or more lists of available vehicles and determining whether the selected vehicle will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the demand, modifying the departure time associated with the demand so that the selected vehicle is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time; and

(iii) repeating steps (i)-(ii) for a plurality of vehicles; and

(iv) assigning to the demand that vehicle which yields the best value of the result function of the vehicles selected in steps (i)-(iii), and

3) modifying the one or more lists of available vehicles in the memory to indicate a revised state based on the assignment of vehicles in step (2); and

4) repeating steps (2) and (3) so that steps (2) and (3) are performed for the plurality of demands according to the order of the demands in the list and so that step (2) for each demand is performed using the state resulting from step (3) for the immediately previous demand;

or

B. a method including steps

     5) through

     9) of;

5) providing in a memory of the computer a list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations, each demand being associated with an origin, a destination and a departure time, and a list of vehicles and information specifying location of each vehicle versus time;

using a processor of the computer to;

6) select a vehicle from the vehicles identified in the list of vehicles;

7) set a schedule fragment, the step of setting a schedule fragment including assigning the selected vehicle to a demand by;

(v) selecting a demand from the list of demands and determining whether the selected vehicle will be available at the departure time associated with the demand;

(vi) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the selected demand, modifying the departure time associated with the demand so that the selected vehicle is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time;

(vii) repeating steps (v)-(vi) for a plurality of demands; and

(viii) assigning the selected vehicle to the demand which yields the best value of the result function of the demands selected in steps (v)-(vii), and

8) modifying the list of vehicles and list of demands to indicate a revised state based on the use of vehicles and demands in step (7); and

9) repeating steps (6) through (8) so that steps (6) through (8) are performed for the plurality of demands and so that step (7) for each repetition is performed using the state resulting from step (8) for the immediately previous repetition; and

e) at least one output node disposed at one or more of the terminal locations and connected to the computer so that output information representing vehicles assigned to schedule fragments by the process will be supplied to the at least one output node.

45. A transportation system as claimed in claim 44 wherein the vehicles include airplanes and the terminal locations include airports.

46. A computer-readable storage medium having a program stored thereon, the program being operative to cause a computer to perform either:

A. a method including steps

     1) through

     4) of;

1) providing one or more lists of available vehicles and an ordered list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations in a memory of the computer, each demand being associated with an origin, a destination and a departure time;

using a processor of the computer to;

2) set a schedule fragment to satisfy one of the demands in the ordered list, the step of setting the schedule fragment including assigning a vehicle from the one or more lists of available vehicles by;

(i) selecting a vehicle from the one or more lists of available vehicles and determining whether the selected vehicle will be available at the departure time associated with the demand;

(ii) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the demand, modifying the departure time associated with the demand so that the selected vehicle is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time; and

(iii) repeating steps (i)-(ii) for a plurality of vehicles; and

(iv) assigning to the demand that vehicle which yields the best value of the result function of the vehicles selected in steps (i)-(iii), and

3) modifying the one or more lists of available vehicles in the memory to indicate a revised state based on the assignment of vehicles in step (2); and

4) repeating steps (2) and (3) so that steps (2) and (3) are performed for the plurality of demands according to the order of the demands in the list and so that step (2) for each demand is performed using the state resulting from step (3) for the immediately previous demand;

or

B. a method including steps

     5) through

     9) of;

5) providing in a memory of the computer a list of a plurality of demands for transportation between a plurality of origins and a plurality of destinations, each demand being associated with an origin, a destination and a departure time, and a list of vehicles and information specifying location of each vehicle versus time;

using a processor of the computer to;

6) select a vehicle from the vehicles identified in the list of vehicles;

7) set a schedule fragment, the step of setting a schedule fragment including assigning the selected vehicle to a demand by;

(v) selecting a demand from the list of demands and determining whether the selected vehicle will be available at the departure time associated with the demand;

(vi) evaluating a result function associated with assignment of the selected vehicle to satisfy the demand, such evaluation including, based on a determination that the selected vehicle is not available at the departure time associated with the selected demand, modifying the departure time associated with the demand so that the selected vehicle is available at the modified departure time, and evaluating an effect of the modified departure time on the result function, the step of evaluating an effect of the modified departure time including evaluating load for the demand as a function of departure time;

(vii) repeating steps (v)-(vi) for a plurality of demands; and

(viii) assigning the selected vehicle to the demand which yields the best value of the result function of the demands selected in steps (v)-(vii), and

8) modifying the list of vehicles and list of demands to indicate a revised state based on the use of vehicles and demands in step (7); and

9) repeating steps (6) through (8) so that steps (6) through (8) are performed for the plurality of demands and so that step (7) for each repetition is performed using the state resulting from step (8) for the immediately previous repetition.