# Application of Fuzzy Optimization to the Orienteering Problem

Authors: Madhushi Verma; K. K. Shukla
Journal: Advances in Fuzzy Systems
 (2015)

---

## Abstract

This paper deals with the orienteering problem (OP) which is a combination of two well-known problems (i.e., travelling salesman problem and the knapsack problem). OP is an NP-hard problem and is useful in appropriately modeling several challenging applications. As the parameters involved in these applications cannot be measured precisely, depicting them using crisp numbers is unrealistic. Further, the decision maker may be satisfied with graded satisfaction levels of solutions, which cannot be formulated using a crisp program. To deal with the above-stated two issues, we formulate thefuzzy orienteering problem (FOP) and provide a method to solve it. Here we state the two necessary conditions of OP of maximizing the total collected score and minimizing the time taken to traverse a path (within the specified time bound) as fuzzy goals and the remaining necessary conditions as crisp constraints. Using the max-min formulation of the fuzzy sets obtained from the fuzzy goals, we calculate the fuzzy decision sets (Z and Z
∗) that contain the feasible paths and the desirable paths, respectively, along with the degrees to which they are acceptable. To efficiently solve large instances of FOP, we also present a parallel algorithm on CREW PRAM model.


---

## Body

## 1. Introduction

The orienteering problem (OP) is an NP-hard problem, derived from the game of orienteering where the player is required to start from the initial control point and arrive at the final control point within the specified time limit, at the same time collecting the rewards (Score) assigned to each of the checkpoints that link the initial control point to the final control point. All those players who arrive at the final control point after the time expires are disqualified and the player reaching the final control point within the allotted time and with the maximum collected score is declared as the winner of the game. This game reflects many real life situations related to the field of logistics, tourism, building telecommunication networks, home delivery systems, and so forth, which can be modelled as OP [1]. There are four types of OP which include the simple orienteering problem, team orienteering problem, orienteering problem with time window, and team orienteering problem with time window. The OP can be observed as a combination of two well-known problems, that is, travelling salesman problem (TSP) and the knapsack problem (KP), where the objective of maximizing the score is derived from KP and the objective of minimizing the time taken to travel from the initial control point and final control point is similar to the objective of TSP with the difference that in TSP all the vertices connecting the source to the target should be visited once, but in OP it is not necessary to visit all the intermediate checkpoints [1]. One real life application of OP is in the tourism industry where tourists come to visit the cities which are rich in culture and traditions and have some historical significance. The aim is to visit as many locations (including palaces, museums, monuments, and restaurants) as possible within their duration of stay. Due to the restriction of time it is not possible to visit all the places, so depending upon the choice and taste of the tourist, the guide can assign priorities to the various locations to be visited and then explore as many of them as possible within the time frame available so as to make their trip as economical and as beneficial as possible [2]. As seen in the stated example, the two parameters involved, that is, time and score, cannot be determined precisely as the priorities differ from one tourist to another and the time taken to travel from one location to another cannot be predicted exactly. So, the uncertainty in both the parameters can be modelled in a better way by representing them using fuzzy numbers instead of crisp or real numbers.Since the orienteering problem is NP-hard, several heuristic algorithms and a few approximation algorithms are available in the literature. Some of the first heuristics for OP were the stochastic (S-algorithm) and deterministic (D-algorithm) ones suggested by Tsiligirides in 1984 [3]. In 1987, a center-of-gravity heuristic was proposed by Golden et al. [4]. A four-phase heuristic was introduced by Ramesh and Brown in 1991 [5]. An artificial neural network based approach was proposed by Wang et al. in 1995 [6] and, in 1996, a five-step heuristic was suggested by Chao et al. [7]. A branch-and-cut heuristic for OP was stated by Fischetti et al. in 1998 [8]. The first genetic algorithm for OP was developed by Tasgetiren in 2001 [9]. In 2002, Liang et al. proposed and compared a tabu search and an ant colony optimization approach for OP [10]. The approximations known for Prize Collecting Travelling Salesman Problem can be easily extended for the unrooted version of OP [11, 12] and, for the rooted version, a constant factor approximation was suggested by Blum et al. [13]. A heuristic method based on the greedy randomized adaptive search procedure and the path relinking methodologies was proposed in 2013 by Campos et al. [14].This paper reports the first use of fuzzy logic to tackle the uncertainty involved in the two parameters (score and time). We introduce the fuzzy orienteering problem (FOP) and model the parameters involved as trapezoidal fuzzy numbers (TFNs). Several types of fuzzy numbers exist like Gaussian fuzzy numbers, exponential fuzzy numbers, quadratic fuzzy numbers, triangular fuzzy numbers, and trapezoidal fuzzy numbers, but here we prefer TFN because its computation is simple; it has a linear membership function and is the most generic class, so it is widely used in the applied engineering problems and in the scientific field.In Section2, we state necessary definitions and Section 3 provides the explanation of fuzzy optimization. In Section 4, the problem definition is stated. Section 5 explains the fuzzy formulation of OP along with the steps to deal with it and obtain a solution. The proposed method of solving FOP is demonstrated in Section 6 through an illustrative example. In Section 7, the parallel algorithm for FOP is presented and, finally, the paper is concluded in Section 8.


## 2. Preliminaries

Definition 1 (trapezoidal fuzzy numbers (TFNs)).
A fuzzy number is an extension of the crisp or real number which refers to a set of possible values represented by a membership function, each of which is assigned a weight called its grade of membership between 0 and 1 whereas the crisp number is associated with a single value.
For any crisp setX which is a subset of the universal set U, the membership function is denoted by μ
X which assigns a value within [
0,1
] called the grade of membership to every element of X. So, the set X
~
=
x
,
μ
X
~
x
:
x
∈
U is called a fuzzy set. A fuzzy set X
~, whose membership function possess the properties stated below, is called a fuzzy number [15]:(a)
μ
X
~ is piecewise continuous,
(b)
X
~ is convex (
μ
X
~
α
x
1
+
1
-
α
x
2
≥
min
⁡
μ
X
~
x
1
,
μ
X
~
x
2
∀
x
1, x
2
∈
R, ∀
α
∈
0,1
),
(c)
X
~ is normal μ
X
~
x
0
=
1
,
x
0
∈
R, where R is the universal set of real numbers.
Fuzzy numbers are used to represent those parameters which are imprecise and, in several real life applications, parameters like cost, time, demand, capacity, and so forth are involved for which it is not possible to specify exact values. In these situations, it is appropriate to use a fuzzy number instead of a crisp number as they provide a more practical presentation of the real world. There are several types of fuzzy numbers, each of which can be defined by a membership function. In this paper, to represent the two parameters time and score as fuzzy numbers, we use TFN. For a trapezoidal fuzzy number represented asA
~
=
a
1
,
a
2
,
a
3
,
a
4, the membership function is as follows [15]: (1)
μ
A
~
x
=
0
,
x
<
a
1
x
-
a
1
a
2
-
a
1
,
a
1
<
x
≤
a
2
1
,
a
2
<
x
<
a
3
a
4
-
x
a
4
-
a
3
,
a
3
≤
x
<
a
4
0
,
x
>
a
4
,where a
1
≤
a
2
≤
a
3
≤
a
4.Definition 2 (addition of TFN).
In applications where the goal is to maximize or minimize some fuzzy quantity, some intermediate mathematical operations are to be performed which mostly include addition. For the problem stated here, we need to maximize the score acquired within a given time bound and for this we need to add the weights assigned to the vertices to calculate the score and the weights assigned to the edges to determine the time taken by a path. As stated the parameters here are considered to be TFNs and the mathematical operations performed on fuzzy numbers (like addition) differ from the usual crisp case.
Two TFNs represented asA
~
=
a
1
,
a
2
,
a
3
,
a
4 and B
~
=
b
1
,
b
2
,
b
3
,
b
4 can be added using the following formula [15]:(2)
A
~
+
B
~
=
a
1
,
a
2
,
a
3
,
a
4
+
b
1
,
b
2
,
b
3
,
b
4
=
a
1
+
b
1
,
a
2
+
b
2
,
a
3
+
b
3
,
a
4
+
b
4
.Definition 3 (ranking of TFN).
In case of crisp numbers, there exists a natural ordering which clearly states that a real number is greater/smaller than other real numbers, but the absence of such a natural ordering in case of fuzzy numbers leads to the requirement of formulating a ranking method, using which the fuzzy numbers can be ordered. Here we use the circumcenter of centroids (COC) method for ranking TFN. Several methods are available in the literature for ranking of TFN, most of which use the centroid of the trapezoid for ranking considering it to be a balancing point, but in the method suggested by Rao and Shankar, the COC value is used for the ranking purpose. The COC is considered to be a better point of reference as it is obtained by calculating the circumcenter of the triangle formed by joining the centroids of the three subparts of the trapezoid which include two triangles and one rectangle [16].
As suggested by Rao and Shankar [16], if A
~
=
a
1
,
a
2
,
a
3
,
a
4, then(3)
COC
A
~
=
x
,
y
=
a
1
+
2
a
2
+
2
a
3
+
a
4
6
,
2
a
1
+
a
2
-
3
a
3
2
a
4
+
a
3
-
3
a
2
+
5
12
.Using this value of C
O
C
A
~, the rank of the TFN A
~ is obtained using the following formula:(4)
R
A
~
=
x
2
+
y
2
.If we have two fuzzy numbers A
~ and B
~, then A
~
>
B
~ if R
A
~
>
R
B
~ and vice versa. When R
A
~
=
R
B
~, it is difficult to determine the ordering and some additional information is used as suggested by Rao and Shankar to tackle the situation.Index of Optimism. The degree of optimism of the decision maker was taken care of by this index as stated by Rao and Shankar in [16]. So the decision maker’s view point was also considered and, for any TFN A
~
=
a
1
,
a
2
,
a
3
,
a
4 and C
O
C
A
~, the formula for the index is as follows [16]:(5)
I
δ
A
~
=
δ
y
+
1
-
δ
x
where
δ
∈
0,1
.Larger value of δ shows that the decision maker is optimistic, whereas smaller values depict the situation where the decision maker is pessimistic.Index of Modality. Another index was introduced by Rao and Shankar to tackle the situation where the rank of two TFNs becomes equal because the index of optimism alone may not be sufficient in such a case to determine the ranking as it considers only the importance of extreme values. The index of modality considers the importance of central value as well as the extreme values and the formula to determine the index is as follows [16]:(6)
I
δ
,
γ
A
~
=
γ
x
+
y
2
+
1
-
γ
I
δ
A
~
,
where
γ
∈
0,1
.If we have two TFNs A
~ and B
~, with R
A
~
=
R
B
~, then A
~
>
B
~ when I
δ
,
γ
A
~
>
I
δ
,
γ
B
~ and vice versa.Definition 4 (expected value of trapezoidal fuzzy number (EV)).
To determine the grade of membership of a TFN, that is, to find out the degree to which the TFN satisfies the specified requirement, we need to calculate its expected value and then use Definition1. The formula for expected value as used by Jimenez et al. in [17] is as follows.
For a given TFNA
~
=
a
1
,
a
2
,
a
3
,
a
4,(7)
EV
A
~
=
1
4
a
1
+
a
2
+
a
3
+
a
4
.This defuzzification technique is used as it is the simplest possible and gives satisfactory results for the fuzzy orienteering problem. It will be interesting to study other defuzzification techniques although the general conclusions of the paper will remain unaffected.Definition 5 (fuzzy decision set (Z)).
Fuzzy decision set is a set of elements providing a feasible solution to the stated problem. The fuzzy linear programming problem can have several goals, each represented by a membership function and a fuzzy set (F
l) containing the elements along with their grades of membership obtained using the membership function [17].
We define the fuzzy decision as(8)
Z
=
F
1
∩
F
2
∩
⋯
∩
F
l
i.e.
μ
Z
x
=
μ
F
1
x
∗
μ
F
2
x
∗
⋯
∗
μ
F
l
x
,where ∗ represents a t-n
o
r
m which can be any operation likeminimum,algebraic product, and so forth. In case of OP, ∗ represents m
i
n
i
m
u
m operation. To obtain the most desirable solution, we determine the element with the highest membership degree in the fuzzy decision set Z, that is, the value of x that maximizes the membership function of fuzzy decision Z denoted by x
∗, using the equation stated below:(9)
μ
Z
∗
x
∗
=
max
⁡
μ
Z
x
,where Z
∗ denotes the fuzzy set of the most desirable solutions.


## 3. Fuzzy Optimization

In engineering design or decision making problems, a large number of feasible solutions are available and to choose the solution which is the best one from this set, we need to concentrate on the uncertainty associated with the variables that lead to the optimal solution. Probabilistic concepts can take care of the randomness that arises due to natural fluctuation or natural variations, but the uncertainty that comes into existence due to qualitative statements, vague statements, vague nature of the objective, and linguistic statements showing the willingness of the decision maker (like the solution is acceptable, low, satisfactory, etc.) cannot be addressed through probabilistic concepts, so we introduce the concept of fuzzy logic in solving the optimization problems. In the crisp definition of optimization problems, we have crisp conditions where solutions violating the constraints or not satisfying the objective function are completely unacceptable, but, in fuzzy optimization, the concept of degree is introduced. The solution becomes a matter of degree; that is, degree of acceptability or degree of satisfaction is associated with the constraints and the objective functions, and this way we provide a latitude to the acceptability of a solution. This degree of acceptability linked with the objective functions and constraints can be reflected through fuzzy membership functions.To deal with the situations where several stakeholders vaguely state their preferences as constraints or objective functions using linguistic statements, we convert these statements into fuzzy sets or fuzzy membership functions and then using some technique find out the best “compromise solution.” In fuzzy optimization, we do not distinguish between the objective functions and the constraints; instead we refer to them as fuzzy goals, represented in the form of fuzzy sets defined by their respective membership functions. So, the latitude or uncertainty present in the decision making is tackled through these membership functions. In addition to the fuzzy goals, we can also have crisp constraints modelling the physical conditions or technological feasibility that have to be met in a particular solution.The whole idea of fuzzy optimization is to allow for latitude in the constraints and flexibility in the objective function. Instead of a 0-1 type solution, we allow for some violation of the original constraints to some degree, set certain limit for the objective function, and accept solutions on both sides of the limit to different degrees. The objective function and the set of constraints are converted into fuzzy sets; their associated membership functions are defined and then all the membership functions are combined to determine the fuzzy decision. Through fuzzy optimization, the preferences of the decision maker are quantified and the uncertainty due to vagueness, imprecision, and so forth, which is common in decision making problems, is tackled using membership functions [18–20].


## 4. Problem Definition

The orienteering problem can be represented by a completely connected undirected graphG
V
,
E, where V
=
v
1
,
…
,
v
N is the set of vertices and E is the set of edges. A score S
i is associated with every vertex v
i
∈
V and the time taken to traverse each edge e
i
j
∈
E is denoted by t
i
j. The goal here is to determine a path P connecting any subset of V that necessarily includes the start vertex v
1 and the end vertex v
N, satisfies the time bound T
m
a
x, and also maximizes the total collected score [1].In this paper, we present the fuzzy orienteering problem (FOP) where the two quantities involved, that is, time and score, are considered to be fuzzy numbers. The reason to introduce fuzziness into the formulation of OP is that the crisp mathematical formulation is very strict in three ways: (1) the objective function should be either maximized or minimized, (2) none of the constraints should be violated as it leads to an infeasible solution, and (3) all constraints are given equal importance. However, these three necessary requirements lead to an unrealistic representation of the real world. By partly relaxing these using fuzzy logic, we can model the physical world in a more realistic manner. Several situations might exist in real life applications that can be easily represented in the fuzzy environment which may include the following [21].(1)
The decision maker is not willing to maximize or minimize the objective function; instead he wants to reach some aspiration level like “improving the present fuel consumption situation to some extent” in transportation problems which cannot even be defined or stated in the crisp case.
(2)
Maybe the decision maker is willing to accept small violations in the constraints especially when the objective function deals with the aspiration levels and the less than or greater than relation is not required to be followed in the strict mathematical sense. Moreover, the parameters or variables involved may have vagueness which cannot be expressed in the crisp formulation.
(3)
In the crisp representation, all constraints are of equal importance but maybe, for the decision maker, different constraints have different importance and small violations of different constraints may be acceptable to different degrees.In this fuzzy formulation of OP, we have recognized that the parameters time and score are fuzzy in nature and in the fuzzy version we provide latitude to the desired solution by relaxing the constraints to some extent and stating the degree up to which they are feasible. Here we do not distinguish between objective function and constraints; instead the two necessary conditions of maximizing the total collected score and following the time bound are represented as two goals which are conflicting as one is to be maximized and the other one is to be minimized. These are represented as linear membership functions and the rest of the constraints are considered to be crisp. The detailed explanation of the fuzzy formulation is presented in the next section.


## 5. Fuzzy Formulation of OP

The fuzzy version can be represented in the following way showing by tilde the parameters that have a fuzzy character:(10)
∑
i
=
1
N
-
1
∑
j
=
2
N
S
i
~
x
i
j
≿
S
m
i
n
,
(11)
∑
j
=
2
N
x
1
j
=
1
,
∑
i
=
1
N
-
1
x
i
N
=
1
,
(12)
∑
i
=
1
N
-
1
x
i
k
≤
1
∀
k
=
2
,
…
,
N
-
1
,
(13)
∑
j
=
2
N
x
k
j
≤
1
∀
k
=
2
,
…
,
N
-
1
,
(14)
∑
i
=
1
N
-
1
∑
j
=
2
N
t
i
j
~
x
i
j
≾
T
m
a
x
,
(15)
2
≤
u
i
≤
N
∀
i
=
2
,
…
,
N
,
(16)
u
i
-
u
j
+
1
≤
N
-
1
1
-
x
i
j
∀
i
,
j
=
2
,
…
,
N
,
(17)
x
i
j
∈
0,1
∀
i
,
j
=
1
,
…
,
N
.As stated above, the constraints represented by (10) and (14) are considered to be fuzzy and represent the two conflicting goals of maximizing the total collected score and minimizing the time taken to traverse a path, respectively. The symbols S
i
~ and t
i
j
~ in (10) and (14) represent the fuzzy score and fuzzy time values, respectively. The remaining constraints represented by (11), (12), (13), (15), (16), and (17) remain crisp. The variable u
i denotes the position of vertex v
i in the path and if vertex v
j is visited after vertex v
i, then x
i
j
=
1; else x
i
j
=
0. The necessary condition that each path starts in v
1 and ends in v
N is ensured by (11). The constraint that each path remains connected and no vertex is visited more than once in a path is taken care of by (12)-(13) and the requirement of eliminating subtours is implemented by (15)-(16) [1]. The symbols “≿” and “≾” are the fuzzy version of “≥” and “≤” representing the “fuzzy greater than or equal to” and “fuzzy less than or equal to,” respectively. The meaning of these symbols is that the constraints can be violated to some extent and, depending on the importance of the constraint, this violation leads to different degree of acceptance [22]. For example, in (10), the symbol “≿” indicates that the total collected score of a particular path should be greater than S
m
i
n (most desirable case), but those paths which have their total collected score slightly less than S
m
i
n, that is, up to S
m
i
n
-
P, are also acceptable but to a lesser degree. Similarly, in (14), the total time taken to traverse a path should be less than T
m
a
x (most acceptable case), but paths having their total time greater than T
m
a
x are also acceptable to different degrees up to the limit of T
m
a
x
+
L as signified by the symbol “≾.” The two fuzzy goals can be represented by their membership functions as shown in Figures 1 and 2. The fuzzy decision sets Z and Z
∗ are depicted in Figure 3. It denotes the best “compromise solution” which is obtained by the following max-min formulation:(18)
Z
=
F
1
∩
F
2
,
μ
Z
x
=
min
⁡
μ
T
x
,
μ
S
x
,
μ
Z
∗
x
∗
=
max
⁡
μ
Z
x
=
max
⁡
min
⁡
μ
T
x
,
μ
S
x
.The intersection of the two fuzzy sets (F
1 and F
2) is the minimum value of the two fuzzy sets for each x, which forms the fuzzy decision set Z (as shown by dark straight lines) and the maximum value of this decision set Z forms the other set Z
∗ which holds the most desirable solution (as shown by the dashed line) of Figure 3.Figure 1
Membership function for total collected score of a path.Figure 2
Membership function for total time taken to traverse a path.Figure 3
Fuzzy decision setsZ and Z
∗.FOP Algorithm. The following are the steps to determine the path that maximizes the total collected score within the specified time limit for a given G
V
,
E with N nodes.(1)
Determine all the possible paths (W
m) connecting v
1 and v
N (using (11), (12), (13), (15), (16), and (17)).
(2)
For each possible path,
(a)
calculate the total time taken to traverse the path and the total collected score (using Definition2 and (2));
(b)
calculate the expected value of the total time taken to traverse the path and the total collected score (using Definition4 and (7));
(c)
calculate its membership degree for the membership function of time (using (14) and Figure 2); let it be denoted by fuzzy set F
1;
(d)
calculate its membership degree for the membership function of score (using (10) and Figure 1); let it be denoted by fuzzy set F
2.
(3)
Determine the feasible paths denoted by the fuzzy decision setZ obtained using Definition 5 and (8).
(4)
The most desirable path (final solution) is denoted by the fuzzy decision setZ
∗ obtained using Definition 5 and (9).
(5)
If the fuzzy decision setZ
∗ contains more than one path, the total collected score (S
i) for each of the paths in Z
∗ can be ranked (using Definition 3 and (3), (4), (5), and (6)) to determine the path that maximizes the total collected score.


## 6. Illustrative Example

Consider the networkG
V
,
E in Figure 4 with total number of nodes N
=
5 and the value for edge weights and node weights of G are stated in Tables 1 and 2, respectively.Table 1
The values of edge weights (time taken to travel from one node to another).
Edge
Label
Fuzzy time values
e
12
A
1,4
,
6,9
e
13
B
6,9
,
13,16
e
14
D
14,15,21,22
e
15
C
4,6
,
8,10
e
23
E
2,3
,
3,4
e
24
G
5,8
,
8,11
e
25
H
14,18,22,26
e
34
I
5,8
,
12,15
e
35
J
0,2
,
10,12
e
45
K
1,2
,
2,3
T
max
⁡
=
20, L
=
15Table 2
The values of node weights (score values).
Node
Label
Fuzzy score values
v
1
1
1,2
,
8,9
v
2
2
8,9
,
11,12
v
3
3
3,5
,
9,11
v
4
4
17,20,24,27
v
5
5
1,2
,
4,5
S
min
⁡
=
25, P
=
13Figure 4
Input graphG
V
,
E with source vertex = 1 and destination vertex = 5.Step 1.
All possible paths connectingv
1 and v
5 are found that satisfy (11), (12), (13), (15), (16), and (17) and are as follows:(19)
W
1
:
1
-
5
,
W
2
:
1
-
2
-
5
,
W
3
:
1
-
3
-
5
,
W
4
:
1
-
4
-
5
,
W
5
:
1
-
2
-
3
-
5
,
W
6
:
1
-
3
-
2
-
5
,
W
7
:
1
-
2
-
4
-
5
,
W
8
:
1
-
4
-
2
-
5
,
W
9
:
1
-
3
-
4
-
5
,
W
10
:
1
-
4
-
3
-
5
,
W
11
:
1
-
2
-
3
-
4
-
5
,
W
12
:
1
-
2
-
4
-
3
-
5
,
W
13
:
1
-
3
-
4
-
2
-
5
,
W
14
:
1
-
4
-
3
-
2
-
5
,
W
15
:
1
-
4
-
2
-
3
-
5
,
W
16
:
1
-
3
-
2
-
4
-
5
.Step 2.
(a) Table3 shows the total time taken to traverse and total collected score for each of the above stated paths which is calculated using Definition 2 and (2).
(b) Next we calculate the expected value of the total time taken to traverse the path and the total collected score using Definition4 and (7) for each of the paths W
1 to W
16 as shown in Table 4.
(c) and (d) The grade of membership of each possible path fromW
1 to W
16 is determined for both the membership functions (time and score) using (10) and (14) and Figures 1 and 2 and their values are shown in Table 5.
So, the two fuzzy setsF
1 and F
2 for the total time taken and total collected score, respectively, are as follows:(20)
F
1
=
W
1
/
1
,
W
2
/
0.67
,
W
3
/
1
,
W
4
/
1
,
W
5
/
1
,
W
6
/
0.06
,
W
7
/
1
,
W
8
/
0
,
W
9
/
0.8
,
W
10
/
0.06
,
W
11
/
1
,
W
12
/
0.4
,
W
13
/
0
,
W
14
/
0
,
W
15
/
0
,
P
16
/
0.73
,
F
2
=
W
1
/
0
,
W
2
/
0.23
,
W
3
/
0
,
W
4
/
1
,
W
5
/
0.77
,
W
6
/
0.77
,
W
7
/
1
,
W
8
/
1
,
W
9
/
1
,
W
10
/
1
,
W
11
/
1
,
W
12
/
1
,
W
13
/
1
,
W
14
/
1
,
W
15
/
1
,
W
16
/
1
.Table 3
The total time taken and total collected score values for each of the paths.
Path
Total time taken to traverse
Total collected score
W
1
4,6
,
8,10
1,2
,
8,9
W
2
15,22,28,35
9,11,19,21
W
3
6,11,23,28
4,7
,
17,20
W
4
15,17,23,25
18,22,32,36
W
5
3,9
,
19,25
12,16,28,32
W
6
22,30,38,46
12,16,28,32
W
7
7,14,16,23
26,31,43,48
W
8
33,41,51,59
26,31,43,48
W
9
12,19,27,34
21,27,41,47
W
10
19,25,43,49
21,27,41,47
W
11
9,17,23,31
29,36,52,59
W
12
11,22,36,47
29,36,52,59
W
13
30,43,55,68
29,36,52,59
W
14
35,44,58,67
29,36,52,59
W
15
21,28,42,49
29,36,52,59
W
16
14,22,26,34
29,36,52,59Table 4
The expected value of the total time taken to traverse the path and the total collected score for each of the paths.
Path
EV (total time taken)
EV (total collected score)
W
1
7
5
W
2
25
15
W
3
17
12
W
4
20
27
W
5
14
22
W
6
34
22
W
7
15
37
W
8
46
37
W
9
23
34
W
10
34
34
W
11
20
44
W
12
29
44
W
13
49
44
W
14
51
44
W
15
35
44
W
16
24
44Table 5
The grade of membership of each possible path for the membership functions of both time and score.
PathW
m
μ
T (W
m)
μ
S (W
m)
W
1
1
0
W
2
0.67
0.23
W
3
1
0
W
4
1
1
W
5
1
0.77
W
6
0.06
0.77
W
7
1
1
W
8
0
1
W
9
0.8
1
W
10
0.06
1
W
11
1
1
W
12
0.4
1
W
13
0
1
W
14
0
1
W
15
0
1
W
16
0.73
1Step 3.
Now the fuzzy decision setZ is obtained using Definition 5 and (8) to determine all the feasible paths along with the membership grades stating the degree up to which each of the feasible paths is acceptable.
Here,μ
Z
x
=
m
i
n
μ
T
x
,
μ
S
x, where x
=
W
1 to W
16 is used to calculate Z:(21)
Z
=
W
1
/
0
,
W
2
/
0.23
,
W
3
/
0
,
W
4
/
1
,
W
5
/
0.77
,
W
6
/
0.06
,
W
7
/
1
,
W
8
/
0
,
W
9
/
0.8
,
W
10
/
0.06
,
W
11
/
1
,
W
12
/
0.4
,
W
13
/
0
,
W
14
/
0
,
W
15
/
0
,
P
16
/
0.73
.Step 4.
Finally, the fuzzy decision setZ
∗ is obtained using Definition 5 and (9) that contains the desirable path:(22)
Z
∗
=
W
4
/
1
,
W
7
/
1
,
W
11
/
1
.Step 5.
As can be observed from Step4, there are three paths that are desirable as they fulfil all the crisp constraints and the two fuzzy goals. To conclude with one most desirable path among the three available in Z
∗, we use the ranking method described in Definition 3 and use (3), (4), (5), and (6) to rank the score of each path in Z
∗ and determine the best one. The values for which are shown in Table 6.
So, the most desirable path isW
11 as it has the highest rank.Table 6
The ranks of the desirable paths.
Path
Score
Rank
W
4
18,22,32,36
3
W
7
26,31,43,48
2
W
11
29,36,52,59
1


## 7. Parallel Formulation of FOP

To solve the FOP more efficiently and to yield a better and improved performance when applied on large instances, we present a parallel algorithm for FOP that uses the CREW PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine) model. In a PRAM model, several processors are connected to a common block of shared memory. This shared memory can be accessed by all the processors and these processors communicate with each other by reading from or by writing to the shared memory. In a PRAM model, each processor is like a sequential RAM and can perform the arithmetic operations, assignment, comparison, memory access, and so forth in unit time. In CREW PRAM, more than one processor can read concurrently from the same cell of the shared memory but cannot write into the same cell concurrently; that is, write operation has to be exclusive [23, 24]. For each parallel algorithm, the following terms are computed to determine whether it is work optimal or not [24]:(23)
a
speed  up
=
runtime  of  the  best  known  sequential  algorithm
runtime  of  the  parallel  algorithm  for  a
p
-processor  machine
b
total  work  done
=
p
∗
runtime  of  the  parallel  algorithm  for  a
p
-processor  machine
c
e
f
f
i
c
i
e
n
c
y
=
runtime  of  the  best  known  sequential  algorithm
total  work  done
.Any parallel algorithm is said to be work optimal if it has a linear speedup and an efficiency of 1.If we have a graph withn nodes, then the maximum number of edges possible in the path connecting the source vertex (
v
1
) and the destination vertex (
v
n
) is n
-
1, so the total number of possible paths can be calculated using the following formula:(24)
Total  no.  of  paths
p
=
∑
i
=
1
n
-
1
n
-
2
!
n
-
i
+
1
!
.Figure 5 shows the several steps of the proposed parallel algorithm for FOP.Figure 5
Several steps of the parallel formulation of FOP.In the parallel formulation of FOP, the moduleS
E
Q
-
N
O
P computes the total number of possible paths (p) for a given input graph G
,
v
1
,
v
n using (24) sequentially. We assume that the number of processors is equal to the total number of paths (p). This value is utilized by the following parallel modules to output the path in G connecting v
1 and v
n that maximizes the total collected score and minimizes the total travel time. If the module P
A
R
-
M
A
X returns more than one path with the same maximum value of membership value (MV), then the module S
E
Q
-
R
D
P sequentially ranks the total collected score (TS) of the paths with the same maximum value of MV using the COC method of ranking fuzzy numbers and using Definition 3 and (3), (4), (5), and (6). Finally, the path with the highest rank is returned as themost desirable path.The pseudocode for each of the modules is as follows.P
A
R
-
P
A
T
H. See Pseudocode 1. The p valid paths can be computed in O
1 time using p CREW PRAM processors.Pseudocode 1
P
r
o
c
e
s
s
o
r
k
(
i
n
p
a
r
a
l
l
e
l
f
o
r
1
≤
k
≤
p
)
d
o
e
s:
c
p
≔
c
o
m
p
u
t
e
a
u
n
i
q
u
e
p
a
t
h
c
o
n
n
e
c
t
i
n
g
v
1
a
n
d
v
n;
i
f
c
p
=
=
V
A
L
I
D
t
h
e
n     // A path is valid if it satisfies the constraints stated in (11), (12), (13), (15), (16) and (17).
D
k
≔
c
p;
e
l
s
e
D
I
S
C
A
R
D
c
p;So,(25)
speed  up
=
O
p
O
1
=
O
p
,
total  work  done
=
O
1
∗
p
=
O
p
,
efficiency
=
O
p
O
p
=
1
.Therefore, this parallel module is work optimal.P
A
R
-
T
O
T. See Pseudocode 2.  The values for TTT and TS for each of the paths in D
k can be obtained in O
1 time using p CREW PRAM processors.Pseudocode 2
P
r
o
c
e
s
s
o
r
k
(
i
n
p
a
r
a
l
l
e
l
f
o
r
1
≤
k
≤
p
)
d
o
e
s:
f
o
r
(
j
=
0
)
d
o:
A
k
j
≔
C
a
l
c
u
l
a
t
e
t
h
e
T
T
T
f
o
r
e
a
c
h
V
A
L
I
D
p
a
t
h
i
n
D
k;
// TTT (Total Time Taken) for each VALID path is calculated using Definition2 and (2).
f
o
r
(
j
=
1
)
d
o:
A
k
j
≔
C
a
l
c
u
l
a
t
e
t
h
e
T
S
f
o
r
e
a
c
h
V
A
L
I
D
p
a
t
h
i
n
D
k;
// TS (Total Collected Score) for each VALID path is calculated using Definition2 and (2).So,(26)
speed up
=
O
p
O
1
=
O
p
,
total work done
=
O
1
∗
p
=
O
p
,
efficiency
=
O
p
O
p
=
1
.Therefore, this parallel module is work optimal.P
A
R
-
M
E
M
B. See Pseudocode 3.  The membership values for TTT and TS for each of the paths in D
k can be calculated in O
1 time using p CREW PRAM processors.Pseudocode 3
P
r
o
c
e
s
s
o
r
k
i
n
p
a
r
a
l
l
e
l
f
o
r
1
≤
k
≤
p
d
o
e
s:
f
o
r
(
j
=
0
)
d
o:
B
k
j
≔
C
a
l
c
u
l
a
t
e
t
h
e
M
V
f
o
r
T
T
T
i
n
A
k
j
f
o
r
e
a
c
h
V
A
L
I
D
p
a
t
h
i
n
D
k;
// MV (Membership Value) for TTT (Total Time Taken) is calculated using Definition4 and (7), (14) and Figure 2.
f
o
r
(
j
=
1
)
d
o:
B
k
j
≔
C
a
l
c
u
l
a
t
e
t
h
e
M
V
f
o
r
T
S
i
n
A
k
j
f
o
r
e
a
c
h
V
A
L
I
D
p
a
t
h
i
n
D
k;
// MV (Membership Value) for TS (Total Collected Score) is calculated using Definition4 and (7), (10) and Figure 1.So,(27)
speed  up
=
O
p
O
1
=
O
p
,
total  work  done
=
O
1
∗
p
=
O
p
,
efficiency
=
O
p
O
p
=
1
.Therefore, this parallel module is work optimal.P
A
R
-
M
I
N. See Pseudocode 4.  The minimum of the two membership values for TTT and TS for each of the paths in D
k can be computed in O
1 time using p CREW PRAM processors.Pseudocode 4
P
r
o
c
e
s
s
o
r
k
(
i
n
p
a
r
a
l
l
e
l
f
o
r
1
≤
k
≤
p
)
d
o
e
s:
f
o
r
(
j
=
0
)
d
o:
L
k
≔
MIN
(
B
[
k
]
[
j
], B
[
k
]
[
j
+
1
]
)
∖
∖ Compute the minimum of the two values using Definition 5 and (8).So,(28)
speed  up
=
O
p
O
1
=
O
p
,
total  work  done
=
O
1
∗
p
=
O
p
,
efficiency
=
O
p
O
p
=
1
.Therefore, this parallel module is work optimal.P
A
R
-
M
A
X. See Pseudocode 5.  The maximum value amongst the values present in the array L can be determined in O
p time using p CREW PRAM processors.Pseudocode 5
P
r
o
c
e
s
s
o
r
k
(
i
n
p
a
r
a
l
l
e
l
f
o
r
1
≤
k
≤
p
)
d
o
e
s:
G
k
≔
G
R
A
D
E
o
f
L
k;
// GRADE of any elementL
k in L is equal to one plus the number of elements in L smaller than L
k.
PRINT the path inD with the greatest G
R
A
D
E in G.So,(29)
speed  up
=
O
p
2
O
p
=
O
p
,
total  work  done
=
O
p
∗
p
=
O
p
2
,
efficiency
=
O
p
2
O
p
2
=
1
.Therefore, this parallel module is work optimal.


## 8. Conclusion

In this paper, we deal with the orienteering problem which is an NP-hard problem and suggest a method to solve the fuzzy orienteering problem. As stated before, in these types of problems, the parameters involved like time and score are naturally imprecise, so representing them using real or crisp numbers leads to an unrealistic presentation of the real world. To provide a realistic model, fuzzy numbers can be used as they are capable of modelling the uncertainty present in the parameters and here we use trapezoidal fuzzy numbers to represent the values of the parameters involved (i.e., time and score). In the literature, the integer program formulation of OP has been stated. For these kinds of formulations, the objective function (either maximization or minimization) and the constraints are to be followed strictly in mathematical sense. However, this may not be the case in real life application where the decision maker may be willing to relax the constraints to some extent to generate a solution that can achieve a level of satisfaction which cannot be represented by the crisp formulation, but the fuzzy version can take care of these requirements. In our work, the two necessary conditions of maximizing the total collected score and that too within the specified time bound is represented by two fuzzy goals and the other requirements like each vertex is visited once, no sub tours are formed etc. are represented as crisp constraints. By representing the two necessary conditions in the form of fuzzy goals we provide a latitude to the desired solution by relaxing the constraints as can be observed in Figures1 and 2 where we have fixed a time bound T
m
a
x and a minimum score S
m
i
n for the desired solution, but we accept solution up to T
m
a
x
+
L and S
m
i
n
-
P up to different degrees and this helps the decision maker to achieve the level he wants in his solution. This approach requires that the shapes and parameters for the membership functions be decided depending on the application at hand taking into account the extent of uncertainty prevailing. To make the proposed method applicable to large instances, we also present a work optimal parallel formulation of FOP. When provided with several graphs as input, further speedup can be expected since the stages will form a 5-stage linear pipeline providing a speedup of 5 ideally when all the stages are busy. In this way the method suggested above provides a more practical illustration of the physical world and generates a solution that is more appropriate and realistic.



---

*Source: 569248-2015-07-13.xml*