Train scheduling on a unidirectional path

DOI10.4230/LIPICS.FSTTCS.2017.29MaRDI QIDQ5136321zbMATH OpenOpenAlexFDO

Authors Apoorv Garg, Abhiram Ranade

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2017.29

zbMATH Keywords

approximation algorithmcombinatorial optimizationcomplexity analysismax-delay minimizationtrain scheduling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Exact train pathing
• Waiting for trains: complexity results
• A fast heuristic for the train scheduling problem
• Complexity, bounds and dynamic programming algorithms for single track train scheduling
• Routing trains through railway stations: Complexity issues

Cites work

• A framework for dynamic dispatch decision-making applied in transportation scheduling
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Job-shop scheduling with blocking and no-wait constraints
• Knowledge-based system for railway scheduling
• Optimal real-time traffic control in metro stations
• OPTIMUM SCHEDULE PROBLEMS IN STORE AND FORWARD NETWORKS
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Packet Routing: Complexity and Algorithms
• Randomized Routing and Sorting on Fixed-Connection Networks
• Vertex disjoint paths for dispatching in railways

Cited in

(10)

• Scheduling the two-way traffic on a single-track railway with a siding
• The single train shortest route problem in a railyard
• The train delivery problem -- vehicle routing meets bin packing
• Scheduling bidirectional traffic on a path
• Fastest, average and quantile schedule
• Constant delay lattice train schedules
• Waiting for trains: complexity results
• Train scheduling: hardness and algorithms
• Scheduling trains with small stretch on a unidirectional line
• Exact train pathing

This page was built for publication: Train scheduling on a unidirectional path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136321)