Train timetabling on complex networks

Calculating an optimal timetable for multiple trains on a network is a difficult optimisation problem. As the number of trains or the size of the network increases the problem grows rapidly in size and complexity. In this paper two approaches to the optimal timetabling problem are explored. In the first method the problem is formulated as a large binary-programming problem. The method of Lagrangian relaxation can then be employed to reduce the size and complexity of the problem. In this method the trains are placed one at a time onto a train graph, then penalties are imposed whenever two trains are occupying the same segment at the same time. With these penalties imposed, the cheapest path for each train will gradually move away from these conflicts. Some conflicts may not be resolved after these penalties have been added and so a heuristic method is used to resolve the remaining conflicts and produce a feasible timetable. Another technlqas is Problem Space Search, which imbeds a fast dispatching heuristic within a probabilistic search procedure. The dispatcher generates a timetable based on the problem data Le. segment running times. The search procedure uses perturbed segment running times to generate alternative dispatching decisions. Many timetables are constructed and the best one kept. The timetables are evaluated against one another using a cost function of the su m of the delays experienced by each train. Both methods are tested on a problem consisting of 34 trains and 62 segments that are to be scheduled daily.

Media Info

  • Pagination: 6p. ; PDF
  • Monograph Title: Railway technology for the 21st century: CORE 2000: conference on railway engineering, May 21-23 2000, Glenelg, South Australia

Subject/Index Terms

Filing Info

  • Accession Number: 01532088
  • Record Type: Publication
  • Source Agency: ARRB
  • Files: ATRI
  • Created Date: Jul 29 2014 11:54AM