|
Routing Planning As An Application Of Graph Theory
[Full Text]
AUTHOR(S)
Prof Boominathan P, Kanchan Arora
KEYWORDS
Keywords: FuzzyLogic,PathFinding,Weighted Graph,Path-RequestBlocking,Fuzzy RoutingAlgorithm,NearestNeighbor Algorithm,DijiktraAlgorithm.
ABSTRACT
ABSTRACT:- This paper presents a routing algorithm that uses fuzzy logic technique to find the shortest routing path. The basic idea behind path finding is searching a graph, starting at one point, and exploring adjacent nodes from there until the destination node is reached. Generally, the goal is of course to obtain the shortest route to the destination. The proposed Fuzzy Routing Algorithm (FRA) modifies the well-known Dijkstra’s Single-source shortest path algorithm by using fuzzy-logic membership functions in the path-cost update process. The main objective of FRA is to reduce path-request blocking and increase overall utilization. The fuzzy weighted graphs, along with generalizations of algorithms for finding optimal paths within them, have emerged as an adequate modeling tool for prohibitively complex and/or inherently imprecise systems. These algorithms are reviewed and formulized with uncertainty which comes from weights on edges according to actual situation on the road such as weather conditions, and road capacity at the specified time. The two key issues need to be addressed in SPP(Shortest Path Algorithm) with fuzzy parameters are to determine the addition of two edges and to compare the distance between two different paths with their edge lengths represented by fuzzy numbers.
REFERENCES
[1]. Y. Deng, W.K. Shi, F. Du, Q. Liu, A new similarity measure of generalized fuzzy numbers and its application to pattern recognition, Pattern Recognition Letters 25 (2004) 875–883.
[2]. H.W. Liu, New similarity measures between intuitionistic fuzzy sets and between elements, Mathematical and Computer Modelling 42 (2005) 61–70.
[3]. J. Ye, Cosine similarity measures for intuitionistic fuzzy sets and their applications, Mathematical and Computer Modelling 53 (2011) 91–97.
[4]. Y. Deng, Plant location selection based on fuzzy topsis, International Journal of Advanced Manufacturing Technology 28 (2006) 839–844.
[5]. Y. Deng, F.T.S. Chan, A new fuzzy Dempster MCDM method and its application in supplier selection, Expert Systems with Applications 38 (2011) 6985–6993.
[6]. M. Xu, Y. Liu, Q. Huang, Y. Zhang, G. Luan, An improved Dijkstra shortest path algorithm for sparse network, Applied Mathematics and Computation 185 (2007) 247–254.
[7]. X. Lu, M. Camitz, Finding the shortest paths by node combination, Applied Mathematics and Computation 217 (2011) 6401–6408.
[8]. T.N. Chuang, J.Y. Kung, The fuzzy shortest path length and the corresponding shortest path in a network, Computers & Operations Research 32 (2005) 1409–1428.
[9]. R. Sadiq, S. Tesfamariam, Developing environmental using fuzzy numbers ordered weighted averaging (FN-OWA) operators, Stochastic Environmental Research and Risk Assessment 22 (2008) 495–505.
[10]. Y. Deng, W. Jiang, R. Sadiq, Modeling contaminant intrusion in water distribution networks: a new similarity-based DST method, Expert Systems with Applications 38 (2011) 571–578.
[11]. Y. Deng, F.T.S. Chan, Y. Wu, D. Wang, A new linguistic MCDM method basedon multiple-criterion data fusion, Expert Systems with Applications 38 (2011) 9854–9861.
[12]. C. Lin, M.S. Chern, The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems 58 (1993) 343–353.
|
