Scheduling system and method

• US 7,340,328 B2
• Filed: 05/16/2003
• Issued: 03/04/2008
• 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): Doren; Beth Van
• Assistant Examiner(s): BOYCE, ANDRE D
• Application Number:
  US10/438,822
• Publication Number:
  US 20040034556A1
• Time in Patent Office: 1,754 Days
• Field of Search: 705/8, 701/19
• US Class Current: 701/19
• 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/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
• 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/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• 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 scheduling system utilizes a cost reactive resource scheduler to minimize resource exception while at the same time minimizing the global costs associated with the solution. 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 a use of resources in a railway system having a plurality of trains for movement along a network of track to reduce a cost of implementing the plan, the method comprising:

(a) developing strategic schedule constraints in a rule based inference engine for movement of the trains along the network of track based on user-defined railway operating rules and an optimization of proposed schedules under relaxed constraint conditions;

(b) developing a detailed movement plan for the plurality of trains along the network of track using a constraint based analysis based upon the strategic schedule constraints and an optimization of the costs of the movement plan;

(c) communicating the movement plan to the trains;

(d) determining train throttle and brake settings of a respective train for implementing the plan; and

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

2. The method of claim 1 wherein said determining is based at least in part on train handling constraints.

3. The method of claim 1 wherein said determining is based at least in part on track parameters.

4. The method of claim 1 wherein the detailed movement plan is developed at least in part on a stopping distance of the train.

5. The method of claim 1 wherein said developing strategic schedule constraints is based at least in part on terminal equipment constraints.

6. The method of claim 1 wherein said developing strategic schedule constraints is based at least in part on maintenance of way constraints.

7. The method of claim 1 wherein said developing strategic schedule constraints is based at least in part on schedule priority for scheduled passenger train traffic.

8. The method of claim 1 wherein the optimization of costs is done within a predetermined tolerance of the costs of the movement plan.

9. The method of claim 1 further comprising providing a model simulating the railway system and wherein said developing of the movement plan is done via the use of the model.

10. The method of claim 9 further comprising providing a model simulating the system and wherein said developing strategic schedule constraints on train movement is done via the use of the model.

11. The method of claim 10 wherein the system model used in the development of the schedule constraints has a higher level of abstraction than that used in the development of the movement plan.

12. The method of claim 1 wherein said determining is based at least in part on topography of the track.

13. A method of scheduling plural trips of a plurality of trains along a network of track, the method comprising:

(a) identifying activities required for each of a plurality of desired trips and 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 desired trips;

(f) seeking the scheduling of the desired trips within the constraints using a constraint based inference engine;

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

(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,

wherein the resources are one of the group comprising locomotives, railway cars, wayside equipment, loading equipment and track segments.

14. A system for planning over a predetermined period of time the use of resources in a railway system having a plurality of trains for movement along a network of track to reduce the costs of implementing the plan, comprising:

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

(b) a constraint based analyzer for developing a detailed movement plan based upon the schedule constraints and an optimization of the movement plan;

(c) a communications channel for communicating the detailed movement plan to the trains;

(d) a processor on the trains for determining throttle and brake settings for implementing the plan; and

(e) a control unit operatively connected to processor for controlling the train in accordance with said settings.

15. A system for scheduling plural trips of a plurality of trains along a network of track comprising:

(a) a processor for identifying activities required for each of a plurality of desired trips and constraints thereof;

(b) a processor for identifying available resources;

(c) a processor for assigning resources to each activity;

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

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

(f) a processor for seeking the scheduling of desired trips within the constraints;

(g) a processor for dividing the desired trips into smaller trip segments, if unable to schedule the entire desired trips;

(h) a processor for seeking the scheduling of the smaller trip segments within the constraints;

(i) a communications channel for reporting the schedule if successful in scheduling the segments; and

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

16. The system of claim 15 further comprising,

a processor for providing data relating to a cost associated with each of the resources;

and

a processor for assigning the available resources to the activities to minimize the costs of the resources.

17. A method of planning an implementation of a schedule of orders over a system having a plurality of trains for movement along a network of track, the method comprising:

(a) providing a schedule of orders to be implemented over a system having a plurality of trains for movement along a network of track;

(b) identifying the trains on the track necessary to implement each of the orders;

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

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

(e) displaying a planned implementation of the schedule; and

(f) controlling an operation of the trains in accordance with the planned implementation of the schedule.

18. The method of claim 17 including the further steps of:

identifying a cost of each of the trains; and

optimizing the resolution of conflicts as a function of costs.

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

20. The method of claim 17 wherein the model takes into consideration one factor of the group of factors comprising track topology, train handling rules, proximity limits, control mechanics, fixed blocks, movable blocks and train characteristics.

21. The method of claim 17 wherein said controlling the operation of the trains further comprises communicating the planned implementation of the schedule to a train operator for operating the train in accordance therewith.

22. A system for optimizing a movement of plural trains through a multi-path railway system, the system comprising:

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

a processor for optimizing the movement of plural trains through the system to provide a coarse schedule which meets the broadly defined constraints;

a processor for abstracting the model of the system to a relatively low level wherein system constraints are defined with particularity; and

,

a processor for optimizing the movement of the same plural trains through the system within the constraints of the coarse schedule to provide a finer schedule which meets the particularly defined constraints;

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

23. A computer program product for use with a railway scheduling computer, said computer program product comprising:

a computer usable medium having computer readable program code modules embodied in said medium for planning over a predetermined period of time the use of resources in a railway system having a plurality of trains for movement along a network of track to reduce a cost of implementing the plan;

a computer readable first program code module for causing a computer to develop strategic schedule constraints for movement of the trains along the network of tracks based on user-defined railway operating rules and an optimization of proposed schedules under relaxed constraint conditions; and

a computer readable second program code module for causing said computer to develop a detailed movement plan for the plurality of trains along the network of track using a constraint based analysis based upon the strategic schedule constraints and an optimization of the costs of the movement plan,

wherein said movement plan is communicated to the plurality of trains and wherein the motion of the plurality of trains is controlled as a function of said movement plan.

24. A computer program product for use with a railway scheduling computer, said computer program product comprising:

a computer usable medium having computer readable program code modules embodied in said medium for scheduling plural trips of a plurality of trains along a network of track;

a computer readable first program code module for causing a computer to identify activities required for each of a plurality of desired trips and associated constraints;

a computer readable second program code module for causing said computer to identify available resources;

a computer readable third program code module for causing said computer to assign the identified resources to each of the identified activities;

a computer readable fourth program code module for causing said computer to convert each of the identified activities into a time interval;

a computer readable fifth program code module for causing said computer to group the time intervals into the desired trips within the associated constraints;

a computer readable sixth program code module for causing said computer to divide the desired trips into smaller segments and seek to schedule the smaller segments within the associated constraints if all the desired trips are not able to be scheduled within the associated constraints using the time intervals; and

a computer readable seventh program code module for causing said computer to report the schedule if the scheduling of the smaller segments is successful, and report the schedule with conflicts if the scheduling of the smaller segments is unsuccessful.

25. A computer program product for use with a railway planning computer, said computer program product comprising:

a computer usable medium having computer readable program code modules embodied in said medium for planning an implementation of a schedule of orders over a system having a plurality of trains for movement along a network of track;

a computer readable first program code module for causing a computer to retrieve the schedule of orders;

a computer readable second program code module for causing said computer to identify from the plurality of trains, a subset of trains on the track necessary to implement each of the orders;

a computer readable third program code module for causing said computer to provide a detailed model of the system over which the schedule of orders is to be implemented;

a computer readable fourth program code module for causing said computer to simulate the schedule of orders on the detailed model to identify and resolve conflicts, and determine a planned implementation based upon the simulation;

a computer readable fifth program code module for causing said computer to display the planned implementation of the schedule of orders; and

a computer readable sixth program code module for causing said computer to control an operation of the subset of trains in accordance with the planned implementation.

26. A computer program product for use with a railway scheduling computer, said computer program product comprising:

a computer usable medium having computer readable program code modules embodied in said medium for optimizing a movement of plural trains through a multi-path railway system;

a computer readable first program code module for causing a computer to abstract a model of the system to a relatively high level wherein system constraints are broadly defined;

a computer readable second program code module for causing said computer to optimize the movement of the plural trains through the system to provide a coarse schedule which meets the broadly defined constraints;

a computer readable third program code module for causing said computer to abstract the model of the system to a relatively low level wherein system constraints are defined with particularity; and

a computer readable fourth program code module for causing said computer to optimize the model of the plural trains through the system within the constraints of the coarse schedule to provide a finer schedule which meets the particularly defined constraints.

27. The computer product of 26, wherein a solution space over which the optimization occurs diminishes as detail is added to the model.