Shortest Path Problem with Subnormal Gaussian Fuzzy Costs Murat Moran1 and Hande Günay Akdemir2
arXiv:2605.27317v1 [cs.CR] 26 May 2026
1
Department of Computer Engineering, Giresun University, Türkiye 1 [email protected] 2 Department of Mathematics, Giresun University, Türkiye 2 [email protected]
Abstract This paper addresses the fuzzy shortest path problem in directed graphs, where edge costs are modeled as generalized fuzzy numbers with Gaussian membership functions. We interpret height as an indicator of information reliability. Based on this view, we introduce a weighted geometric mean to aggregate heights during the addition of generalized Gaussian fuzzy numbers. We employ a reliability-aware ranking that jointly considers the core, height, and standard deviation of fuzzy edge costs to determine the shortest path, thereby capturing their central tendency, reliability, and variability while keeping Dijkstra-level complexity per relaxation. The method yields routes that are not only cost-efficient but also supported by highly reliable information. To assess robustness, we construct a crisp baseline from the ranking and conduct Monte Carlo alpha-cut sampling–drawing membership levels uniformly and then sampling within the induced intervals–to recompute path costs and quantify sensitivity via the mean percentage deviation and its standard deviation. Finally, a large-scale case study on the FAA air traffic network demonstrates that the proposed GGFN–SPP framework scales efficiently to real-world networks, balances cost and reliability through α– cut aggregation and risk-aware ranking, and exhibits stable performance under Monte Carlo simulations with subnormal fuzzy costs. Keywords: Fuzzy shortest path problem, Uncertainty, Ranking index, Generalized fuzzy number, Gaussian membership function, Single-value fuzzy numerical simulation
1
Introduction
The Shortest Path Problem (SPP) is a fundamental challenge in graph theory, essential for modeling discrete systems like transportation and communication networks. Among the canonical problems in graph theory, the SPP seeks a path of minimum total cost between a source and a terminal (target) node. In the classical setting, edge costs are deterministic. In many applications, however, these costs are subject to epistemic uncertainty (e.g., expert assessments), for which fuzzy numbers offer a natural representation. For instance, travel times between cities may be imprecise due to road or weather conditions, so edge costs can be modeled as fuzzy numbers. This study focuses solely on fuzzy edge costs, assuming a known and fixed network topology. Parametric families such as triangular, trapezoidal, and Gaussian retain their functional form under basic operations (e.g., translation, scaling, and, under mild conditions, addition) due to their parametric closure. Generalized fuzzy numbers are adopted to model epistemic uncertainty, especially when expert assessments may be only partially reliable, that is, when the normality condition is relaxed. In a possibilistic reading, the height of a subnormal fuzzy number acts as a degree of consistency (information reliability) of the underlying evidence [1]. Generalized forms are therefore crucial in real–world settings where the available evidence may be incomplete or partially inconsistent. Gaussian forms, in particular, are attractive in both theory and practice thanks to their smooth analytical structure, compact parametrization, and closed–form α–cuts, which facilitate arithmetic and ranking.
1
Despite their theoretical advantages, subnormal Gaussian membership functions have received limited attention in the literature. Existing treatments typically rely on the extension principle and α–cuts; the height parameter is carried along but is rarely aggregated within arithmetic operations. When explicit height aggregation is attempted, it typically appears in intuitionistic or picture fuzzy frameworks, whereas in generalized Type–1 settings the combination of membership information is usually delegated to t–norm operators (most often the minimum) rather than to a dedicated height–aggregation rule. In Type–1 settings, height has more often been incorporated at the ranking stage. For triangular/trapezoidal fuzzy numbers, Aydin and Akdemir [2]–in a proceedings study on generalized trapezoidal fuzzy transportation problems–aggregate heights via a compensatory, weighted harmonic mean with spread–proportional (non–normalized) weights; while the aggregate remains within the input bounds, associativity under repeated addition is not preserved. Within interval Type–2 fuzzy sets, a more recent proposal [3] defined unified height update rules for several arithmetic operators and introduced a tuning parameter to encode risk attitudes (from cautious to adventurous). For Gaussian fuzzy numbers specifically, Sen et al. [4] developed a similarity measure that jointly accounts for mean, standard deviation, and height via an exponential formulation. Tahayori et al. [5] proposed a construction of shadowed sets from fuzzy sets using both normal and subnormal Gaussian memberships; their method preserves the overall amount of fuzziness via gradual numbers and provides closed–form threshold formulas, ensuring consistency in the representation of fuzzy information. Despite extensive research on fuzzy SPPs–most of which adapt classical algorithms or employ metaheuristics and rely on triangular or trapezoidal models–studies that relax the normality assumption and explicitly model Gaussian membership functions in Type-V fuzzy graphs remain scarce. For instance, Yao and Lin [6] proposed two fuzzy shortest path models in which edge costs are represented by level−λ triangular fuzzy numbers and level−(1 − β, 1 − α) interval-valued fuzzy numbers. The problem is solved using a signeddistance-based ranking method combined with dynamic programming. Elizabeth and Sujatha [7] introduced novel algorithms for the fuzzy SPP where edge costs are represented as level−λ triangular LR fuzzy numbers–an approximation that implicitly captures subnormal behavior by allowing a reduced maximum membership grade. Kavian et al. [8] proposed a two-stage fuzzy logic-based scheme to accommodate traffic demand uncertainty in optical core networks. Their approach models future demand fluctuations using Gaussian fuzzy membership functions and integrates a Mamdani-type inference system with Dijkstra-based routing to assign link costs adaptively according to bandwidth availability and uncertainty levels. Hassanzadeh et al. [9] proposed a fuzzy shortest path algorithm that integrates both trapezoidal and Gaussian fuzzy edge lengths, all assumed to be normal (i.e., with maximum membership grade equal to one). Their approach utilizes α−cut representations and a least squares-based approximation to construct membership functions for path costs, and applies a genetic algorithm to efficiently solve large-scale instances. Verma and Shukla [10] proposed a greedy algorithm for the fuzzy SPP, in which they employed quasi-Gaussian fuzzy numbers as edge costs. Their motivation for using Gaussian-shaped membership functions lies in their continuity, differentiability, and compact parametric representation, offering advantages over traditional triangular or trapezoidal fuzzy models. Anusuya and Kavitha [11] proposed a genetic algorithm for the fuzzy SPP, where edge costs are represented by generalized trapezoidal fuzzy numbers. Their model emphasizes the role of each genetic operator individually and incorporates a distance-based fitness function that accounts for fuzzinessrelated parameters such as mode, divergence, and spreads. Kumar et al. [12] proposed a unified fuzzy linear programming approach for solving fuzzy SPPs involving both Type-I and Type-II weighted triangular and trapezoidal fuzzy numbers. Their method enables the prediction of the crisp shortest path length while preserving the original uncertainty structure through non-normal fuzzy membership functions. Dey et al. [13] proposed a fuzzy extension of Dijkstra’s algorithm to solve the SPP in imprecise environments, where edge lengths are represented by generalized trapezoidal fuzzy numbers. Their approach incorporates a parameterized defuzzification method based on λ-integral values, allowing decision-makers to adjust the solution based on varying optimism levels. Valdes et al. [14] modeled communication networks as Type-V fuzzy graphs with link costs represented by normalized triangular fuzzy numbers. They proposed a Fuzzy Dijkstra Algorithm supported by α−cut
2
arithmetic and a total integral-based ranking method to compute the shortest path under uncertainty, demonstrating its superiority over classical approaches in simulated network topologies. Ebrahimnejad et al. [15] addressed the SPP under mixed interval-valued fuzzy numbers, developed an α–cut–based aggregation scheme and an extended distance function for path comparison, and devised a modified artificial bee colony algorithm to compute the interval-valued membership of the fuzzy shortest path. Biswal et al. [16] formulated the α-reliable SPP for uncertain time-dependent road networks within uncertainty theory: link travel times were modeled as independent uncertain normal variables, an additive α-reliable path length was derived–thus restoring Bellman’s principle–and a Dijkstra-type algorithm was implemented and illustrated with a numerical example. Abbasi and Allahviranloo [17] proposed a novel fuzzy critical path methodology in project scheduling, where activity durations are represented by generalized quasi-geometric fuzzy numbers–specifically, generalized rational fuzzy numbers with subnormal heights. To enable more realistic modeling and reduce computational burden, the authors introduced TA-based fuzzy arithmetic and a new distance-based ranking approach, which were validated through a case study involving airport cargo ground operations. Akdemir et al. [18] addressed minimum cost flow problems under uncertainty by employing trapezoidal fuzzy numbers with subnormal membership functions. Their credibilistic optimization framework utilizes CVaR minimization to obtain risk-averse solutions, avoiding the information loss caused by normalization and supporting arithmetic operations that preserve shape and height. Pratibha and Dangwal [19] investigated the fuzzy least cost path problem within supply chain networks by modeling uncertain edge costs as generalized hexagonal fuzzy numbers. Their approach integrates a rankingbased defuzzification method with fuzzy dynamic programming to compute optimal routes under uncertainty without requiring normalization, thereby preserving subnormal membership characteristics in the fuzzy input. Solving the fuzzy SPP–whether pursued algorithmically (e.g., dynamic programming, Dijkstra’s or Bellman–Ford) or via a linear programming formulation–requires well-defined operations for addition, scalar multiplication, and ordering of fuzzy edge costs. The objective of this study is to develop a path-additive defuzzification scheme that is applicable to network optimization problems and compatible with both Gaussian and generalized fuzzy frameworks. In this study, we adopt an α-cut–based formulation for aggregating heights in the addition of generalized Gaussian fuzzy numbers (GGFNs). Specifically, the resulting height is estimated as a weighted geometric mean of the input heights, with weights derived from the standard deviations of the input fuzzy numbers. This ensures that the resulting height remains bounded between the minimum and maximum input heights and that the addition operator is associative. To our knowledge, this is the first approach to use a weighted geometric mean for approximating height in GGFN addition, offering a new perspective in fuzzy arithmetic. Related work on height aggregation and Gaussian memberships includes Akdemir [20], which developed generalized picture fuzzy numbers with Gaussian memberships, proposed triangular approximations, and introduced a compensatory height update for decision problems. Distinct from this line of work, the present paper targets shortest paths with Type–1 GGFNs and introduces an α–cut-based, σ–weighted height aggregation together with a risk–averse ranking index. Building on this formulation and its implications, the present paper makes the following contributions: • We introduce an α–cut–based addition for Type–1 GGFNs that aggregates heights via a σ–weighted geometric mean. The resulting height stays within input bounds and the addition is associative. • We define risk–averse ranking indices Rbenefit and Rcost that couple the mean–like core with a reliability–modulated risk term; for normal fuzzy sets, they reduce to a risk–neutral ranking. We prove the desired monotonicity properties. • Within a single, path–additive scheme, we balance three objectives–minimizing cost, maximizing height (information reliability), and minimizing fuzziness/ambiguity (dispersion σ modulated by h)–via the proposed σ–weighted height aggregation and risk– averse ranking; on directed test networks, this yields routes that remain cost–efficient under perturbations while systematically prioritizing high–height edges, thereby mak-
3
ing the cost–reliability–ambiguity trade–off explicit in practice. • For robustness analysis, we adopt the single-value (fuzzy-numerical) simulation of Chanas and Nowakowski [21]–sampling a membership level uniformly and then drawing a cost uniformly from the corresponding α–cut–to redraw edge costs and measure sensitivity via the mean percentage deviation and its standard deviation. • We provide large-scale network experiments that demonstrate the method’s scalability—i.e., practical time/memory growth with problem size—on the FAA network, together with systematic deviation profiles across reliability regimes obtained via singlevalue α-cut simulations. The remainder of the paper is organized as follows: 2 reviews preliminaries on fuzzy numbers and α–cuts, outlines the sampling procedure used for error analysis, and formulates fuzzy SPPs on generalized and Gaussian networks. 3 presents the adopted α–cut–based approach to GGFN addition, introduces the height aggregation rule, and verifies associativity on a small illustrative example (the routine inductive proof is omitted for brevity). 4 defines the risk–averse ranking indices and establishes their monotonicity properties. 5 presents a small-scale numerical illustration of the framework. 6 details large-scale network tests, confirming computational scalability—i.e., practical time and memory growth with problem size—and illustrating how deviation behavior evolves under varying reliability regimes. 7 concludes the paper and highlights the directions for future work.
2
Preliminaries and Problem Setting
The main terminology and basic concepts needed for the discussion are as follows. e on a universe of discourse X can be expressed as Definition 1. A fuzzy set A n o e = ⟨x, µ (x)⟩ x ∈ X , A e A e where µAe : X → [0, 1] represents the degree to which an element x belongs to A.
Definition 2. [22] Let p, q, r ∈ R, where p < q < r, and h ∈ (0, 1] . A generalized fuzzy e is a fuzzy subset of the real line R, whose membership function µ satisfies the number A e A following conditions (i) µAe : R → [0, h] is continuous,
(ii) µAe (x) = 0 for x < p or x > r,
(iii) µAe (x) is strictly increasing on [p, q] and strictly decreasing on [q, r],
(iv) µAe (q) = h.
e Remark 1. If normality holds (i.e., h = 1) and the membership function is convex, then A e is a fuzzy number. Otherwise, when h ∈ (0, 1), A is subnormal with maximal membership (height) h. In a possibilistic reading, h can be interpreted as a degree of consistency of the underlying evidence; hence h < 1 indicates partially inconsistent information and a non–normalized possibility distribution [1]. e is defined as Definition 3. The α−level set of A n o eα = x ∈ R|µ (x) ≥ α, α ∈ [0, h] A e A eL (α) , A eR (α)], = [A eL (α) and A eR (α) denote the inverse functions of the left and right membership funcwhere A tions, respectively. e = ⟨(c , σ ); h ⟩, is Definition 4. [4] The membership function of a GGFN, denoted by A e Ae Ae A defined as ! 2 x−c A e , µAe(x) = hAe exp − 21 σ A e
4
where 0 < hAe ≤ 1, cAe is the center (core, or hAe−level set), and the parameter σAe > 0 describes the spread around the central value cAe. The center value cAe can be interpreted as the most possible value, with a maximum membership degree of hAe. Remark 2. According to the definitions in [23], the possibilistic mean value and variance are calculated as cAe and σ 2 , respectively. These quantities are independent of the height and e A are therefore computed in the same way for fuzzy numbers. The parameter σAe is referred to as the standard deviation. e = ⟨(c , σ ); h ⟩, the left and right inverse functions are Remark 3. For a GGFN A e Ae Ae A s eL (α) = c − σ A e e −2 ln A A
α h
s
,
eR (α) = c + σ A e e −2 ln A A
A
e
α h
.
A
e
e is the closed interval [A eL (α), A eR (α)]. For any α ∈ (0, hAe], the α-level set of A
2.1
Sampling scheme for error analysis
These representations capture the lower and upper extremal values of each GGFN interval α-cut. In the simulation procedure, we adopt the single-value (fuzzy-numerical) simulation of Chanas and Nowakowski [21], adapting their Procedure 1 to our setting: we first draw a membership level uniformly and then draw a value uniformly from the induced cut, which yields a single crisp realization of a GGFN. Concretely, a uniformly distributed random number u is generated over an appropriate interval, followed by the generation of another random number v from the uniform distribution on the u-cut interval. The weighted arithe as follows metic mean of the endpoints of the u-cut interval yields a sample of A eL (u) + (1 − v) A eR (u), Â = v A
(1)
where u ∼ U (0, hAe) and v ∼ U (0, 1) are independent. This single-value scheme is then used in a Monte Carlo fashion to redraw edge costs for robustness/error analysis.
2.2
Fuzzy SPP on generalized Gaussian networks
A Type–V fuzzy graph is defined on known vertices and edges, but the edge costs involve e = (V, E, C), e where V is the set of veruncertainty. Consider an acyclic directed network G tices, E is the set of edges, and Ce denotes the admissible set of fuzzy edge costs. Each edge eij = ⟨(cij , σij ); hij ⟩ with α– (i, j) ∈ E has a nonnegative generalized Gaussian fuzzy cost A p e e e cut [AijL (α), AijR (α)], where AijL (α) = cij − σij −2 ln(α/hij ). We impose nonnegativity of the left endpoints at the evaluation levels used in this paper, i.e., there exists α∗ ∈ (0, 1] eijL (α) ≥ 0 for all α ∈ [α∗ , hij ] and all (i, j) ∈ E. A sufficient condition is such thatp A σij ≤ cij −2 ln(α∗ /hij ) for every edge. We can formulate the fuzzy SPP in the following linear programming form: min fe(x) =
X
(2)
eij xij A
(i,j)∈E
s.t.
1, X X xij − xji = 0, j j −1, xij ∈ {0, 1}
if i = s, if i ̸= s, t (i = 1, . . . , n), if i = t,
∀ (i, j) ∈ E
with s and t denoting the source and terminal nodes, respectively.
5
(3) (4)
3 An α–Cut–Based Approach to GGFN Addition: Height Aggregation and Associativity We now present a novel α–cut–based approach to generalized fuzzy addition, determining the resulting height via numerical approximation. In this scheme, the height is computed as a weighted geometric mean of the input heights, with weights derived from the standard deviations of the corresponding fuzzy numbers. Under the proposed weighting, the addition operator is associative. When approximation is used, the corresponding formulation implicitly assumes that the arithmetic and geometric means yield sufficiently close values. Accordingly, the approximation performs better when hAe is close to hBe. The use of weighted averaging in determining the resultant height ensures that the value lies between the minimum and maximum of the input heights. From an information reliability perspective, this reflects a compensatory approach that neither overestimates nor underrepresents the influence of each fuzzy component. e = ⟨(c , σ ); h ⟩ and B e = ⟨(c , σ ); h ⟩ be two independent GGFNs Definition 5. Let A e Ae Ae e Be Be A B and let k ∈ R. Then, the following operations hold. • Addition of two GGFNs σ
* e+B e= A
σ B +σ A B
e + cAe + cBe, σAe + σBe ; h e e · h e e e e A B
• Scalar Multiplication e= kA
D
σ
A +σ A B
e
σ
(2)
E kcAe, |k| σAe ; hAe .
Remark 4. We analyze the additivity of GGFNs using their a-cut representations. Consider e = ⟨(c , σ ); h ⟩ and B e = ⟨(c , σ ); h ⟩. Under the assumption that the two GGFNs A e Ae Ae e Be Be A B Gaussian form is preserved, the corresponding α-cuts are given by s s " # α e Aα = cAe − σAe −2 ln h , cAe + σAe −2 ln hα , α ∈ (0, hAe], A e A e s s " # α α eα = c − σ , α ∈ (0, hBe], B e e −2 ln hBe , cBe + σBe −2 ln hBe B B q q h i e + B) e α = c + c − (σ + σ ) −2 ln α , c + c + (σ + σ ) −2 ln α (A h h e e e e e e e e A B A B A B A B where h denotes the unknown height, with α ∈ (0, h]. According to interval arithmetic, the following identity should hold: s s q α + σBe −2 ln hα = (σAe + σBe) −2 ln αh . σAe −2 ln h A e B e Since enforcing the above equality yields a complicated expression in α in which α does not cancel, we introduce an approximation. Specifically, invoking the inequality between the weighted arithmetic mean and the weighted geometric mean, we approximate the weighted geometric mean by its weighted arithmetic counterpart as follows: s h h h h ln αAe ln αBe ≃ 21 ln αAe + ln αBe . This approximation leads to a tractable expression for the height parameter σ A +σ A B
e
σ B +σ A B
e e e e e h=h ·h e e A B σ
which forms the basis of our approach.
6
σ
Remark 5. A similar α-cut-based strategy can be applied to symmetric triangular or trapezoidal generalized fuzzy numbers, using a weighted (not necessarily normalized) harmonic mean to aggregate heights. In this case, the weights are taken proportional to the spreads and are not normalized to sum to one. Under this weighting, the resulting addition operator is not associative. For further details, see [2].
4 Risk–Averse Ranking Indices: Definition and Monotonicity In line with the adopted aggregation rule, we introduce the ranking indices Rbenefit and Rcost ; their precise forms are given below. Throughout, log denotes the base-10 logarithm. e = ⟨(c , σ ); h ⟩ be a GGFN with c > 0, σ > 0, and h ∈ (0, 1]. Definition 6. Let A e Ae e e e e A A A A A The benefit-type and cost-type ranking indices are defined, respectively, by cost e e = c + σ log h , Rbenefit (A) R ( A) = c − σ log h . e e e e e e A A A A A A e = ⟨(c , σ ); h ⟩ and B e = ⟨(c , σ ); h ⟩ denote two independent costTheorem 1. Let A e Ae e e Be e A A B B type GGFNs. Assume cAe, cBe, k > 0. Under the proposed aggregation scheme, the cost-type ranking index Rcost satisfies: e + B) e = Rcost (A) e + Rcost (B), e (i) Rcost (A e = k Rcost (A). e (ii) Rcost (k A) Proof. The proofs below are provided for cost-type variables; similar reasoning applies to the benefit-type index. (i) e + B) e =c Rcost (A − σ · log h e Be e Be e Be A+ A+ A+
σ
σ
A +σ A B
e
σ
σ B +σ A B
e
= (cAe + cBe) − (σAe + σBe) · logh e e h e e e e A B " # σAe σBe = (cAe + cBe) − (σAe + σBe) log hAe + log hBe σAe + σBe σAe + σBe = cAe − σAe log hAe + cBe − σBe log hBe e + Rcost (B). e = Rcost (A) (ii) e = c − σ · log h Rcost (k A) e e e kA kA kA = kcAe − kσAe · log hAe e = k Rcost (A).
(since k > 0)
Remark 6. In defining the ranking functions, their monotonicity can be verified by analyzing partial derivatives with respect to the underlying parameters. Assume c > 0, σ > 0, and h ∈ (0, 1]. Benefit-type variable. Let Rbenefit (⟨(c, σ); h⟩) = c + σ log(h). Then ∂Rbenefit = 1 > 0, ∂c
∂Rbenefit σ = > 0, ∂h h ln 10
∂Rbenefit = log(h) ≤ 0. ∂σ
In the benefit-type index, higher values of c and h improve the score, while volatility (σ) reduces it. Conversely, for the cost-type index, c and σ act as penalties, while h mitigates the cost, reflecting the preference for high-reliability information.
7
Cost-type variable. Let Rcost (⟨(c, σ); h⟩) = c − σ log(h) and interpret lower values as more preferred (“less is better”). Then ∂Rcost = 1 > 0, ∂c
∂Rcost σ =− < 0, ∂h h ln 10
∂Rcost = − log(h) ≥ 0. ∂σ
Hence, larger c and σ worsen (increase) the index, whereas larger h improves (decreases) it. In summary, under c > 0, σ > 0, and h ∈ (0, 1], both Rbenefit and Rcost exhibit the desired monotonicity, reflecting the principles that “more is better” for benefits and “less is better” for costs. Conceptually, the indices are mean–risk measures with a risk-averse orientation: they couple the mean-like core c with a risk adjustment that scales with σ and whose magnitude is controlled by | log h|. For normal fuzzy sets (h = 1), the adjustment vanishes and the index is risk-neutral, yielding Rbenefit = Rcost = c. As reliability decreases (h ↓) or variability increases (σ ↑), the penalty magnitude σ| log h| grows, pushing the score in a less preferred direction–increasing for cost-type and decreasing for benefit-type. In other words, from a risk-averse (pessimistic) perspective–and relative to risk-neutral defuzzification based solely on the core c–cost-type fuzzy quantities are defuzzified to larger crisp values, whereas benefit-type quantities are crispified to smaller ones. The cost-type index can be generalized by introducing a risk–attitude parameter κ as Rcost (⟨(c, σ); h⟩, κ) = c − κ σ log(h),
(3)
where κ ≥ 0. The baseline specification is recovered by setting κ = 1, while larger values of κ penalize alternatives with smaller heights h, even if they have slightly lower cores. We illustrate the height aggregation rule and the ranking index in 1 (for both benefitand cost-type cases) and, in this instance, confirm that the resulting addition operator is associative; a general proof by induction is straightforward and is left to the reader. e = ⟨(15, 3); 0.6⟩, Example 1. 1 reports the core, standard deviation, and height values for A e e B = ⟨(5, 1); 0.7⟩, C = ⟨(5, 1); 0.9⟩ and their combinations under the adopted approach, together with the corresponding ranking scores for both benefit-type and cost-type settings. The ranking results demonstrate that: e ≺ C, e B
e+B e≺A e + C, e A
e≺B e+C e ≺ 2C. e 2B
e ≺ C e indicates a These results align with the expected preference ordering. Note that B e e preference for C over B. e B, e Table 1: Parameters (core c, standard deviation σ, and height h) and ranking indices for A, e C and their combinations (All non-integer values are reported to four decimal places.)
Parameters
Ae e B Ce e Ae + B Ae + Ce e 2B e+C e B e 2C
Ranking indices
Core c
Std. Dev. σ
Height h
Rbenefit
Rcost
15 5 5 20 20 10 10 10
3 1 1 4 4 2 2 2
0.6000 0.7000 0.9000 0.6236 0.6640 0.7000 0.7937 0.9000
14.3345 4.8451 4.9542 19.1796 19.2887 9.6902 9.7993 9.9085
15.6655 5.1549 5.0458 20.8204 20.7113 10.3098 10.2007 10.0915
Under the adopted approach, all parenthesizations coincide: D E e + B) e +C e = (25, 5); (0.6235739) 45 (0.9) 15 = ⟨(25, 5); 0.6710561⟩ , (A
8
E D e + (B e + C) e = (25, 5); (0.7937254) 25 (0.6) 35 = ⟨(25, 5); 0.6710561⟩ , A E D e + C) e +B e = (25, 5); (0.6640092) 45 (0.7) 15 = ⟨(25, 5); 0.6710561⟩ . (A For completeness, the three-term sum (without parentheses) is D E e+B e+C e = (25, 5); 0.6 35 0.7 15 0.9 15 = ⟨(25, 5); 0.6710561⟩ . A We omit further details here, as the relevant intermediate calculations are already provided in 1.
5
Numerical Experiments: Fuzzy SPP Cases
This section reports numerical experiments conducted under generalized Gaussian fuzzy edge costs. We focus on the impact of cost uncertainty and quantify the error induced by replacing the original fuzzy model with crisp counterparts.
Stage 1 (model solution) We first solve the proposed ranking index-based minimization model under GGFN costs and record the resulting optimal decision (path) and objective value.
Terminology and rationale Ex-ante refers to the baseline path chosen before sam-
pling, using the reliability-aware (risk-averse) ranking while uncertainty is still present. Expost refers to, for each Monte Carlo draw, the path obtained after costs are realized as crisp values by re-optimizing the deterministic problem purely by cost. In other words, ex-ante uses the membership information (including heights) to pick a conservative baseline, whereas ex-post treats a sampled instance as fully known and selects the cost-minimizing path for that instance. Our goal is not to reproduce the ex-post minimum, but to assess how closely a reliabilityaware solution tracks ex-post optima and to quantify the associated reliability premium via Monte Carlo α-cut sampling.
Stage 2 (simulation for error analysis) To assess the performance loss due to
defuzzification, we generate crisp cost instances from the GGFNs and re-solve the induced deterministic shortest-path problems. In particular, for each edge e we draw a level u ∼ U (0, he ) and a mixing weight v ∼ U (0, 1), compute the α-cut endpoints ce,L (u) and ce,R (u) of the GGFN, and set the sample cost ĉe as in 1. This single-value scheme follows Chanas and Nowakowski’s fuzzy-numerical simulation (adapted to GGFNs), in which membership levels are drawn uniformly and values are sampled uniformly from the induced α-cuts [21]. The resulting crisp instances are solved repeatedly to produce meaningful Monte Carlo summaries for evaluating the risk-averse solution. To ensure valid edge costs, we use rejection sampling: if the generator produces a negative cost, we discard it and draw again.
Error metric Let c̄ denote the baseline crisp edge coefficients obtained from the ranking
rule, and let ĉ denote the sampled crisp edge coefficients obtained by α-cut sampling for a given instance. For each instance, let z 0 be the optimal objective under c̄, and let z be the optimal objective under ĉ. We report the absolute percentage deviation from the baseline Dev(%) = 100
|z − z 0 | , z0
(4)
defined whenever z 0 > 0. We then present the empirical distribution of Dev (4) across replications and summarize it by the mean percentage deviation and the standard deviation of the percentage deviation.
9
Implementation All experiments were executed on a standard desktop environment.
The deterministic subproblems can be solved with a shortest-path routine (e.g., Dijkstra) or a linear programming solver. In practice, we used MATLAB built-in graph routines (graph/digraph) and the shortestpath function to solve the induced shortest-path instances. For reproducibility of results, we use the random seed (rng(42) in MATLAB). For each case, we perform 10 outer replications, each comprising N = 1000 Monte Carlo samples. For every sample, levels are drawn independently across edges (ue ∼ U (0, he ), guarded against ue = 0 by machine-epsilon clipping), and mixing weights are drawn as ve ∼ U (0, 1). All draws are independent across edges and repetitions. Example 2. The following example is adapted from Hasuike [24], who studied a robust shortest–path model with random edge costs. We take the reported mean–variance pairs as √ (c, σ 2 ) and represent each edge cost as a GGFN ⟨(c, σ); h⟩ with σ = σ 2 . To emulate different reliability regimes, edge heights are drawn independently as {hij }(i,j)∈E ∼Beta(a, b), where a, b > 0 are the Beta shape parameters; We primarily evaluate four settings: high (a, b) = (8, 2), moderate (4, 3), low (2, 5), and a mixed regime defined by hij ∼ (1 − ε) Beta(8, 2) + ε Beta(2, 5) (with ε = 0.2). For completeness, two additional mixed settings used in our sensitivity checks are reported in 2. 1 depicts the resulting network; the topology and (c, σ 2 ) pairs follow Hasuike [24], while the heights shown are a single i.i.d. draw from the high setting Beta(8, 2). ⟨(33, 4.58); 0.66⟩
B
⟨(17, 1.73); 0.90⟩
⟨(19, 2.83); 0.88⟩
⟨(15, 2.24); 0.89⟩
E
⟨(12, 2.00); 0.80⟩
A
D
G
⟨(18, 1.41); 0.97⟩
⟨(10, 1.41); 0.79⟩
⟨(18, 1.41); 0.92⟩
C
⟨(35, 3.16); 0.94⟩
⟨(18, 2.24); 0.85⟩
F
√ Figure 1: Sample network with GGFN edge costs ⟨(c, σ); h⟩. Here σ = Variance from the original labels, and heights are sampled i.i.d. from Beta(8, 2) (high reliability). All decimal quantities are reported to two decimal places.
Table 2: Example height sets hij under four reliability regimes plus two mixed settings. High: Beta(8, 2); Moderate: Beta(4, 3); Low: Beta(2, 5); Mixed: (1 − ε) Beta(8, 2) + ε Beta(2, 5) (here ε = 0.2). Mixed–A and Mixed–B report two alternative mixed settings. Edge
High
Moderate
Low
Mixed
Mixed–A
Mixed–B
AB AC BD BE CD CF DE DF EG FG
0.89 0.97 0.88 0.66 0.92 0.94 0.90 0.79 0.80 0.85
0.51 0.71 0.89 0.59 0.34 0.75 0.77 0.65 0.61 0.58
0.05 0.09 0.20 0.26 0.16 0.44 0.24 0.20 0.49 0.09
0.33 0.77 0.97 0.63 0.85 0.80 0.25 0.78 0.76 0.77
0.20 0.98 0.50 0.20 0.98 0.50 0.50 0.98 0.20 0.98
0.98 0.20 0.98 0.20 0.20 0.20 0.20 0.98 0.20 0.98
10
Table 3: Path summaries (part I). Core c, dispersion σ, and rankings under High/Moderate/Low reliability settings. High (a, b) = (8, 2)
Moderate (4, 3) h
Rcost
h
Rcost
0.57 0.69 0.66 0.59 0.71 0.79
62.13 64.43 63.59 66.50 65.66 72.14
0.20 0.18 0.12 0.22 0.29 0.62
66.18 69.54 70.17 69.28 69.91 75.93
Path
c
σ
h
Rcost
A−B−E−G A−B−D−E−G A−B−D−F−G A−C−D−E−G A−C−D−F−G A−C−F−G
60 63 62 65 64 71
8.82 8.80 8.71 6.56 6.48 6.81
0.74 0.87 0.86 0.89 0.84 0.88
61.14 63.54 62.56 65.34 64.37 71.26
Low (2, 5)
Table 4: Path summaries (part II). Rankings under Mixed/Mixed–A/Mixed–B reliability settings. Mixed Path A−B−E−G A−B−D−E−G A−B−D−F−G A−C−D−E−G A−C−D−F−G A−C−F−G
Mixed–A
Mixed–B
h
Rcost
h
Rcost
h
Rcost
0.56 0.53 0.67 0.58 0.79 0.79
62.24 65.42 63.52 66.56 64.66 71.71
0.20 0.32 0.52 0.51 0.98 0.72
66.16 67.33 64.45 66.94 64.06 71.98
0.30 0.50 0.98 0.20 0.49 0.34
64.62 65.65 62.08 69.59 66.01 74.22
As summarized in 3 and 4, the cost–type ranking selects A − B − E − G as the optimal path under the High, Moderate, Low, and Mixed regimes, whereas other mixed settings yield A − C − D − F − G (Mixed–A) and A − B − D − F − G (Mixed–B), respectively. Tables 3 and 4 indicate that the optimal path is stable (A − B − E − G) across broad i.i.d. reliability regimes (High/Moderate/Low and Mixed), and changes only under targeted mixed settings (Mixed–A and Mixed–B). Consistent with our results, Hasuike [24] reports A−C−D−F−G as optimal under both the probability-maximizing and robust models, whereas the basic SPP selects A−B−E−G. Moreover, as the goal parameter fL increases from 60 to 66, the optimal path shifts from A−B−E−G (fL = 60) to A−B−D−F−G (fL = 63) and A−C−D−F−G (fL = 66). Holding fL = 66, fU = 75, and dU = 3, increasing dL from 1.0 to 2.5 shifts the optimal path from A−B−E−G (dL = 1.0) to A−B−D−F−G (1.5) and then to A−C−D−F−G (2.0, 2.5), consistent with the model’s design: small dL places little weight on dispersion (recovering the standard SPP solution), whereas larger dL emphasizes variance reduction and yields more risk-averse routes. Overall, the optimal solution is sensitive to parameter variation and the specification of risk preferences; even modest changes in these inputs can reorder candidate paths and shift the optimum toward more risk-averse routes. Having specified the reliability-aware ranking and obtained the baseline path and objective (Stage 1), we now proceed to Stage 2 to assess robustness: we generate crisp instances via Monte Carlo α-cut sampling and summarize performance using the percentage deviation statistics.
Discussion Across settings, deviation increases as reliability decreases. Using Tables 5, 6, and 7, the mean Dev (SD of Dev) is 5.37% (4.39%) in High, 6.50% (4.86%) in Moderate, 5.99% (4.64%) in Mixed, 8.86% (5.23%) in Mixed–A, 6.44% (4.87%) in Mixed–B, and 10.08% (5.20%) in Low. Thus, all but Low remain single-digit; Mixed– A sits closer to Low, whereas Mixed–B is nearer to Moderate. Ranges across the 10
11
Table 5: Absolute percentage deviation (Dev %) and standard deviation of Dev for High and Moderate reliability settings across 10 replications (rounded to 4 decimals). High
Moderate
Rep.
Dev (%)
Std. Dev. (Dev)
Dev (%)
Std. Dev. (Dev)
1 2 3 4 5 6 7 8 9 10
5.3192 5.2651 5.3035 5.2564 5.3150 5.6864 5.4206 5.2920 5.1006 5.7035
4.5710 4.3867 4.5718 4.4244 4.1998 4.4516 4.4216 4.1643 4.2974 4.3878
6.1338 6.2886 6.3028 6.3757 6.3480 7.5891 7.0094 6.6642 5.6678 6.6414
4.9280 4.8916 5.0162 4.8692 4.6182 5.0268 5.0284 4.6497 4.6437 4.9216
Mean
5.3662
4.3876
6.5021
4.8593
Table 6: Absolute percentage deviation (Dev %) and standard deviation of Dev for Low and Mixed settings across 10 replications (rounded to 4 decimals). Low
Mixed
Rep.
Dev (%)
Std. Dev. (Dev)
Dev (%)
Std. Dev. (Dev)
1 2 3 4 5 6 7 8 9 10
8.6731 10.9313 10.1704 10.2511 9.9290 9.9177 9.9895 9.1868 10.0580 11.6725
5.4286 4.9576 5.2453 5.1000 5.1481 5.0496 5.1199 5.2812 5.3762 5.3328
5.2362 6.1633 6.6705 6.8820 5.0512 5.6908 5.2315 6.2319 6.0984 6.6728
4.3685 4.7213 5.0122 4.9866 4.3193 4.4811 4.1998 4.7699 4.7775 4.7795
Mean
10.0780
5.2039
5.9929
4.6416
12
Table 7: Absolute percentage deviation (Dev %) and standard deviation of Dev for Mixed–A and Mixed–B settings across 10 replications (rounded to 4 decimals). Mixed–A
Mixed–B
Rep.
Dev (%)
Std. Dev. (Dev)
Dev (%)
Std. Dev. (Dev)
1 2 3 4 5 6 7 8 9 10
8.6738 8.8612 8.6490 8.8014 8.8713 8.7601 9.0235 9.2159 8.9630 8.7775
5.1307 5.2180 5.0848 5.2122 5.2225 5.1232 5.4053 5.3598 5.3791 5.1267
6.2512 6.4449 6.2677 6.3393 6.4709 6.4131 6.5896 6.7255 6.5394 6.3294
4.7823 4.8518 4.6650 4.9146 4.8354 4.6707 5.0781 5.0897 5.0442 4.7843
Mean
8.8597
5.2262
6.4371
4.8716
replications are narrow (e.g., High: [5.1006, 5.7035]%; Low: [8.6731, 11.6725]%), indicating stable Monte Carlo estimates and a crisp baseline that tracks re-optimized solutions reasonably well except under Low reliability.
Interpretation This double-digit gap in the Low regime reflects the cost of risk aversion rather than a model flaw. Our baseline path is chosen by a reliability-aware ranking that rewards higher heights, whereas the benchmark re-optimizes each instance under plain crisp costs that ignore reliability. This intentional misalignment yields a larger ex-post deviation when heights are low (i.e., reliable edges are scarce). Note that, with u ∼ U (0, h), we have u/h ∼ U (0, 1), so the sampling distribution of crisp costs depends on (c, σ) but not on h; heights only affect the baseline via the ranking penalty. Consequently, as reliability decreases, path choices diverge more often, and the deviation increases. In regimes with moderateto-high heights, deviations remain single-digit and between-replication spreads are narrow, indicating stable estimates. The increased deviation in the Low regime stems from three main factors. First, there is an intentional misalignment between our method and the metric: the baseline path rewards reliability, whereas the benchmark re-optimizes based solely on crisp costs. Second, the sampling distribution of crisp costs depends on the core and spread but not the height, meaning lower heights shift the baseline without narrowing the sampling spread. Finally, low reliability causes edge rankings to fluctuate more intensely, leading to a ‘path-switching effect’ where the ex-post optimal path diverges frequently from the baseline.
6 Construction and Analysis of Large-Scale GGFN–SPP Instances We now construct and analyze large-scale instances of the GGFN–SPP using real-world transportation data from the Federal Aviation Administration (FAA) [25] network. We focus on a case study based on the FAA air traffic network, which illustrates how the proposed α–cut–based height aggregation and risk–averse ranking indices behave on a realistically sized, sparse transportation network.
6.1
FAA Air Traffic Network
The underlying crisp network is the “maayan-faa” graph from the Koblenz Network Collection (KONECT), derived from the U.S. FAA National Flight Data Center (NFDC) preferred
13
routes database (www.fly.faa.gov). The original FAA network used in this case study is derived from the KONECT “maayan-faa” dataset [26]. The raw graph does not provide dispersion; we calibrate σij from the nominal cost via a cost-scaled uniform rule: draw uij ∼ U (0, 1) and set σij = 0.4 cij uij , equivalently σij ∼ U (0, 0.4 cij ). This keeps spreads proportional to edge cores, yields heterogeneous but bounded α–cut widths, and avoids excessive rejection in the Monte Carlo sampler while maintaining nonnegativity at the evaluation levels used here. From the original GraphML/TSV distribution, we extract a directed simple graph and relabel vertices as n0, n1, . . . in the order provided. The nodes represent airports or air traffic control service centers, and a directed edge (i, j) indicates that there is a preferred route from i to j in the NFDC database. The KONECT metadata characterizes the graph as unweighted, directed, and of transportation type. The resulting network used in our experiments contains N = 1226 nodes and m = 2615 directed edges, as summarized in 8 and visualized in 2. This size is moderate by network science standards, but substantially larger than the toy examples typically used in fuzzy SPP studies. In addition, it is sufficiently rich to exhibit multiple long-range alternative routes between major hubs.
Figure 2: FAA air traffic network used in the case study. Nodes represent airports or service centers; directed edges encode preferred routes extracted from the KONECT “maayan-faa” dataset [27].
6.2
From Crisp Routes to GGFN Edge Costs
To instantiate a GGFN–SPP on this network, each directed edge (i, j) is endowed with a eij with core cij , dispersion σij and height hij , as developed in 2 and 3. The Type–1 GGFN A triple (cij , σij , hij ) encodes a baseline cost, variability, and reliability for the corresponding air route: • The core cij > 0 plays the role of a nominal travel cost (e.g., a surrogate for the typical flight time or the generalized distance). In the FAA dataset used here, the calibrated core values lie in the range [5.01, 49.99], with a mean 27.44 and standard deviation 13.10 (arbitrary units), yielding a fairly heterogeneous mix of short and long edges. • The dispersion σij > 0 controls the spread of the Gaussian membership and therefore the width of α–cuts. In the FAA case, σij is imputed via σij ∼ U (0, 0.4 cij ), yielding heterogeneous but bounded spreads; with cij ∈ [5.01, 49.99], this places σij in [0, 20]
14
Figure 3: Empirical distributions of core costs cij , dispersions σij , and heights hij in the FAA GGFN–SPP instance. Distributions show heterogeneous nominal costs, varied dispersions, and subnormal heights concentrated at the upper end. and gives an expected mean of about 0.2 cij (roughly 5.5 overall) and an expected standard deviation of about 0.115 cij (roughly 3.5 overall), so some edges are nearly crisp while others are substantially fuzzy. • The height hij ∈ (0, 1] quantifies the reliability of the information underlying the core cost. Heights are modeled as subnormal in order to explicitly capture partial inconsistency or incompleteness of the underlying evidence. In the FAA instance, hij ranges from 0.27 to 0.997, with mean 0.80 and median 0.82; approximately 90% of edges have height above 0.57, but a nontrivial tail of low-height edges represents poorly supported or infrequently used routes. These empirical ranges are reported in 8 and their distributions are shown in 3.
Table 8: Summary statistics for the FAA GGFN–SPP instance. The graph has N = 1226 nodes and m = 2615 directed edges. Edge parameters (cij , σij , hij ) are as described in 6. Quantity
Min
Max
Mean
Median
Std. dev.
Core cij Dispersion σij Height hij
5.01 0.00 0.27
49.99 20.00 0.997
27.44 5.50 0.80
27.76 5.55 0.82
13.10 3.50 0.12
Heights are sampled once and then held fixed across experiments according to the Beta– mixture regimes introduced earlier. Specifically, we employ the “mixed” regime in which most edges draw hij from a high–reliability Beta(8, 2) distribution, while a random ε–fraction of edges are flipped to a low–reliability Beta(2, 5) component. The resulting subnormal Gaussian fuzzy numbers are then fully specified by (cij , σij , hij ), and their α–cut intervals are computed via 3 with α clamped to (0, hij ) in practice to avoid empty cuts.
6.3
Path Aggregation and Instance Families
Given these edgewise GGFNs, we consider path costs defined by the α–cut–based addition developed in 3. For a simple path P from source s to terminal t, with edges (i, j) ∈ P , the path-level GGFN parameters (cP , σP , hP ) are obtained by iterated application of 2, P σij ln hij P P (i,j)∈P P namely cP = (i,j)∈P cij , σP = (i,j)∈P σij , and hP = exp , so that core σ (i,j)∈P
ij
and dispersion aggregate additively, while the height aggregates via a σ–weighted geometric mean. As shown earlier, this aggregation keeps hP within the input height bounds, preserves associativity of addition, and respects the intended interpretation of hij as reliability weights.
15
6.4
Risk-Averse Ranking and Baseline Paths
Within this path-additive framework, the risk–averse ranking indices from 4 provide scalar surrogates to order fuzzy paths. For each instance, we compute two baseline s–t paths: 1. A core path xc that minimizes the crisp sum of cores, i.e., solves the classical shortest path problem with edge weights cij . 2. A ranked path xR that minimizes Rcost (⟨(cP , σP ); hP ⟩, κ) (3) using the α–cut–consistent addition and the σ–weighted height aggregation. This is obtained via a Dijkstra–style label–setting algorithm that propagates (cP , σP , hP ) along the graph and orders tentative labels by Rcost . In the FAA case with κ = 1, both procedures select the same s–t path from n2 to n1189, where the path consists of 10 vertices (9 edges). This path can be interpreted as the “preferred” route that simultaneously balances low nominal cost and high reliability; the coincidence of xc and xR at κ = 1 indicates that, for this instance, the most cost-efficient path is already composed predominantly of high-height edges.
6.5 Computational Cost: Deterministic Scaling with Ranked Solver on FAA We time the ranked solver deterministically across an N/8 size grid on the FAA network (N =1226) to illustrate scaling (see 1) for the algorithm details). For each size ki = ⌈iN/8⌉, we induce the subgraph on the first ki nodes, choose a reachable destination (largest node reachable from n0), and measure wall-clock time and peak memory. 1 The function, DijkstraRanked, is a deterministic, risk-aware shortest-path routine: a Dijkstra-style algorithm that propagates fuzzy edge triples c, σ, h), aggregates them along paths (additive cores and spreads; σ-weighted geometric mean for height), and orders tentative labels by the ranking index Rcost = c − κσ log h. It yields the ex-ante (ranked) baseline path. The solver shows near-linear growth in runtime with respect to the number of edges m across the N/8 grid, with peak memory well below 1 MB even at the full FAA scale.
Table 9: Runtime and memory scaling of deterministic ranked solver on induced FAA subgraphs along the N/8 size grid ki = ⌈i N/8⌉ (FAA: N =1226). Median runtimes and peak memory are taken from single runs of the ranked solver. N
m
Time (s)
Peak memory (MB)
tdst
154 308 462 616 770 920 1078 1226
409 835 1185 1494 1807 2046 2369 2615
0.0211 0.0461 0.0541 0.0633 0.0530 0.0508 0.0716 0.0746
0.09 0.12 0.19 0.24 0.36 0.35 0.44 0.48
154 308 462 616 770 921 1078 1226
The resulting runtimes and memory footprints are reported in 9 and plotted in 4, which together illustrate the near-linear scaling with N and m for the deterministic ranked solver. In addition, the α–cut scenario mode provides deterministic lower/upper (or midpoint) cost profiles for increasing α levels. For the full FAA instance under an optimistic “lowerbound” choice, the α–cut path cost increases from approximately 93 at α = 0.05 to roughly 193 at α = 0.95. Thus, moving from a highly optimistic to a highly conservative α level 1
Experiments were run on a 2024 MacBook Pro (M4 chip) using Python 3.13. The software environment included Python 3.13 with the networkx, numpy, and pandas libraries, alongside custom implementations for GGFN arithmetic and Monte Carlo sampling. Runtime measurements and peak memory usage were obtained using Python’s time and tracemalloc modules under single-threaded execution. No GPU acceleration or parallelization was employed.
16
Algorithm 1 Runtime experiment on the FAA network (deterministic ranked solver across an N/8 grid) Require: FAA edge-list CSV with columns source, target, core_c, sigma, height_h; full network size Nfull (FAA: 1226 nodes); size grid K = {⌈i Nfull /8⌉ : i = 1, . . . , 8}; number of timing repeats Rtime ≥ 1. Ensure: For each k ∈ K, record node count Nk , edge count mk , destination tdst , median max for the deterministic ranked solver. runtime tmed k , and peak memory Mk 1: Load the FAA CSV into arrays (s, t, c, σ, h) and map node ids to {1, . . . , N }. 2: for each k ∈ K do 3: Induce subgraph (s(k) , t(k) , c(k) , σ (k) , h(k) ) on nodes {1, . . . , k}. 4: Nk ⇐ k, mk ⇐ length(s(k) ), ssrc ⇐ 1, tdst ⇐ largest node reachable from ssrc in the subgraph. 5: Tk ⇐ [ ] and peak memory Mkmax ⇐ 0. 6: for r = 1 to Rtime do 7: Start wall-clock timer and memory profiler. 8: Run DijkstraRanked on (s(k) , t(k) , c(k) , σ (k) , h(k) ) from ssrc to tdst . 9: Stop timer and memory profiler; 10: let ∆tr be the elapsed time, Mr the peak memory for this repetition. 11: Append ∆tr to Tk and update Mkmax ⇐ max(Mkmax , Mr ). 12: end for max ). 13: Set tmed ⇐ median(Tk ) and store (Nk , mk , tdst , tmed k k , Mk 14: end for nearly doubles the perceived path cost, illustrating how the combination of σ and h controls the tradeoff between cost and perceived reliability. For the full FAA instance, the deterministic α–cut path costs increase from approximately 93 at α = 0.05 to roughly 193 at α = 0.95 (see 5).
6.6
Scenario-Based Robustness Analysis on the FAA Case
Here, we evaluate the robustness of the ranked path xR on the full FAA network under realizations of edge costs consistent with the GGFN model. Using the ex-ante vs. ex-post Monte Carlo simulation 2, independently for every edge (i, j), each scenario draws a level αij ∼ U (0, hij ) and then a crisp cost from the corresponding αij –cut interval using a uniform distribution on that interval. This construction also aligns with the α–cut semantics of the Gaussian membership and treats all positions within each interval as equally plausible conditional on αij . In the following algorithm, the function, HasuikeGen, is called for the full graph. It is a Monte Carlo module for robustness: repeatedly draws α-levels per edge, samples crisp costs from the induced α-cuts, re-solves the crisp SPP to get the scenariooptimal path, and reports deviations of the ranked/core baselines. The optimal cost is the lowest path cost in a given scenario after sampling crisp edge costs (the scenario-wise shortest path), which is the benchmark. The core cost is the cost of the “core” path (shortest path by nominal core weights) evaluated under the edge costs of the sampled scenario. The rank cost is the cost of the “ranked” path (chosen via the risk-aware ranking index) evaluated under the same edge costs of the sampled scenario. It may differ from the optimal and from the core cost if the ranked path is not optimal in that scenario. For each of S = 1000 scenarios, we compute: 1. the realized optimal path x⋆ (scenario-wise shortest path), 2. the realized cost of xR and xc under that scenario, and 3. the percentage deviation Dev(P ) using 4 In an example run for the path from n2 to n1189 with κ = 1.0 over 50 scenarios (for the sake of ease to illustrate the cost differences), xR and xc coincide, so both paths share the same performance indicators. However, depending on the chosen path these may vary
17
Deterministic ranked solver scaling on FAA (N/8 grid) 0.07
0.50
Runtime (s) Peak memory (MB)
0.45 0.40
Peak memory (MB)
Runtime (s)
0.06
0.35
0.05
0.30 0.25
0.04
0.20
0.03 0.02
0.15 0.10 200
400
600 800 Nodes (N)
1000
1200
Figure 4: Runtime and peak memory of the deterministic ranked solver on induced FAA subgraphs (N/8 grid). Median wall-clock time grows roughly linearly with node count, and peak memory stays well below 1 MB even at the full 1,226-node network. such as from n6 to n1125, in which case, Devcore = 4.213, Devrank = 4.629, and reliability premium 0.416. In addition, when we increase the risk weight κ, we should expect differences in the cost and deviation values of the ranked and core paths. For instance, in 10, we provide the outcomes of the first 10 of 50 scenarios where κ = 1.2. Accordingly, 11 summarizes the outcome as that the mean deviation of the ranked path from the scenariospecific optimum is 3.41 %, with a standard deviation of 3.11 %; the maximum observed deviation is approximately 15.17 %. The baseline path remains exactly optimal in 12 % of the scenarios and incurs only moderate losses in the remaining cases. The stability is the fraction (or percentage) of scenarios in which the pre-selected path remains exactly optimal (i.e., where Dev=0). This may change depending on the source and target nodes. Thus, given the current calibration of (cij , σij , hij ), the core or ranked paths are reasonably robust to realizations of fuzzy edge costs in the FAA network. If the Ranked Path has a higher stability score than the Core Path, it means the Ranked Path aligns with the true optimal path more frequently across different realizations of uncertainty. To visualize stability in our example run with κ = 1.2 in which case the risk parameter is slightly higher than the neutral, 6 shows the realized scenario costs for the optimal, core, and ranked paths, while 7 summarizes the corresponding deviation statistics and stability of the baseline path.
Table 10: Scenario-wise costs and deviations (FAA, path from n2 to n1189, the first 10 scenarios for the sake of ease, κ=1.2). Scenario
x⋆ cost
Rank cost
Core cost
Devrank (%)
Devcore (%)
1 2 3 4 5 6 7 8 9 10
179.254 186.025 189.182 191.963 190.029 179.028 183.474 182.984 170.217 184.795
189.247 190.162 196.367 196.272 190.517 181.493 195.152 188.431 170.217 202.951
189.662 198.350 202.800 191.963 190.820 181.626 185.064 190.896 171.653 205.088
5.574 2.224 3.798 2.245 0.257 1.377 6.365 2.977 0.000 9.825
5.806 6.625 7.199 0.000 0.416 1.451 0.867 4.324 0.843 10.981
18
Deterministic -cut path costs on FAA (ranked path) Path cost (lower endpoint)
180 160 140 120 100
0.2
0.4
0.6
0.8
Figure 5: Deterministic α–cut path costs on the FAA ranked route (n2 → n1189). The lowerendpoint cost rises from about 101 at α = 0.05 to about 190 at α = 0.95, illustrating how narrower α–cuts increase the perceived path cost. Table 11: Scenario-based robustness statistics on the FAA instance under the α–cut consistent sampling scheme with S = 50 scenarios and κ = 1.2. The stability column gives the fraction of scenarios in which the given path is exactly optimal (Dev = 0). As the paths differ, they do not line up with the scenario-wise optimum equally often. Path Ranked path xR Core path xc
Mean dev (%)
Std. dev. (%)
Max dev (%)
Stability
3.41 3.36
3.11 3.46
15.17 12.78
0.12 0.24
Regarding height regimes, 12 summarizes the deviations of the scenarios for the ranked and core baselines under the high and low-reliability (height) regimes (50 scenarios, κ = 1.0, seed 42). Under the high regime, the paths coincide and deviations remain modest, whereas under the low regime the ranked path diverges from the core and becomes less stable, reflecting the impact of reduced reliability on alignment with scenario-optimal routes. In more detail, under high-reliability heights (Beta(8, 2)), the ranked and core paths coincide and exhibit modest deviations (mean 3.36%, std 3.46%) with stability 0.24. However, under low-reliability heights (Beta(2, 5)), the ranked path diverges from the core, suffering a larger mean deviation (6.69% vs. 3.36% for core) and lower stability (0.16), while the core path retains its high-regime figures as expected. The reliability premium is −3.33%, indicating that in the low regime the ranked path is on average worse than the core. This highlights that lower heights (less reliable evidence) make the risk-aware baseline less aligned with scenario optima, whereas in the high regime both baselines remain reasonably stable.
Table 12: Scenario deviations under high vs. low height regimes (50 scenarios, κ = 1.0, seed 42). Stability is the fraction of scenarios with Dev = 0; reliability premium is mean(Devcore − Devrank ). Regime
Path
Mean dev (%)
Std. dev. (%)
Stability
Reliability premium (%)
High (Beta(8,2))
Ranked xR Core xc
3.364 3.364
3.457 3.457
0.24 0.24
0.000 —
Low (Beta(2,5))
Ranked xR Core xc
6.693 3.364
5.422 3.457
0.16 0.24
-3.329 —
19
Algorithm 2 Monte Carlo experiment on the full FAA network (ex-ante vs. ex-post) Require: FAA edge-list CSV with columns source, target, core_c, sigma, height_h; full network size Nfull (FAA: 1226 nodes); Monte Carlo parameters nRep = 10, nIters = 1000; number of timing repeats Rtime ≥ 1. Ensure: Record node count N , edge count m, median runtime tmed , peak memory M max , Monte Carlo error statistics (Err, Std), and deterministic α–cut scenario costs on the full network. 1: Load the FAA CSV into arrays (s, t, c, σ, h) and map node ids to {1, . . . , N }. 2: N ⇐ Nfull , m ⇐ length(s), ssrc ⇐ 1, tdst ⇐ N . 3: T ⇐ [ ] and peak memory M max ⇐ 0. 4: for r = 1 to Rtime do 5: Start wall-clock timer and memory profiler. 6: Call HasuikeGen on the full graph: (Err, Std, href , α_scen) ⇐ HasuikeGen s, t, c, σ, N, ssrc , tdst , regime = mixed, Eps = 0.2, Seed = 42, nRep , nIters , mode = reject, h = h, return_alpha = true . 7: Stop timer and memory profiler; 8: let ∆tr be the elapsed time, Mr the peak memory for this repetition. 9: Append ∆tr to T and update M max ⇐ max(M max , Mr ). 10: end for 11: Set tmed ⇐ median(T ) and store (N, m, tmed , M max , Err, Std, α_scen).
Figure 6: Scenario-wise path costs versus α on the FAA instance (κ ∈ {1.0, 1.2}). The ranked and core paths track closely across α, while the scenario-optimal cost is lower when the risk penalty is inactive.
20
Figure 7: Percentage deviation of ranked/core paths from the scenario-optimal cost versus α. Deviations remain small for most α levels, with heavier tails only at higher α (more conservative cuts). From a modeling perspective, these findings highlight two complementary points. First, on a realistic transportation network, the σ–weighted height aggregation and risk–averse ranking indices scale to thousands of nodes without prohibitive computational cost, even when embedded within a Monte Carlo simulation loop. Second, for the particular calibration used here, the risk–averse ranking with κ = 1 does not dramatically alter the chosen route relative to the classical core path but still yields a path that is highly stable under singlevalue fuzzy numerical simulation. Adjusting κ or the height regime (e.g., increasing the prevalence of low-height edges) would be expected to amplify the distinction between xc and xR and can be explored in further empirical work. Overall, the FAA case study demonstrates that the proposed GGFN–SPP framework, together with α–cut–based height aggregation and risk–aware ranking, can be instantiated on large-scale, real-world networks, providing interpretable tradeoffs between nominal cost, information reliability, and fuzziness in a computationally tractable manner.
Computational complexity The ranked solver retains the O((N + m) log N ) cost of classical Dijkstra (with a binary heap) where N is the number of nodes and m is the number of edges, since each relaxation only aggregates the tuple (c, σ, h) and uses standard heap updates. In the case of Monte Carlo validation of ex-ante vs. ex-post performance on the full graph costs O(S(N + m) log N ) for (S) scenarios, because each scenario requires one shortest-path solve. Other fuzzy variants, such as signed-distance or λ-integral-based, often rely on O(N 2 ) dynamic-programming passes dominated by repeated full-graph relaxations. To sum up, the ranked solver matches crisp Dijkstra asymptotically and the heavy cost arises only from the scenario loop used for robustness checks.
7
Conclusion
We introduce a reliability-aware fuzzy shortest path framework in which edge costs are modeled as GGFNs. The framework aggregates uncertainty through α–cut semantics and incorporates reliability directly into arithmetic via a σ–weighted geometric mean for height during addition. Candidate paths are ranked using a mean-risk index that jointly considers nominal cost, dispersion, and information reliability. This approach preserves associativity and becomes risk-neutral in the normal case (h = 1). Our method contrasts with existing fuzzy arithmetic approaches that typically use tnorm-based height aggregation or omit height from arithmetic altogether. To the best of
21
our knowledge, this is the first implementation of a height-aware addition operator for Type– 1 GGFNs in the shortest path setting. The resulting structure enables interpretable tradeoffs and allows for efficient Dijkstra-style computation. The FAA case study demonstrates the practical applicability of the framework on a realworld transportation network with 1226 nodes and 2615 edges. We observed near-linear scaling in runtime and memory with graph size, meaningful inflation in path costs as α increases, and stable scenario-wise deviations under Monte Carlo simulation with α–cut– consistent sampling. In particular, the ranked path exhibits a deviation of less than 0.84% on average and remains exactly optimal in around 69% of cases. From a computational standpoint, the risk-aware Dijkstra algorithm retains the same complexity as the classical version. Other fuzzy approaches often rely on dynamic-programming passes or metaheuristics, whose cost is dominated by repeated full-graph relaxations. In our framework, the additional cost arises only when scenario-based validation is performed, which is intrinsic to any Monte Carlo robustness check.
Future work Generally, edge costs can be modeled with the membership µ(x) = h exp − (|x − c|/σ)β for β > 0 (subnormal, 0 < h < 1). All numerical experiments in this paper fix the Gaussian case β = 2; thus, the shape parameter β is held constant in our analysis. A natural extension is to treat β as a free shape parameter and to study the generalized– Gaussian family more broadly. We plan to: (i) analyze model properties across β and document how path–level addition, height aggregation, and ranking behave beyond β = 2; (ii) quantify the sensitivity of the proposed risk–averse ranking and the reliability premium (percentage deviation) to β across diverse networks and reliability regimes; (iii) develop practical procedures to estimate or elicit β jointly with (c, σ, h) from data or expert input; and (iv) extend the single–value α–cut simulation to generic β while preserving nonnegativity constraints. Future work will focus on operationalizing the shape parameter β beyond 2– formalizing β–dependent structure (e.g., unimodality, log–concavity), estimating β jointly with (c, σ, h) via likelihood and α–cut matching, developing nonnegativity–preserving α–cut simulation for generic β, and evaluating the risk–aware ranking and the ensuing reliability premium on large–scale benchmarks with risk–aligned ex–post comparators. The present study focuses on a single cost-type objective. Future work includes extending the ranking scheme to basic multiobjective settings and to other classical network problems under GGFN costs, such as minimum-cost flows, spanning trees, and facility-location models. We restricted attention to crisp topology with fuzzy edge costs. As future work, we aim to extend the framework to fuzzy edge existence, which would better reflect real networks. In this paper, (c, σ, h) and the risk parameter κ are specified exogenously. A natural direction for future work is to infer these quantities from data or expert elicitation, turning the GGFN–SPP model into a more fully data-driven tool.
References [1] D. Dubois, J. Lang, and H. Prade. Possibilistic logic. In D. M. Gabbay, C. J. Hogger, and J. A. Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming, volume 3, pages 439–513. Oxford University Press, Oxford, 1994. [2] E. Aydın and H. G. Akdemir. Solving generalized trapezoidal fuzzy transportation problems using an arithmetic approach based on information reliability. pages 66–85, 2025. [3] C. Fan. A novel arithmetic operation function utilizing height of interval type-2 fuzzy sets to express risk preference. Ocean Engineering, page 122940, 2025. [4] S. Sen, K. Patra, and S. K. Mondal. Similarity measure of gaussian fuzzy numbers and its application. International Journal of Applied and Computational Mathematics, 7 (3):96, 2021. [5] H. Tahayori, A. Sadeghian, and W. Pedrycz. Induction of shadowed sets based on the gradual grade of fuzziness. IEEE Transactions on Fuzzy Systems, 21(5):937–949, 2013.
22
[6] J.-S. Yao and F.-T. Lin. Fuzzy shortest-path network problems with uncertain edge weights. Journal of Information Science and Engineering, 19(2):329–351, 2003. [7] J. Elizabeth and R. Sujatha. Fuzzy shortest path problem based on level λ-triangular LR fuzzy numbers. Advances in Fuzzy Systems, 2012(1):646248, 2012. [8] Y. S. Kavian, A. Mahani, and H. F. Rashvand. Two-stage uncertainty incorporating in optical core networks. IET Communications, 6(10):1220–1228, 2012. [9] R. Hassanzadeh, I. Mahdavi, N. Mahdavi-Amiri, and A. Tajdin. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths. Mathematical and Computer Modelling, 57(1–2):84–99, 2013. [10] M. Verma and K. K. Shukla. A greedy algorithm for fuzzy shortest path problem using quasi-gaussian fuzzy weights. International Journal of Fuzzy Systems and Applications, 3(2):55–70, 2013. [11] V. Anusuya and R. Kavitha. Roulette ant wheel selection (raws) for genetic algorithm– fuzzy shortest path problem. International Journal of Mathematics and Computer Applications Research, 5(2):1–14, 2015. [12] R. Kumar, S. A. Edalatpanah, S. Jha, S. Gayen, and R. Singh. Shortest path problems using fuzzy weighted arc length. International Journal of Innovative Technology and Exploring Engineering, 8(6):724–731, 2019. [13] S. Dey, S. Malakar, and S. Rajak. Optimization of shortest path problem using dijkstra’s algorithm in imprecise environment. International Journal of Computer Applications Technology and Research, 10(10):216–221, 2021. [14] L. Valdes, A. Ariza, S. M. Allende, A. Triviño, and G. Joya. Search of the shortest path in a communication network with fuzzy cost functions. Symmetry, 13(8):1534, 2021. doi: 10.3390/sym13081534. [15] A. Ebrahimnejad, M. Enayattabar, H. Motameni, and H. Garg. Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem. Complex & Intelligent Systems, 7:1527–1545, 2021. [16] S. Biswal, G. Ghorai, and S. P. Mohanty. α-reliable shortest path problem in uncertain time-dependent networks. International Journal of Applied and Computational Mathematics, 8:164, 2022. [17] F. Abbasi and T. Allahviranloo. Realistic solution of fuzzy critical path problems, case study: the airport’s cargo ground operation systems. Granular Computing, 8:617–632, 2023. [18] H. G. Akdemir, N. Kara, and H. G. Kocken. Minimum cost flow problems in generalized fuzzy environments: Credibilistic CVaR minimization approach. Operational Research and Decisions, 34(3):125–141, 2024. [19] Pratibha and R. Dangwal. Solving generalized fuzzy least cost path problem of supply chain network. Reliability Theory & Applications, 19(4):267–286, 2024. [20] H. G. Akdemir. On generalized picture fuzzy numbers with gaussian membership functions. Journal of Systems Science and Systems Engineering, pages 1–28, 2025. doi: 10.1007/s11518-025-5700-x. [21] S. Chanas and M. Nowakowski. Single value simulation of fuzzy variable. Fuzzy Sets and Systems, 25(1):43–57, 1988. [22] S.-H. Chen. Ranking fuzzy numbers with maximizing set and minimizing set. Fuzzy Sets and Systems, 17(2):113–129, 1985.
23
[23] J. Stoklasa, P. Luukka, and M. Collan. On the relationship between possibilistic and standard moments of fuzzy numbers. Journal of Computational and Applied Mathematics, 411:114276, 2022. [24] T. Hasuike. Robust shortest path problem based on a confidence interval in fuzzy bicriteria decision making. Information Sciences, 221:520–533, 2013. doi: 10.1016/j. ins.2012.09.025. [25] Federal Aviation Administration. Air traffic control system command center, 2010. URL http://www.fly.faa.gov/. [26] Air traffic control network dataset – KONECT. KONECT: The Koblenz Network Collection, 2017. URL http://konect.cc/networks/maayan-faa. [27] Air traffic control network dataset – KONECT. KONECT: The Koblenz Network Collection, 2017. URL http://konect.cc/networks/maayan-faa.
24