Solving Stochastic Shortest Distance Path Problem by Using Genetic Algorithms

摘要

Shortest Distance Path problem has been studied extensively in the literature. This is an important problem with a wide range of applications in the world particularly, transportation, trip planning, etc. Various mathematical models have been proposed in the literature to solve the basic problem and its variations. In this study, we incorporate weather forecast into trip planning. Due to adverse weather conditions, shortest distance path to follow may vary. Furthermore, travel times also become less predictable. Various weather forecast scenarios are generated following a given distribution. Furthermore, stochastic travel times are also considered as part of the analysis. In this study, GA will produce multiple acceptable solutions where fitness function values for each acceptable solution can vary. The average value of arriving time will be considered as the fitness function for a chromosome after simulating the chromosome under different conditions randomly 100 times.