Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1999-12-30
2003-04-08
Hafiz, Tariq R. (Department: 3623)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
C705S002000, C701S019000, C701S117000
Reexamination Certificate
active
06546371
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a process for scheduling the movement of trains over a rail corridor having a plurality of sidings or parallel tracks with crossover switches.
BACKGROUND OF THE INVENTION
A rail corridor is a collection of tracks and sidings connecting two rail terminal areas. An example of a rail corridor
8
is shown in
FIG. 1
, showing a single main track
10
and three sidings
20
. The western end of the rail corridor is on the left side of FIG.
1
and the eastern end on the right.
Scheduling rail transportation on a rail corridor is particularly complex as compared to highway, water, or air transportation. Trains using a single track traveling in opposite directions (i.e., a meet) or trains traveling in the same direction (i.e., a pass) must meet in the vicinity of a siding so that one train can be sided to let the other pass. Alternatively, if there exists a double main line with crossover switches, one train can be switched to the second main line to allow the other train to pass. Also, when such meets or passes occur at a siding, the siding chosen must be long enough to accommodate the train to be sided, and the train to be sided must arrive at the siding and have sufficient time to pull onto the siding before the passing train arrives at the siding.
The railroad must earn revenue from its transportation operations, and some of this revenue is generally at risk if trains cannot deliver freight on time. The destination time of the trains must be managed insofar as possible to prevent late penalties incurred by the railroad. Therefore scheduling trains across a rail corridor involves arranging meets and passes as required for all trains, and while also meeting the schedule for each train so that they all arrive, on time, at the end of the corridor.
Commercially applied scheduling processes attempted to date have been based on paradigms which involve simulation with branch and bound techniques to find a conflict-free schedule. Since a branch and bound process must sort through many binary choices as it proceeds toward a solution, these techniques are slow, and do not take advantage of quantitative relationships that can be adduced from the scheduling context.
Additionally, the prior art technique search processes actually become more complex and take longer to arrive at a solution as the number of sidings in the rail corridor increases. This is due to the search algorithms that form the basis for these prior art techniques. More sidings requires the search algorithm to search through and consider more choices before arriving at an optimum solution. As will be shown below, the technique of the present invention overcomes this disadvantage. Since the present invention calculates a cost function where each siding represents a lower cost, having more sidings will make it easier for the algorithm to identify the optimal (i.e. minimal) cost.
One prior art technique uses quantitative information such as train speed, destination, and time of departure as discrete variables in an artificial intelligence based system. The artificial intelligence process involves rules that are used to search through the trial cases until the best case is found. In addition to the considerable time taken by an artificial intelligence system to optimize a solution, it is also known that a slight change to the initial conditions may produce a significantly different result. In any case, a slight change to the initial conditions will require a new and lengthy computation to find the optimum solution. A commercial product referred to as The Movement Planner, offered by G E-Harris Railway Electronics L.L.C. of Melbourne, Fla., implements such an artificial intelligence solution.
As can be seen, the total set of parameters for scheduling a corridor can be large, and of both discrete and continuous types. Generally, a cost function based on these parameters can be formulated, and then some method of search is executed that will reduce the cost and/or find a feasible schedule for the subject trains. But, the presence of discrete variables in the search space prevents or greatly complicates the application of any “hill-climbing” search processes based on the use of gradients
SUMMARY OF THE INVENTION
Cost functions that are everywhere differentiable have the advantage over prior art artificial intelligence solutions of being amenable to gradient-based minimization algorithms that do not have to accommodate the difficulties that arise in discrete or partially discrete search spaces. The present invention is a process whereby a rail corridor and the train schedule along that corridor can be characterized by a differentiable (i.e., continuous) cost function, so that a search process based on differentiation may be applied to scheduling train activity in the corridor.
The present invention is an analytical process for scheduling trains across a corridor that is driven by a cost function to be minimized, where the cost function is a continuous and differentiable function of the scheduling variables. The present invention is an improvement over the prior art cost functions that include discrete variables and thus are not differentiable everywhere. The present invention will permit the use of search processes relying on gradients, and as such, will converge to solutions much more quickly than the prior art scheduling processes involving simulation, or searching through discrete options.
The corridor scheduling process of the present invention involves three steps for identification of the optimum schedule. After an acceptable differentiable cost function is derived, the first step is the gradient search process wherein the gradient of the differentiable cost function is determined. The cost function is a sum of individual localizer functions. For each pair of trains in the corridor that might intersect, using the localizer function, the intersection point is identified as having a high value if the train trajectories do not intersect near a siding and lower values as the intersection point moves toward any siding. The gradient process may not move all intersection points precisely to the center of sidings dependent upon the selected threshold value and parametric values of the localizer function. Instead, the gradient process varies train departure times so that the set of all intersection points of trains are moved nearer to sidings. The second phase of the process simply moves the points precisely to the centers of sidings, selects which train to side, and computes exact arrival and departure times for the trains at the siding to assure the physical integrity of the meet. In order to center the intersection points at sidings and side specific trains, the speeds of the individual trains must be modified. This is accomplished during the second step of the scheduling process.
The third step maintains the proper siding relationships between any two meeting trains, as determined in step two, but allows the meet time to vary in an effort to assure that no train exceeds an upper speed limit. This final phase is again a gradient search process applied to all of the meet points determined in the second step.
REFERENCES:
patent: 5177684 (1993-01-01), Harker et al.
patent: 5487516 (1996-01-01), Murata et al.
patent: 5794172 (1998-08-01), Matheson et al.
patent: 6135396 (2000-10-01), Whitfield et al.
patent: 6154735 (2000-11-01), Crone
patent: 0 933 280 (1999-08-01), None
patent: 2 767 770 (1997-09-01), None
Cai et al “Greesy heuristics for rapid scheduling of trains on a single track”, May 1998; IIE Transaction, V30, n5, p481(13), Dialog file 148, Accession No. 10301494.*
Webster et al “a real-time software controller for a digital model railroad system”, Dec. 1993, Dialog file 2, Accession No. 4547313,.
Beusse Brownlee Bowdoin & Wolter P.A.
DeAngelis Jr. John L.
GE-Harris Railway Electronics, L.L.C.
Hafiz Tariq R.
Jeanty Romain
LandOfFree
Train corridor scheduling process including various cost... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Train corridor scheduling process including various cost..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Train corridor scheduling process including various cost... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3099861