Train corridor scheduling process

• US 6,873,962 B1
• Filed: 12/30/1999
• Issued: 03/29/2005
• Est. Priority Date: 12/30/1999
• Status: Expired due to Term

• Current Assignee: GE Global Sourcing LLC (Westinghouse Air Brake Technologies Corporation)
• Original Assignee: GE Harris Railway Electronics, LLC (GE Aerospace)
• Inventors: Doner, John R.
• Primary Examiner(s): Jeanty, Romain
• Assistant Examiner(s): BOYCE, ANDRE D
• Application Number:
  US09/475,566
• Time in Patent Office: 1,916 Days
• Field of Search: 705/7, 705/8, 705/5, 705/6, 705/9, 701/19, 701/20, 701/117, 701/116, 246/187, 246/182.R, 246/182.C, 246/5, 246/2.R
• US Class Current: 705/7.22
• CPC Class Codes: B61L 27/12 Preparing schedules
• 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/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/06375 Prediction of business process outcome or impact based on a proposed change

Abstract

A process for scheduling the travel of trains on a rail corridor. The rail corridor includes a plurality of siding tracks onto which trains can be sided when a meet or pass occurs with another train on the corridor. A gradient search process is used with a cost function to determine the optimum schedule by moving each meet and pass to a siding. The individual train schedules are varied by changing train speed and/or the train departure time (i.e., the time at which the train enters the corridor).

Claims

1. A method for scheduling the movement of a plurality of trains operating on a rail corridor, wherein trains traversing the rail corridor may intersect on the same track, whereby each train has at least one travel parameter that can be varied, whereby the rail corridor includes at least one main line and a plurality of secondary tracks onto which a train may be moved to avoid an intersection with another train, said method comprising the steps of:

(a) deriving a localizer function to represent the rail corridor, wherein said localizer function has a value in a first range between secondary tracks and has a value in a second range in the vicinity of each secondary track;

(b) selecting a value for at least one travel parameter for each of the plurality of trains set to travel on the rail corridor in accordance with a schedule;

(c) finding the intersection points for the plurality of trains;

(d) determining the value of said localizer function for each one of the intersection points;

(e) determining a cost function value in response to the said value of said localizer functions, wherein the cost function value indicates whether the trains intersect at or near a junction between the main line and one of the plurality of secondary tracks;

(f) revising the schedule such that the cost function value indicates that train intersections occur at or near the junction between a main line and one of the plurality of secondary tracks; and

(g) providing the schedule to at least one of the plurality of trains for directing its movement along the rail corridor; and

(h) wherein the steps (a) through (f) are executed by a computing device.

2. The method of claim 1 wherein the travel parameter includes train speed.

3. The method of claim 2 wherein the speed of at least one train is varied between intersection points to ensure the intersection occurs at a secondary track.

4. The method of claim 1 wherein the travel parameter includes the entry time of the train onto the rail corridor.

5. The method of claim 1 wherein the travel parameter includes train speed and the entry time of the train onto the rail corridor.

6. The method of claim 1 wherein the secondary track includes a passing siding.

7. The method of claim 1 wherein the secondary track includes two parallel tracks with crossover switches therebetween.

8. The method of claim 1 wherein the localizer function is derived by summing a plurality of sigmoid functions, wherein said sigmoid functions are translated and inverted with respect to each other and the location of the secondary tracks such that the localizer function has a value in the first range between secondary tracks and has a value within the second range in the vicinity of each secondary track.

9. The method of claim 1 including the step of forming a first vector wherein the elements of the first vector comprise the values selected in step (b), and wherein step (f) includes:

(f1) determining the gradient of the cost function of the first vector;

(f2) calculating a second vector by subtracting the product of a predetermined step size and the gradient calculated in step (f1), from the first vector;

(f3) calculating the cost function value of the second vector;

(f4) calculating the magnitude of the difference between the cost function value calculated in step (e) and the cost function value calculated in step (f);

(f5) if the result of step (f4) is greater than a predetermined threshold, returning to step (f1) wherein the second vector is now used in lieu of the first vector in the gradient calculating step (f1).

10. The method of claim 1 wherein the localizer function of step (a) is modified to account for rail corridor end points by setting the localizer function value to a value within the first range beyond the end points of the rail corridor.

11. The method of claim 1 wherein step (e) includes the process of summing said localizer function values to create the cost function value.

12. An apparatus for scheduling the movement of a plurality of trains operating on a rail corridor, wherein trains traversing the rail corridor may intersect on the same track, whereby each train has at least one travel parameter that can be varied, whereby the rail corridor includes at least one main line and a plurality of secondary tracks onto which a train may be moved to avoid an intersection with another train, said apparatus comprising:

means for deriving a localizer function to represent the rail corridor, wherein said localizer function has a value within a first range between secondary tracks and has a value within a second range in the vicinity of each secondary track;

means for selecting a value for at least one travel parameter for each of the plurality of trains set to travel on the rail corridor in accordance with a schedule;

means for finding the intersection points for the plurality of trains;

means for determining the value of said localizer function for each one of the intersection points;

means for determining a cost function value in response to said value of said localizer functions, wherein the cost function value indicates whether the trains intersect at or near a junction between the main line and one of the plurality of secondary tracks; and

means for revising the schedule such that the cost function value indicates that train intersections occur at or near the junction between a main line and one of the plurality of secondary tracks.

13. The apparatus of claim 12 wherein the travel parameter includes train speed.

14. The apparatus of claim 13 including means for adjusting the speed of at least one train between intersection points to ensure that the intersection occurs at a secondary track.

15. The apparatus of claim 12 wherein the travel parameter includes the entry time of the train onto the rail corridor.

16. The apparatus of claim 12 wherein the travel parameter includes train speed and the entry time of the train onto the rail corridor.

17. The apparatus of claim 12 wherein the secondary track includes a passing siding.

18. The apparatus of claim 12 wherein the secondary track includes two parallel tracks with crossover switches therebetween.

19. The apparatus of claim 12 wherein the localizer function is derived by summing a plurality of sigmoid functions, wherein said sigmoid functions are disposed with respect to each other and the location of the secondary tracks such that the localizer function has a value within the first range between secondary tracks and has a value within the second range in the vicinity of each secondary track.

20. The apparatus of claim 12 including:

means for forming a first vector wherein the elements of the first vector comprise the selected values, and further including;

means for determining the gradient of the cost function of the first vector;

means for calculating a second vector by subtracting the product of a predetermined step size and the gradient calculated, from the first vector;

means for calculating the value of the cost function of the second vector;

means for calculating the magnitude of the difference between the cost function value based on the first vector and the cost function value based on the second vector;

means for determining if the magnitude of the difference is greater than a predetermined threshold; and

means for recalculating the gradient when the magnitude of the difference is greater than a predetermined threshold, wherein the second vector is used in lieu of the first vector in the gradient recalculation.

21. The apparatus of claim 12 wherein the localizer function is modified to account for rail corridor end points by setting the localizer function value to a value within the first range beyond the end points of the rail corridor.

22. The apparatus of claim 12 wherein means for combining includes means for summing said localizer function values to create the cost function value.

23. A method for scheduling the movement of a plurality of trains operating on a rail corridor to minimize train delays, wherein trains traversing the rail corridor may intersect, whereby each train has at least one travel parameter that can be varied, whereby the rail corridor includes at least one mainline track and a plurality of secondary tracks onto which a train traversing the mainline track may be moved to avoid an intersection with another train traversing the mainline track, said method comprising the steps of:

(a) selecting a value for at least one travel parameter for each of the plurality of trains set to travel on the rail corridor in accordance with a schedule;

(b) determining a cost function, wherein at least one independent variable of the cost function comprises a travel parameter, and wherein the cost function indicates whether the trains intersect at or near a junction between a mainline track and a secondary track;

(c) determining a value of the cost function that minimizes the train delays;

(d) determining the travel parameters associated with the value of the cost function determined at the step (c);

(e) revising the schedule in accordance with the travel parameters determined at the step (d) such that the cost function indicates that train intersections occur at or near the junction between a mainline track and a secondary track; and

(f) providing the schedule to at least one of the plurality of trains for directing its movement along the rail corridor; and

(g) wherein the steps (a) through (e) are executed by a computing device.