Overview
This paper investigates the fuzzy shortest path problem (FSPP) within directed graphs, focusing on edge costs represented by generalized fuzzy numbers (GFN) with Gaussian membership functions. The study introduces a framework that interprets the height of these fuzzy numbers as an indicator of information reliability. A weighted geometric mean is employed to aggregate heights during the addition of generalized Gaussian fuzzy numbers (GGFN). The proposed method leverages a reliability-aware ranking approach that considers the core, height, and standard deviation of fuzzy edge costs to identify the shortest path. This approach aims to capture the central tendency, reliability, and variability inherent in the fuzzy edge costs while maintaining a computational complexity comparable to Dijkstra's algorithm for each relaxation step. The resultant routes are characterized by both cost efficiency and supporting reliable information.
Approach
The methodology developed for the fuzzy shortest path problem involves several key components. Edge costs within the directed graph are modeled as generalized fuzzy numbers, specifically utilizing Gaussian membership functions. A central concept in this modeling is the interpretation of fuzzy number 'height' as a measure of information reliability associated with the edge cost. To facilitate aggregation of fuzzy costs, particularly during path summation, a weighted geometric mean is introduced. This mean is designed to aggregate the heights of generalized Gaussian fuzzy fuzzy numbers (GGFNs) during summation operations.
The determination of the shortest path relies on a reliability-aware ranking mechanism. This ranking procedure integrates three critical attributes of the fuzzy edge costs: their core, representing the central tendency; their height, reflecting reliability; and their standard deviation, indicating variability. By jointly considering these aspects, the ranking aims to provide a comprehensive evaluation of fuzzy cost elements. The computational efficiency of this approach is maintained at a level comparable to Dijkstra's algorithm per relaxation step.
To assess the robustness of the proposed framework, a crisp baseline is constructed directly from the established ranking. Robustness evaluation is further conducted through Monte Carlo alpha-cut sampling. This involves uniformly drawing membership levels and subsequently sampling within the induced intervals to recompute path costs. Sensitivity is then quantified using two metrics: the mean percentage deviation and its standard deviation. This multi-faceted approach aims to provide a thorough analysis of the method's performance under various conditions, particularly concerning subnormal fuzzy costs.
Findings
- The proposed GGFN-SPP framework effectively addresses the fuzzy shortest path problem in directed graphs with Gaussian fuzzy edge costs.
- The framework maintains Dijkstra-level complexity per relaxation, suggesting efficient computational performance.
- The method yields routes that are not only cost-efficient but are also associated with highly reliable information, as indicated by the reliability-aware ranking.
- The framework scales efficiently to real-world networks, as demonstrated by a large-scale case study on the FAA air traffic network.
- The approach successfully balances cost and reliability through its $\alpha$-cut aggregation and risk-aware ranking mechanisms.
- Monte Carlo simulations with subnormal fuzzy costs indicated stable performance for the proposed framework, supported by analysis of mean percentage deviation and its standard deviation.
Why This Matters
This research provides a framework that can generate routes optimized not just for cost, but also for the reliability of the underlying cost information. Its demonstrated scalability to large-scale networks like the FAA air traffic network suggests practical applicability in optimizing routing decisions where uncertainty in cost estimation is a factor.
Potential Applications
A large-scale case study demonstrated the applicability of the proposed GGFN-SPP framework to the FAA air traffic network.