Resource scheduler for scheduling railway train resources

• US 6,154,735 A
• Filed: 08/06/1998
• Issued: 11/28/2000
• 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: Crone, Michael S.
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US09/129,863
• Time in Patent Office: 845 Days
• Field of Search: 706/45, 706/16, 706/23, 706/61, 706/932
• US Class Current: 706/45
• 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 resource scheduler for scheduling railway train resources over a track system with a high degree of optimization. The scheduler is implemented in an expert system that employs simulated annealing techniques to approximate the optimum solution.

Claims

1. A resource scheduler for performing globally optimized scheduling of train resources using an abstraction of train movement and resources using a Constraint Propagation Expert System (COPES) shell as the virtual engine for developing algorithms which may be implemented on one or more machines in a Transmission Control Protocol/Internet Protocol (TCP/IP) environment, said algorithms moving time intervals abstracted from train resources, thereby providing a realizable solution in near real-time.

2. The resource scheduler of claim 1 wherein said virtual engine provides a constraint propagation inferencing environment.

3. The resource scheduler of claim 2 wherein said virtual engine also comprises built-in means for communication and means for providing a discrete-simulation.

4. The resource scheduler of claim 1 including means for receiving asynchronous requests to schedule and for alternatively (i) ceasing the scheduling process and reporting the best solution known at the time of the request or (ii) abandoning the then current scheduling process and initiating a new scheduling process inclusive of the request or means for asynchronously receiving commands to (iii) return status concerning the search process, or (iv) dynamically alter search parameters during a search, or (v) return a status based on certain conditions, or (vi) command to save the state of a schedule and receive subsequent commands to introduce anomalies into the partially complete schedule, and restart the scheduling process at some future time where some trips are either complete or in progress and other trips have not begun.

5. The resource scheduler of claim 4 wherein said certain conditions comprise a cost below a certain value.

6. A resource scheduler including a UNIX operating system with:

means for receiving orders (batch or sequentially) for rail service, each of the orders including the identification of the time interval over which the service is to be provided and a cost function (e.g., penalties/incentives);

means for receiving user-defined constraints;

means for receiving data as to the availability and capability of resources including train action effects and associated costs;

means for selecting resources to perform each activity in the orders;

means for providing an activity list for the selected resources for each of the orders;

means for converting the activity lists into time intervals;

means for grouping the time intervals for the orders;

means for moving the grouped time intervals relative to each other to effect scheduling consistent with user-defined constraints and minimum cost.

7. The resource scheduler of claim 6 wherein the means for includes a distributed simulated annealing processor.

8. The resource scheduler of claim 6 wherein the means for moving includes a focused simulated annealing processor.

9. The resource scheduler of claim 6 wherein the means for effecting the scheduling includes means for focusing attention on the critical areas during two phases,

said focusing means being responsive in the early phase to the likelihood of the degree of constraint of the solution and selected goals (e.g., minimum siding usage;

earliest delivery) to determine the selection and frequency of firing of move operators.

10. The resource scheduler of claim 6 wherein time intervals are combined based at least in part on the type of resource.

11. The resource scheduler of claim 6 wherein moves for resources having the highest number of exceptions are scheduled to fire more frequently than other resources.

12. The resource scheduler of claim 6 wherein the means for converting activity lists into time intervals comprises means for varying the length of the time interval depending on start time.

13. A train resource scheduler having

a Constraint Propagation Expert System (COPES) shell for developing a distributed algorithm in which train trips include a sequence of COPES class objects each representing a train resource having a time availability profile;

and including temporal logic means for manipulating said time availability profiles to reflect changes in train trips.

14. The resource scheduler of claim 13 in which said temporal logic means considers constraints (e.g., moving block distances) and in which global costs are modified as a side effect.

15. A method of distribution of a simulated annealing process by which multiple train trips are scheduled comprising the steps of:

(a) attaching constraint routines to each train trip; and

(b) using the constraint routines to make decisions about the modification of the schedule for each train trip based on the utility of the modification to the overall solution.

16. The method of claim 15 wherein the scheduling of each train trip for modification by the attached constraint routine is on a random basis with the time range being a variable indicative of the importance of the next move.

17. A method of scheduling resources to effect the movement of plural trains over a multitrack railway system including the steps of:

(a) abstracting resources and train movement;

(b) using simulated annealing techniques in a COPES shell to operate on the abstracts to thereby provide a schedule with the generation of move operators being influenced by the evaluation by the constraints attached to each trip of the usefulness of potential modifications of the schedule to the global solution constraints.

18. A method of scheduling trips of multiple trains over a multitrack railway system comprising the steps of:

(a) providing a COPES based inference engine;

(b) providing a plurality of constraint routines;

(c) providing a plurality of class objects each having at least one variable;

(d) binding one or more routines to each of the trips;

(e) providing a database containing resource usage times for each train type using each resource and siding possibilities between track segments;

(f) initializing search parameters;

(g) performing a first phase search by randomly scheduling trip constraints for firing, firing a constraint, and either

(i) determine that no change is required or

(ii) determine that a change is required, lower the temperature and reinitialize the search parameters;

(h) performing a second phase search using a reduced number of attempts at each temperature at the same or lower energy level to provide a schedule;

(i) performing a directed search to refine the schedule;

(j) alternatively reporting the schedule if all constraints are satisfied and reporting the best possible schedule with exceptions (including the identity of resources and activities involved in the exception) noted in the event that all constraints cannot be satisfied.

19. The method of claim 18 further comprising the step of providing a database containing alternate track routes which may be used for passes when parallel tracks are in operation.

20. A resource scheduler comprising:

means for receiving orders (batch or sequentially) for rail service, each of the orders including the identification of the time interval over which the service is to be provided and a cost function (e.g., penalties/incentives);

means for receiving user-defined constraints;

means for receiving data as to the availability and capability of resources including train action effects and associated costs;

means for selecting resources to perform each activity in the orders;

means for providing an activity list for the selected resources for each of the orders;

means for converting the activity lists into time intervals;

means for grouping the time intervals for the orders;

moving the grouped time intervals relative to each other to effect scheduling consistent with user-defined constraints and minimum cost.

21. The scheduler of claim 20 wherein the scheduling employs a dynamic and distributed simulated annealing within a COPES shell.

22. The scheduler of claim 20 wherein the scheduling is controlled, at least in part, by parameters provided by the scheduling request related to costs.

23. The scheduler of claim 20 wherein train trips are COPES class objects each having constraint objects bound thereto which fire independently of each other.

24. The scheduler of claim 20 wherein said moving is accomplished in plural phases, a first phase in which relatively large moves are permitted within a permissible time interval and a second phase in which relatively small moves are permitted, the size of the permitted move decreasing as the temperature decreases.

25. The scheduler of claim 20 wherein said moving is evaluated relative to both the feasibility of a schedule and the cost of a schedule.

26. The scheduler of claim 20 wherein one or more of said resources are abstracted.

27. The scheduler of claim 26 wherein the abstracted resources comprise one or more of trip segments, track switches, and track sidings.