{'fraction_non_alphanumeric': 0.01920768307322929, 'fraction_numerical': 0.0, 'mean_word_length': 5.087591240875913, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic Shortest Path Problem with Uncertain Delays

This paper considers a stochastic version of the shortest path problem, the Stochastic Shortest Path Problem with Delay Excess Penalty on directed, acyclic graphs. In this model, the arc costs are deterministic, while each arc has a random delay, assumed normally distributed. A penalty occurs when the given delay constraint is not satisfied. The objective is to minimize the sum of the path cost and the expected path delay penalty. In order to solve the model, a Stochastic Projected Gradient method within a branch-and-bound framework is proposed and numerical examples are given to illustrate its effectiveness. We also show that, within given assumptions, the Stochastic Shortest Path Problem with Delay Excess Penalty can be reduced to the classic shortest path problem.