Record Details

Exact train pathing

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Exact train pathing
 
Creator NAGARAJAN, V
RANADE, AG
 
Subject train pathing
dynamics
signaling
train simulation
train scheduling
 
Description Suppose we are given a schedule of train movements over a rail network into which a new train is to be included. The origin and the destination are specified for the new train; it is required that a schedule (including the path) be determined for it so as to minimize the time taken without affecting the schedules for the old trains. In the standard formulations of this single train pathing problem, the time taken by the train to traverse any block (track segment guarded by a signal) in the network is deemed to be a fixed number, independent of how the train arrived onto that block. In other words, the standard formulations of train pathing do not accurately model the acceleration/deceleration restrictions on trains. In this paper we give an algorithm to solve the single train pathing problem, while taking into account the maximum allowed acceleration and deceleration as well as explicitly modeling signals. For trains having 'arge' maximum acceleration and deceleration, our algorithm runs in polynomial time. On the other hand, if the train to be pathed is capable of only very small acceleration so that it must take a long time to reach full speed, our algorithm takes exponential time. However, we prove that the pathing problem is NP-complete for small acceleration values, thus justifying the time required by our algorithm. Our algorithm can be used as a subroutine in a heuristic for multiple train pathing. If all trains have large (but possibly different) accelerations this algorithm will run in polynomial time.
 
Publisher SPRINGER
 
Date 2011-08-29T12:46:07Z
2011-12-26T12:58:36Z
2011-12-27T05:48:48Z
2011-08-29T12:46:07Z
2011-12-26T12:58:36Z
2011-12-27T05:48:48Z
2008
 
Type Article
 
Identifier JOURNAL OF SCHEDULING, 11(4), 279-297
1094-6136
http://dx.doi.org/10.1007/s10951-008-0056-x
http://dspace.library.iitb.ac.in/xmlui/handle/10054/12086
http://hdl.handle.net/10054/12086
 
Language en