Uncertain multiobjective orienteering problem and its application to UAV reconnaissance mission planning

Abstract

Orienteering problem is gradually prevalent in the recent decade, but studies considering both uncertainty and multiobjective are still at low pace. In this paper, the uncertain multiobjective orienteering problem (UMOOP) is modeled based on uncertainty theory, in which objective functions contain uncertain vectors. Firstly, the Kataoka criterion and the ‘worst-case-oriented’ philosophy are adopted, and the UMOOP is transformed into a deterministic problem α -UMOOP with a series of chance constrains. On this basis, concept of efficient solution with belief degree is defined. Secondly, two assumptions are introduced to deal with the uncertain vectors, and a deterministic equivalent form D-UMOOP can be obtained. It is theoretically proved that efficient solutions to D-UMOOP are equivalent to the efficient solutions with belief degrees to the UMOOP. Additionally, since the D-UMOOP is NP-hard, a discrete multiobjective bat algorithm is designed with the discrete updating process and the multiobjective local search strategy. Finally, an application is presented to the unmanned aerial vehicle (UAV) reconnaissance mission planning problem, which is modeled as uncertain biobjective orienteering problems, and tackled by the theoretical result and algorithm in this paper. The studies provide a new way for multiple attribute and uncertain decision-making problems.

Keywords

Uncertainty theory uncertainty multiobjective orienteering problem efficient solutions with belief degrees discrete multiobjective bat algorithm UAV reconnaissance mission planning

1 Introduction

Orienteering problem (OP) is a typical discrete combinatorial optimization problem, which originated from the outdoor sports in Sweden. It is also called the selective traveling salesman problem. In the last decade, the OP has a wide range of applications in logistics, tourism and military. More details and variants can be found in several surveys [1, 2]. Under the situation of more than one conflicting and incommensurable objective, the OP can be formulated as a multiobjective orienteering problem (MOOP). For example, when UAV performs a reconnaissance mission, all targets may have their value and the security for scouting as a pair of conflicting and incommensurable objectives, consequently, a multiobjective decision situation arises. The multiobjective orienteering problem is a must in the practical application, but there is a lack of relevant research. Sometimes, people have to make decisions with imprecise information or data making the problem harder to tackle. Stochastic service times are first introduced in the OP by Tang and Miller-Hooks [3]. İlhan et al. [4] takes the uncertainties in scores into account, and other investigations can be found in [5 –9].

In fact, the main theory to deal with the OP under the condition of indeterminacy is probability theory. However, the premise of probability theory should be emphasized that the estimated probability must be close enough to the real frequency. Once no samples are available, probability theory would be no longer applicable, and decision-makers have to invite some experienced experts to evaluate the belief degree of the event. A phenomenon was found that human beings have the tendency of exaggerating unlikely events [10]. If the belief degrees are treated as probability, something counterintuitive will arise [11]. For these reasons, uncertainty theory with complete axiomatic foundation was founded by Liu [12], and redefined by [13]. Until now, applications of uncertainty theory are across a wide spectrum of domains, including finance [14], regression analysis [15, 16], risk [17], differential equation [18, 19], and other areas [20 –22].

Although uncertainty theory and application has received much attention and developed quickly in recent years, studies on uncertainty multiobjective problems are rare except works in [23 –28] etc. Besides, many realistic issues both uncertainty and multiobjective can not be referred so far. This lack of study is very unfortunate, because those issues cannot be ignored in practice. Therefore, model of UMOOP is first formulated in our works, whose objective functions contain uncertain vectors to characterize the uncertain factors. However, it is extremely challenging to solve UMOOP for the existence of uncertain vectors, since the traditional multiobjective theory is not suitable at all. Hence, efficient solution theory for uncertain multiobjective programming is necessary. Expected-value efficient solution is a basic and commonly used concept, whereas this kind of efficient solution is generally propitious to a long term decision-making. However, it is not always considered as a good measure, likely to obtain some terrible results in the next decision-making for the dispersion of the uncertain variables.

For the above reasons, the Kataoka criterion and the ‘worst-case-oriented’ philosophy are adopted. Firstly, a series of minimum profit levels are set for each objective. Then, belief degrees of the events that each objective is not lower than the minimum profit levels, are controlled with a set of certain levels. Finally, maximizing the minimum profit levels becomes the objective of decision-making in the new model α -UMOOP. Furthermore, based on it, efficient solution with belief degrees to UMOOP is defined. Although the α -UMOOP is essentially a deterministic MOOP model, the uncertain vectors are still the biggest obstacle. However, it is not hard to find that the uncertain functions are all linear, therefore two kinds of assumptions are introduced to solve the efficient solutions with belief degrees. The first assumption is that uncertain vectors are normal uncertain vectors, and the second is that uncertain vectors are affine forms of an uncertain variable. We succeed in transforming the α -UMOOP model into the crisp deterministic form D-UMOOP. It is proved that efficient solutions to the D-UMOOP are equivalent to the efficient solutions with belief degrees to UMOOP in both situations.

However, it is more ambitious to obtain efficient solutions to the D-UMOOP, because OP and its variation are NP-hard. In our works, a newly-developing bat algorithm is chosen to find Pareto efficient solutions to the D-UMOOP. It is proposed by Xin-She Yang in 2010, and reasons for efficiency of the bat algorithm have been analyzed [29]. However, the traditional bat algorithm is not suitable for the discrete optimization problem. Therefore, a modified discrete multiobjective bat algorithm (MOBA) is developed for D-UMOOP by designing discrete updating process and combining with the fast non-dominated sorting genetic algorithm. In order to improve the exploitation capability, a multiobjective local search strategy is designed based on the reduced variable neighborhood search. Some standard benchmark instances are used to show the performance of the algorithm.

Finally, the theoretical result and algorithm in the paper are applied to UAV reconnaissance mission planning with uncertain factors to describe how to make decisions in the practical application. An uncertain biobjective UAV reconnaissance mission planning problem is modeled. Both the profit and security in the mission are considered, and minimum profit level and security level are set. Then belief degrees are controlled to a set of certain levels to make the profit and security not lower than the minimum levels. Through the assumptions, a D-URMPP model is obtained. After this, efficient solutions with belief degrees are given each representing a feasible flight path for the UAV. In conclusion, this studies provide an innovative method to the UAV reconnaissance mission planning problem considering multiobjective and uncertainty in practice.

The paper is organized in the following manner. The next section reviews some basic relational contents of uncertain theory. In Section 3, model of UMOOP is established and the concept of efficient solution with belief degree is defined. In Section 4, how to obtain efficient solutions with belief degrees is deduced, and the crisp deterministic equivalent form has been obtained. In Section 5, the variation of the bat algorithm for MOOP is designed. In Section 6, an application to the uncertain biobjective UAV reconnaissance mission planning problem is provided. Finally, the main results of this paper are summarized in Section 7.

2 Preliminary

Let Γ be a nonempty set, and $L$ a σ-algebra over Γ. Each element Λ in $L$ is called an event. A set function $M$ from $L$ to [0, 1] is called an uncertain measure if it satisfies the following axioms [12]:

Axiom 1. (Normality Axiom) $M {Γ} = 1$ for the universal set Γ.

Axiom 2. (Duality Axiom) $M {Λ} + M {Λ^{c}} = 1$ for any event Λ.

Axiom 3. (Subadditivity Axiom) For every countable sequence of events Λ₁, Λ₂, …, we have $\begin{matrix} M {⋃_{i = 1}^{\infty} Λ_{i}} \leq \sum_{i = 1}^{\infty} M {Λ_{i}} . \end{matrix}$

The triplet $(Γ, L, M)$ is called an uncertainty space. Furthermore, a product uncertain measure is defined by the fourth axiom [30]:

Axiom 4. (Product Axiom) Let $(Γ_{k}, L_{k}, M_{k})$ be uncertainty space for k = 1, 2, …. The product uncertain measure $M$ is an uncertain measure satisfying $\begin{matrix} M {\prod_{k = 1}^{\infty} Λ_{k}} = ⋀_{k = 1}^{\infty} M {Λ_{k}}, \end{matrix}$ where Λ_k are arbitrarily chosen events from $L_{k}$ for k = 1, 2, …, respectively.

Definition 1. [12]An uncertain variable is a measurable function ξ from an uncertainty space $(Γ, L, M)$ to the set of real numbers, i.e., for any Borel set B of real numbers, the set {ξ ∈ B} = {γ ∈ Γ ∣ ξ (γ) ∈ B} is an event.

Definition 2. [12]The uncertainty distribution Φ of an uncertain variable ξ is defined by $Φ (x) = M {ξ \leq x}$ for any real number x.

Definition 3. [30] The uncertain variables ξ₁, ξ₂, …, ξ_n are said to be independent if $\begin{matrix} M {⋂_{i = 1}^{n} (ξ_{i} \in B_{i})} = ⋀_{i = 1}^{n} M {ξ_{i} \in B_{i}} \end{matrix}$ for any Borel sets B₁, B₂, …, B_n of real numbers.

Definition 4. [13] An uncertain variable Φ is said to be regular if its inverse function Φ^-1 (α) exists and is unique for each α ∈ (0, 1).

Definition 5. [12] Let ξ be an uncertain variable. Then the expected value of ξ is defined by $\begin{matrix} E [ξ] = \int_{0}^{\infty} M {ξ \geq x} dx - \int_{- \infty}^{0} M {ξ \leq x} dx \end{matrix}$ provided that at least one of the two integrals is finite.

Definition 6. [12] Let ξ be uncertain variables with finite expected value e, then the variance V [ξ] = E [(ξ - e) ²].

Definition 7. [12] An uncertain variable ξ is called linear if it has a linear uncertainty distribution $\begin{matrix} Φ (x) = {\begin{matrix} 0, & if x \leq a \\ (x - a) / (b - a), & if a < x \leq b \\ 1, & if x > b \end{matrix} \end{matrix}$ denoted by $L (a, b)$ where a and b are real numbers with a < b.

Definition 8. [12] An uncertain variable ξ is called normal if it has a normal uncertainty distribution $Φ (x) = {(1 + \exp (π (e - x) / \sqrt{3} σ))}^{- 1}, x \in R$ , denoted by $N (e, σ)$ where e and σ are real numbers with σ > 0.

Theorem 1. [13] Let ξ₁, ξ₂, …, ξ_n be uncertain variables, and f a real-valued measurable function. Then f (ξ₁, ξ₂, …, ξ_n) is an uncertain variable.

Theorem 2. [13] Let ξ and η be independent uncertain variables with finite expected values. Then for any real numbers a and b, E [aξ + bη] = aE [ξ] + bE [η].

Theorem 3. [31] If ξ is an uncertain variable with finite expected value, a and b are real numbers, then, V [aξ + b] = a²V [ξ].

Theorem 4. [13] Let ξ₁ and ξ₂ be independent normal uncertain variables with uncertainty distributions $N (e_{1}, σ_{1})$ and $N (e_{2}, σ_{2})$ , respectively. Then the sum ξ₁ + ξ₂ is also normal with uncertainty distribution $N (e_{1} + e_{2}, σ_{1} + σ_{2})$ . The product of a normal uncertain variable with uncertainty distribution $N (e, σ)$ and a scalar number k > 0 is also a normal uncertain variable with uncertainty distribution $N (ke, k σ)$ .

3 Model of UMOOP

In this section, a model of UMOOP is originally established based on uncertainty theory, and how to introduce and deal with the uncertain vectors in the objective functions is described.

In order to model the uncertain multiobjective orienteering problem, a directed graph with a vertex set V = {v₁, v₂, …, v_N} and an arc set A = {(v_i, v_j) |v_i, v_j ∈ V, i ≠ j, v_i ≠ v_N, v_j ≠ v₀} is considered. The travel time between the vertex i and j is represented as t_ij, the total tour time cannot exceed T_max. Except for the starting vertex v₁ and the ending vertex v_N, each vertex has one or more nonnegative scores. When coming by a vertex, its score is gathered. In primal OP, the aim is to find a feasible tour maximizing the total score. However, decision-maker usually has different types of preferences for the vertex to be visited in practice, and these preferences can’t meet at the same time. In other words, vertex may have more than one score corresponding to different preferences, which are conflicted with each other. Therefore, a multiobjective situation needs to be considered. Besides, the scores of each vertex are actually not inherent, generally decided by the decision-makers or some experts. Actually, the scores of the vertexes are usually uncertain, and different scores may be decided by different decision-makers for the same vertex. Once the scores are given, they may change over time due to the environmental factors.

To characterize the uncertainty in the process of determining the vertex scores, the uncertainty vectors are introduced. Assume vertex scores vectors ξ ₁, ξ ₂, …, ξ _K are independent uncertain vectors with uncertainty distributions Φ₁, Φ₂, …, Φ_K, respectively. The uncertain objective functions can be denoted as $\begin{matrix} f_{k} (x, ξ_{k}) = \sum_{i = 2}^{N - 1} \sum_{j = 2}^{N} ξ_{k}^{i} x_{ij} (i \neq j, k = 1, \dots, K) . \end{matrix}$

Then, the mathematical model of the UMOOP is defined as the form: $\begin{matrix} max F (x, ξ) = (f_{1} (x, ξ_{1}), \dots, f_{K} (x, ξ_{K})) \\ s . t . \sum_{j = 2}^{N} x_{1 j} = \sum_{i = 1}^{N - 1} x_{iN} = 1; \end{matrix}$ (1) $\sum_{i = 1}^{N - 1} x_{ik} = \sum_{j = 2}^{N} x_{kj} \leq 1; \forall k = 2, \dots, N - 1$ (2) $\sum_{i = 1}^{N - 1} \sum_{j = 2}^{N} t_{ij} x_{ij} \leq T_{\max};$ (3) $2 \leq u_{i} \leq N; \forall i = 2, \dots, N$ (4) $\begin{matrix} u_{i} - u_{j} + 1 \leq (N - 1) (1 - x_{ij}); \\ \forall i, j = 2, \dots, N \end{matrix}$ (5) $x_{ij} \in {0, 1}; \forall i, j = 1, \dots, N .$ (6) where the decision variables x_ij = 1, if and only if vertex v_j is visited immediately after the vertex v_i, 0 otherwise. The uncertain objective functions are determined together by the feasible solution x and a series of uncertain vectors ξ _k, all the uncertain vectors defined on the same uncertainty space $(Γ, L, M)$ . Constraint (1) ensures that each tour starts from vertex v₁ and ends at vertex v_N. That all the vertexes must be visited at most once is guaranteed by the constraint (2). Constraint (3) means that the time cost of each tour can’t exceed the maximum time limit T_max. Auxiliary variables u_i represent the position of the vertex v_i in the tours. Constraints (4) and (5) are subtour elimination constraints, obliterating those irrational tours. To simplify the said, a feasible set x ∈ D is introduced to denote that decision variables x meet the constraints (1) to (6). The problem UMOOP can be represented in other forms: $\begin{matrix} max_{x \in D} F (x, ξ) = (f_{1} (x, ξ_{1}), \dots, f_{K} (x, ξ_{K})) . \end{matrix}$

Since each objective function comprises a series of uncertain vectors, it cannot be directly dealt with traditional multiobjective optimization theory. In the existing literatures, expected-value efficient solution is a basic and commonly used concept for a long term decision-making, but some low objective values may be obtained in the next plan because of the dispersion of the uncertain variables. Therefore, we propose a practical method by defining efficient solution with belief degree, which inspired by the Kataoka criterion and the ‘worst-case-oriented’ philosophy. In the method, the minimum profit levels are set for each objective, and each uncertain objective function is not less than the minimum level with a certain belief degree. The Pareto efficient solution is to maximize all the minimum level. The minimum profit levels μ_k are set for each objective, μ_k ≤ f_k ( x , ξ _k) , k = 1, …, K. Then the UMOOP can be transformed as follows, $\begin{matrix} max_{x \in D} μ = (μ_{1}, μ_{2}, \dots, μ_{K}) \\ s . t . μ_{k} \leq f_{k} (x, ξ_{k}), \forall k = 1, \dots, K \end{matrix}$

Since the uncertain constraints cannot define a feasible set, we refer to the Kataoka criterion controlling the belief degrees that the uncertain constraints hold to a series of confidence levels α₁, α₂, …, α_K. Then we propose the following certain model ( α -UMOOP), $\begin{matrix} max_{x \in D} μ = (μ_{1}, μ_{2}, \dots, μ_{K}) \\ s . t . M {μ_{k} \leq f_{k} (x, ξ_{k})} \geq α_{k}, \forall k = 1, \dots, K \end{matrix}$ where the objective is to maximize the minimum profit levels, and the vector μ is introduced to restrict the UMOOP with certain objectives. Then, the chance constraints are used to guarantee that the inequations f_k ( x , ξ _k) ≥ μ_k hold with belief degrees α _k. Therefore, only the chance constraints are affected by uncertainty. Next, the concept of efficient solutions with belief degrees is introduced based on the α -UMOOP.

Definition 9. (Efficient solutions with belief degrees of the UMOOP) The solution x ∈ D is an efficient solution with belief degree vector α = (α₁, α₂, …, α_K) ^T ∈R^K to the UMOOP, if it is an Pareto efficient solution to the α -UMOOP.

In the section, model of UMOOP is established, and the concept of efficient solution with belief degree is defined through Kataoka criterion and the ‘worst-case-oriented’ philosophy. Next, the main task is to solve the Pareto efficient solutions to the α -UMOOP, whose constraints contain uncertain vectors.

4 Efficient solutions with belief degrees of the UMOOP

In this section, we try to obtain efficient solutions with belief degrees to the UMOOP. As we can see, it is difficult to solve Pareto efficient solutions to α -UMOOP, because of the uncertain vectors. But it is not hard to see that functions f_k ( x , ξ _k) are linear, our studies show that chance constraints can be handled well by introducing two kinds of assumptions. The first is that uncertain vectors are normal uncertain vectors, and the second is that uncertain vectors are affine forms of a single uncertain variable.

Since the uncertain vectors are involved in the first assumption, some basic definitions and lemmas about the expected value and variance of the uncertain vector are given and deduced.

Definition 10. Let τ₁, τ₂, …, τ_m be independent normal uncertain variables. Then τ = (τ₁, τ₂, …, τ_m) is a standard normal uncertain vector.

Definition 11. Let τ = (τ₁, τ₂, …, τ_m) be a standard normal uncertain vector, and let x_i and σ_ij be real numbers. Then ξ is a normal uncertain vector with the form ξ = (ξ₁, ξ₂, …, ξ_n) , where each component is defined by $ξ_{i} = x_{i} + \sum_{j = 1}^{m} σ_{ij} τ_{j}, \forall i = 1, 2, \dots, n$ .

Definition 12. Let ξ be an uncertain variable and have a standard normal uncertainty distribution $Φ_{s} (x) = {(1 + \exp ((- π x) / \sqrt{3}))}^{- 1}$ , denoted by $N (0, 1)$ , then ξ is a standard normal uncertain variable.

Lemma 1. If $ξ \sim N (e, σ)$ , and $η = \frac{ξ - e}{σ}$ , then $η \sim N (0, 1)$ .

Lemma 2. Let τ = (τ₁, τ₂, …, τ_m) is a standard normal uncertain vector, and let c = (c₁, c₂, …, c_n) ^T ∈ Rⁿ be a real number vector. Uncertain vector ξ can be got through the affine operation, ξ = Aτ + b , where A = (a_ij) _n×m, b ∈ Rⁿ. Then, $c^{T} ξ \sim N (c^{T} b, ∥ c^{T} A ∥_{1})$ .

Proof. Since ξ = Aτ + b , it is evident to obtain $\begin{matrix} c^{T} ξ = \sum_{i = 1}^{n} c_{i} b_{i} + \sum_{i = 1}^{n} c_{i} a_{i 1} τ_{1} + \dots + \sum_{i = 1}^{n} c_{i} a_{im} τ_{m} . \end{matrix}$

By the formula above and Theorem 4, c ^T ξ can be regarded as the sum of a real number and m independent normal uncertain variables. Moreover, through mathematical induction, it is not hard to find that the Theorem 4 is also available when dealing with sum of finite independent normal uncertain variables.Therefore, it is unquestionable that variable c^T ξ is also normal.

Besides, by Theorems 2 and 3, the expected value $E [c^{T} ξ] = \sum_{i = 1}^{n} c_{i} b_{i} = c^{T} b$ , and the valiance $V [c^{T} ξ] = {(\sum_{j = 1}^{m} | \sum_{i = 1}^{n} c_{i} a_{ij} |)}^{2} = ∥ c^{T} A ∥_{1}^{2}$ .

Then, $c^{T} ξ \sim N (c^{T} b, ∥ c^{T} A ∥_{1})$ . The theorem is proved. □

Lemma 3. Let τ = (τ₁, τ₂, …, τ_m) be a standard normal uncertain vector, and c = (c₁, c₂, …, c_n) ^T ∈ Rⁿ be a real vector. Uncertain vector ξ can be got through the operation, ξ = Aτ + b , where A = (a_ij) _n×m, b ∈ Rⁿ. Then, $(c^{T} ξ - c^{T} b) / {‖ c^{T} A ‖}_{1} \sim N (0, 1)$ .

Proof. By Lemmas 1 and 2, Lemma 3 holds. □

Note that objective functions of UMOOP are

$f_{k} (x, ξ_{k}) = \sum_{i = 2}^{N - 1} \sum_{j = 2}^{N} ξ_{k}^{i} x_{ij} = d^{T} ξ_{k}$ (7) where the vector $d = (0, \sum_{j = 2}^{N} x_{2 j}, \sum_{j = 2}^{N} x_{3 j}, \dots,$ ${\sum_{j = 2}^{N} x_{(N - 1) j}, 0)}^{T}$ and i ≠ j, k = 1, 2, …, K. The linear objective functions can be deduced in the Equation (7), whereas it is still challenging to cope with the chance constraints. Uncertainty distributions of the uncertain vectors ξ _k are necessary. Therefore, more assumptions about the uncertain vectors ξ _k are clarified to make the model tractability. We consider two kinds of situations. The first is that the uncertain vectors ξ _k are normal uncertain vectors, and the second is the affine form of a single uncertain variable. The rest of this section is to derive the deterministic equivalence form on the premise of the two situations.

Situation 1. There exists standard normal uncertain vectors τ _k ∈ R^M, and affine functions g_k with the forms g_k (x) = A _kx + b _k, where A _k ∈ R^N×M, b _k ∈ R^N. Normal uncertain vectors ξ _k can be denoted by $ξ_{k} = g_{k} (τ_{k}) = A_{k} τ_{k} + b_{k} .$

By the Equation (7), uncertain objective functions f_k ( x , ξ _k) can be represented by f_k ( x , ξ _k) = d ^T ξ _k.

By Lemmas 1 and 2, the expected value and the valiance of the k-th objective function are E [f_k ( x , ξ _k)] = d ^T b _k and $V [f_{k} (x, ξ_{k})] = ∥ d^{T} A_{k} ∥_{1}^{2}$ , respectively. Then, the right of the chance constraints $\begin{matrix} M {f_{k} (x, ξ_{k}) ⩾ μ_{k}} = 1 - Φ_{s} (\frac{μ_{k} - d^{T} b_{k}}{∥ d^{T} A_{k} ∥_{1}}) \end{matrix}$ where Φ_s represents the uncertainty distribution of standard normal uncertain variable, which is strictly increasing function, and then we have the chance constraints for k = 1, 2, …, K, $M {f_{kitsc} (x, ξ_{kitsc}) \geq μ_{kitsc}} \geq α_{kitsc}$ , which are equivalent to $\begin{matrix} d^{T} b_{k} + Φ_{s}^{- 1} (1 - α_{k}) ∥ d^{T} A_{k} ∥_{1} \geq μ_{k} . \end{matrix}$

Thus, we obtain

$E [f_{k} (x, ξ_{k})] + ω_{k} σ [f_{k} (x, ξ_{k})] \geq μ_{k},$ (8) where $ω_{k} = Φ_{s}^{- 1} (1 - α_{k}), k = 1, \dots, K$ .

Next we continue to give some derivations under the situation 2.

Situation 2. Let η_k be an uncertain variable with a regular uncertainty distribution Φ_k, whose expected value is e_k and standard deviation v_k. And there are affine functions g_k with the forms g_k (x) = a _kη_k + b _k, where a _k > 0 , b _k ∈ R^N. Uncertain vectors ξ _k can be denoted by ξ _k = g_k (η_k) = a _kη_k + b _k.

Then the k-th objective function of the UMOOP is $\begin{matrix} f_{k} (x, ξ_{k}) = ξ_{k}^{T} d = a_{k}^{T} d η_{k} + b_{k}^{T} d . \end{matrix}$

For any given x ∈ D , we get $a_{k}^{T} d > 0$ . Then, $E [f_{k} (x, ξ_{k})] = a_{k}^{T} d e_{k} + b_{k}^{T} d$ , and $σ (f_{k} (x, ξ_{k})) = a_{k}^{T} d v_{k}$ .

Then, the right of the chance constraints $\begin{matrix} M {f_{k} (x, ξ_{k}) ⩾ μ_{k}} = 1 - Φ_{k} (\frac{μ_{k} - b_{k}^{T} d}{a_{k}^{T} d}) \end{matrix}$

Then we have the chance constraints for k = 1, 2, …, K, $M {f_{k} (x, ξ_{k}) \geq μ_{k}} \geq α_{k}$ , which are equivalent to $\begin{matrix} b_{k}^{T} d + a_{k}^{T} d e_{k} + a_{k}^{T} d v_{k} \frac{Φ_{k}^{- 1} (1 - α_{k}) - e_{k}}{v_{k}} \geq μ_{k} . \end{matrix}$

Thus, we obtain

$E [f_{k} (x, ξ_{k})] + ω_{k} σ [f_{k} (x, ξ_{k})] \geq μ_{k},$ (9) where $ω_{k} = (Φ_{k}^{- 1} (1 - α_{k}) - e_{k}) / v_{k}, k = 1, \dots, K$ .

By Equations (8) and (9), we can see that the μ_k is less than or equal to the same form E [f_k ( x , ξ _k)] + ω_kσ [f_k ( x , ξ _k)]. In the α -UMOOP, the objective is to maximize all the μ_k. Also we can know that the equation E [f_k ( x , ξ _k)] + ω_kσ [f_k ( x , ξ _k)] = μ_k holds under a certain conditions, therefore we can get the crisp deterministic equivalent form (D-UMOOP) as follows, $\begin{matrix} max_{x \in D} (E [f_{1} (x, ξ_{1})] + ω_{1} σ [f_{1} (x, ξ_{1})], \dots, \\ E [f_{K} (x, ξ_{K})] + ω_{K} σ [f_{K} (x, ξ_{K})]), \end{matrix}$ and the parameters of the D-UMOOP for different situations can be found above.

Through the above deduction, it is not hard to find that we can get efficient solutions with belief degrees to the UMOOP by solving the D-UMOOP. The D-UMOOP is essentially a multiobjective orienteering problem, harder than the OP. In the existing literatures, few algorithms for MOOP have been researched. Therefore, a discrete multiobjective algorithm for the model D-UMOOP will be designed.

5 Algorithm variation for MOOP

As a variation of OP, MOOP is typical multiobjective discrete combined optimization, which is proved to be NP-hard. A newly proposed bat algorithm famous for its accuracy and efficiency has been gradually used to tackle combinatorial optimization and scheduling problem. Nevertheless, the standard bat algorithm is not suitable for MOOP, because the updating equations are continuous in the iterations process. In the section, a discrete multiobjective bat algorithm (MOBA, Algorithm 1) is developed. Then the processes of initialization, updating and local search are introduced.

Algorithm 1
The discrete multiobjective bat algorithm

Output: A set of non-dominated solutions X_Pareto;

1: Initialization;

2: X ← non-domonated sorting (X);

3: X* ← tournament selection (X)

4: while (iter ≤ max_iter) do

5: Update by Eqs. (13) to (15);

6: ifrand > r_ithen

7: Random walk by Eqs. (16) and (17);

8: end if

9: Generate a new solution by flying randomly;

10: Multiobjective RVNS (X);

11: ifrand < A_i & X_i dominated Xthen

12: Accept the new solutions;

13: Increase r_i and reduce A_i;

14: end if

15: X_Pareto ← non-domonated sorting (X);

16: Update X8;

17: iter = iter + 1;

18: end while

5.1 Initial solution construction

In the algorithm, each artificial bat has two important kinds of information, the position and the velocity. The initial velocity has the same length as the corresponding position, and adopts binary codes, if there is a velocity vector $V_{i} = (V_{i}^{1}, V_{i}^{2}, \dots, V_{i}^{N})$ , and $V_{i}^{m} = 1$ , the corresponding element $P_{i}^{m}$ of the position vector $X_{i} = (X_{i}^{1}, X_{i}^{2}, \dots, X_{i}^{N})$ will change after an operation, otherwise not.

In the initialization phase, the velocity is built arbitrarily. Each position represents a feasible route, which starts from the vertex v₁, and ends at the vertex v_N. Each vertex cannot be visited repeatedly, and the time cost of each route cannot exceed the maximal time limitation. Therefore, during constructing the solution, we use the vertex numbers from 1 to N to denote all the vertex. At the beginning, each position just includes numbers 1 and N. Then, the unvisited vertex’s number is inserted randomly before the N until none can be inserted because of the maximal time limitation.

5.2 The process of updating

In traditional bat algorithm, the rules of positions and velocities updating are given by these equations, $f_{i} = f_{\min} + (f_{\max} - f_{\min}) β,$ (10) $V_{i}^{t + 1} = V_{i}^{t} + (X_{i}^{t} - X^{*}) f_{i},$ (11) $X_{i}^{t + 1} = X_{i}^{t} + V_{i}^{t + 1},$ (12) where f is the frequency in a range of [f_min, f_max], and β is a random vector with a range [0, 1]. The x^∗ is the current best location of the bats. The continuous updating form is based on the Equations (11) and (12), but it is not suitable for the OP. For this reason, some operations are redefined, and the updating equations are adjusted, $V_{i}^{t + 1} = sig (V_{i}^{t} + (X_{i}^{t} \circ X^{*}) f_{i}),$ (13) $X_{i}^{t + 1} = X_{i}^{t} ⊙ V_{i}^{t + 1},$ (14) $V_{i}^{t + 1} = X_{i}^{t + 1} \circ X_{i}^{t},$ (15) where the X ∘ Y is defined as an operation that if the element of the X is not in Y, then the corresponding element of the V becomes 1, otherwise 0. For example, let X = (2, 11, 8, 13, 10, 20) and X^∗ = (3, 11, 6, 10, 15, 14, 18, 7), then X ∘ X^∗ = (1, 0, 1, 1, 0, 1). The operation X ⊙ V means that if the corresponding element of the X is 1, then we use a random vector number not in X to replace it after the operation. We also use an example to explain the function sig (), D = {d₁, d₂, …, d_n} and V = (v₁, v₂, …, v_n), V = sig (D), $\begin{matrix} v_{i} = {\begin{matrix} 1 & if rand (0, 1) < sigmoid (d_{i}) \\ 0 & if rand (0, 1) \geq sigmoid (d_{i}) \end{matrix} \end{matrix}$ where the sigmoid (d) =1/(1 + e^-d).

In addition a new solution for each bat is generated locally using discrete random walk as follows $X_{i}^{t + 1} = X_{i}^{t} ⊙ sig (\in A),$ (16) $V_{i}^{t + 1} = X_{i}^{t + 1} \circ X_{i}^{t} .$ (17)

After the process of updating, a judgement about the maximal time limitation is made, then we ensure the path feasible by deleting or inserting point randomly.

5.3 Local search

In the above, the process of initialization and discrete updating are given to obtain various feasible paths. Next, an approach of local search is introduced to improve the path, which is called reduced variable neighborhood search [32]. In order to solve MOOP, a multiobjective reduced variable neighborhood (MORVNS) search is designed. The objectives in the D-UMOOP are transformed into a single objective by introducing a random weight vector c = (c₁, c₂, …, c_K), where $\sum_{k = 1}^{K} c_{k} = 1, c_{k} > 0$ .

Then Four kinds of neighborhood structures are chosen to realize local search, and some brief description is provided about four structures, referred to Fig. 1. Randomly insert unvisited vertex: a unvisited vertex is chosen randomly, then it is inserted into the solution between every two adjacent vertexes until the maximal time limitation is exceeded. The neighborhood structure aims to add the unvisited vertex to the path getting the higher profit. Exchange vertex: an unvisited vertex with a higher fitness value is chosen randomly, then the vertex in the path with a lower fitness value is exchanged in turn by the unvisited vertex chosen until the new path is feasible. Randomly reinsert visited vertex: a vertex in the path is reinserted until the new path is shorter than the former one. Path Invert: we use the familiar operation 2-opt to make the path shorter.

Fig.1

The neighborhood structures in the MORVNS.

In order to demonstrate the applicability of MOBA algorithm, 67 OP benchmark problems and 6 biobjective OP benchmark problem (Table 1) are introduced.

Table 1

Description of benchmark problems

Sort	Dataset	Benchmark problems	Amount
OP	1	Tsiligirides 1_P21	11
	2	Tsiligirides 1_P32	18
	3	Tsiligirides 1_P33	20
	4	Chao 1_P32	18
BOOP	5	Schilde 2_P64_(t015,t050,t080)	3
	6	Schilde 2_P66_(t005,t070,t130)	3

First, 10 independent runs are made in the experimentation on Dataset 1-4, the algorithm is set including 10 artificial bats and the maximal iterative time is 10. Then two statistical parameters are introduced to test the performance of the algorithm. The first parameter is relative percentage error (RPE), showing whether the best known solution has been found, its mathematical formula can be listed as follows, RPE = (S_known - S_best)/S_known ∗ 100, where the S_known is the best known solution and S_best is the best solution in the 10 independent runs. The second parameter is standard deviation (Std. Dev.), which is used to quantitatively measure the robustness of the algorithm. After the running, statistical analysis is made, the results are compared with some basic algorithms in Table 2.

Table 2

Comparisons with previous studies’s results on Dataset 1-4

Algorithms	1	2	3	4	Avg
RPE	GA	0	0	0	0	0
	ACO	0	0	0	0	0
	VNS	0	0	0	0	0
	StPSO	0.14	0	0.15	0	0.07
	MOBA	0	0	0	0	0
Std. Dev.	GA	1.29	2.63	3.38	1.36	2.17
	ACO	0.59	1.66	0.72	0.48	0.86
	VNS	2.73	2.49	6.04	2.82	3.52
	StPSO	2.13	3.78	4.43	1.94	3.1
	MOBA	0	0.11	0	0.16	0.07

By the results, we know that the best known solutions can be solved by the algorithm in all 67 OP benchmark problems, and computational results also show that it provides competitive results for the single objective problem than other algorithms.

In order to further verify the performance of the algorithm, some experiment on Dataset 5 and 6 are performed. the algorithm is set including 100 artificial bats and the maximal iterative time is 200. Then we compare with the results of ACO [33]. On the benchmark problems 2_P64_t015, 2_P66_t005, and 2_P66_t130, we have obtained the same results with ACO, and the objective values are (96, 253), (10, 97), and (1680, 916), respectively. Computational results on the problems 2_P64_t050, 2_P64_t080, and 2_P66_t070 are shown in Fig. 2, which are competitive comparing with the ACO.

Fig.2

Results of some multiobjective benchmark problems.

In the section, a discrete multiobjective bat algorithm is developed and tested on the 73 benchmark problems. The result shows that the MOBA has the better capabilities and robust at the same time. Consequently, the algorithm can be used to solve the D-UMOOP problem. Next, a practical application is provided using the theoretical result and algorithm in the paper.

6 Case study

We illustrate detailedly the practical application of the efficient solutions with belief degrees and the MOBA by dealing with the unmanned aerial vehicle (UAV) reconnaissance mission planning problem.

6.1 The uncertain UAV reconnaissance mission planning problem

The actual case and data are customarily unobtainable for the reason of security. A situation is considered where a tactical UAV in a base is assigned to complete a reconnaissance mission. There are a lot of targets so that a single UAV can’t reach all for maximum range limitation. Consequently, when planning a reconnaissance mission for the UAV, the decision-maker must consider the value and security of the target, then some of the targets are chosen based on the value and security information to maximize the mission profit on the premise of security. Whereas, the value and security coefficients of each target are hard to obtain through experiments, and have to be evaluated by the commanders or skilled pilots of the UAV. Coefficients of the targets will be different and uncertain affected by the evaluators or the battlefield intelligence. Then, uncertainty variables are used to model uncertainties of the expert belief degrees in the process of evaluating.

In Fig. 3, the sketch map of the mission area and relative coordinates of the base and targets are given, where the UAV base is denoted by number 1 and the targets 2 to 16 respectively. Only an available UAV is for the reconnaissance mission. Bound by the fuel quantity, UAV’s maximum range D_max is 200 km, which the distance of the flight path cannot exceed. When implementing the reconnaissance mission, a UAV takes off from the base and visits the targets as much as possible, returns to the base finally. In the RMPP, each target has its value coefficient and security coefficient, and the vectors of target value coefficients are denoted by uncertain vector ξ = (0, ξ₂, …, ξ₁₆) ^T and security coefficients are denoted by η = (0, η₂, …, η₁₆) ^T. Then let P ( x , ξ ) and S ( x , η ) be the profit function and security function of the reconnaissance mission, respectively. Once the target is scouted, its value coefficient is added to the profit, and meanwhile deducting its threaten from the security. The value coefficients and security coefficients of all the targets are ranging from 0 to 10. Then the profit function can be denoted by P ( x , ξ ) = d ^T ξ , and the security function S ( x , η ) = d ^T η + 10 × (16 - d ^T 1 ), where $d = {(0, \sum_{j = 2}^{16} x_{2 j}, \dots, \sum_{j = 2}^{16} x_{16 j})}^{T}$ . Then, we can model uncertain UAV reconnaissance mission planning problem as the following form (URMPP), $\begin{matrix} max (d^{T} ξ, d^{T} η + 10 \times (16 - d^{T} 1)) \\ s . t . \sum_{j = 2}^{16} x_{1 j} = \sum_{i = 2}^{16} x_{i 1} = 1; \end{matrix}$ (18) $\sum_{i = 1}^{16} x_{ik} = \sum_{j = 1}^{16} x_{kj} \leq 1; \forall k = 2, \dots, 16$ (19) $\sum_{i = 1}^{16} \sum_{j = 1}^{16} d_{ij} x_{ij} \leq 200;$ (20) $2 \leq u_{i} \leq 16; \forall i = 2, \dots, 16$ (21) $\begin{matrix} u_{i} - u_{j} + 1 \leq (16 - 1) (1 - x_{ij}); \\ \forall i, j = 2, \dots, 16 \end{matrix}$ (22) $x_{ij} \in {0, 1} . \forall i, j = 1, \dots, 16$ (23) where the objective functions are to maximize the uncertain profit and security of the reconnaissance mission. Constraint (18) means that the UAV takes off from the base and returns back finally, and all the targets must be scouted at most once is guaranteed by the constraint (19). The maximum range of the UAV is ensured by the constraint (20). Constraints (21) and (22) are subtour elimination constraints, obliterating the irrational flight paths. Whether UAV flights from target i to j or not is decided by the variables x_ij = 1 or 0.

Fig.3

The sketch map of the mission area.

In the problem, the objective functions are affected by the uncertain variables, therefore it is hard to deal with the uncertain biobjective orienteering problem using the traditional multiobjective theory. Some attempts can be adopted to solve it, deduced in the Section 4. By Definition 9, a solution x representing a feasible flight path is the efficient solution with belief degrees of the uncertain biobjective UAV reconnaissance mission planning problem, if it is a Pareto efficient solution to the following problem ( α -URMPP): $\begin{matrix} max_{x \in D} & μ & = (μ_{1}, μ_{2}) \\ s . t . & M & {d^{T} ξ \geq μ_{1}} \geq α_{1} \\ M & {d^{T} η + 10 \times (16 - d^{T} 1) \geq μ_{2}} \geq α_{2} \end{matrix}$ where x ∈ D means that all the solution should satisfy the constraints during the flight, and the profit function and the security function are not less than μ₁ and μ₂ with a belief degree α₁ and α₂, respectively.

Then, we can deduce the crisp deterministic equivalent form (D-URMPP) of the problem as follows, $\begin{matrix} max_{x \in D} (E [P] + ω_{1} σ [P], E [S] + ω_{2} σ [S]), \end{matrix}$ where the parameters for two situations can be obtained in Section 4.

6.2 Test and analysis

Scenario 1. Assuming that uncertain vectors ξ and η are affine forms of the uncertain variable ζ₁ and ζ₂, can be denoted by ξ = a ₁ζ₁ + b ₁ and η = a ₂ζ₂ + b ₂. Let ζ₁ be a linear uncertain variable with an uncertainty distribution $L (- 1, 1)$ , and let ζ₂ be a normal uncertain variable with an uncertainty distribution $N (0, 1)$ . a ₁ = a ₂ = (0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) ^T and b ₁ = (0, 8, 5, 8, 3, 3, 6, 8, 6, 5, 5, 6, 8, 5, 6, 6) ^T, b ₂ = (10, 2, 5, 2, 7, 7, 4, 2, 4, 5, 5, 4, 2, 5, 4, 4) ^T, α₁ = α₂ = 0.9. Since ω = (Φ^-1 (1 - α) - e)/v, we can obtain that ω₁ = -2.4 and ω₂ = -1.2114. By Section 2, the expected value and variance of the uncertain variables ζ₁ and ζ₂ can be obtained. Then, we solve the problem D-URMPP using the discrete multiobjective bat algorithm developed in Section 5. The parameters in the MOBA are given in Table 3.

Table 3
Parameters in the MOBA

Parameters Values Parameters Values

Population numbers 20 Frequency minimum 0

Iteration numbers 100 Frequency maximum 20

Loudness rate 0.9 Pulse emission rate 0.9

Parameters	Values	Parameters	Values
Population numbers	20	Frequency minimum	0
Iteration numbers	100	Frequency maximum	20
Loudness rate	0.9	Pulse emission rate	0.9

By using the MOBA algorithm, we will obtain Pareto efficient solutions to D-URMPP, which are also efficient solutions with belief degrees to the URMPP. In Table 4, we list all the efficient solutions with belief degrees to the uncertain RMPP, and each solution represents an alternative flight path. For instance, if mission mean profit is required greater than 140, then solutions S_1.1, S_1.2, S_1.4, S_1.5 should be eliminated; if the mean security function is required greater than 300, then the solutions S_1.8 should be eliminated. Further, if the decision-maker considers both their mean and standard deviation, then the solutions S_1.3, S_1.6, S_1.7 may be more appropriate for these scenarios.

Table 4

Solutions in the Scenario 1

Solution	Objective 1	Objective 2	E [P]	E [S]	σ [P]	σ [S]
S_1.1:(1,6,14,11,12,8,13,7,1)	99.4	381.5	105	390	7/3	7
S_1.2:(1,5,6,14,12,7,13,8,9,1)	118.6	370.3	125	380	8/3	8
S_1.3:(1,5,10,3,6,14,11,12,7,9,1)	142.8	359.1	150	370	3	9
S_1.4:(1,6,14,12,2,8,13,7,9,1)	123.6	360.3	130	370	8/3	8
S_1.5:(1,6,14,12,7,13,8,9,10,1)	123.6	360.3	130	370	8/3	8
S_1.6:(1,5,6,14,3,10,9,8,13,7,1)	147.8	349.1	155	360	3	9
S_1.7:(1,6,14,3,10,9,4,8,13,7,1)	162.8	329.1	170	340	3	9
S_1.8:(1,5,6,14,3,10,15,4,9,1)	163.6	270.3	170	280	8/3	8

Scenario 2. In order to study the influence of the uncertainty distribution, we change the uncertainty distributions of ξ₂, ξ₈, ξ₁₃, ξ₄, which are $L_{1} (6, 10)$ in Scenario 2. We can obtain that ω₁ = -2.4 and ω₂ = -1.2114.

Then we list the Pareto efficient solutions in the Table 5. Comparing the solutions of the first two scenarios, we can see that most of the solutions are uniform, but when uncertainty distributions of some targets are changed, the solutions S_1.5 and S_1.6 are not in scenario 2, and a new solution S_2.4 appears. As we can see, solutions S_1.2 and S_1.4 contain targets (2, 8, 13), but solution S_2.3 not. Consequently, efficient solutions with belief degrees theory can make UAV not scout the targets as far as possible, whose uncertain coefficients have large variation range. This character may prevent the solutions from uncertainty to some extent.

Table 5

Solutions in the Scenario 2

Solution	Objective 1	Objective 2	E [P]	E [S]	σ [P]	σ [S]
S_2.1:(1,6,14,11,12,8,13,7,1)	97.8	381.5	105	390	3	7
S_2.2:(1,5,6,14,12,7,13,8,9,1)	117	370.3	125	380	10/3	8
S_2.3:(1,5,10,3,6,14,11,12,7,9,1)	142.8	359.1	150	370	3	9
S_2.4:(1,5,6,14,11,12,7,9,10,1)	123.6	360.3	130	370	8/3	8
S_2.5:(1,5,6,14,3,10,9,8,13,7,1)	146.2	349.1	155	360	11/3	9
S_2.6:(1,6,14,3,10,9,4,8,13,7,1)	160.4	329.1	170	340	4	9
S_2.7:(1,5,6,14,3,10,15,4,9,1)	162.8	270.3	170	280	3	8

Scenario 3. In order to study the influence of the belief degrees, we change belief degree α₁, it has a different value between scenario 1 and scenario 3, 0.9 and 0.96, respectively. We can obtain that ω₁ = -2.76 and ω₂ = -1.2114.

Then Pareto efficient solutions are listed in the Table 6, some comparison and analysis are made to study the influence of belief degree. In scenario 3, we change the belief degree α₁ from 0.9 to 0.96 on the base of scenario 1, then solution S_3.5 appears in the solution set, thereby belief degree can be regarded as a tolerance degree to the uncertainty, adjusted by the decision makers in practical application.

Table 6

Solutions in the Scenario 3

Solution	Objective 1	Objective 2	E [P]	E [S]	σ [P]	σ [S]
S_3.1:(1,6,14,11,12,8,13,7,1)	98.7	381.5	105	390	7/3	7
S_3.2:(1,5,6,14,12,7,13,8,9,1)	117.6	370.3	125	380	8/3	8
S_3.3:(1,5,10,3,6,14,11,12,7,9,1)	141.7	359.1	150	370	3	9
S_3.4:(1,6,14,12,2,8,13,7,9,1)	122.6	360.3	130	370	8/3	8
S_3.5:(1,5,6,14,11,12,7,9,10,1)	122.6	360.3	130	370	8/3	8
S_3.6:(1,6,14,12,7,13,8,9,10,1)	122.6	360.3	130	370	8/3	8
S_3.7:(1,5,6,14,3,10,9,8,13,7,1)	146.7	349.1	155	360	3	9
S_3.8:(1,6,14,3,10,9,4,8,13,7,1)	161.7	329.1	170	340	3	9
S_3.9:(1,5,6,14,3,10,15,4,9,1)	162.6	270.3	170	280	8/3	8

Next, an example under the situation 2 is taken to make a theoretical analysis. We can know that $ω_{k} = (Φ_{k}^{- 1} (1 - α_{k}) - e_{k}) / v_{k}$ and standard deviation v_k > 0 hold. Then, integrating the ω_k in the interval α_k ∈ (0, 1), we have $\int_{0}^{1} ω_{k} d α_{k} = \int_{0}^{1} (Φ_{k}^{- 1} (1 - α_{k}) / v_{k} - e_{k} / v_{k}) d α_{k} = 0$ . Since the distribution Φ_k is regular,and function $Φ_{k}^{- 1} (α_{k})$ is increasing, then ω_k is decreasing in the interval α_k ∈ (0, 1). Since equation $\int_{0}^{1} ω_{k} d α_{k} = 0$ holds, there exists a value α₀ making equation ω_k = 0 hold, where α₀ = 1 - Φ (e_k). It is evident that ω_k < 0, α_k ∈ (α₀, 1) holds. Furthermore, in D-UMOOP, terms E [f_k ( x , ξ )] and σ [f_k ( x , ξ )] are also nonnegative. In brief, the expected values and standard deviations of the uncertain objectives are considered in the crisp deterministic equivalent form, which is similar with penalty method. The standard deviation can be regarded as the penalty item, and penalty factor is the function of the belief degree. When a bigger belief degree or standard deviation is set, the objective value will become lower, this is the primary reason that when choosing different the parameters, the Pareto efficient solutions change. In conclusion, the theoretical analysis is consistent with the experimental results.

7 Conclusions

This paper first proposed a UMOOP model based on uncertainty theory, considering uncertain factors in the objective functions. Besides, a concept called efficient solutions with belief degrees has been defined, and we have transformed the α -UMOOP into the D-UMOOP on the premise of two assumptions. Derivations have proved that efficient solutions to the D-UMOOP were efficient solutions with belief degrees to the UMOOP.

Then, the proposed MOBA was first adapted to the D-UMOOP using a discrete updating rules. A multiobjective reduce variable neighborhood is designed to improve the ability in exploitation. The algorithm is tested on the 73 benchmark problems to experimentally investigate the performances.

Finally, the theoretical result and algorithm in the paper have successfully applied in the UAV reconnaissance mission planning problem. Both mission profit and security are regarded as uncertain factors. Then a model of URMPP has been established, and transformed into the D-URMPP. Pareto efficient solutions are obtained through the MOBA representing the alternative flight paths. Uncertainty distributions and belief degrees have been changed to study the influences, and the theoretical analysis demonstrated that our proposed theories and algorithm are effective and consistent with the experimental results.

Footnotes

Acknowledgments

This work was supported by National Natural Science Foundation of China (No. 61502521).

References

Vansteenwegen

, Souffriau

and Oudheusden

D.V.

, The orienteering problem: A survey, European Journal of Operational Research 209(1) (2011), 1–10.

Gunawan

, Lau

H.C.

and Vansteenwegen

, Orienteering problem: A survey of recent variants, solution approaches and applications, European Journal of Operational Research 255(2) (2016), 315–332.

Tang

and Miller-Hooks

, Algorithms for a stochastic selective travelling salesperson problem, Journal of the Operational Research Society 56(4) (2005), 439–452.

İlhan

, Iravani

S.M.R.

and Daskin

M.S.

, The orienteering problem with stochastic profits, Iie Transactions 40(4) (2008), 406–421.

Evers

, Glorie

, Suzanne

V.D.S.

and Barros

A.I.

, and H. Monsuur, A two-stage approach to the orienteering problem with stochastic weights, Computers & Operations Research 43(4) (2014), 248–260.

Papapanagiotou

and Montemanni

, Objective function evaluation methods for the orienteering problem with stochastic travel and service times, Journal of Applied Operations Research 6(1) (2014), 16–29.

Zhang

, Ohlmann

J.W.

and Thomas

B.W.

, A priori orienteering with time windows and stochastic wait times at customers, European Journal of Operational Research 239(1) (2014), 70–79.

Verbeeck

, Vansteenwegen

and Aghezzaf

E.H.

, Solving the stochastic time-dependent orienteering problem with time windows, European Journal of Operational Research 255(3) (2016), 699–718.

Angelelli

, Archetti

, Filippi

and Vindigni

, The probabilistic orienteering problem, Computers & Operations Research 81(C) (2017), 269–281.

10.

Kahneman

and Tversky

, Prospect theory: An analysis of decisions under risk, Journal of the Econometric Society 47(2) (1979), 263–291.

11.

Liu

, Why is there a need for uncertainty theory, Journal of Uncertain Systems 6(1) (2012), 3–10.

12.

Liu

, Uncertainty theory. 2. Springer, 2007.

13.

Liu

, Uncertainty Theory - A Branch of Mathematics for Modeling Human Uncertainty, Springer, 2010.

14.

Liu

, Toward uncertain finance theory, Journal of Uncertainty Analysis & Applications 1(1) (2013), 1–15.

15.

Lio

and Liu

, Uncertain data envelopment analysis with imprecisely observed inputs and outputs, Fuzzy Optimization and Decision Making (2017), 1–17.

16.

Yao

and Liu

, Uncertain regression analysis: An approach for imprecise observations, Soft Computing (2017), 1–4.

17.

Liu

, Extreme value theorems of uncertain process with application to insurance risk model, Soft Computing 17(4) (2013), 549–556.

18.

Yang

and Gao

, Linearquadratic uncertain differential game with application to resource extraction problem, IEEE Transactions on Fuzzy Systems 24(4) (2016), 819–826.

19.

Yang

, Ni

and Zhang

, Stability in inverse distribution for uncertain differential equations, Journal of Intelligent & Fuzzy Systems 32(3) (2017), 2051–2059.

20.

Zheng

, Yuan

, Wang

and Chen

J.-F.

, Study on twostage uncertain programming based on uncertainty theory, Fuzzy Optimization and Decision Making 28(3) (2017), 633–642.

21.

Zheng

, Yuan

, Wang

and Mao

, The information value and the uncertainties in two-stage uncertain programming with recourse, Soft Computing 4 (2017), 1–11.

22.

Liu

, Totally ordered uncertain sets, Fuzzy Optimization and Decision Making (2017), 1–11.

23.

Wang

, Guo

, Zheng

and Wang

, Uncertain multiobjective traveling salesman problem, European Journal of Operational Research 241(2) (2015), 478–489.

24.

Guo

, Wang

, Zheng

and Wang

, An approach for UAV reconnaissance mission planning problem under uncertain environment, International Journal of Imaging & Robotics 14(3) (2014), 1–15.

25.

Wang

, Zheng

, Guo

and Huang

, Uncertain UAV ISR mission planning problem with multiple correlated objectives, Journal of Intelligent & Fuzzy Systems 32(1) (2017), 321–335.

26.

Guo

, Wang

, Zheng

and Wang

, Uncertain multiobjective redundancy allocation problem of repairable systems based on artificial bee colony algorithm, Chinese Journal of Aeronautics 27(6) (2014), 1477–1487.

27.

Zheng

, Yuan

, Wang

and Liao

, Relations among efficient solutions in uncertain multiobjective programming, Fuzzy Optimization and Decision Making 16(3) (2017), 329–357.

28.

Zheng

, Yuan

, Wang

and Liao

, Efficient solution concepts and their application in uncertain multiobjective programming, Applied Soft Computing 56 (2017), 557–569.

29.

Yang

X.S.

, Nature-Inspired Optimization Algorithms, Elsevier, 2014.

30.

Liu

, Some research problems in uncertainty theory, Journal of Uncertain Systems 3(1) (2009), 3–10.

31.

Liu

, Uncertainty theory, 4nd ed., 2015, Elsevier.

32.

Mladenovic

and Hansen

, A variable neighborhood search, Computers & Operations Research 24(11) (1997), 1097–1100.

33.

Schilde

, Doerner

K.F.

, Hartl

R.F.

and Kiechle

, Metaheuristics for the bi-objective orienteering problem, Swarm Intelligence 3(3) (2009), 179–201.

Uncertain multiobjective orienteering problem and its application to UAV reconnaissance mission planning

Abstract

Keywords

1 Introduction

2 Preliminary

3 Model of UMOOP

5.2 The process of updating

6.1 The uncertain UAV reconnaissance mission planning problem

Table 3 Parameters in the MOBA Parameters Values Parameters Values Population numbers 20 Frequency minimum 0 Iteration numbers 100 Frequency maximum 20 Loudness rate 0.9 Pulse emission rate 0.9

Footnotes

Acknowledgments

References

Table 3
Parameters in the MOBA

Parameters Values Parameters Values

Population numbers 20 Frequency minimum 0

Iteration numbers 100 Frequency maximum 20

Loudness rate 0.9 Pulse emission rate 0.9