Talks & Seminars
Title: Exact Train Pathing
Prof. Abhiram Ranade, Dept. of Computer Science & Engg., IIT Bombay
Date & Time: April 9, 2008 15:00
Venue: F.C. Kohli Auditorium, K.R. Bldg. 1st floor

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 trains scheduled earlier. In 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 arrives onto that block. In other words, this formulation does not accurately model the acceleration/deceleration restrictions on trains.

In this talk we give an algorithm to solve the single train pathing problem which takes into account the acceleration and deceleration restrictions. For a train having "large" (defined later) maximum acceleration and deceleration the algorithm runs in polynomial time. For small accelerations the algorithm takes exponential time. We also prove that the pathing problem is NP-complete for small accelerations, thus justifying the time requirement.

Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback