@techreport{oai:ipsj.ixsq.nii.ac.jp:00194470,
 author = {Tomoshi, Otsuki and Hideo, Sakamoto and Hideki, Kubo and Tomoshi, Otsuki and Hideo, Sakamoto and Hideki, Kubo},
 issue = {7},
 month = {Feb},
 note = {Accurate delay evaluation of timetables is crucial for railway companies. There have been some conventional methods utilizing continuous random variables directly. These methods, however, suffer combinatorial expansion problems, which require complex pruning techniques. In this paper, discretizing the delay distribution on railway networks, we present a method calculating propagated delay distributions on each event analytically under the assumption of propagated delays' independence. We also show the complexity of the proposed method is O (M²N) in the general case and can be reduced to O (MN) especially for the special cases where the source distribution is the negative binominal distribution, where M denotes the number of quantization levels in discretization and N denotes the total number of events. Finally, computational experiments on test scenarios with M ～ 700 show that the proposed method provides almost same results as and in over 500 times faster computation time than Monte Carlo simulations., Accurate delay evaluation of timetables is crucial for railway companies. There have been some conventional methods utilizing continuous random variables directly. These methods, however, suffer combinatorial expansion problems, which require complex pruning techniques. In this paper, discretizing the delay distribution on railway networks, we present a method calculating propagated delay distributions on each event analytically under the assumption of propagated delays' independence. We also show the complexity of the proposed method is O (M²N) in the general case and can be reduced to O (MN) especially for the special cases where the source distribution is the negative binominal distribution, where M denotes the number of quantization levels in discretization and N denotes the total number of events. Finally, computational experiments on test scenarios with M ～ 700 show that the proposed method provides almost same results as and in over 500 times faster computation time than Monte Carlo simulations.},
 title = {Fast Railway Delay Evaluation Method Based on Discrete Distribution Propagation},
 year = {2019}
}