Robuste Algorithmen für diskrete Optimierungsprobleme

• Antragstellerin: Professorin Dr. Anita Schöbel
• 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
• Teilprojekt zu: SPP 1307: Algorithm Engineering