Chance Constrained Programming Models for Constrained Shortest Path Problem with Fuzzy Parameters
Pinar Dursun and Erhan Bozdag
Shortest path problem is a fundamental problem in transportation networks, communication networks and optimal control. The number of studies using different tools to solve this problem in deterministic, stochastic or fuzzy environment as well as the constrained version is increasing. In this paper, two chance constrained programming models are proposed for the shortest path problem with fuzzy parameters. The first model has fuzzy constraints in addition to the classical shortest path problem. The weights of arcs which form objective function are also fuzzy in the second model. To solve the models, a hybrid algorithm consists of fuzzy simulation and genetic algorithm is developed. To demonstrate the applicability of these proposed models and algorithms, some illustrating examples are given using a sample network. From the results, we can assert that the proposed methods are promising for the real life applications of the problem.
Keywords: Constrained Shortest Path Problem, Fuzzy Arc Weight, Chance Constrained Programming, Possibility, Fuzzy Simulation, Genetic Algorithm.