Path finding under uncertainty

Path finding problems have many real-world applications in various fields, such as operations research, computer science, telecommunication, transportation, etc. In this paper, we examine three definitions of optimality for finding the optimal path under an uncertain environment. These three stochastic path finding models are formulated as the expected value model, dependent-chance model, and chance-constrained model using different criteria to hedge against the travel time uncertainty. A simulation-based genetic algorithm procedure is developed to solve these path finding models under uncertainties. Numerical results are also presented to demonstrate the features of these stochastic path finding models.