Solution time reduction techniques of a stochastic dynamic programming approach for hazardous material route selection problem
We use a stochastic dynamic programming (SDP) approach to solve the problem of determining the optimal routing policies in a stochastic dynamic network. Due to its long time for solving SDP, we propose three techniques for pruning stochastic dynamic networks to expedite the process of obtaining optimal routing policies. The techniques include: (I) use of static upper/lower bounds, (2) pre-processing the stochastic dynamic networks by using the start time and origin location of the vehicle, and (3) a mix of preprocessing and upper/lower bounds. Our experiments show that while finding optimal routing policies in stochastic dynamic networks, the last two of the three strategies have a significant computational advantage over conventional SDP. Our main observation from these experiments was that the computational advantage of the pruning strategies that depend on the start time of the vehicle varies according to the time input to the problem. We present the results of this variation in the experiments section. We recommend that while comparing the computational performances of time-dependent techniques, it is very important to test the performance of such strategies at various time inputs. (C) 2013 Elsevier Ltd. All rights reserved.
dynamic programming stochastic dynamic networks markov decision process