An algorithmic approach for finding the fuzzy constrained shortest paths in a fuzzy graph

摘要

Shortest path problem (SPP) is a fundamental and well-known combinatorial optimization problem in the area of graph theory. In real-life scenarios, the arc weighs in a shortest path of a network/graph have the several parameters which are very hard to define exactly (i.e., capacity, cost, demand, traffic frequency, time, etc.). We can incorporate the fuzziness into a graph to handle this type of uncertain situation. In this manuscript, we propose the idea of constrained SPP (CSPP) in fuzzy environment. CSPP has an useful real-life application in online cab booking system. The main motivation of this study is to determine a path with minimal cost where traveling time within two locations does not more than predetermined time. We can not predicate the exact time and cost of the path due to uncertain traffic scenarios and another unexpected reasons; still, the geometrical distance between the locations is fixed. Here, we use trapezoidal fuzzy number to describe the edge weight of a fuzzy network/graph for CSPP. We define this CSPP as fuzzy CSPP (FCSPP). The utility of FCSPP is described in several real-life scenarios. We propose a mathematical formulation for the FCSPP and an algorithm is proposed for solving the FCSPP. We describe an application of our proposed algorithm on an online cab booking system.