Scheduling method and system for rail networks

• US 7,428,452 B2
• Filed: 05/20/2003
• Issued: 09/23/2008
• Est. Priority Date: 05/20/2002
• Status: Active Grant

• Current Assignee: TTG Limited (TUI AG)
• Original Assignee: Ausrail Technologies Pty., Limited
• Inventors: Howlett, Philip George, Pudney, Peter John
• Primary Examiner(s): Nguyen; Cuong H
• Application Number:
  US10/517,352
• Publication Number:
  US 20050261946A1
• Time in Patent Office: 1,953 Days
• Field of Search: 701/19, 246/2.R, 246/182, 705/8, 700/28, 295/1
• US Class Current: 701/19
• CPC Class Codes: B61L 27/12 Preparing schedules
• 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: G09D 1/00 Railway or like time or fare tables; Indicating or reading aids therefor essentially incorporating maps or route diagrams G09B; railway routing charts G09B; display devices, e.g. railway indicator boards G09F

Abstract

A method and system for calculating a plan for moving trains on a network to reduce the cost of delays or late running. The method and system can be used to develop a timetable for real time dynamic rescheduling of trains on a network and for assessing proposed changes to network infrastructure.

Claims

1. A method of moving a given set of trains from their respective origins to their respective destinations on a rail network, said method comprising:

(i) forming a schedulable set of trains consisting of every train not at its destination;

(ii) removing from said schedulable set any train whose next movement may result in the network becoming deadlocked;

(iii) generating a dispatch decision time for each of the trains remaining in the schedulable set after having trains removed in step (ii), wherein the dispatch decision time is somewhere between the earliest time the train can start a next movement and the earliest time the train can complete its next movement;

(iv) generating a perturbed dispatch decision time for each of the trains remaining in the schedulable set after having trains removed in step (ii) by adding a random perturbation to the dispatch decision time of each train;

(v) selecting a train from said schedulable set with the earliest perturbed dispatch decision time;

(vi) scheduling said selected train over its chosen movement to its successor station;

(vii) repeating steps (i) to (vi) until the schedulable set is empty to create a possible schedule;

(viii) assessing said possible schedule by means of an objective function;

(ix) repeating steps (i) to (viii) to create N possible schedules; and

(x) selecting a desired schedule from said N possible schedules on the basis of said objective function and moving said set of trains from their respective origins to their respective destinations on the rail network in accordance with said desired schedule.

2. The method of moving a given set of trains from their respective origins to their respective destinations on a railway network as claimed in claim 1, wherein said objective function is the sum of the lateness costs of each train, wherein the lateness cost of each train is zero if the train arrives at its destination before the desired arrival time, and some train dependent multiple of the lateness if the train arrives after the desired arrival time.

3. The method of moving a given set of trains from their respective origins to their respective destinations on a rail network as claimed in claim 1, wherein said objective function used to evaluate each schedule is the sum of the lateness of each train, wherein the lateness of each train is given by the function:

4. The method of moving a given set of trains from their respective origins to their respective destinations on a rail network as claimed in claim 1, wherein track capacity constraints are included in the objective function by means of lagrange multipliers.

5. The method of moving a given set of trains from their respective origins to their respective destinations on a rail network as claimed in claim 3, wherein track capacity constraints are included in the objective function by means of lagrange multipliers.

6. The method of moving a given set of trains from their respective origins to their respective destinations on a rail network as claimed in claim 1, wherein a heuristic method is used to remove any infeasible train movements.

7. The method of moving a given set of trains from their respective origins to their respective destinations on a rail network as claimed in claim 1, wherein the size of the perturbation ε

added to the dispatch decision time is governed by the parameter α and

is given by

ε

=α

U(0,1)

where U(0,1) is a uniformly distributed random variable on the interval [0,1].