{'fraction_non_alphanumeric': 0.03643874794767226, 'fraction_numerical': 0.012552301255230125, 'mean_word_length': 4.378578550064093, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
RISK-AVERSE STOCHASTIC ORIENTEERING PROBLEMS

In this study, we consider risk-averse orienteering problems with stochastic travel times or stochastic rewards. In risk-neutral orienteering problems, the objective is generally to maximize the expected total reward of visited notes. However, due to uncertain travel times or uncertain rewards, the dispersion in total reward collected may be large, which necessitates an approach that minimizes the dispersion (risk) in addition to maximizing the expected total reward. To handle this, for the orienteering problems with stochastic travel times or stochastic rewards, we suggest two different formulations with an objective of coherent measures of risk. For both problems, we conduct an experimental study using two different coherent measures of risk, which have been extensively used in the literature, and compare the results. The computational results show that, in both models suggested and under both risk measures used, the decision maker is able to obtain a tour with expected total reward being close to the expected total reward of risk-neutral solution, however with a significant decrease in the standard deviation of total reward.


INTRODUCTION
Orienteering Problem (OP) aims to find a tour that starts at a depot node, visits each node in a subset of all nodes exactly once and ends at the depot node. Different from the travelling salesman problem, not all the nodes are required to be visited, the tour should be completed within a given time limit, and each node has an associated reward. The objective of OP is to maximize the total reward collected from the visited nodes. The orienteering problem is first introduced by Tsiligirides [1] and Golden et al. [2], since then has been studied extensively in the literature. The reader is referred to the survey papers Vansteenwegen et al. [3] and Gunawan et al. [4] for details.
The OP has many different applications in many different areas, e.g. logistics, traffic problems and defense industry. In the literature, there is a large number of studies focusing on deterministic OP, however, the number of studies on stochastic variant is limited. In deterministic OP, the profit and service time of each node and the travel times between the nodes are assumed to be deterministic. However, this assumption may not be realistic for some real life applications, for example, in a logistics system, the congestion on the road network leads to random travel times or customers may have stochastic demands.
The stochastic OP is first introduced by Teng et al. [5], where a two-stage stochastic programming formulation with stochastic travel and service times is proposed. The tour is constructed in the first stage before observing the uncertainty, and after the uncertainty is resolved, the time of the tour in excess of the time limit is computed in the second stage. The objective is to maximize the expected profit of the tour, which is total reward of the tour minus the expected penalty of exceeding the time limit. A twostage problem with stochastic travel and service times is also considered by Campbell et al. [6], however, with different penalty cost definition. A penalty is incurred if a customer in the first stage tour is not visited due to resolved uncertainty. Tang and Miller-Hooks [7] suggest a risk-averse orienteering model with stochastic service times, where risk-aversion is modeled by a chance constraint ensuring that the probability of the tour not being completed within the time limit does not exceed a threshold probability. Differently, Ilhan et al. [8] study the case of stochastic rewards and propose a model maximizing the probability that the collected total reward will exceed a target level. This model constitutes a risk-averse formulation where risk-aversion is controlled by changing the target level.
Most of the studies on stochastic OP consider only stochastic travel times. Evers et al. [9] propose a two-stage stochastic programming model where the tour constructed in the first stage can be aborted in the second stage before reaching the depot node due to random travel times. The objective is to maximize the expected total reward of visited nodes. A similar model is suggested by Shang et al. [10], however with less number of variables and constraints. A chance constrained model with stochastic travel times is proposed by Varakantham and Kumar [11]. With chance constraint, the probability that the tour will not be completed within the time limit is forced to be less than some threshold. Dolinskaya et al. [12] propose a dynamic OP with stochastic travel times, where the uncertainty is resolved gradually and the tour is constructed dynamically based on resolved uncertainty. All these studies consider time independent stochastic travel times. On the other hand, in Hoong et al. [13], random travel times are assumed to be time dependent. Here, the travel time from node a to node b depends on the arrival time at node a. Additionally, the decision maker is supposed to be risk-aware and this is taken into account by maximizing total expected utilities of the visited nodes subject to a chance constraint which ensures the tour will be completed within the time limit with at least a threshold probability. Varakantham et al. [14] extend the study in [11] by considering time dependent stochastic travel times. Verbeeck et al. [15] also work on an OP with stochastic time dependent travel times and with time windows.
A different version of OP, which has an application in pharmaceutical industry, is considered by Zhang et al. [16]. In that problem context, the sales representatives visit doctors and the time that a sales representative waits at the office of a doctor before seeing him/her, called as waiting time, is assumed to be random. The problem is modeled as a two-stage stochastic programing model with time windows. The tour is constructed in the first stage. In the second stage, there are two different recourse actions: a doctor in the tour can be skipped if the representative cannot arrive within the time window of doctor or the representative may renege from or balk the queue if the queue at the doctor is long upon arrival. The objective is to maximize the expected total reward of the tour. This study is extended in [17] by allowing the routing and queuing decisions to be made dynamically based on the realized waiting times.
The literature on the stochastic OP assumes, in general, the decision maker is risk-neutral. Therefore, there is a very limited number of studies focusing on risk-averse decision makers. The risk-averse orienteering studies in the literature can be categorized into three groups based on the modeling approach of the risk-aversion: (i) using probabilistic objective functions [8], (ii) using chance constraints [7], [11], [13], (iii) using utility functions [13]. However, chance constraints are in general nonconvex and additionally may ignore the deviation of the extreme losses (or costs) and the utility functions are difficult to interpret (see, for instance, Shapiro et al. [18]). A modern approach in the literature to model risk-aversion is to use coherent measures of risk. The coherent measures of risk are first introduced by Artzner et al. [19] and the theoretical properties of the stochastic optimization problems with an objective of coherent measure of risk are studied in Ruszczynski and Shapiro [20]- [21].
In general, the objective in a risk-neutral stochastic OP is to maximize the expected total reward of the visited nodes. However, due to the uncertainty in the travel times or the rewards of the nodes, the deviation in the total reward collected may be large. In this study, we do not only aim to maximize the expected total reward of visited nodes but also to minimize the dispersion of total reward. Therefore, the decision maker is assumed to be risk-averse and we use coherent measures of risk to model the risk-aversion. To the best of our knowledge, this is the first study considering coherent measures of risk in OP framework. We focus on two versions of the problem: (i) with stochastic rewards and (ii) with stochastic travel times. For both problems, we propose a stochastic programming model with an objective of coherent measure of risk. We then use two different coherent measures of risk, which are extensively used in the literature: mean conditional-value-at risk (mean-CVaR) and mean semideviation. For both orienteering problems with different risk measures, we provide numerical results on different levels of risk-aversion.
The presentation of the paper is as follows: In Section 2, we briefly explain the concept of coherent measures of risk and provide the definitions of the risk measures considered in the computational results. We introduce our mathematical models in Section 3 and present the numerical results in Section 4. Section 5 is devoted to the concluding remarks.

COHERENT MEASURES OF RISK
The concept of coherent measures of risk is first introduced by Artzner et al. [19]. In this section, we briefly explain the axiomatic properties of these risk measures and provide the definitions of the measures of risk we consider in our computational results.
Let (Ω, ℱ, ) be a probability space where is Ω the sample space, ℱ is sigma algebra of the subsets of Ω, and is a probability distribution on Ω. In this study, we assume that Ω is finite. Also, let = ℒ (Ω, ℱ, ) be the space of -integrable random costs (for which lower values are preferable) for ≥ 1 and be the probability of elementary event ∈ Ω. A risk measure : → ℝ is called coherent if it satisfies the following four axioms [19]: All these axioms have rational interpretations. Subadditivity (or convexity) axiom implies that diversification decreases the risk. If a random cost is smaller than or equal to a random cost for each elementary event ∈ Ω, then we expect the risk of to be smaller than or equal to the risk of . This is what monotonicity axiom implies. Translation invariance axiom states that if a random cost is increased by a constant then the risk of it will increase by the same amount. Finally, the constant in positive homogeneity axiom can be interpreted as a currency exchange rate, implying that it does not matter in which currency the risk is computed.
In this study, we use two different coherent measures of risk: mean-CVaR and first-order mean semideviation.
Conditional value-at-risk (CVaR) is introduced by Rockafellar and Uryasev [22] and its definition is extended to any general distribution in [23]. Given an atomless random cost , CVaR of at confidence level ∈ (0,1), denoted as CVaR ( ), is defined as: where VaR ( ) = inf{ : ℙ( ≤ ) ≥ }. Note that, for an atomless random cost , CVaR ( ) is the conditional expectation of the values of exceeding value-at-risk (VaR) at level , that is VaR ( ).
For a general cost distribution, the definition of CVaR ( ) is as follows: where ( ) + = max{ , 0} for ∈ ℝ and the infimum is attained at * =VaR ( ). As increases in CVaR, the decision maker becomes more risk-averse.
If the sample space Ω is finite then the expression in (1) can be written as the following linear program (see [23]): In this study, in order to consider the expected cost in addition to the dispersion of cost measured by CVaR, we use mean-CVaR risk measure, which is a weighted sum of mean and CVaR: where ∈ [0,1]. Note that the risk measure in (5) is a coherent measure of risk since it satisfies the axioms A1-A4. Clearly, as decreases, the decision maker becomes more risk-averse and it is riskneutral when =1. Here, the dispersion of the random cost is measured by CVaR. Since a high deviation in the upper tail of a cost distribution is not desirable, one may take ≥0.7 in order to focus on the deviation of upper tail. The reader is referred to [18] for the details of mean-CVaR.
Although both CVaR and VaR are used extensively in the literature, CVaR has some advantages compared to VaR. Firstly, VaR is not a coherent measure of risk due to violating the convexity axiom A1. Furthermore, while CVaR is a convex function, VaR is nonconvex in general. Additionally, VaR is insensitive to the magnitude of the extreme costs on the other hand CVaR is sensitive. For a detailed discussion on the disadvantages of VaR optimization, the reader is referred to [22] and [24]. Here, it is important to remark that a chance constraint can be written as a VaR constraint. Therefore, the riskaverse orienteering studies [7], [11], [13] consider indeed VaR as the measure of risk.
The second coherent risk measure used in this study is first-order mean semi-deviation, which has the following representation (see [18] and references therein for the details): where ∈ [0,1]. This risk measure is a weighted sum of the mean of cost and expected upper deviation of the cost from its mean. Here, the second term is the dispersion measure. As increases, the decision maker becomes more risk-averse, furthermore, = 0 implies that the decision maker is risk-neutral. When the sample space Ω is finite, similar to (1), the risk measure in (6) can be written as the following linear program: s.t.

RISK-AVERSE STOCHASTIC ORIENTEERING MODELS
In this section, we introduce two different risk-averse stochastic orienteering problems, each having different stochastic parameters. While the first model we suggest assumes the rewards are random, the second one assumes stochastic travel times. We first provide an existing formulation of deterministic OP (see [3] and references therein) and then introduce the proposed risk-averse models.

Deterministic Orienteering Problem
Let denote the set of nodes and | | be its cardinality. We also define a depot node 0 ∉ and set + ≔ ∪ {0}. We assume that there is a direct path from each node ∈ + to any node ∈ + \{ } and denote this path as arc ( , ) and its travel time as (it may include the service time of node ). We call a tour feasible if it starts from a depot node, visits each node in a subset of exactly once, and ends at the depot node with a total travel time of at most . Each node ∈ has an associated reward . For ∈ + , ∈ + \{ }, let be a binary decision variable taking value of 1 if the arc ( , ) is traveled in the tour and 0 otherwise. Also, let be an auxiliary decision variable denoting the position of node in the tour for ∈ . Then the orienteering problem is to find a feasible tour having the maximum total reward: Constraint (11) ensures that the tour starts and ends at depot node. Constraints (12) are flow balance constraints also guaranteeing that a node in the tour can be visited at most once. Constraint (13) implies that the total travel time of the tour cannot exceed . Constraints (14) and (15) eliminate the subtours and finally constraints (16) are domain restrictions.

Risk-Averse Orienteering Problem with Stochastic Rewards
Given a finite sample space Ω, let us call an elementary element ∈ Ω as a scenario and as its probability. For each ∈ , let be a random variable having value under scenario ∈ Ω. Then, we can model the risk-averse OP with stochastic rewards (RA-OP-SR) as: where is a coherent measure of risk which may have the form given in (5) or (6). Note that, the concept of coherent measures of risk and also the risk measures in (5) and (6) are defined for random costs for which lower values are preferable. Therefore, in objective (17), we consider negative value of the total reward of the tour. Then, the objective is to find a tour, which has minimum risk in terms of total collected reward. To explain more clearly, if has the form provided in (6), then the objective is to minimize a weighted sum of negative expected total reward and expected lower deviation of total reward from its mean.

Risk-Averse Orienteering Problem with Stochastic Travel Times
We formulate risk-averse OP with stochastic travel times as a two-stage stochastic programming, which is an extension of the risk-neutral model, suggested in [10] to risk-averse setting. In two-stage stochastic programming, there are two stages of decision making. While the first stage decisions are taken before the uncertainty is resolved, the second stage decisions are made after the uncertainty is realized. In our formulation, in the first stage, the decision maker decides on a priori tour. In the second stage, based on realized travel times, the decision maker decides on at which node to quit a priori tour in order to return back to the depot node within the time limit.
Some of the applications of this stochastic OP model with a priori tour are in the sectors of fast moving consumer goods (FMCG) and energy. Generally, in FMCG sector, especially in the traditional channel, a list of customers to be visited is provided to the sales representative at the beginning of the day. However, the travel times on the network are not deterministic in general. Additionally, the amount of time that the sales representative spends at a customer is also random. Therefore, the sales representative may not be able to complete the tour during the work time and may quit it earlier. A similar application exists in energy sector where sales representatives visit customers in order to add them to their customer pool. For a general application similar to these, the reader is referred to Campbell et al. [6] where a business providing deliveries or services to its customers is discussed.
To this end, for each ∈ + and ∈ + \{ }, let the travel time from node to node have value under scenario ∈ Ω. Here, may include the service time at node ∈ . Note that, we again assume the sample space Ω to be finite. We define a new parameter ̅ denoting the mean travel time of arc ( , ). For ∈ + , ∈ + \{ }, let be a binary decision variable taking value of 1 if the arc ( , ) is traveled in a priori tour. Also, let be an auxiliary decision variable denoting the position of node in a priori tour for ∈ . Note that, these variables are related to a priori tour and they are first stage decision variables since their values should be decided before uncertainty related to travel times is resolved. Additionally, for ∈ + , ∈ + \{ }, ∈ Ω, let be a second stage decision variable taking value of 1 if arc ( , ) of a priori tour is cancelled under scenario and 0 otherwise. Since second stage decisions are taken after uncertainty is resolved those variables have a scenario index. Therefore, under two different scenarios, the tour may be quitted at different nodes of a priori tour. Now, we define a random variable , which takes value of under scenario ∈ Ω. Then the objective is to minimize the risk involved in the total reward of the visited nodes. Below, we provide the extensive formulation of our risk-averse two-stage stochastic program, named as RA-OP-ST: Here, is a coherent measure of risk. The first term of the objective function is deterministic and gives the total reward of a priori tour. This deterministic term is moved out of the risk measure due to translation invariance axiom A3. The term inside the risk measure is random and gives the total reward lost due to cancelled arcs. Constraints (19) ensure that under any scenario, only an arc existing in a priori tour can be cancelled. Constraints (20) imply that, under any scenario and for any node , if an outgoing arc from this node is not cancelled then an incoming arc to this node cannot be cancelled neither. Constraints (21) state that, under any scenario, when a priori tour is quitted the summation of the total travel time observed so far and the mean time necessary to return back to the depot node must be within the time limit . Finally, the domain restrictions on second stage variables are provided in (22).
Note that, an optimal solution of this model, that is * , ∈ + , ∈ + \{ }, * , ∈ , * , ∈ + , ∈ + \{ }, ∈ Ω, gives the optimal a priori tour (provided by optimal first stage decisions) and at which node to quit the a priori tour under each scenario (provided by optimal second stage decisions).

COMPUTATIONAL RESULTS
In this section, we present the results of the computational experiments conducted on RA-OP-SR and RA-OP-ST models under two different coherent measures of risk, which are mean-CVaR and firstorder mean semi-deviation, introduced earlier in (5) and (6). Each risk measure results in a nonlinear objective function for each model. On the other hand, using the linearization techniques provided in (2)-(4) and (7)-(9) for mean-CVaR and first-order mean semi-deviation objectives, respectively, we are able to obtain mixed integer linear programming (MILP) formulations for both problems. We solve the resulting MILP models using IBM ILOG CPLEX version 12.6.

Data and Test Instances
We create test instances of 21 nodes for the problem RA-OP-SR, using a deterministic OP data set of 64 nodes, provided by Chao et al. [25]. The first two nodes of this data set are the start and end nodes of a feasible tour. Since a feasible tour starts from and ends at a depot node in our formulations, we use the second node of this data set as depot and select 20 nodes out of remaining 62 nodes randomly. With this, we generate two different data sets, which we name as DS1 and DS2.
These data sets provide the coordinates of the nodes and the deterministic reward values of each node. We then set the deterministic travel time to the Euclidean distance between nodes and . To generate reward scenarios, normal distribution with mean of and standard deviation of 0.25 at node is used. Note that, here denotes the deterministic reward of node . Then a scenario ∈ Ω specifying a reward realization for each node is obtained by drawing a value from the associated normal distribution. Whenever a negative reward realization is obtained, a new value is drawn until getting a positive value. We generate a test instance with 100 scenarios from each data set and assume that the probability of each scenario is equally likely.
To obtain test instances for RA-OP-ST, we follow a similar procedure on problem sets 1 and 3 from Tsiligirides [1] and generate data sets including 11 nodes, named as DS3 and DS4. We again use normal distribution to obtain travel time scenarios. We get a realization of the travel time between nodes and from a normal distribution with mean of and standard deviation of 0.25 . We generate two test instances of 25 scenarios, one from each of the data sets DS3 and DS4, and again assume that the probability of each scenario is equally likely. The mean travel time ̅ is assumed to be equal to deterministic travel time value .

Results
For the test instances generated, we use three different values and two different risk measures. In all computational experiments, the parameter of mean-CVaR gets values from the set {0, 0.5, 1} and the parameter takes values from the set {0, 0.7, 0.9}. Note that =0 or =1 implies that the decision maker is risk-neutral and the level of risk-aversion is expected to increase when the value of increases or the value of decreases. When =0, all the weight is given to the CVaR term of the objective function and the other case, =0.5, gives equal weight to the expected value and CVaR. In this way, we are able to investigate risk-neutral, moderate risk-aversion and high risk-aversion cases. Similarly, =0.7 and =0.9, respectively, imply moderate and high risk-aversion. The parameter of first-order mean semi-deviation takes values from the set {0, 0.5, 1}. The value of zero provides the risk-neutral case, the level of risk-aversion increases as the value of increases and =1 denotes the highest risk-aversion.
We first provide the results of our experiments for RA-OP-SR instances with 100 scenarios in Tables 1 and 2. The first column of these tables lists the data set, the second column shows values, that is the maximum total travel time that a feasible tour can have. The third column and fourth columns of Table 1 (third column of Table 2) are for the values of the risk-aversion parameters. Note that an optimal tour will result in a different total reward value for each scenario. Therefore, in the fifth and seventh columns of Table 1 (fourth and sixth columns of Table 2), we report the mean and the standard deviation of the total reward of an optimal tour, denoted as and , respectively. The sixth column of Table 1 (fifth column of Table 2) gives the percentage deviation of mean total reward of the risk-averse solution from the one of risk-neutral solution. Similarly, the percentage deviation of is reported in the last column of both tables. Table 1 provides the results for an objective of mean-CVaR. We can see that when =21 in DS1 data set, a risk-averse decision maker can have a 20.5% gain in standard deviation by sacrificing 0.28% from the mean of the total reward. For all values in both data sets, under risk-aversion, the percentage gain in is larger than the percentage loss in except 5 instances out of 24. In these five instances the optimal solution is same as the risk-neutral solution. In mean-CVaR risk measure, we expect the decision maker to get more risk-averse as increases or decreases. In data set DS1 with =26 and data set DS2 with =31 when =0.7 and =0 or 0.5, a solution with smaller expected total return and standard deviation than that of risk-neutral case is obtained. However, when is increased to 0.9, for both =0 and 0.5, the optimal solution is same as the one in risk-neutral case. Such behavior of mean-CVaR at high values is reported in some other studies in the literature, see for instance [26]. Recall from Section 2, given a random cost , CVaR ( ) can be interpreted as the conditional expectation of values exceeding VaR ( ), where VaR ( ) is -quantile of the distribution of . In other words, CVaR considers the loss values falling into the tail exceeding -quantile. We will call this tail as -upper tail for the rest of the paper. Even the standard deviation of a distribution is large; it might be the case that the dispersion of the -upper tail is small. In such cases, mean-CVaR may prefer a cost distribution with high standard deviation to a cost distribution with less standard deviation.
To explain more specifically, we focus on data set DS1 with =26. In order to make the explanation easier, we take λ=0, because in this case, the objective reduces to minimize CVaR value of negative total reward. Let 1 and 2 denote negative of optimal total reward under scenario ∈ Ω when =0.7 and =0.9, respectively. Also let be a discrete random variable for which ( ) = with probability 1/100 for =1,2. We provide the histograms and VaR 0.9 values of 1 and 2 in Figure 1. It can be seen that even VaR 0.9 ( 1 ) and VaR 0.9 ( 2 ) are close to each other, the -upper tail of 1 is fatter than theupper tail of 2 . Therefore, CVaR 0.9 ( 1 ) > CVaR 0.9 ( 2 ) and 2 is preferred to 1 at significance level = 0.9. This means that, when risk measure mean-CVaR is used, focusing on tails of random cost distribution exceeding different quantiles, we may have solutions with different behavior. If we analyze the effect of , from Table 1, it can be seen that when is decreased from 0.5 to 0, the solution remains the same in 9 out of 12 cases. Therefore, the effect of is minimal in these test instances.
The computational results of the same instances but with an objective of first-order mean semideviation are provided in Table 2 for different values. As increases, after a certain level, the decision maker sacrifices mean of total reward but gets a decrease in standard deviation.
Different than mean-CVaR, when first-order mean semi-deviation is used; we can guarantee that the standard deviation of total reward does not increase with increasing risk-aversion. This is due to Proposition 6.1 of Shapiro et al. [18], which states that, for first-order mean semi-deviation, the expected upper deviation from the mean (the second term of Equation (6) of our study) is equal to the expected lower deviation from the mean. Therefore, decreasing the expected upper deviation from mean will also decrease the expected lower deviation, which will affect the overall standard deviation of the distribution.
From Table 2, when =0.5 in DS2 data set, we obtain the risk-neutral solution for all three values. On the other hand, mean-CVaR risk measure is able to provide a solution different than the risk-neutral solution even for =0.7, which can be considered as low level of risk-aversion for mean-CVaR. In most of RA-OP-SR instances, an optimal tour of a risk-averse decision maker is rather different than an optimal tour of a risk-neutral decision maker. We illustrate this in Figure 2 which includes the optimal tours of risk-neutral and risk-averse decision makers for the data set DS1 with =21.  Tables 3 and 4, respectively. Tables 5 and 6 present the results on the total reward for both risk measures. The first four columns of Table 3 and the first three columns of  Table 4 are for the data set, maximum travel time and risk parameters. The fifth column of Table 3 and fourth column of Table 4 provide an optimal a priori tour, where node 0 denotes the depot node. The sixth column of Table 3 and fifth column of Table 4 give the arcs cancelled after the uncertainty related to the travel times is resolved. Note that the numbers in parenthesis provide the number of scenarios in which the corresponding arc is cancelled.  As seen from Tables 3 and 4, while the level of risk-aversion increases, in general, the decision maker tends to construct a priori tour resulting in less number of cancelled arcs or in less number of scenarios with at least one cancelled arc. The intuition behind this is to minimize the dispersion of the reward lost because of the cancelled arcs. Moreover, for both data sets and all values, there are cases where mean-CVaR and first-order mean semi-deviation provide tours which are completely different from each other. For example, for data set DS3 with =40, a priori tour given by first-order mean semideviation at =0.5 or =1 is rather different than a priori tours provided by mean-CVaR at =0.7 and =0.9 with both =0 and =0.5. A similar example is the data set DS4 with =20. Tables 5 and 6 report the results on total reward for mean-CVaR and first-order mean semideviation, respectively. Table 5 shows that, when compared to the risk-neutral solution, a risk-averse decision maker with mean-CVaR can decrease the standard deviation of total reward to zero with a 6.72% sacrifice in mean of total reward (see data set DS4 with =20 in Table 5). Similarly, when firstorder mean semi-deviation is used, the maximum decrease in the standard deviation is by 67% with a 2.4% sacrifice in mean (see data set DS3 with =35 in Table 6). For both risk measures, the lowest decrease in the standard deviation of total reward is by 17% with a 0.75% sacrifice in mean of total reward (see DS4 with =20 in Tables 5 and 6). In all the instances under mean-CVaR with =0.7 or 0.9 and =0 or 0.5, the percentage decrease in the standard deviation of total reward is much larger than the percentage loss in the mean of total reward, while the lowest gain in is at level 17% and the highest loss in is attained as 15.67%, please see Table 5. From Table 6, we can see that in some instances with first-order mean semi-deviation and =0.5, an optimal solution is same as the one in the risk-neutral case. On the other hand, when a solution different than the risk-neutral solution is obtained, the percentage gain in is much larger than the percentage loss in , where the minimum gain in is 17% and maximum loss in is 2.78%. Furthermore, for both data sets and all values, mean-CVaR can provide a solution with smaller than the one given by first-order mean semi-deviation. For example, for the data set DS4 with =20, a standard deviation of zero is obtained when mean-CVaR with =0 and =0.7 or 0.9 is used (see Table  5). On the other hand, for this instance, the lowest standard deviation value obtained is 18.3 if firstorder mean semi-deviation is used (see Table 6).
As risk-aversion increases, one may expect the percentage loss in mean of total reward will increase in both risk measures to minimize the dispersion. We observe such behavior in our computational study. However, in some cases, an opposite behavior is observed in mean-CVaR. For example, for data set DS3 with =30, when =0.5, the sacrifice in and the gain in at =0.9 is smaller than the ones obtained at =0.7. On the other hand, such a situation is not observed in first-order mean semideviation. As stated previously, when risk measure mean-CVaR is used, focusing on tails of random cost distribution exceeding different quantiles, we may have solutions with different behavior.
Although the effect of parameter of mean-CVaR is minimal for problem RA-OP-SR, its effect is very significant for problem RA-OP-ST, see Tables 3 and 5 for the details. Note that problem RA-OP-SR is a single stage stochastic problem, where all the decisions should be taken before uncertainty is resolved. On the other hand, RA-OP-ST is a two-stage problem, where the second stage decision variables are called as recourse variables, which provide recourse actions depending on the observed scenario. Therefore, in RA-OP-ST, a small change in a priori tour can result in a significant difference in the distribution of total reward with the help of second stage decisions. An interesting example is data set DS3 with =35. In the instance with =0.7, when is decreased to 0 from 0.5, just node 9 is eliminated from a priori tour, but with such a small change in the tour, the standard deviation of total reward decreases to 1.4 from 3.3. When =0.5, arc (2,9) is cancelled in 24 scenarios out of 25. Therefore, eliminating node 9 from the tour results in a significant decrease in the standard deviation. Similarly, in data set DS4 with =20 and =0.9, when is decreased to 0 from 0.5, the standard deviation decreases to zero from 26 by eliminating nodes 5 and 9 from a priori tour.   Tables 3 and 5, it can be seen that, in 9 out of 12 cases, a different solution is obtained if is decreased to 0 from 0.5. When =0, the objective function gives all the weight to CVaR and completely ignores the mean of total reward. In this case, however, a significant sacrifice in mean may occur as in data set DS4 with =24 and =0.9, which may be undesirable by the decision maker.

A detailed analysis with different test instances
The aim of our study is to discuss how the solutions of a stochastic OP problem may change when the decision maker is risk-averse. In order to analyze whether results similar to our previous conclusions are obtained with different set of scenarios, we generate new test instances for both problems RA-OP-SR and RA-OP-ST. For problem RA-OP-SR, we consider the data set DS1 with =21 under first-order mean semideviation and generate four new instances each with 100 scenarios in a way as discussed in Section 4.1. The results of new instances are provided in Table 7. For comparison purpose, the old instance is kept as the first instance. Note that the fourth and sixth columns of Table 7 respectively show the percentage deviation of mean of total reward and standard deviation of total reward from the ones of risk-neutral case. As it can be seen, we obtain results similar to Table 2. As risk-aversion increases (after a certain level of ), the decision maker is able to find a tour with slightly smaller expected total reward than that of risk-neutral case but with a smaller standard deviation. Furthermore, the percentage gain in standard deviation of total reward is larger than the percentage loss in mean. Table 8. The optimal first and second stage solutions of the problem RA-OP-ST on data set DS3 with =35 and 25 scenarios under first-order mean semi-deviation.  Using data set DS3 with =35, a similar computational study is also conducted on problem RA-OP-ST. Again the risk-aversion is modeled with first-order mean semi-deviation and four new instances each with 25 scenarios are generated using the procedure discussed in Section 4.1. The results are presented in Tables 8 and 9. Similar to our previous results, as risk-aversion increases, the decision maker tends to construct a priori tour resulting in less number of cancelled arcs or in less number of scenarios with at least one cancelled arc. Also, as expected, the percentage gain in the standard deviation of total reward is larger than the percentage loss in mean.

Instance
With these new computations, it is possible to conclude that our results on risk-averse decisions do not change with different instances of both problems.

CONCLUSION
In this study, we consider two different stochastic orienteering problems: one with random rewards and the other one with random travel times. For both problems, we propose a risk-averse stochastic programming formulation with an objective of coherent measures of risk. The numerical results conducted on different problem instances show that, for each orienteering problem, a risk-averse solution might be significantly different than the risk-neutral solution in terms of the constructed tour. Furthermore, the risk-averse solutions may provide a significant decrease in the standard deviation of total reward without sacrificing much from the expected total reward.
Since the formulation suggested for OP with stochastic travel times is a two-stage stochastic model, it is much more difficult to solve than the static stochastic model suggested for OP with random rewards. Furthermore, the risk-averse objective function brings additional complexity in solving both models. As a future research direction, a solution methodology can be proposed for the problem RA-OP-ST in order to solve instances with large number of scenarios on larger networks.