Detailseite
Projekt Druckansicht

Robuste Algorithmen für diskrete Optimierungsprobleme

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2009 bis 2014
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 147522655
 
Our work will focus on three kinds of sections of special interest to Indian Railways. In the first, there is mainly a single bidirectional line with multiple lines in some parts, e.g. Konkan Railway. In the second kind, there are three lines, two unidirectional (up only and down only) and one bidirectional (can carry both up and down traffic). Sometimes the bidirectional line is between the up and down lines, and sometimes it is on one side as in the Tiruvallur-Arakkonam section. In case the bidirectional line is on one side, to use it trains must cross one of the unidirectional lines, which can be a serious overhead. Finally we will consider a “Y” shaped compound section in which there is merging traffic, e.g. The Karjat-Kalyan, Kasara-Kalyan, Kalyan - Mumbai CST compound section. In all these cases, the algorithms can be based on the so-called “greedy strategy” which often works well if the traffic is light, or the more common integer linear programming based strategies, together with heuristics for rounding and exhaustive search as needed. We plan to use these techniques, but also investigate ideas from approximation algorithms, i.e. Consider questions such as: how close to the optimal is the solution that our algorithm has come up with? We will exercise our algorithms on real data which we will acquire from the Indian Railways as well as some benchmarks available in the literature.
DFG-Verfahren Schwerpunktprogramme
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung