Transportation scheduling system

• US 20070214033A1
• Filed: 02/21/2007
• Published: 09/13/2007
• Est. Priority Date: 02/21/2006
• Status: Active Grant

• Current Assignee: Intelligent IP Corp.
• Original Assignee: Dynamics Intelligence Inc.
• Inventors: Miller, H.
• Granted Patent: US 8,260,650 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• 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 an ordered 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 or arrival time;

using a computer to;

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

c) modifying the one or more lists of available resources to indicate a revised state based on the use of resources in step (b); and

d) repeating 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 next previous demand.

2. A method as claimed in claim 1 wherein the step of setting a schedule fragment for a demand includes adjusting a departure time within a range of times adjacent to a departure time in the demand.

3. A method as claimed in claim 2 wherein the step of setting a schedule fragment includes determining at least one result based upon information relating departure time to load for the demand.

4. A method as claimed in claim 2 wherein the range of times is selected based at least in part upon previously-determined schedule fragments for other demands.

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

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

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

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

9. 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.

10. A method as claimed in claim 9 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.

11. A method as claimed in claim 10 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.

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

13. A method as claimed in claim 11 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.

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

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

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

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

18. 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.

19. A method as claimed in claim 18 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.

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

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

22. A method as claimed in claim 18 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.

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

24. 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.

25. A method as claimed in claim 24 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.

26. A method as claimed in claim 24 further comprising the step of determining if 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, if so, 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.

27. A method as claimed in claim 26 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.

28. A method as claimed in claim 27 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.

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

30. A method as claimed in claim 29 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.

31. A method as claimed in claim 25 wherein the mobile resources include vehicles.

32. A method as claimed in claim 28 wherein the mobile resources include crews.

33. 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.

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

48. 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 a process as claimed in claim 1 or claim 36 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 resources assigned to schedule fragments by the process will be supplied to the at least one output node.

50. A programming element for a computer comprising a computer-readable medium having a program stored thereon, the program being operative to cause a computer to perform a method as claimed in claim 1 or claim 36.

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

a) providing 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 at least one of a departure time and an arrival time, and a list of resources including a plurality of vehicles and information specifying location of each vehicle versus time;

using a computer for;

b) selecting a vehicle from the vehicles identified in the list of resources;

c) selecting one of the demands from the list of the demands and setting a schedule fragment to satisfy the selected demand by assigning the selected vehicle to the selected demand, and

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

e) repeating 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 next previous repetition.

36. A method as claimed in claim 35 wherein the step of selecting one of the demands includes evaluating a result function for each one of a set of demands based on using the selected vehicle to meet that demand.

37. A method as claimed in claim 36 wherein, for each demand of the set of demands, the step of evaluating a result function includes adjusting a departure time within a range of times adjacent to a departure time in the demand based at least in part on a time of availability of the selected vehicle and wherein the step of evaluating a result function is based at least in part upon information relating departure time to load for the demand.

38. A method as claimed in claim 36 wherein the step of selecting a demand includes selecting the demand from the set which yields the best result function.

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

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

41. A method as claimed in claim 39 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.

42. A method as claimed in claim 41 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.

43. A method as claimed in claim 42 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.

44. 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 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 at least one of a time for departure from the particular origin and a time for arrival at the particular destination;

(2) set a schedule fragment to satisfy one of the demands in the ordered list, the step of setting the schedule fragment including assigning resources from one or more lists of available resources, the step of setting the schedule fragment being performed so that a result function for the schedule fragment meets one or more criteria;

(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 next 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.

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

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

46. 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 from or arrival 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) select one of the demands from the list of the demands and set a schedule fragment to satisfy selected demand by assigning the selected vehicle to the selected demand;

(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 previous repetition.

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