On Multi-Objective Minimum Spanning Tree Problem under Uncertain Paradigm

Abstract

Minimum spanning tree problem (MSTP) has allured many researchers and practitioners due to its varied range of applications in real world scenarios. Modelling these applications involves the incorporation of indeterminate phenomena based on their subjective estimations. Such phenomena can be represented rationally using uncertainty theory. Being a more realistic variant of MSTP, in this article, based on the principles of the uncertainty theory, we have studied a multi-objective minimum spanning tree problem (MMSTP) with indeterminate problem parameters. Subsequently, two uncertain programming models of the proposed uncertain multi-objective minimum spanning tree problem (UMMSTP) are developed and their corresponding crisp equivalence models are investigated, and eventually solved using a classical multi-objective solution technique, the epsilon-constraint method. Additionally, two multi-objective evolutionary algorithms (MOEAs), non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA) are also employed as solution methodologies. With the help of the proposed UMMSTP models, the practical problem of optimizing the distribution of petroleum products was solved, consisting in the search for symmetry (balance) between the transportation cost and the transportation time. Thereafter, the performance of the MOEAs is analyzed on five randomly developed instances of the proposed problem.

1. Introduction

The quest for studying network optimization problems has been emphasized for long time. Subsequently, being a crucial and significant network problem, the minimum spanning tree problem (MSTP) has captivated many researchers. The applications of MSTP are varied and include brain networks [1], cluster analysis [2], and image segmentation [3]. Borüvka [4] first studied classical minimum spanning tree (MST) with crisp parameters. Since then, different researchers proposed various effectual algorithms, including Jarník [5], Kruskal [6] and Prim [7] while revisiting the problem. Furthermore, there have been various developments on the solution methodologies of the multi-objective MSTP including the exact algorithms [8,9,10] and evolutionary [11,12,13].

The MMSTP is an upfront generalization of MSTP, where multiple criteria are associated with each edge. Many classical applications [14,15] allow the inclusion of multiple criteria while exploring a minimum spanning tree which essentially requires the modelling of MMSTP. In this context, we provide an example of modelling MMSTP. In this example, we consider a transportation company, which is eager to begin its bus facilities to link the major cities of a country. Accordingly, the management of the company recognized possible intercity bus routes, which will connect the cities. Furthermore, in the course of a journey, the company offers an attractive payback of $50 if the estimated travelling time between the source and destination cities of the passenger availing the bus service of their company is delayed or interrupted by 45 min. In the following quarter, the management should plan a bus schedule so that the cost of availing bus services among the cities and the estimated travelling time between the cities is minimized. For such networks, it is usually observed that there prevails conflicting nature in the travelling cost and the expected travelling time. Moreover, for this problem, the bus service network can be realized by a connected graph, where a city implies a vertex and an intercity bus route is denoted by an edge. If an edge of such a graph connecting two cities, X and Y is associated with two edge weights, namely, cost of availing intercity bus service and the estimated travel time then the problem can be considered as MMSTP, where the cost of providing intercity bus services and the estimated travel time between the cities can be considered as two different objective functions of the corresponding MMSTP. Here, the expense of providing bus service and estimated travel time between the cities depend on many indeterminate factors such as fuel price, labor charge, overhaul and maintenance costs, slower bus speed and increased vehicular queuing due to traffic congestion of the buses, which essentially fluctuate with time. Therefore, usually, the decision makers (management of the company) become indeterminate while estimating the travelling costs for availing intercity bus facilities and the estimated travel time.

The above mentioned example implies that studying MMSTP under indeterminate environment is significant. Therefore, a proper representation of the uncertain parameters is necessary while building any real-world problem under an uncertain paradigm. Usually, the existence of sufficient historical data for any problem parameter motivates us to possibly estimate its distribution function and the analysis of the problem can be performed by following the fundamental principle of probability theory. In this context, for the first time, Ishii et al. [16] modeled an MSTP with edges having random weights whose probability distributions are not known. Frieze [17] determined an MST for a complete graph, where the edge lengths are represented as a nonnegative independent stochastic variable, which is identically distributed. Ishii and Matsutomi [18] designed an algorithm with polynomial execution time, in the extended work of Ishii et al. [16], where the parameters of probability distributions are not known in advance to solve the problem. Later, Dhamdhere et al. [19] discussed a two-stage stochastic MSTP and accordingly presented an approximation algorithm. Under fuzzy paradigm, Orazbayev et al. [20] studied the production plan optimization problem under fuzzy constraints and solved the problem using a unique heuristic method, which is based on the expert information of the decision maker. Later, Zhumadillayeva et al. [21] developed optimization models to solve the production problem and waste management consumption problem under the fuzzy environment.

Although it is unanimously considered that, a large number of samples are looked-for while building stochastic models, but, in many cases, estimation of probability distribution becomes infeasible due to the unavailability of sufficient samples. Under such circumstances, there are no other choices but to depend on the domain experts for estimating the belief degrees of the occurrence of events. Consequently, Liu [22] investigated the uncertainty theory to address the belief degree of an event.

Uncertainty theory has been progressively developed as an important area of mathematics, which can express and model human uncertainty. In this aspect, to tackle optimization problems with uncertain parameters, the concept of uncertain programming is presented by Liu [23]. Successively, a project-scheduling problem is first formulated by Liu [24], where the duration times are expressed as uncertain variables. Thereupon, Gao [25] conceptually presented the shortest path with a chance (confidence) level α and the most measured shortest path along with their corresponding uncertainty distributions. Consequently, Zhang and Peng [26] extended the Chinese postman problem under uncertain paradigm and presented three uncertain programming models of the problem. Subsequently, a project-scheduling problem under an uncertain environment is proposed by Zhang and Chen [27], where the elapsed time for the activities is represented as uncertain variables. Moreover, Zhang et al. [28] proposed sum-type and minimax-type uncertain programming models for α-MST, and solve the crisp equivalents of the models using classical optimization methods. Consequently, Zhang et al. [29] proposed a chance-constrained model to solve an inverse spanning tree problem with indeterminate problem parameters. Furthermore, Zhou et al. [30] defined the path optimality conditions of uncertain expected MST and uncertain α-MST. Moreover, for an uncertain network, the authors proposed an uncertain most MST and established its relation with uncertain α-MST. In the following year, Zhou et al. [31] proposed an ideal uncertain α-MST by using the concept of uncertain α-MST. Further, the authors also proposed the definition of uncertain distribution of MST based on the concept of ideal uncertain α-MST. Moreover, different other uncertain optimization problems including quadratic MST [32], uncertain degree constrained MST [33], uncertain random MST [34], uncertain random degree constrained MST [35] and uncertain routing problem on multi-depot emergency facilities [36] are studied as an application of uncertain programming.

The MMSTP is an important variant of the classical MSTP, which can address many real world problems, where the state of indeterminacy is a vital concern as in the case of above mentioned example. However, considering the existing studies of the MST in uncertain environment, to the best of our knowledge, a study on UMMSTP in indeterminate framework based on uncertainty theory is yet to be investigated. Accordingly, in this article, we have formulated a multi-objective minimum spanning tree problem following the principles of uncertainty theory. Consequently, in our study, the following contributions are emphasized.

• A multi-objective minimum spanning tree problem with indeterminate parameters based on uncertainty theory is studied.
• The expected value model (EVM) and chance-constrained model (CCM) are formulated for the proposed UMMSTP.
• The deterministic equivalent models of the corresponding EVM and CCM of UMMSTP are proposed and solved using the epsilon (ε)-constraint method [37]. Furthermore, two MOEAs: NSGAII) [38] and DENSEA [39] are also used as solution methodologies for the proposed problem.

The remaining portion of the article is structured as follows. Some rudimentary notions relevant to our research are reviewed in Section 2. In Section 3, we illustrate the modelling of the UMMSTP and formulate the related EVM and CCM. Subsequently, we investigate the crisp transformations of the respective models of UMSTPP in Section 4. The solution procedures employ for the deterministic models of the UMMSTP are conferred in Section 5. The proposed UMMSTP is illustrated numerically with an example in Section 6. In Section 7, for the proposed problem, we provide the necessary results and their corresponding discussions. The culmination of the study is reported in Section 8. To end with, we summarize all the abbreviations related to this study in Appendix A.

2. Preliminaries

The rudimentary notions and important results of uncertainty theory, which constitute the foundation of our study, are presented in this section.

Let $\mathcal{L}$ be a $\sigma$-algebra over a non-empty set $\Gamma$. An element $\Lambda \in$ $\mathcal{L}$ is assigned a numeric value $\mathcal{M}\left\{\Lambda \right\}$ to represent the chance of occurrence of the uncertain event $\Lambda$, where $\mathcal{M}:\mathcal{L}\mapsto \left[0, 1\right]$ represents a set function. Subsequently, $\mathcal{M}$ is known as uncertain measure if the normality, duality, and countable subadditivity axioms [22] hold for $\mathcal{M}$. Here, the triplet $\left(\Gamma ,\mathcal{L},\mathcal{M}\right)$ represents the uncertainty space. Moreover, Liu [40] defined the product uncertain measure and put forward the product measure axiom. Let $\left({\Gamma }_r,{\mathcal{L}}_r,{\mathcal{M}}_r\right)$ be the uncertainty spaces and there exists an arbitrary event ${\Lambda }_r$ to each ${\mathcal{L}}_r$, $r=1,2,\dots ,$ then $\mathcal{M}$ is regarded as product uncertain measure if

$$\mathcal{M}\left\{{\displaystyle \prod }_{p=1}^{\infty }{\Lambda }_p\right\}=\underset{p=1}{\overset{\infty }{{\displaystyle \bigwedge }}}{\mathcal{M}}_p\left\{{\Lambda }_p\right\}.$$

(1)

Definition 1.

(Liu [22]). A measurable function from $\mathcal{S}$ to $ℝ$ defines an uncertain variable $\xi$, where $\mathcal{S}$=$\left(\Gamma ,\mathcal{L},\mathcal{M}\right)$ is an uncertainty space. In other words, the set

$$\left\{\xi \in \mathcal{B}\right\}=\left\{\lambda \in \Gamma |\xi \left(\lambda \right)\in \mathcal{B}\right\}$$

(2)

is an event $\forall \mathcal{B}\in ℝ$, where $\mathcal{B}$ is the Borel set.

Definition 2.

(Liu [24]). Suppose ${\xi }_1, {\xi }_2,\dots ,{\xi }_n$ are the uncertain variables defined on the uncertainty space $\mathcal{S}$=$\left(\Gamma ,\mathcal{L},\mathcal{M}\right)$. Then the uncertain variable $\xi =f\left({\xi }_1, {\xi }_2,\dots ,{\xi }_n\right)$ is denoted as

$$\xi \left(\lambda \right)=f\left({\xi }_1\left(\lambda \right), {\xi }_2\left(\lambda \right),\dots ,{\xi }_n\left(\lambda \right)\right),\forall \lambda \in \Gamma ,$$

(3)

where $f:{ℝ}^n\mapsto ℝ$ is a measurable function.

Definition 3.

(Liu [22]). For any uncertain variable $\xi$ with $\mathsf{\Phi }:ℝ\to \left[0, 1\right]$ as the corresponding uncertainty distribution satisfies Equation (4) as expressed below.

$$\mathsf{\Phi }\left(x\right)=\mathcal{M}\left\{\mathsf{\xi }\le x\right\}, \forall x\in ℝ$$

(4)

Definition 4.

(Liu [40]). If ${\xi }_1$, ${\xi }_2$, $\dots$, ${\xi }_n$ are the independent uncertain variables then for any Borel sets ${\mathcal{B}}_1,{\mathcal{B}}_2,\dots ,{\mathcal{B}}_n$ $\in ℝ$

$$\mathcal{M}\left\{{\displaystyle \bigcap }_{p=1}^n\left({\xi }_p\in {\mathcal{B}}_p\right)\right\}={{\displaystyle \bigwedge }}_{p=1}^n\mathcal{M}\left\{{\xi }_p\in {\mathcal{B}}_p\right\}.$$

(5)

Definition 5.

(Liu [22]). The uncertainty distribution of an uncertain variable $\xi$ represented in Equation (6)

$$\mathsf{\Phi }\left(x\right)=\left\{\begin{array}{cc}0;& if x<l\\ \frac{x-l}{2\left(m-l\right)};& if l\le x<m\\ \frac{x+n-2m}{2\left(n-m\right)};& if m\le x<n\\ 1;& if x\ge n\end{array}\right.$$

(6)

is known as zigzag uncertain variable and denoted by $\mathcal{Z}\left(l,m,n\right)$ such that $l<m<n$ and $l,m,n\in \Re .$

Example 1.

Let us consider a zigzag uncertain variable $\mathcal{Z}\left(10,12,17\right)$, then its corresponding uncertainty distribution is graphically depicted in Figure 1.

Definition 6.

(Liu [24]). A continuous and strictly increasing uncertainty distribution function $\mathsf{\Phi }\left(x\right)$ is regular with respect to $x$ such that

$$\begin{array}{c}lim\\ x\to -\infty \end{array}\mathsf{\Phi }\left(x\right)=0,\begin{array}{c}lim\\ x\to +\infty \end{array}\mathsf{\Phi }\left(x\right)=1.$$

(7)

a function $f\left(x_1,x_2,\dots ,x_r\right)$ satisfying the conditions, (i) $f\left(x_1,x_2,\dots ,x_r\right)\le f\left(y_1,y_2,\dots ,y_r\right),$ when $x_i\le y_i$ and (ii) $f\left(x_1,x_2,\dots ,x_r\right)<f\left(y_1,y_2,\dots ,y_r\right),$ when $x_i<y_i$, is a strictly increasing function, where $i=1,2,\dots ,r$.

Accordingly, following Definition 6, the inverse uncertainty distribution proposed by Liu [24] is defined as follows. The inverse uncertainty distribution of an uncertain variable $\xi$ with regular uncertainty distribution $\mathsf{\Phi }$ is denoted as ${\mathsf{\Phi }}^{-1}$. Later on, considering the uncertain variables with strict monotone functions, Liu [24] put forward the following operational law by extending the concept of ${\mathsf{\Phi }}^{-1}$.

Theorem 1.

(Liu [24]). Let ${\xi }_1,{\xi }_2,\dots ,{\xi }_r$ be the independent uncertain variables with regular uncertainty distributions ${\Phi }_1,{\Phi }_2,\dots ,{\Phi }_r$, respectively. If $\xi =f\left({\xi }_1,{\xi }_2,\dots ,{\xi }_r\right)$ is a continuous and strictly increasing function, then $\xi$ is an uncertain variable with inverse uncertainty distribution

$${\mathsf{\Phi }}^{-1}\left(\alpha \right)=f\left({\mathsf{\Phi }}_1^{-1}\left(\alpha \right),{\mathsf{\Phi }}_2^{-1}\left(\alpha \right),\dots ,{\mathsf{\Phi }}_r^{-1}\left(\alpha \right)\right).$$

(8)

Example 2.

Let $\xi$ = $\mathcal{Z}\left(l,m,n\right)$ is a zigzag uncertain variable with regular uncertainty distribution $\mathsf{\Phi }$. Then, the inverse uncertainty distribution of $\xi$ is represented as below.

$${\mathsf{\Phi }}^{-1}\left(\alpha \right)=\left\{\begin{array}{cc}\left(1-2\alpha \right)l+2\alpha m& ;if \alpha <0.5\\ \left(2-2\alpha \right)m+\left(2\alpha -1\right)n& ;if \alpha \ge 0.5.\end{array}\right.$$

(9)

Definition 7.

(Liu [22]). The expected value of an uncertain variable $\xi$ is defined as

$$E\left[\mathsf{\xi }\right]={{\displaystyle \int }}_0^{+\infty }\mathcal{M}\left\{\mathsf{\xi }\ge x\right\}\mathrm{d}x-{{\displaystyle \int }}_{-\infty }^0\mathcal{M}\left\{\mathsf{\xi }\le x\right\}\mathrm{d}x,$$

(10)

if at least one of the two integrals is finite.

Furthermore, as useful information, Liu [24] considered the inverse uncertainty distribution of an uncertain variable $\xi$ and redefine the expected value of $\xi$ as

$$E\left[\xi \right]={{\displaystyle \int }}_0^1{\mathsf{\Phi }}^{-1}\left(\mathsf{\alpha }\right)\mathrm{d}\alpha .$$

(11)

Example 3.

The expected value for a zigzag uncertain variable $\mathcal{Z}\left(l,m,n\right)$ is calculated as

$$E\left[\xi \right]=\frac{l+2m+n}{4}.$$

(12)

Theorem 2.

(Liu and Ha [41]). Let ${\Phi }_1$, ${\Phi }_2$, $\dots$, ${\Phi }_r$ are respectively the regular uncertainty distributions of the independent uncertain variables ${\xi }_1$, ${\xi }_2$, $\dots$, ${\xi }_r$. If $\xi =f\left({\xi }_1, {\xi }_2,\dots , {\xi }_r\right)$ is strictly increasing with respect to ${\xi }_1$, ${\xi }_2$, $\dots$, ${\xi }_r$ then

$$E\left[\xi \right]={{\displaystyle \int }}_0^{1}f\left({\mathsf{\Phi }}_1^{-1}\left(\alpha \right), {\mathsf{\Phi }}_2^{-1}\left(\alpha \right),\dots ,{\mathsf{\Phi }}_r^{-1}\left(\alpha \right)\right)\mathrm{d}\alpha$$

(13)

is the expected value of $\xi =f\left({\xi }_1, {\xi }_2,\dots , {\xi }_r\right)$.

Moreover, Liu [24] investigated the property of expected value operator for any independent uncertain variables ${\xi }_1$ and ${\xi }_2$ with finite expected values such that

$$E\left[a{\xi }_1+b{\xi }_2\right]=aE\left[{\xi }_1\right]+bE\left[{\xi }_2\right],$$

(14)

where $a$ and $b$ are any real numbers.

3. Problem Description

This section emphasizes on the formulation of the proposed UMMSTP for a graph with uncertain parameters.

Let $G=\left(V,E\right)$ be a weighted connected undirected graph (WCUG), with $n=\left|V\right|$ and $m=\left|E\right|$, where $V=\left\{v_1,v_2,\dots ,v_n\right\}$ and $E$ are correspondingly the finite sets of vertices and edges of $G$, respectively. Each undirected edge $e_{ij}\in E$ connects a pair of vertices $v_i$ and $v_j$, and is related to two uncertain weights, namely uncertain cost and uncertain time, which are respectively represented as ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ hereafter. In a realistic scenario, a vertex of $G$ may be represented by a city, whereas an edge establishing a link in a pair of cities may represents the travel cost and travel time between two cities. Here, the objective may be to connect all the cities with minimum possible overall cost and time. It is usually observed that in a particular context, some kind of symmetry exists between ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ while travelling between the cities. Moreover, the travel cost and travel time may contain indeterminacy due to a number of factors such as the price of fuel, levied toll, vehicle overhaul costs, and traffic congestion time, varying from time to time. Hence, keeping in views all these factors, in this study, under the paradigm of uncertainty theory [22] we have proposed an uncertain multi-objective minimum spanning tree problem (UMMSTP) to deal with the associated uncertain parameters of the UMMSTP in a legitimate way. Accordingly, the proposed UMMSTP is formulated in (15).

$$\left\{\begin{array}{c}Min Z_1={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{c_{ij}}{x}_{ij}\\ Min Z_2={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{t_{ij}}{x}_{ij}\\ subject to \\ {{\displaystyle \sum }}_{i=1}^m{{\displaystyle \sum }}_{j=1,i\ne j}^m{x}_{ij}=\left|V\right|-1\\ {{\displaystyle \sum }}_{i,j\in E_{\kappa },i\ne j}{x}_{ij}\le \left|\kappa \right|-1, \left|\kappa \right|\ge 3\\ x_{ij}\in \left\{0,1\right\}, \forall e_{ij}\in E,\end{array}\right.$$

(15)

where ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ are respectively the uncertain travel cost and the uncertain travel time from $v_i$ to $v_j$ using $e_{ij}$, $E_{\kappa }$ is a set of edges in the subgraph of $G$ induced by the vertex set $\kappa$, i.e., $E_{\kappa }$ is the subset of edges in $E$ having both their endpoints in $\kappa$. In the Model (15), the first constraint is the cardinality constraint, which determines that exactly $\left|V\right|-1$ edges are selected. While the second constraint is the packing constraint, which ensures that there exists no cycle among the selected edges. Here, every $x_{ij}$ either accepts 0 or 1. If $x_{ij}=1$, then the corresponding edge $e_{ij}$ is selected for the formation of a MST. Whereas, if $x_{ij}=0$, then $e_{ij}$ is not included in the MST. Since Model (15) is an uncertain programming problem, we formulate the corresponding EVM and CCM of UMMSTP in the subsequent subsections.

3.1. Expected Value Model of the Proposed Problem

Expected value model (EVM) introduced by Liu and Liu [42] is regarded as a coherent and apprehensible method for designing mathematical problems with uncertain parameters. Larger the expected value, the larger will be the uncertain variable. For the UMMSTP, if the decision maker wishes to optimize the problem in the sense of the expected value then the corresponding mathematical model of UMMSTP is shown below.

$$\left\{\begin{array}{c}Min E\left[Z_1\right]=E\left[{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{c_{ij}}{x}_{ij}\right]\\ Min E\left[Z_2\right]=E\left[{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{t_{ij}}{x}_{ij}\right]\\ subject to\\ constraints of \left(15\right).\end{array}\right.$$

(16)

In Model (16), the objective functions are represented as expected values of the overall travel cost and total travel time between the cities. These objective functions are essentially minimized subject to the constraints of (15).

3.2. Chance-Constrained Model of the Proposed Problem

An alternate approach to optimize uncertain programming problem is the chance-constrained model (CCM) [43]. The central idea of CCM is that the objective function(s) are minimized or maximized with respect to a deterministic target value(s) at a preordained confidence level(s) under the chance constraints such that the optimized value(s) of the objective function(s) does not exceed the corresponding target value(s). The CCM allows the constraints to be violated. However, at certain confidence levels, it ensures the feasibility of the constraints. If the decision maker prefers to optimize the UMMSTP under the constraints, then the corresponding CCM of UMMSTP can be formulated as below.

$$\left\{\begin{array}{c}Min {\overline{Z}}_1\\ Min {\overline{Z}}_2\\ subject to\\ \mathcal{M}\left\{{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{c_{ij}}{x}_{ij}\le {\overline{Z}}_1\right\}\ge {\alpha }_1\\ \mathcal{M}\left\{{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\xi }_{t_{ij}}{x}_{ij}\le {\overline{Z}}_2\right\}\ge {\alpha }_2\\ constraints of \left(15\right).\end{array}\right.$$

(17)

In Model (17), the target values for the first two constraints are respectively represented as ${\overline{Z}}_1$ and ${\overline{Z}}_2$. ${\alpha }_1$ and ${\alpha }_2$ are the predetermined confidence levels for the first and second constraints, respectively. Furthermore, as far as the determination of the MST for $G$ is concerned, the first constraint specifies the total incurred ${\alpha }_1$-cost while traversing between the cities at the chance level ${\alpha }_1$, and the second constraint characterizes the overall ${\alpha }_2$-travel time spent while traversing between the cities with respect to the chance level ${\alpha }_2$.

4. Deterministic Transformation of the Models

In this section, we present the deterministic models corresponding to the EVM and CCM of the proposed UMMSTP.

Theorem 3.

Let${\xi }_{c_{ij}}$and${\xi }_{t_{ij}}$are the independent uncertain variables with regular uncertainty distributions${\Phi }_{{\xi }_{c_{ij}}}$and${\Phi }_{{\xi }_{t_{ij}}}$respectively. Then the deterministic transformation of Model (16) is presented as

$$\left\{\begin{array}{c}Min E\left[Z_1\right]=E\left[{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{{\displaystyle \int }}_0^1{\mathsf{\Phi }}_{{\xi }_{c_{ij}}}^{-1}\left({\mathsf{\alpha }}_1\right){\mathrm{d}\mathsf{\alpha }}_1{x}_{ij}\right]\\ Min E\left[Z_2\right]=E\left[{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{{\displaystyle \int }}_0^1{\mathsf{\Phi }}_{{\xi }_{t_{ij}}}^{-1}\left({\mathsf{\alpha }}_2\right){\mathrm{d}\mathsf{\alpha }}_2{x}_{ij}\right]\\ subject to\\ constraints of \left(15\right).\end{array}\right.$$

(18)

Proof. 

It is implied from the property of linearity of the expected value operator of an uncertain variable that

$$\left\{\begin{array}{c}Min E\left[Z_1\right]={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^{n}E\left[{\xi }_{c_{ij}}\right]x_{ij} \\ Min E\left[Z_2\right]={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^{n}E\left[{\xi }_{t_{ij}}\right]x_{ij}\\ subject to\\ constraints of \left(15\right).\end{array}\right.$$

(19)

Moreover, following Equations (11) and (14), Model (18) follows Model (19). □

Corollary 1.

Assuming ${\xi }_{c_{ij}}=\mathcal{Z}\left(p_{c_{ij}},q_{c_{ij}},r_{c_{ij}}\right)$ and ${\xi }_{t_{ij}}=\mathcal{Z}\left(p_{t_{ij}},q_{t_{ij}},r_{t_{ij}}\right)$ as the independent zigzag uncertain variables such that $p_{c_{ij}}<q_{c_{ij}}<r_{c_{ij}}$, $p_{t_{ij}}<q_{t_{ij}}<r_{t_{ij}}$ and $p_{c_{ij}},q_{c_{ij}},r_{c_{ij}},p_{t_{ij}},q_{t_{ij}},r_{t_{ij}}\in \Re$. Then Model (18) is equivalent to

$$\left\{\begin{array}{c}Min E\left[Z_1\right]={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\vartheta }_{c_{ij}}{x}_{ij}\\ Min E\left[Z_2\right]={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\vartheta }_{t_{ij}}{x}_{ij}\\ subject to\\ constraints of \left(15\right),\end{array}\right.$$

(20)

where ${\vartheta }_{c_{ij}}$=$\frac{p_{c_{ij}}+2q_{c_{ij}}+r_{c_{ij}}}{4}$ and ${\vartheta }_{t_{ij}}$=$\frac{p_{t_{ij}}+2q_{t_{ij}}+r_{t_{ij}}}{4}$.

Theorem 4.

Suppose, the regular uncertainty distributions of the uncertain variables${\xi }_{c_{ij}}$and${\xi }_{t_{ij}}$are respectively${\Phi }_{{\xi }_{c_{ij}}}$and${\Phi }_{{\xi }_{t_{ij}}}$. Then the deterministic transformation of the CCM reported in Equation (17) is presented as

$$\left\{\begin{array}{c}Min {\overline{Z}}_1={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\mathsf{\Phi }}_{{\xi }_{c_{ij}}}^{-1}\left({\mathsf{\alpha }}_1\right)x_{ij} \\ Min {\overline{Z}}_2={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\mathsf{\Phi }}_{{\xi }_{t_{ij}}}^{-1}\left({\mathsf{\alpha }}_2\right)x_{ij}\\ subject to\\ constraints of \left(15\right).\end{array}\right.$$

(21)

Proof. 

Since ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ are the independent uncertain variables in the Model (14) therefore, the constraints $\mathcal{M}\left\{{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1,j\ne i}^n{\xi }_{c_{ij}}{x}_{ij}\le {\overline{Z}}_1\right\}\ge {\alpha }_1$ and $\mathcal{M}\left\{{\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1,j\ne i}^n{\xi }_{t_{ij}}{x}_{ij}\le {\overline{Z}}_2\right\}\ge {\alpha }_2$ at the respective chance levels ${\alpha }_1$ and ${\alpha }_2$ can be correspondingly expressed as $\mathcal{M}\left\{Z_1\le {\overline{Z}}_1\right\}\ge {\alpha }_1$ and $\mathcal{M}\left\{Z_2\le {\overline{Z}}_2\right\}\ge {\alpha }_2$. Subsequently, following Theorem 1, $\mathcal{M}\left\{Z_1\le {\overline{Z}}_1\right\}\ge {\alpha }_1$ and $\mathcal{M}\left\{Z_2\le {\overline{Z}}_2\right\}\ge {\alpha }_2$ are respectively reconstructed as ${\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1,j\ne i}^n{\mathsf{\Phi }}_{{\xi }_{c_{ij}}}^{-1}\left({\mathsf{\alpha }}_1\right)x_{ij}\le {\overline{Z}}_1$ and ${\displaystyle \sum }_{i=1}^n{\displaystyle \sum }_{j=1,j\ne i}^n{\mathsf{\Phi }}_{{\xi }_{t_{ij}}}^{-1}\left({\mathsf{\alpha }}_2\right)x_{ij}\le {\overline{Z}}_2$. Consequently, Model (21) becomes the crisp equivalent of the Model (17). □

Corollary 2.

Suppose ${\xi }_{c_{ij}}=\mathcal{Z}\left(p_{c_{ij}},q_{c_{ij}},r_{c_{ij}}\right)$ and ${\xi }_{t_{ij}}=\mathcal{Z}\left(p_{t_{ij}},q_{t_{ij}},r_{t_{ij}}\right)$ are the independent zigzag uncertain variables such that $p_{c_{ij}}<q_{c_{ij}}<r_{c_{ij}}$, $p_{t_{ij}}<q_{t_{ij}}<r_{t_{ij}}$ and $p_{c_{ij}},q_{c_{ij}},r_{c_{ij}},p_{t_{ij}},q_{t_{ij}},r_{t_{ij}}\in \Re$. Then Model (21) can be equivalently formulated in Model (22).

$$\left\{\begin{array}{c}Min {\overline{Z}}_1={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\varkappa }_{c_{ij}}{x}_{ij}\\ Min {\overline{Z}}_2={{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1,j\ne i}^n{\varkappa }_{t_{ij}}{x}_{ij}\\ subject to\\ constraints of \left(15\right).\end{array}\right.$$

(22)

Here,${\varkappa }_{c_{ij}}$and${\varkappa }_{t_{ij}}$are expressed as below.

$${\varkappa }_{c_{ij}}=\left\{\begin{array}{cc}\left(1-2{\alpha }_1\right)p_{c_{ij}}+2{\alpha }_1{q}_{c_{ij}}& ;if {\alpha }_1<0.5\\ \left(2-2{\alpha }_1\right)q_{c_{ij}}+\left(2{\alpha }_1-1\right)r_{c_{ij}}& ;if {\alpha }_1\ge 0.5\end{array}\right.$$

and

$${\varkappa }_{t_{ij}}=\left\{\begin{array}{cc}\left(1-2{\alpha }_2\right)p_{t_{ij}}+2{\alpha }_2{q}_{t_{ij}}& ;if {\alpha }_2<0.5\\ \left(2-2{\alpha }_2\right)q_{t_{ij}}+\left(2{\alpha }_2-1\right)r_{t_{ij}}& ;if {\alpha }_2\ge 0.5.\end{array}\right.$$

5. Solution Methodologies

The methodologies employed to solve the deterministic equivalent models of UMMSTP are presented in this section. These solution procedures are broadly categorized as: (i) classical technique and (ii) multi-objective evolutionary algorithms (MOEAs). As far as our proposed problem is concerned, we have used epsilon ($ϵ$)-constraint method as the classical solution technique of multi-objective optimization problem (MOOP). Moreover, among the MOEAs, we have considered non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA) to solve the proposed model.

5.1. Epsilon-Constraint Method

Epsilon ($ϵ$)- constraint [37] method is an approach to solve a MOOP. In this method, a MOOP under consideration is converted to its equivalent compromise single objective optimization problem (CSOOP). Here, one objective function is arbitrarily chosen and essentially optimized subject to the set of constraints. This constraint set includes rest of the objective functions, each of which is constrained to a user specified value. $ϵ$- constraint is regarded as one of the important solution methodologies of MOOP due to its ability to explore solutions in the non-convex region of the objective space of the problem. The crisp transformations of Model (18) and Model (21) of UMSPP are converted to their equivalent CSOOP and respectively presented in Models (23) and (24).

$$\left\{\begin{array}{c}Min E{\left[Z\right]}^{Comp}=E\left[Z_1\right]\\ subject to\\ E\left[Z_2\right]\le {ϵ}_{E\left[Z_2\right]}\\ constraints of \left(15\right),\end{array}\right.$$

(23)

where ${ϵ}_{E\left[Z_2\right]}$ is not necessarily a value close to zero and represents an upper bound of $E\left[Z_2\right]$, obtained when $E\left[Z_2\right]$ in Model (18) is solved individually as a maximization single objective problem.

$$\left\{\begin{array}{c}Min {\overline{Z}}^{Comp}={\overline{Z}}_1\\ subject to\\ {\overline{Z}}_2\le {ϵ}_{{\overline{Z}}_2}\\ constraints of \left(15\right),\end{array}\right.$$

(24)

where ${ϵ}_{{\overline{Z}}_2}$ represents an upper bound of ${\overline{Z}}_2$, obtained when ${\overline{Z}}_2$ in Model (21) is solved individually as a maximization single objective problem.

5.2. Multi-Objective Evolutionary Algorithm

A MOOP comprises of multiple conflicting objectives, and therefore it is hard and cumbersome to find an optimum solution based on one objective, especially when the rest of the objectives are also important. The confliction nature of the objective functions implies two important characteristics of a MOOP: convergence and diversity. In this regard, an MOEA attempts to achieve both the convergence and diversity among the generated solutions while solving a MOOP. Considering the stochastic nature of the MOEAs, at times, exploring Pareto optimal solutions of a MOOP may not be guaranteed by a MOEA. Nevertheless, the MOEAs have essential operators to continually achieve the convergence and diversity of the non-dominated solutions in a similar way as compared to the way most of the natural and artificial evolving systems operate while improving their solutions. The striking difference between the MOEAs and the classical multi-objective solution techniques is that, in a single simulation run, the population based approach of MOEAs can yield several compromise solutions of MOOPs in contrast to classical techniques which can only produce a sole compromise solution.

In the subsequent subsections, we present two MOEAs, NSGAII and DENSEA, which are employed to yield multiple compromised solutions of the proposed problem.

5.2.1. Non-Dominated Sorting Genetic Algorithm II

Proposed by Deb et al. [38], NSGAII is one of the most popular MOEAs, which incorporates elitism by preserving superior candidate solutions in the subsequent population. The algorithm instigates with $N$ randomly generated solutions in a population $P_0$. In a particular generation $t$, the individuals in a parent population $P_t$ use the genetic operators ($selection$, $crossover$ and $mutation$ operators) to yield equal number of offsprings. These offsprings constitute the offspring population $C_t$. Consequently, the parent population is combined with the offspring population to produce a population $S_t$ of size $2N$. Among these $2N$ solutions of $S_t$, the best $N$ solutions are selected by crowded tournament selection operator for the subsequent generation of NSGAII. If $p$ and $q$ are the two solutions then the crowded tournament selection operator selects $p$ over $q$, if $p_{rank}<q_{rank}$, where $p_{rank}$ and $q_{rank}$ are the ranks of $p$ and $q$ respectively. Furthermore, if in case $p_{rank}$ and $q_{rank}$ are the same then the crowding distances $p_{distance}$ and $q_{distance}$ of $p$ and $q$ are computed respectively and if $p_{distance}$ is greater than $q_{distance}$ then $p$ is preferred over $q$. The ranking and the crowding distance of the solutions are discussed as below.

Ranking of solutions: Considering population $S_t$, a rank ($p_{rank})$ is allocated to each of its solution $p$. Accordingly, based on the rank of the solutions, these solutions are categorized into different non-dominated fronts $N_1$, $N_2,\dots ,N_l$. The solutions which exist in a front $N_k$, $k\in \left\{1,2,\dots ,l\right\}$ are non-dominated to each other and assigned with the same rank $k$. Here, it is to be mentioned that for any solution $p$ in $S_t$, the rank of $p$ and its corresponding front number is the same. Any solution with a lower value of $k$ becomes superior and is always preferred. In order to create a population $P_{t+1}$ for ${\left(t+1\right)}^{th}$ generation, firstly all the non-dominated solutions representing the front $N_1$ are considered. If the number of such non-dominated solutions of $N_1$ is equal to the original population size $N$ then the remaining solutions with higher ranks present in $S_t$ are ignored. Otherwise, the solutions of the next higher order fronts are considered for the formation of $P_t$. This process continues until all the solutions of a particular front $N_k$ cannot be entirely contained in $P_{t+1}$.

Crowding distance for solutions: The crowding distance measure as originated by Deb et al. [38] is employed while estimating solution density in the neighboring region of a particular solution. Each non-dominated solution $p$ of the front $N_k$ are assigned with a crowding distance value ($p_{distance}$) if the solutions of $N_k$ are not entirely included in $P_{t+1}$. The crowding distance of a particular solution measures the neighboring search space of that solution, where there is no occurrence of any other solution. A solution from a less crowded area in the search space has a greater crowding distance compared to the one residing in a more crowded area. In this way, the solutions having larger crowding distance are always preferred and are eventually chosen from $N_k$ to fill the leftover slots of $P_{t+1}$.

Once, the formation of $P_{t+1}$ is done, then $P_{t+1}$ becomes the parent population by replacing $P_t$ in the next generation. This process of creating a new population for each generation goes on until the termination condition (i.e., maximum function evaluations or generations) is satisfied.

5.2.2. Duplicate Elimination Non-Dominated Sorting Evolutionary Algorithm

Greiner et al. [39] proposed the Duplicate Elimination Non-dominated Sorting Evolutionary Algorithm (DENSEA) as a variant of MOEA. The objective of DENSEA is to accentuate on formation and preservation of diversity among the individuals of a population to avoid the generation of limited non-dominated solutions. The generation of inadequate number of non-dominated solutions in a population of MOEA is usually responsible for slowing down the evolution process in a MOEA and achieve an early state of homogeneity in the population leading to a possible premature convergence of the algorithm. In order to incorporate some elitism, DENSEA implements the non-domination sorting [38] technique. However, the main characteristic of DENSEA is emphasized by the maintenance of population diversity by eliminating and replacing the duplicate individuals of the population in the subsequent generation. We discuss the workflow of the algorithm below.

The execution DENSEA is initiated by the random generation of initial population $P_0$ of size $N$ and evaluating the fitness of the chromosomes of $P_0$. Subsequently, the chromosomes of the population are ordered by employing non-domination sorting [38] technique. At every subsequent generation $t$, an offspring population $O_t$ is created by using the genetic operators ($selection$, $crossover$ and $mutation$) on the parent population $P_t$. Accordingly, the fitness evaluation of $O_t$ is determined and similar to the parent population, the offspring population is also sorted by using the non-domination sorting.

In particular, the deletion operator of DENSEA removes the duplicate solutions generated due to the formation of fewer non-dominated solutions in the functional space. Here, the population is divided into two halves $P_{1t}$ and $P_{2t}$ each having the size $\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$. Accordingly, for each elimination of a duplicate solution in one half of the population (say $P_{1t}$) follows the inclusion of a solution maintaining the same order in $P_{2t}$. This process of replacing a duplicate solution is continued until half of the population size $\left(\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)$ is achieved. For instance, for a population of size $N$, if the fifth individual is identified as a duplicate solution then it is replaced with the ${\left(\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$2$}\right.+5\right)}^{th}$ individual from the second half of the population. In this way, the population diversity is maintained by replacing the duplicates with individuals from diverse regions of the functional space. This process is implemented both in $P_t$ and $O_t$ to generate the corresponding filtered parent and offspring populations $P_f$ and $O_f$ each having population size $\raisebox{1ex}{$N$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$. Subsequently, the individuals of the new population $P_{t+1}$ in the next generation are selected by the combination of $P_f$ and $C_f$. Accordingly, the individuals belonging to $P_{t+1}$ promote elitism among themselves and at the same time, the population diversity among these individuals is also maintained by the renovation of $50\%$ of the duplicate solution in each generation without the loss of any genetic information in $P_{t+1}$. This process in the DENSEA continues until the termination condition is attained.

6. Numerical Experiments

While exploring the characteristic of the proposed UMMSTP, an appropriate numerical example is presented in this section. In many real-world situations, due to the existence of some intricate social and economic situations in decision-making problems such as MMSTP, the problem parameters may not always be determined exactly or are unavailable. Therefore, to incorporate such types of indeterminate parameters in a decision making problem we have to depend on domain experts for estimating and evaluating the belief degrees of the indeterminacy existing in those parameters. As a matter of fact, it becomes quite legitimate to consider the uncertainty theory [22,24] paradigm while modelling the individual beliefs. Accordingly, in this study, the parameters of G are represented under the framework of uncertainty theory.

In the proposed study, we consider a petroleum products distribution network in the form of a weighted connected undirected graph (WCUG) G as shown in Figure 2 with ten vertices and nineteen edges. In G, a vertex is considered as a city and an edge is considered as a roadway, which connects a pair of cities. Roadways transportation of petroleum products by tankers or tank trucks generally includes several factors such as cost of fuel, labor cost, overhaul and maintenance costs, road tax, traffic congestion time and vehicle maintenance costs which alter from time to time. Moreover, in a country such as India, where the price of petroleum largely depends on the international price of crude oil, the price of the petroleum products fluctuates in short durations. For example, the fluctuation pf the petrol or diesel price may change during the midst of their transportation from one city to other. As a matter of the fact, the transportation cost and the transportation time of such a distribution network become very crucial factors, since the objective is to minimize the transportation cost which includes certain factors as mentioned above which fluctuate from time to time. Further, any delay in transportation of the products due to traffic congestion, mechanical faults of the transportation vehicle, road blockage due to political agendas, etc., can increase the possibility of the increase in the price of the petroleum products. Therefore, in order to model the uncertain fluctuating factors which involves in the transportation cost and the transportation time, as well as to explore the symmetry (balance) between the transportation cost and the transportation time, in the study, we minimize simultaneously the cost and time parameters by considering the parameters as uncertain variables, i.e., uncertain transportation cost ${\xi }_{c_{ij}}$ and uncertain transportation time ${\xi }_{t_{ij}}$. These parameters are denoted as zigzag uncertain variables and reported in

Table 1. Uncertain parameters corresponding to each edge of G.

Edge	${\mathit{\xi }}_{{\mathit{c}}_{\mathit{i}\mathit{j}}}$	${\mathit{\xi }}_{{\mathit{t}}_{\mathit{i}\mathit{j}}}$	Edge	${\mathit{\xi }}_{{\mathit{c}}_{\mathit{i}\mathit{j}}}$	${\mathit{\xi }}_{{\mathit{t}}_{\mathit{i}\mathit{j}}}$
$e_{12}$	$\mathcal{Z}\left(67.8, 68.2,70.1\right)$	$\mathcal{Z}\left(54.7, 57.8,58.2\right)$	$e_{57}$	$\mathcal{Z}\left(71.9,73.1,74.6\right)$	$\mathcal{Z}\left(53.9,55.3,57.2\right)$
$e_{13}$	$\mathcal{Z}\left(69.2, 70.7,71.2\right)$	$\mathcal{Z}\left(57.9, 59.7,61.2\right)$	$e_{58}$	$\mathcal{Z}\left(68.7,69.2,70.1\right)$	$\mathcal{Z}\left(56.8,57.9,58.8\right)$
$e_{23}$	$\mathcal{Z}\left(70.4, 71.2, 72.5\right)$	$\mathcal{Z}\left(61.1, 63.2, 64.6\right)$	$e_{68}$	$\mathcal{Z}\left(73.3, 74.5, 75.2\right)$	$\mathcal{Z}\left(59.3, 60.4, 61.9\right)$
$e_{24}$	$\mathcal{Z}\left(69.8,71.5,72.3\right)$	$\mathcal{Z}\left(58.4,59.5,60.9\right)$	$e_{610}$	$\mathcal{Z}\left(69.2,71.2,72.6\right)$	$\mathcal{Z}\left(56.1,57.4,58.7\right)$
$e_{25}$	$\mathcal{Z}\left(68.8,69.5,70.9\right)$	$\mathcal{Z}\left(58.4,60.9,61.7\right)$	$e_{78}$	$\mathcal{Z}\left(70.2,71.8,72.5\right)$	$\mathcal{Z}\left(60.2,61.3,64.7\right)$
$e_{27}$	$\mathcal{Z}\left(69.3, 71.8,72.2\right)$	$\mathcal{Z}\left(54.3, 55.8,57.2\right)$	$e_{79}$	$\mathcal{Z}\left(69.2,71.6,72.5\right)$	$\mathcal{Z}\left(62.8,63.2,64.1\right)$
$e_{34}$	$\mathcal{Z}\left(72.2, 73.6, 74.2\right)$	$\mathcal{Z}\left(56.9, 58.6, 59.7\right)$	$e_{89}$	$\mathcal{Z}\left(70.1,72.3,73.2\right)$	$\mathcal{Z}\left(61.9,62.6,63.5\right)$
$e_{45}$	$\mathcal{Z}\left(71.1,72.9,73.7\right)$	$\mathcal{Z}\left(52.7,54.7,56.6\right)$	$e_{810}$	$\mathcal{Z}\left(69.2,70.2,71.7\right)$	$\mathcal{Z}\left(54.2,56.4,57.9\right)$
$e_{46}$	$\mathcal{Z}\left(68.1,69.9,70.8\right)$	$\mathcal{Z}\left(59.2,61.4,62.4\right)$	$e_{910}$	$\mathcal{Z}\left(72.3,73.6,74.2\right)$	$\mathcal{Z}\left(53.1,54.9,55.6\right)$
$e_{56}$	$\mathcal{Z}\left(69.8,72.5,74.3\right)$	$\mathcal{Z}\left(57.8,58.2,59.1\right)$	$--$	$--$	$--$

.

In order to determine the MMST of $G$, we consider the corresponding deterministic Models, (20) and (22) of the EVM (cf. Model (16)) and CCM (cf. Model (17)) of the proposed UMMSTP (cf. Model (15)). Since the Models (20) and (22) are the MOOPs, therefore, we have employed the classical multi-objective solution technique, $ϵ$-constraint method on their corresponding compromise Models (23) and (24). Lingo 11.0 (optimization problem solver) is used to determine the compromise solutions of these models. While solving Model (24), we have set the chance (confidence) level of the problem parameters to $0.8$. Subsequently, the compromise solutions of the Models (23) and (24) are shown in

Table 2. Minimum spanning trees of G created by solving the compromise crisp equivalents of EVM and CCM.

EVM			CCM
$\mathit{E}\left[{\mathit{Z}}_1\right]$	$\mathit{E}\left[{\mathit{Z}}_2\right]$	$\mathbf{Minimum} \mathbf{Spanning} \mathbf{Tree} \mathbf{of} \mathit{G}$	${\overline{\mathit{Z}}}_1$	${\overline{\mathit{Z}}}_2$	$\mathbf{Minimum} \mathbf{Spanning} \mathbf{Tree} \mathbf{of} \mathit{G}$
$631.5500$	$528.9000$	$\left\{\begin{array}{c}{e}_{12}, e_{13}, e_{25},e_{27},e_{46},\\ e_{58}, e_{610},e_{79},e_{810}\end{array}\right\}$	$638.1200$	$538.4800$	$\left\{\begin{array}{c}{e}_{12}, e_{13}, e_{24},e_{25},e_{27},\\ e_{46}, e_{58},e_{79},e_{810}\end{array}\right\}$

. Here, it is observed that two different minimum spanning trees are generated by solving Models (23) and (24).

For determining the multiple non-dominated solutions of the EVM and CCM of $G$, the corresponding deterministic multi-objective Models (20) and (22) are solved with the two MOEAs, NSGAII and DENSEA. Both the MOEAs are executed for $250$ maximum generations. Here, each of these NSGAII and DENSEA uses the genetic operators $binary tournament selection$, $single point crossover$ and $bit$-$flip mutation$. Moreover, the crossover and the mutation probabilities for each of these MOEAs are respectively considered as 0.9 and 0.05. In addition, jMetal4.5 [44] framework is used to generate the non-dominated solutions of the Models (20) and (22) for $G$. These non-dominated (non-inferior) solutions are reported in

Table 3. Non-dominated solutions generated by solving the Model (20) of G with the MOEAs.

NSGAII		DENSEA
$\mathit{E}\left[{\mathit{Z}}_1\right]$	$\mathit{E}\left[{\mathit{Z}}_2\right]$	$\mathit{E}\left[{\mathit{Z}}_1\right]$	$\mathit{E}\left[{\mathit{Z}}_2\right]$
$640.225$	$508.725$	$\mathbf{631.550}$	$\mathbf{528.900}$
$631.650$	$528.600$	$631.650$	$528.600$
$633.200$	$522.425$	$632.300$	$528.225$
$636.725$	$513.775$	$633.150$	$526.175$
$635.350$	$517.475$	$633.200$	$522.425$
$638.850$	$512.425$	$633.750$	$520.200$
$638.325$	$512.875$	$634.575$	$518.725$
$633.750$	$520.200$	$635.35$	$517.475$
$634.575$	$518.725$	$636.175$	$517.425$
$\mathbf{631.550}$	$\mathbf{528.900}$	$636.725$	$513.775$
$--$	$--$	$637.550$	$513.725$
$--$	$--$	$638.325$	$512.875$
$--$	$--$	$638.850$	$512.425$
$--$	$--$	$640.225$	$508.725$

and

Table 4. Non-dominated solutions generated by solving the Model (22) of G with the MOEAs.

NSGAII		DENSEA
${\overline{\mathit{Z}}}_1$	${\overline{\mathit{Z}}}_2$	${\overline{\mathit{Z}}}_1$	${\overline{\mathit{Z}}}_2$
$\mathbf{638.120}$	$\mathbf{538.48}$	$637.96$	$538.780$
$646.600$	$516.800$	$\mathbf{638.120}$	$\mathbf{538.480}$
$639.360$	$530.580$	$638.020$	$536.620$
$646.560$	$519.620$	$638.180$	$536.320$
$642.940$	$521.740$	$638.880$	$535.720$
$642.880$	$523.900$	$639.360$	$530.580$
$638.180$	$536.320$	$639.940$	$530.060$
$641.340$	$525.560$	$640.000$	$527.900$
$640.000$	$527.900$	$640.960$	$526.760$
$644.580$	$520.700$	$641.340$	$525.560$
$645.000$	$520.620$	$642.320$	$525.300$
$640.960$	$526.760$	$642.880$	$523.900$
$639.940$	$530.060$	$642.940$	$521.740$
$--$	$--$	$643.920$	$521.480$
$--$	$--$	$644.580$	$520.700$
$--$	$--$	$645.900$	$520.400$
$--$	$--$	$646.560$	$519.620$
$--$	$--$	$646.600$	$516.800$
$--$	$--$	$649.560$	$515.460$

. Here, for both the EVM and CCM, it is observed that a particular solution among the set of non-inferior (non-dominated) solutions, created by both the MOEAs is identical to the solution produced by ϵ-constraint method (cf. Table 2). This solution is highlighted in bold. From Table 3 and Table 4, it is also observed that DENSEA generates more non-dominated solution compared to NSGAII for both the EVM and CCM of $G$. Furthermore, the graphical representation of these non-dominated solutions generated for the EVM and CCM are depicted in Figure 3 and Figure 4, respectively.

We study the sensitivity analysis of the compromise deterministic CCM model in (24) for $G$ by varying the confidence levels. Subsequently, the related results are presented in

Table 5. Solutions of the crisp equivalent compromise Model (24) of the CCM for G at various confidence levels of α₁ and α₂.

Confidence Levels		$\mathbf{Model} \left(24\right)$		Confidence Levels		$\mathbf{Model} \left(24\right)$
${\alpha }_1$	${\alpha }_2$	${\overline{Z}}_1$	${\overline{Z}}_2$	${\alpha }_1$	${\alpha }_2$	${\overline{Z}}_1$	${\overline{Z}}_2$
$0.005$	$0.005$	$619.6280$	$514.5610$	$0.60$	$0.60$	$634.2600$	$532.4400$
$0.10$	$0.10$	$622.0600$	$517.6200$	$0.70$	$0.70$	$636.2200$	$534.3800$
$0.20$	$0.20$	$624.6200$	$520.8400$	$0.80$	$0.80$	$638.1200$	$538.4800$
$0.30$	$0.30$	$627.1800$	$524.0600$	$0.90$	$0.90$	$639.9600$	$540.4400$
$0.40$	$0.40$	$629.7400$	$527.2800$	$0.995$	$0.995$	$641.7080$	$542.3020$
$0.50$	$0.50$	$632.3000$	$530.5000$	$--$	$--$	$--$	$--$

. For convenience, here, the value of the confidence levels, i.e., ${\alpha }_1$ and ${\alpha }_2$ are considered the same. From Table 5, we observe that as the value of ${\alpha }_1$ and ${\alpha }_2$ gradually increase, the value of ${\overline{Z}}_1$ and ${\overline{Z}}_2$ also increase progressively. Moreover, the inverse uncertainty distribution of ${\overline{Z}}_1$ and ${\overline{Z}}_2$ with respect to ${\alpha }_1$ and ${\alpha }_2$ of the Model (24) is graphically displayed in Figure 5.

7. Results and Discussions

For the sake of discussion, we have purposefully generated five random instances of UMMSTP: (i) $UncertainMMST\#10,$ (ii) $UncertainMMST\#20,$ (iii) $UncertainMMST\#30$, (iv) $UncertainMMST\#40$ and (v) $UncertainMMST\#50$, which contains 10, 20, 30, 40 and 50 vertices, respectively. Each of the instances is a WCUG and considered as complete graphs with $\left(\begin{array}{c}n\\ 2\end{array}\right)$ edges, where $n$ is the number of edges. Here, for each instance, the edge weight of an edge $e_{ij}$ connecting vertices $v_i$ and $v_j$ is represented by (i) uncertain travel cost ${\xi }_{c_{ij}}$ and (ii) uncertain travel time ${\xi }_{t_{ij}}$, which are considered as zigzag uncertain variables. In addition, ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ are randomly generated and respectively expressed as zigzag uncertain variables $\mathcal{Z}\left(p_{c_{ij}},q_{c_{ij}},r_{c_{ij}}\right)$ and $\mathcal{Z}\left(p_{t_{ij}},q_{t_{ij}},r_{t_{ij}}\right)$. Specifically, for each edge $e_{ij}$ of an instance, the $p_{c_{ij}},q_{c_{ij}}$ and $r_{c_{ij}}$ are randomly generated from the interval $\left[65.5, 85.5\right]$ such that $p_{c_{ij}}<q_{c_{ij}}<$ $r_{c_{ij}}$. Whereas, $p_{t_{ij}},q_{t_{ij}}$ and $r_{t_{ij}}$ are selected randomly from the interval $\left[50.5, 75.5\right]$ so that $p_{t_{ij}}<q_{t_{ij}}<r_{t_{ij}}$.

Considering all the above mentioned five instances of UMMSTP, the crisp equivalent Models (20) and (22) for the EVM the CCM are consequently solved by NSGAII and DENSEA. Moreover, to analyze the performance of the MOEAs on the five instances, we consider four different performance metrics: (i) hypervolume $\left(HV\right)$ [45], (ii) spread $\left(SPREAD\right)$ [46], (iii) inverted generational distance $\left(IGD\right)$ [47] and, (iv) epsilon $\left(EPSILON\right)$ [48]. For $HV$, a higher value is always desirable. However, for $SPREAD$, $IGD$ and $EPSILON$, smaller values are likely to be achieved. Among these performance metrics, $HV$ and $IGD$ confirm together the convergence and diversity of the non-dominated solutions produced by an MOEA, $SPREAD$ promises the diversity of the non-dominated solutions, while $EPSILON$ assures the convergence of an MOEA.

The jMetal4.5 framework is used for the execution of NSGAII and DENSEA on the Models (20) and (22) of EVM and CCM respectively, for each of the instances. Moreover, the stochastic characteristics of the MOEAs has encouraged us to execute each algorithm with 500 generations, independently for100 times. Here, for both the algorithms, the genetic operators and their corresponding settings are the same as mentioned above in Section 6.

The set of Pareto solutions in a Pareto front (PF) of real-world problems are generally unattainable. Hence, the PF of a particular instance is approximated by producing a reference front, which is created by considering the non-inferior solutions that coexist in the first front produced after every execution of both NSGAII and DENSEA on that instance. Once the reference front is generated, the value of the performance metrics is calculated based on the solutions constituting the reference front.

Statistically we analysis the performance metrics by determining $mean$, standard deviation ($sd$), $median$ and interquartile range ($IQR$). For all the UMMSTP instances, the $mean$ and $sd$ for all the performance metrics generated by the MOEAs are presented in

Table 6. mean and sd corresponding to HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (20).

MOEA	Uncertain Instance	$\mathit{H}\mathit{V}$		$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$		$\mathit{I}\mathit{G}\mathit{D}$		$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
		$\mathit{M}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{M}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{M}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{M}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$
NSGAII	$Uncertain$ $MMST\#10$	6.18 × 10−1	1.4 × 10−2	1.32 × 10+00	1.4 × 10−2	3.4 × 10−4	1.9 × 10−4	6.90 × 10−1	4.6 × 10−1
	$Uncertain$ $MMST\#20$	7.43 × 10−1	2.3 × 10−2	9.94 × 10−1	5.9 × 10−2	5.2 × 10−4	2.2 × 10−4	1.67 × 10+00	6.7 × 10−1
	$Uncertain$ $MMST\#30$	6.86 × 10−1	2.1 × 10−2	7.49 × 10−1	5.5 × 10−2	2.7 × 10−4	1.4 × 10−4	2.19 × 10+00	7.1 × 10−1
	$Uncertain$ $MMST\#40$	6.48 × 10−1	1.2 × 10−2	6.88 × 10−1	4.8 × 10−2	2.3 × 10−4	9.0 × 10−5	5.11 × 10+00	1.5 × 10+00
	$Uncertain$ $MMST\#50$	5.90 × 10−1	2.9 × 10−2	8.45 × 10−1	7.3 × 10−2	3.7 × 10−3	7.9 × 10−4	8.51 × 10+00	1.8 × 10+00
DENSEA	$Uncertain$ $MMST\#10$	6.27 × 10−1	1.1 × 10−3	6.46 × 10−1	5.1 × 10−2	5.2 × 10−5	8.6 × 10−5	1.14 × 10−1	1.6 × 10−1
	$Uncertain$ $MMST\#20$	7.72 × 10−1	3.4 × 10−3	6.17 × 10−1	5.3 × 10−2	1.5 × 10−4	7.7 × 10−5	5.20 × 10−1	2.5 × 10−1
	$Uncertain$ $MMST\#30$	7.04 × 10−1	9.8 × 10−3	6.03 × 10−1	4.2 × 10−2	1.5 × 10−4	6.4 × 10−5	1.61 × 10+00	7.3 × 10−1
	$Uncertain$ $MMST\#40$	6.59 × 10−1	7.8 × 10−3	6.12 × 10−1	3.7 × 10−2	1.6 × 10−4	3.9 × 10−5	3.45 × 10+00	1.3 × 10+00
	$Uncertain$ $MMST\#50$	6.40 × 10−1	1.5 × 10−2	7.12 × 10−1	3.9× 10−2	2.0 × 10−3	7.1 × 10−4	5.36 × 10+00	2.0 × 10+00

and

Table 7. mean and sd corresponding to HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (22).

MOEA	Uncertain Instance	$\mathit{H}\mathit{V}$		$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$		$\mathit{I}\mathit{G}\mathit{D}$		$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
		$\mathit{m}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{m}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{m}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$	$\mathit{m}\mathit{e}\mathit{a}\mathit{n}$	$\mathit{s}\mathit{d}$
NSGAII	$Uncertain$ $MMST\#10$	6.0 × 10−1	1.4 × 10−2	1.32 × 10+00	1.4 × 10−2	3.57 × 10−4	2.2 × 10−4	1.07 × 10+00	5.3 × 10−1
	$Uncertain$ $MMST\#20$	6.5 × 10−1	1.7 × 10−2	1.00 ×10+00	3.7 × 10−2	2.31 × 10−4	1.4 × 10−4	2.23 × 10+00	1.0 × 10+00
	$Uncertain$ $MMST\#30$	6.7 × 10−1	2.7× 10−2	8.21 × 10−1	7.7 × 10−2	2.92 × 10−4	1.7 × 10−4	2.37 × 10+00	8.4 × 10−1
	$Uncertain$ $MMST\#40$	6.48 × 10−1	1.2 × 10−2	6.66 × 10−1	5.8 × 10−2	2.58 × 10−4	8.7 × 10−5	6.18 × 10+00	1.6 × 10+00
	$Uncertain$ $MMST\#50$	5.95 × 10−1	3.3 × 10−2	7.83 × 10−1	8.7 × 10−2	2.78 × 10−3	7.5 × 10−4	9.18 × 10+00	2.8 × 10+00
DENSEA	$Uncertain$ $MMST\#10$	6.14 × 10−1	8.6 × 10−4	6.18 × 10−1	4.0 × 10−2	3.69 × 10−5	3.5 × 10−5	1.71 × 10−1	1.4 × 10−1
	$Uncertain$ $MMST\#20$	6.74 × 10−1	4.2 × 10−3	6.64 × 10−1	4.2 × 10−2	1.00 × 10−4	5.2 × 10−5	1.16 × 10+00	4.9 × 10−1
	$Uncertain$ $MMST\#30$	6.92 × 10−1	1.1 × 10−2	5.57 × 10−1	5.4 × 10−2	1.59 × 10−4	8.1 × 10−5	1.45 × 10+00	6.4 × 10−1
	$Uncertain$ $MMST\#40$	6.57 × 10−1	6.1 × 10−3	5.95 × 10−1	4.0 × 10−2	1.82 × 10−4	4.1 × 10−5	4.06 × 10+00	1.4 × 10+00
	$Uncertain$ $MMST\#50$	6.57 × 10−1	1.5 × 10−2	7.38 × 10−1	3.6 × 10−2	1.34 × 10−3	4.2 × 10−4	4.96 × 10+00	1.8 × 10+00

, respectively, whereas, the $median$ and $IQR$ of the performance metrics are shown in

Table 8. median and IQR corresponding to HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (20).

MOEA	Uncertain Instance	$\mathit{H}\mathit{V}$		$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$		$\mathit{I}\mathit{G}\mathit{D}$		$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
		$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$
NSGAII	$Uncertain$ $MMST\#10$	6.23 × 10−1	7.3 × 10−3	1.33 × 10+00	1.8 × 10−2	4.19 × 10−4	2.7 × 10−4	6.50 × 10−1	2.5 × 10−1
	$Uncertain$ $MMST\#20$	7.48 × 10−1	2.5 × 10−2	9.94 × 10−1	8.3 × 10−2	5.04 × 10−4	2.7 × 10−4	1.52 × 10+00	8.4 × 10−1
	$Uncertain$ $MMST\#30$	6.91 × 10−1	2.4 × 10−2	7.47 × 10−1	6.5 × 10−2	2.38 × 10−4	1.5 × 10−4	2.18 × 10+00	8.5 × 10−1
	$Uncertain$ $MMST\#40$	6.50 × 10−1	1.2 × 10−2	6.89 × 10−1	5.9 × 10−2	2.11 × 10−4	8.3 × 10−5	4.96 × 10+00	1.9 × 10+00
	$Uncertain$ $MMST\#50$	5.95 × 10−1	3.6 × 10−2	8.41 × 10−1	1.0 × 10−1	3.79 × 10−3	1.1 × 10−3	8.20 × 10+00	2.3 × 10+00
DENSEA	$Uncertain$ $MMST\#10$	6.28 × 10−1	9.0 × 10−5	6.56 × 10−1	5.8 × 10−2	3.19 × 10−5	4.1 × 10−5	5.00 × 10−2	8.7 × 10−2
	$Uncertain$ $MMST\#20$	7.73 × 10−1	3.0 × 10−3	6.20 × 10−1	7.3 × 10−2	1.32 × 10−4	8.6 × 10−5	4.50 × 10−1	2.3 × 10−1
	$Uncertain$ $MMST\#30$	7.05 × 10−1	1.3 × 10−2	6.03 × 10−1	6.5 × 10−2	1.49 × 10−4	8.6 × 10−5	1.57 × 10+00	1.1 × 10+00
	$Uncertain$ $MMST\#40$	6.59 × 10−1	1.1 × 10−2	6.12 × 10−1	5.2 × 10−2	1.55 × 10−4	5.4 × 10−5	3.35 × 10+00	1.5 × 10+00
	$Uncertain$ $MMST\#50$	6.43 × 10−1	2.3 × 10−2	7.18 × 10−1	6.4 × 10−2	1.97 × 10−3	9.4 × 10−4	4.99 × 10+00	2.7 × 10+00

and

Table 9. median and IQR corresponding to HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (22).

MOEA	Uncertain Instance	$\mathit{H}\mathit{V}$		$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$		$\mathit{I}\mathit{G}\mathit{D}$		$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
		$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$	$\mathit{m}\mathit{e}\mathit{d}\mathit{i}\mathit{a}\mathit{n}$	$\mathit{I}\mathit{Q}\mathit{R}$
NSGAII	$Uncertain$ $MMST\#10$	6.08 × 10−1	6.3 × 10−3	1.32 × 10+00	1.7 × 10−2	3.06 × 10−4	3.8 × 10−4	1.04 × 10+00	7.5 × 10−1
	$Uncertain$ $MMST\#20$	6.62 × 10−1	1.9 × 10−2	1.00 × 10+00	5.3 × 10−2	2.07 × 10−4	1.5 × 10−4	2.39 × 10+00	1.5 × 10+00
	$Uncertain$ $MMST\#30$	6.83 × 10−1	2.3 × 10−2	8.13 × 10−1	8.6 × 10−2	2.55 × 10−4	1.8 × 10−4	2.29 × 10+00	1.2e × 10+00
	$Uncertain$ $MMST\#40$	6.49 × 10−1	1.4 × 10−2	6.65 × 10−1	7.5 × 10−2	2.44 × 10−4	9.4 × 10−5	6.21 × 10+00	2.2 × 10+00
	$Uncertain$ $MMST\#50$	6.01 × 10−1	5.0 × 10−2	7.80 × 10−1	1.2 × 10−1	2.76 × 10−3	9.9 × 10−4	8.95 × 10+00	4.2 × 10+00
DENSEA	$Uncertain$ $MMST\#10$	6.14 × 10−1	5.4× 10−4	6.27 × 10−1	5.8× 10−2	2.41 × 10−5	4.9× 10−5	1.60 × 10−1	1.0× 10−1
	$Uncertain$ $MMST\#20$	6.75 × 10−1	4.4× 10−3	6.71 × 10−1	5.9× 10−2	7.98 × 10−5	8.6× 10−5	1.06 × 10+00	6.1× 10−1
	$Uncertain$ $MMST\#30$	6.95 × 10−1	9.0× 10−3	5.53 × 10−1	5.6× 10−2	1.37 × 10−4	7.3× 10−5	1.40 × 10+00	7.3× 10−1
	$Uncertain$ $MMST\#40$	6.58 × 10−1	8.1× 10−3	5.95 × 10−1	5.3× 10−2	1.74 × 10−4	5.4× 10−5	3.93 × 10+00	1.5× 10+00
	$Uncertain$ $MMST\#50$	6.59 × 10−1	1.8× 10−2	7.35 × 10−1	4.6× 10−2	1.31 × 10−3	5.2× 10−4	4.49 × 10+00	2.5× 10+00

, respectively. Here, the better values are displayed in bold in all these tables.

Considering the $mean$ in Table 6 and Table 7 and $median$ in Table 8 and Table 9, we observe that with respect to all the UMMSTP instances, DENSEA performs superiorly to NSGAII for all the performance metrics.

For all the instances, the graphical elucidation of the results of $HV$, $SPREAD$, $IGD$ and $EPSILON$, in terms of letter-value plots [49] and violin plots [50] are depicted in Figure A1, Figure A2, Figure A3 and Figure A4 as provided in the Appendix B. All these plots graphically display the $median$s of the performance metrics (cf. Table 8 and Table 9). These figures explicate clearly that DENSEA performs better than NSGAII as far as the performance metrics are concerned. In particular, the letter-value plots in Figure A1 and Figure A2, display the $median$s as the red horizontal lines along with many quartiles. From both these figures, it can be inferred that for all the instances of UMMSTP, the $median$s of the performance metrics are better for DENSEA compared to NSGAII. Moreover, in these figures, with respect to each of the instances, for all the performance metrics, the quartiles generated in case of DENSEA have lesser width compared to those for the case of NSGAII.

This fact essentially suggests that the performance metrics generated by DENSEA are more consistent and does not fluctuate much as in the case of NSGAII. The violin plots in Figure A3 and Figure A4 depict the distribution of the data and inscribe the box plots within themselves. These figures also display the $median$s as white circles within the corresponding box plots. For all the five instances, the plots in Figure A3 and Figure A4 provide a similar implication that the distribution of the generated values corresponding to each performance metric is more compact for DENSEA with respect to NSGAII. This in turn suggests that for all the instances, the existence of the outliers in the data corresponding to all the performance metrics are less for DENSEA as compare to NSGAII. Moreover, from Figure A3 and Figure A4, it is also inferred that for every instances, the $median$s of the performance metrics are better for DENSEA as compare to those generated by NSGAII.

In addition, considering all the five UMMSTP instances, the Wilcoxon rank sum test is conducted for all performance metrics. Accordingly, the null Hypothesis 1 (H₁) for the test is set as follows.

Hypothesis 1 (H₁).

The performance metrics generated by NSGAII and DENSEA are significantly equal.

In

Table 10. Wilcoxon rank sum test of HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (20).

Uncertain Instance	$\mathit{H}\mathit{V}$	$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$	$\mathit{I}\mathit{G}\mathit{D}$	$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$
$Uncertain$ $MMST\#10$	${\prec }_{2.3956\times {10}^{-30}}$	${\prec }_{1.2405\times {10}^{-34}}$	${\prec }_{1.3579\times {10}^{-29}}$	${\prec }_{2.5282\times {10}^{-28}}$
$Uncertain$ $MMST\#20$	${\prec }_{5.6397\times {10}^{-31}}$	${\prec }_{2.5620\times {10}^{-34}}$	${\prec }_{3.1703\times {10}^{-30}}$	${\prec }_{7.0463\times {10}^{-30}}$
$Uncertain$ $MMST\#30$	${\prec }_{2.1034\times {10}^{-14}}$	${\prec }_{2.8233\times {10}^{-32}}$	${\prec }_{8.2378\times {10}^{-15}}$	${\prec }_{2.1057\times {10}^{-27}}$
$Uncertain$ $MMST\#40$	${\prec }_{2.1050\times {10}^{-11}}$	${\prec }_{1.3281\times {10}^{-21}}$	${\prec }_{3.8558\times {10}^{-13}}$	${\prec }_{2.0566\times {10}^{-13}}$
$Uncertain$ $MMST\#50$	${\prec }_{4.3185\times {10}^{-30}}$	${\prec }_{6.1249\times {10}^{-28}}$	${\prec }_{3.5908\times {10}^{-27}}$	${\prec }_{5.9250\times {10}^{-20}}$

and

Table 11. Wilcoxon rank sum test of HV, SPREAD, IGD and EPSILON for the UMMSTP instances considering Model (22).

Uncertain Instance	$\mathit{H}\mathit{V}$	$\mathit{S}\mathit{P}\mathit{R}\mathit{E}\mathit{A}\mathit{D}$	$\mathit{I}\mathit{G}\mathit{D}$	$\mathit{E}\mathit{P}\mathit{S}\mathit{I}\mathit{L}\mathit{O}\mathit{N}$
	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$	$\mathbf{DENSEA}\star \mathbf{HSGAII}$
$Uncertain$ $MMST\#10$	${\prec }_{1.6510\times {10}^{-25}}$	${\prec }_{2.0173\times {10}^{-34}}$	${\prec }_{2.0824\times {10}^{-27}}$	${\prec }_{2.6926\times {10}^{-28}}$
$Uncertain$ $MMST\#20$	${\prec }_{7.1968\times {10}^{-18}}$	${\prec }_{2.5621\times {10}^{-34}}$	${\prec }_{4.0284\times {10}^{-16}}$	${\prec }_{5.6276\times {10}^{-15}}$
$Uncertain$ $MMST\#30$	${\prec }_{1.7225\times {10}^{-12}}$	${\prec }_{4.8090\times {10}^{-34}}$	${\prec }_{7.0592\times {10}^{-15}}$	${\prec }_{2.4548\times {10}^{-15}}$
$Uncertain$ $MMST\#40$	${\prec }_{7.2285\times {10}^{-10}}$	${\prec }_{6.6706\mathrm{e} \times {10}^{-17}}$	${\prec }_{3.5046\times {10}^{-14}}$	${\prec }_{1.7694\times {10}^{-17}}$
$Uncertain$ $MMST\#50$	${\prec }_{8.8897\times {10}^{-31}}$	${\prec }_{7.5103\times {10}^{-25}}$	${\prec }_{1.1173\times {10}^{-29}}$	${\prec }_{5.4751\times {10}^{-23}}$

, we provide the results of the test, which is executed by considering the significance level to $1\%$. In these tables, the column DENSEA$\star$NSGAII infer each of the following two conditions.

(i)

DENSEA ${\prec }_{p_v}$ NSGAII: DENSEA is significantly better than NSGAII at $1\%$ significance level and $H_1$ is not accepted at the p-value ($p_v$).

(ii)

DENSEA ${\succ }_{p_v}$ NSGAII: NSGAII is significantly better than DENSEA at $1\%$ significance level and $H_1$ is not accepted at the $p_v.$

From Table 10 and Table 11, we can conclude that for all the performance metrics, DENSEA is significantly better than NSGAII and $H_1$ is rejected.

8. Conclusions

The originality of the present study includes the investigation of a multi-objective minimum spanning tree with uncertain parameters. Here, we propose a UMMSTP, which optimized the uncertain parameters in terms of ${\xi }_{c_{ij}}$ and ${\xi }_{t_{ij}}$ in a minimum spanning tree. Based on uncertainty theory, we have developed two uncertain programming models of UMMSTP: the EVM and the CCM. In order to solve these models expediently, subsequently, we determine the deterministic transformation of these models. These deterministic models are solved with the $ϵ$- constraint method as well as with two MOEAs: NSGAII and DENSEA. Accordingly, a suitable numerical example is presented to elucidate the application of the models. Thereafter, the performance of the MOEAs on some of the larger instances of the UMMSTP are compared and analyzed.

Being a multi-objective optimization problem, our proposed UMMSTP generates multiple non-dominated (non-inferior) solutions in the approximate front. Subsequently, selection of a single solution from a set of solution becomes a difficult task for a decision maker. Further, the multi-objective nature of the proposed problem characterizes it as a NP-hard problem. Accordingly, designing of any conventional algorithm to explore the exact solution of the problem becomes computationally very expensive. As a matter of the fact, we have to compromise with the approximate solutions of the problem as generated by the MOEAs. Hence, the above-mentioned factors essentially become the limitation of our study.

We believe that our models extend the ability of an MMSTP to deal with uncertain parameters. Notably, the proposed UMMSTP in our study can be extended to different variants of multi-objective minimum spanning tree problem including multi-objective degree-constrained MST, multi-objective capacitated MST under uncertain and uncertain random environment. Furthermore, the possible extension of our study in a rather complex environment will be our interest in future research, where there is a coexistence of both uncertainty and randomness.