Scheduling system and method

• US 5,623,413 A
• Filed: 09/01/1994
• Issued: 04/22/1997
• Est. Priority Date: 09/01/1994
• Status: Expired due to Fees

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Julich, Paul M., Vu, Thu V., Crone, Michael S., Wills, M. Scott, Thomae, Douglas A., Matheson, William L.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Walker, Tyrone V.
• Application Number:
  US08/299,271
• Time in Patent Office: 964 Days
• Field of Search: 364/426.05, 364/401, 364/402, 364/406, 364/468, 364/436, 246/1 R, 246/2 R, 246/2 F, 104/307, 395/902
• US Class Current: 701/117
• CPC Class Codes: B61L 2205/04 Satellite based navigation systems, e.g. global positioning system [GPS]
• CPC Class Codes: B61L 27/12 Preparing schedules
• CPC Class Codes: B61L 27/14 Following schedules
• CPC Class Codes: B61L 27/16 Trackside optimisation of vehicle or train operation
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: Y10S 706/932 Mathematics, science, or engineering

Abstract

A scheduling system and method for moving plural objects through a multipath system described as a freight railway scheduling system. The achievable movement plan can be used to assist in the control of, or to automatically control, the movement of trains through the system.

Claims

1. A method of planning over a predetermined period of time the use of resources in a freight railway system to reduce the costs of the plan, comprising the steps of:

(a) developing strategic schedule constraints on train movement in a rule based inference engine based on user-defined freight railway operating rules and an optimization of proposed schedules under relaxed constraint conditions; and

(b) developing a detailed movement plan in a constraint based inference engine based upon an optimization within a predetermined tolerance of the costs of the movement plan wherein the strategic schedule constraints developed by the rule based inference engine are provided as sequencing constraints to the constraint based inference engine for development of the movement plan.

2. The method of claim 1 including the further steps of:

c) communicating the movement plan to a train;

d) determining on the train throttle and brake settings related to the plan;

e) controlling the train in accordance with said settings; and

,

f) repeating steps (e) and (d) plural times.

3. The method of claim 2 wherein said determining is related to train handling constraints.

4. The method of claim 2 wherein said determining is related to track parameters.

5. The method of claim 2 including the selective overriding of said controlling by a controller remote from said train.

6. The method of claim 1 wherein the plan is developed with reference to track parameters.

7. The method of claim 1 wherein the plan is developed with reference to the stopping distance of the train and to the ambiguity of the position of the train on the track.

8. The method of claim 1 wherein the plan is developed so that it terminates with the train in a safe position on the track.

9. The method of claim 2 wherein the step of communicating is repeated with a new plan before the train reaches the end of the first plan.

10. The method of claim 1 wherein the step of developing strategic schedule constraints comprises the step of accounting for terminal equipment constraints.

11. The method of claim 1 wherein the step of developing strategic schedule constraints comprises the step of accounting for maintenance of way constraints.

12. The method of claim 1 wherein the step of developing strategic schedule constraints comprises the step of accounting for and giving schedule priority to scheduled passenger train traffic.

13. The method of claim 1 further comprising the step of not scheduling a train movement in order to schedule remaining train movements when all train movements cannot be scheduled.

14. The method of scheduling plural trips comprising the steps of:

(a) identifying the activities required for each desired trip and the constraints thereof;

(b) identifying available resources;

(c) assigning the identified resources to each of the activities;

(d) converting each of the activities into a time interval;

(e) grouping time intervals into the desired trips;

(f) seeking the scheduling of entire trips within the constraints;

(g) dividing the trips into smaller segments and seeking the scheduling of the segments within the constraints if unable to schedule entire trips;

(h) if successful in scheduling the segments, reporting the schedule; and

(i) if unsuccessful in scheduling the segments, reporting the schedule with the conflicts identified.

15. The method of claim 14 wherein the step of converting activities to time intervals includes consideration of train action effects.

16. The method of claim 14 wherein the groups of time intervals are permitted to overlap predetermined amounts.

17. The method of claim 14 wherein the groups of time intervals are treated as fixed blocks in seeking to schedule.

18. The method of claim 14 wherein the groups of time intervals are treated as moving blocks in seeking to schedule.

19. The method of claim 14 including the further steps of:

providing data relating to the operating cost associated with each of the resources as a function of time; and

assigning the available resources to the activities to minimize the operational costs of the resources.

20. A system for planning over a predetermined period of time the use of resources in a freight railway system to reduce the costs of the plan, comprising:

(a) a rule based inference engine for developing strategic schedule constraints on train movement based on user-defined freight railway operating rules and an optimization of proposed schedules under relaxed constraint conditions; and

(b) a constraint based inference engine for developing a detailed movement plan based upon an optimization within a predetermined tolerance of the costs of the movement plan wherein the strategic schedule constraints developed by said rule based inference engine are provided as sequencing constraints to said constraint based inference engine for development of the movement plan.

21. The system of claim 20 further comprising:

(c) means for communicating the detailed movement plan to a train;

(d) means on said train for determining throttle and brake settings related to the plan; and

(e) means operatively connected to said means for determining throttle and brake settings for controlling the train in accordance with said settings.

22. A system for scheduling plural trips comprising:

(a) means for identifying the activities required for each desired trip and the constraints thereof;

(b) means for identifying available resources;

(c) means for assigning resources to each activity;

(d) means for converting each of the activities into a time interval;

(e) means for grouping time intervals into the desired trips;

(f) means for seeking the scheduling of entire trips within the constraints;

(g) means for dividing the trips into smaller segments if unable to schedule entire trips;

(h) means for seeking the scheduling of the segments within the constraints

(i) means for reporting the schedule if successful in scheduling the segments; and

(j) means for reporting the schedule with the conflicts identified if unsuccessful in scheduling the segments.

23. The system of claim 22 further comprising,

means for providing data relating to the operating cost associated with each of the resources as a function of time;

and

means for assigning the available resources to the activities to minimize the operational costs of the resources.

24. A method of planning the implementation of an order schedule over a system comprising the steps of:

(a) providing the order schedule to be implemented;

(b) identifying the resources and location of resources necessary to implement each of the orders;

(c) providing a detailed model of the system over which the schedule is to be implemented;

(d) simulating the schedule on the model to identify and resolve conflicts;

(e) displaying a planned implementation of the schedule

(f) communicating to a train the train'"'"'s portion of the planned implementation; and

(g) determining in a processor on the train throttle and brake settings for implementing the plan.

25. The method of claim 24 including the further steps of:

identifying delivery cost;

identifying the operating cost of each of the resources as a function of time; and

optimizing the resolution of conflicts as a function of costs.

26. The method of claim 24 including the further step of optimizing by the use of branch and bound techniques.

27. The method of claim 24 wherein the model takes into consideration system topology, handling rules, proximity limits, control mechanics (fixed or movable blocks) and resource characteristics.

28. The method of claim 24 including the further step of controlling the train in accordance with said settings responsive to signals from the processor.

29. A method of planning the movement of plural trains through a multipath railway system comprising the steps of:

(a) developing a schedule for train movement using the combination of a rule based inference engine and a constraint based inference engine, wherein constraints generated by the rule based inference engine are provided as sequencing constraints to the constraint based inference engine;

(b) providing the schedule and cost data relating to the trains to a procedure based inference engine for optimizing the schedule into a movement plan; and

(c) displaying the modified movement plan.

30. The method of claim 29 wherein the display of the movement plan from the procedure based inference engine requires prior approval by the rule based inference engine.

31. The method of claim 29 wherein the movable resource data is statistical in the development of the schedule and simulated in the development of the movement plan.

32. The method of claim 31 wherein the same system model is used in the development of the schedule and the movement plan.

33. The method of claim 32 wherein the system model is used in the development of the schedule has a higher level of abstraction than as used in the development of the movement plan.

34. The method of claim 29 including the further step of:

(d) alternatively providing the movement plan;

(i) to a display,

(ii) to the rule based inference engines for rescheduling by relaxation of a rule;

or

(iii) to the constraint based inference engine for rescheduling by the relaxation of a constraint.

35. The method of claim 29 including the further steps of:

(d) communicating the modified movement plan to a train;

(e) determining throttle and brake settings related to the plan; and

(f) controlling the train in accordance with said settings.

36. A method of scheduling the orders relating to the use of plural resources over time in a single system comprising the steps of:

(a) providing data relating to;

(i) the activities required to accomplish each of the orders,

(ii) delivery cost associated with each of the desired orders,

(iii) selected constraints, and

(iv) the availability of resources; and

(b) determining the possible assignment of available resources to each of the identified activities as a function of resource capability;

(c) converting the assigned activities to time intervals;

(d) grouping the time intervals into complete orders;

(e) seeking the scheduling of entire orders with satisfaction of all of the constraints;

(f) if able to schedule entire orders, adjusting the orders within the constraints as a function of delivery cost, and reporting the schedule;

(g) if unsuccessful in scheduling entire orders, dividing at least one of the complete orders into smaller groups of time intervals;

(h) seeking the scheduling of the divided orders with satisfaction of all of the constraints;

(i) if successful in scheduling the divided orders, adjusting the groups of time intervals within the constraints as a function of delivery cost and reporting the schedule; and

(j) if unsuccessful in scheduling the divided orders, reporting the schedule with the conflicts identified.

37. The method of claim 36 including the further steps of:

providing data relating to the operating cost associated with each of the resources as a function of time; and

assigning the available resources to the activities to minimize the operational costs of the resources.

38. The method of claim 36 wherein the system is a railway system and wherein the resources are train engines and cars, loading equipment, and track segments including the location where time gaps may be inserted.

39. The method of claim 36 wherein the step of converting activities to time intervals includes consideration of train action effects.

40. The method of claim 36 wherein the groups of time intervals are permitted to overlap predetermined amounts.

41. The method of claim 36 wherein the groups of time intervals are treated as fixed blocks in seeking to schedule.

42. The method of claim 36 wherein the groups of time intervals are treated as moving blocks in seeking to schedule.

43. A method of scheduling plural trips through a multipath system comprising the steps of:

(a) identifying the activities required for each desired trip and associating the cost thereof;

(b) identifying available resource;

(c) assigning resources to each activity;

(d) converting each activity into a time interval;

(e) grouping time intervals into the desired trips;

(f) scheduling entire trips;

(g) dividing the trips into smaller segments if unable to schedule entire trips; and

(h) scheduling segments and reporting the schedule.

44. The method of claim 43 including the further step of reporting the best schedule with all conflicts identified.

45. The method of claim 43 including the further steps of:

communicating the schedule to a train;

providing a computer on the train for determining throttle and brake settings which will allow the train to carry out the schedule; and

controlling the train in accordance with said settings.

46. A system for scheduling orders relating to the use of plural resources over time in a single system comprising:

(a) means for providing data relating to;

(i) the activities required to accomplish each of the orders,

(ii) delivery cost associated with each of the desired orders,

(iii) selected constraints, and

(iv) the availability of resources; and

(b) means for determining the possible assignment of available resources to each of the identified activities as a function of resource capability;

(c) means for converting the assigned activities to time intervals;

(d) means for grouping the time intervals into complete orders;

(e) means for seeking the scheduling of entire orders with satisfaction of all of the constraints;

(f) if able to schedule entire orders, means for adjusting the orders within the constraints as a function of delivery cost, and reporting the schedule;

(g) if unsuccessful in scheduling entire orders, means for dividing at least one of the complete orders into smaller groups of time intervals;

(h) means for seeking the scheduling of the divided orders with satisfaction of all of the constraints;

(i) if successful in scheduling the divided orders, means for adjusting the groups of time intervals within the constraints as a function of delivery cost and reporting the schedule; and

(j) if unsuccessful in scheduling the divided orders, means for reporting the schedule with the conflicts identified.

47. The system of claim 46 wherein said means for determining further comprises means for providing data relating to the operating cost associated with each of the resources as a function of time.

48. The system of claim 47 wherein both said means for seeking further comprise means for seeking a schedule wherein the operating costs are minimized.

49. A system for planning the movement of plural trains through a multipath railway system comprising:

(a) means for developing a schedule for movement of trains using the combination of a rule based inference engine and a constraint based inference engine in which constraints generated by said rule based inference engine are provided as sequencing constraints to said constraint based inference engine;

(b) means for providing the schedule and cost data relating to the trains to a procedure based inference engine for optimizing the schedule into a movement plan;

(c) means for communicating the movement plan to a one of the trains;

(d) a computer on the one train for determining throttle and brake settings related to the movement plan; and

(e) means operatively connected to said computer for controlling the one train in accordance with said settings.

50. A method of optimizing the movement of plural trains through a multipath railway system, comprising the steps of:

(a) abstracting a model of the system to a relatively high level wherein system constraints are broadly defined;

(b) optimizing the movement of plural trains through the system to provide a coarse schedule which meets the broadly defined constraints;

(c) abstracting the model of the system to a relatively low level wherein system constraints are defined with particularity; and

,

(d) optimizing the movement of the same plural trains through the system within the constraints of the first schedule to provide a finer schedule which meets the particularly defined constraints;

whereby the optimization is hierarchical in nature such that the solution space over which the search for optimizing occurs diminishes as detail is added to the model.