System and method for scheduling and train control

• US 20040093245A1
• Filed: 05/16/2003
• Published: 05/13/2004
• Est. Priority Date: 09/01/1994
• Status: Active Grant

• Current Assignee: Alan L. Polvika, Douglas A. Thomae, Michael S. Crone, Paul M. Julich, Thu V. Vu, William L. Matheson, Wills M. Scott
• Original Assignee: Alan L. Polvika, Douglas A. Thomae, Michael S. Crone, Paul M. Julich, Thu V. Vu, William L. Matheson, Wills M. Scott
• Inventors: Vu, Thu V., Crone, Michael S., Polvika, Alan L., Julich, Paul M., Wills, M. Scott, Thomae, Douglas A., Matheson, William L.
• Granted Patent: US 7,343,314 B2
• Time in Patent Office: Days
• 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. In a multiple move, simulated annealing method for resolving a scheduling problem associated with a plurality of orders for train resources, each order having a cost function and a scheduling window associated therewith, the improvement comprising the steps of:

(a) establishing plural criteria for acceptance of a solution;

(b) classifying the scheduling problem; and

(c) selecting the criteria for acceptance of a solution as a function of the classification of the scheduling problem.

2. The method of claim 1 wherein the step of classifying includes the steps of:

(a) determining the total trip time associated with the plurality of orders;

(b) determining the total slack time associated with the plurality of orders;

(c) determining the classification of the problem as a function of the total trip time and the slack time.

3. The method of claim 2 wherein the classification is determined by the steps of:

(a) selecting a predetermined percentage of total trip time to provide a threshold value; and

(b) comparing slack time with the threshold value.

4. The method of claim 3 wherein the selected percentage is less than about one hundred percent.

5. The method of claim 3 wherein the selected percentage is more than about one hundred fifty percent.

6. The method of claim 1 wherein the step of classifying includes the steps of:

(a) determining the total trip time associated with the plurality of orders;

(b) determining the resource exception associated with the plurality of orders;

(c) determining the classification of the problem as a function of the total trip time and the resource exception.

7. The method of claim 6 wherein the classification is determined by the steps of:

(a) selecting a predetermined percentage of total trip time to provide a threshold value; and

(b) comparing resource exception with the threshold value.

8. In a multiple move, simulated annealing method for resolving a scheduling problem associated with a plurality of orders for train resources having an initial resource exception and a cost associated therewith by evaluating the resource exception and cost associated with each move during a search phase, the step of emphasizing cost over resource exception for a predetermined initial period of the search phase.

9. The method of claim 8 wherein the initial period is a function of one of (1) a predetermined number of moves and (2) the value of the resource exception.

10. The method of claim 9 wherein the initial period is limited to about one hundred moves.

11. The method of claim 9 wherein the initial period is limited to the time at which the value of the resource exception becomes less than about one percent.

12. The method of claim 8 wherein the step of emphasizing cost includes the steps of:

(a) classifying the scheduling problem;

(b) determining a maximum number of moves as a function of the classification of the scheduling problem;

(c) determining the initial resource exception associated with the scheduling problem;

(d) setting a threshold value as a predetermined percentage of the initial resource exception;

(e) emphasizing cost over resource exception until the first to occur of;

(i) a reduction of the resource exception below the threshold value, and

(ii) the maximum number of moves is reached.

13. A method for resolving a scheduling problem associated with a plurality of orders for train resources by evaluating available moves in a simulated annealing process, each move resulting in a change in the resource exception associated with the problem and a change in cost associated with the move, comprising the steps of:

(a) classifying the scheduling problem;

(b) making a random move;

(c) weighting the resource exception and cost factors associated with the random move with a scaling parameter related to the classification of the problem;

(d) evaluating the resource exception and the cost of the solution against a predetermined criteria; and

g) accepting or rejecting the move based on the evaluation.

14. The method of claim 13 wherein the step of determining the scaling parameter by the steps of:

(a) determining a normalizing component of the scaling parameter as a function of the change in resource exception and cost from previous moves;

(b) determining a target resource exception as a function of the number of previous moves; and

(c) determining a biasing component of the scaling parameter as a function of a comparison of the resource exception of the current move to the target resource exception.

15. The method of claim 14 wherein the predetermined criteria is the classification of the problem.

16. The method of claim 13 wherein the predetermined criteria is the classification of the problem.

17. In a multiple move, simulated annealing method of scheduling train resources by considering the resource exception value and the cost associated with each of the moves, the improvement comprising the step of limiting the total resource exception time to approximately one percent of the total unopposed trip time.

18. In a multiple move, simulated annealing method of solving a problem in the scheduling of train resources, the improvement comprising the step of reducing the level of acceptance of a solution in the evaluations of the results of early moves in order to preserve options for subsequent moves.

19. In a multiple move, simulated annealing method for resolving a scheduling problem associated with a plurality of orders for train resources having an initial resource exception and a cost associated therewith by evaluating the resource exception and cost associated with each move during a search phase, the steps of:

(a) providing a target resource exception; and

(b) weighting evaluations of the effects of subsequent moves on the resource exception and cost as a function of the departure of resource exception from the target.