GGenetic Algorithm with Path Relinking for the Orienteering Problem with Time WindowsJoanna Karbowska-Chilinska0Pawel Zabielski0Faculty of Computer Science Bialystok University of Technology
,
Poland23245258
The Orienteering Problem with Time Windows (OPTW) is an optimisation NP-hard problem. This paper proposes a hybrid genetic algorithm (GAPR) for approximating a solution to the OPTW. Instead of the usual crossover we use a path relinking (PR) strategy as a form of intensification solution. This approach generates a new solution by exploring trajectories between two random solutions: genes not present in one solution are included in the other one. Experiments performed on popular benchmark instances show that the proposed GAPR outperforms our previously published version of GA and yields better results than the well-known iterated local search method (ILS) as well.
orienteering problem with time windowsgenetic algorithmpath relinkingIntroduction
The Orienteering Problem with Time Windows (OPTW) is a type of
optimisation routing problem first introduced by Kantor et al. [
7
]. The OPTW can be
modelled as a weighted graph with a positive score/profit associated with each
vertex. Let G be a graph with n vertices, in which each vertex i has a profit
pi, a service time Ti and a time window [Oi; Ci], where Oi and Ci denote the
opening and closing times of a vertex i. Each edge between vertices i and j has a
fixed cost tij associated with it. The value tij is interpreted as the time or length
needed to travel between vertices. The objective is to determine a single route,
from a starting point s to a fixed ending point e, that visits some of the vertices
within the fixed time windows and maximises the total profit. In addition, the
total cost of the edges on the path must be less than the given constraint tmax
and each vertex on the route is visited only once. It is possible to wait at a vertex
for service before its time windows opens.
The OPTW is derived from the more general Orienteering Problem (OP)
[
23
], [
14
]. In the OP each vertex inserted into the route could be visited in any
time interval (there is no restriction in the form of time windows). The OP is
seen as a combination of the Knapsack Problem and the Travelling Salesperson
Problem, because in the OP the selected route limited in length contains the
most profitable vertices. Both the OP and the OPTW are NP-hard [
7
].
Numerous applications can be found for the OPTW, e.g. in logistics for
planning optimal routes, such as profitable delivery routes, as well as in optimisation
of production scheduling [
20
]. The OPTW successfully models problems related
to tourism [
24
]. Tourists visiting a city are usually unable to visit all points
of interests (POI) because they are limited by time or money. The most
effective heuristics for the OPTW are applied in electronic devices known as mobile
tourist guides [
24
], [
2
] which make it possible to visit the most valuable POIs
(taking into account their opening and closing times) within a fixed time limit.
The Team Orienteering Problem with Time Windows (TOPTW) [
12
], which is
an extension of the OPTW, is used to model multiple tours, with each tour
satisfying the same fixed travel length or time constraint.
In this paper we present an improved version of the genetic algorithm for the
OPTW described in [
10
]. We use hybridization of our genetic algorithm with a
path relinking method (PR) instead of the crossover operator. In the PR
approach two random solutions are chosen and routes combining these solutions
are explored to provide better solutions: genes not present in one solution are
included in the other one. Path relinking was originally described by Glover [
5
]
and Laguna [
6
] for intensification and diversification of the tabu search method.
Moreover, the PR significantly improves the results of the Greedy Randomised
Adaptive Search Procedure (GRASP) for the general version of OP [
21
], [
1
].
This led us to use this method in combination with the previously developed
genetic algorithm for solving the OPTW [
10
].
The remainder of the paper is organised as follows. The mathematical
formulation of the problem is presented in Section 2. An overview of the main
approaches in the literature is presented in Section 3. In section 4, we describe
the concept of the hybrid genetic algorithm with path relinking. The results of
computational experiments illustrating the effectiveness of our approach in
comparison with other methods are discussed in Section 5. Concluding remarks and
plans for further research are given in Section 6.
2
Mathematical formulation
Based on the notation introduced in the previous section the OPTW can be
formulated as an mixed integer problem as follows [
26
]:
n 1 n
max ∑ ∑ pixij
i=1 j=2
n
∑ x1j =
j=2
n 1
∑ xin = 1
i=1
n 1
∑ xik =
i=1
starti + Ti + tij
startj 6 M
(1
xij )
Oi 6 starti 6 Ci 8i = 1; :::; n
(4)
(5)
(6)
where xij are binary variables, such that xij = 1 if the edge between i and j is
included in a solution, and xij = 0 otherwise. Moreover, we assume that s=1
and e = n. Let starti denote the start of service time at vertex i and M be a
large constant. The objective function (1) maximises the total collected profit of
the route. The constraint in (2) guarantees that the path starts at vertex 1 and
ends at vertex n. Constraint (3) requires that there may be at most one visit to
any vertex. The constraint in (4) ensures that the time of the route is limited by
tmax. Constraint (5) ensures the timeline of the route. The start of the service
is restricted by a time window as in (6).
3
Literature review
It can be easily observed that the OPTW is a special case of the TOPTW: in the
OPTW one route is constructed, while in TOPTW several routes are generated.
Methods for the TOPTW could also be applied to the OPTW. Therefore, in
this section we present solution approaches described in the literature for the
OPTW as well as the TOPTW.
The Orienteering Problem with Time Windows has been studied since Kantor
and Rosenweins article [
7
]. Their insertion heuristic constructs a route by
iteratively inserting the vertex with the highest ratio score=T imeInsertion without
violating time windows and tmax constraints. In the second method proposed,
they developed what is known as a tree heuristic, in which a depth-search
algorithm constructs routes that begin in a given vertex. If a route is infeasible or
unlikely to yield a better result, the route is abandoned. In this case the
algorithm backtracks to the previous level of the tree and attempts to insert another
vertex.
Righini et al. [
18
] developed an exact optimisation algorithm for the OPTW
based on bi-directional dynamic programming. This technique requires extension
of non-dominated states from both sides of the route: forward from the start
vertex and backward from the end vertex. The decremental state relaxation method
was also introduced for this algorithm with the idea of iteratively reducing the
number of explored states [
19
].
Mansini et al. [
17
] introduced the Granular Variable Neighbour Search
approach for TOPTW based on the idea of exploring a reduced neighbourhood
instead of a complete one and not including arcs that are not promising. The
method improved algorithm efficiency with no loss of effectiveness. A more
general concept of granularity was described in [
11
]. The cost of an arc was identified
by the formula (tij + wij )=(pi + pj ), where wij is the maximum possible waiting
time at j provided that the service at i is assumed to start at the fixed time.
Promising arcs were identified as follows: the lower the reduced cost associated
with the arc, the higher the probability it will belong to a good solution.
Montemanni et al. [
15
] proposed a solution model using hierarchical
generalization of TOPTW based on an Ant Colony System (ACS) algorithm. Two
improvements to the ASC method were included in the ACS [
16
]: the
constructive phase was sped up by considering the best solution computed so far, and
the local search procedure was applied only to those solutions to which it had
not been applied in the previous iteration (the same route was not optimised
too often).
Tricoire et al. [
22
] adapted a solution to the Multi-Period Orienteering
Problem with Multiple Time Windows for the TOPTW. They proposed an exact
algorithm for the path feasibility sub-problems, and embedded it in a variable
neighbourhood search (VNS) approach to solve the whole problem.
Vansteenwegen et al. proposed the Iterated Local Search approach (ILS) [
25
]
to tackle the TOPTW. Because it is the fastest known heuristic, ILS is applied,
for example, in electronic devices such as mobile tourist guides [
4
], [
24
]. The ILS
method iteratively builds and improves one route by combining an insertion step
and deletion of some consecutive locations (a shake step) to escape from a local
maximum.
Lambadie et al. [
12
] developed a method for solving TOPTW which combines
a greedy randomised adaptive search procedure (GRASP) with an evolutionary
local search (ELS). In the ELS phase deletion and insertion mutations are
performed for multiple child solutions. Child solutions are further improved by a
variable neighbourhood descent procedure. The GRASP ELS method gives the
best results on benchmark instances in comparison with the other methods
mentioned [
11
]
4
Genetic Algorithm
The proposed method, called GAPR, is an extended version of the genetic
algorithm GA proposed in [
10
]. The individuals (routes) are encoded as a sequence
of vertices (genes). The GAPR starts by generating an initial population of
Psize routes. Next, each individual is evaluated by means of the fitness function
F . We use F as in [
10
], [
8
], [
9
], which is equal to T otalP rof it3/T ravelT ime.
T otalP rof it and T ravelT ime denote the sum of the profits assigned to the
vertices on the route and the total travel time from the starting point to the
ending point. In subsequent iterations of the GAPR the population is evolved
by applying genetic operators selection, recombination and mutation in order
to create new, better routes. The optimisation strategy, in contrast with the
method proposed in [
10
], involves a recombination stage (crossover) performed
on two random routes: instead of randomly choosing a crossing point between
vertices with similar time windows and starting and ending time of service [
10
],
we used a path relinking process. In this process routes in the graph solution
space connecting two random solutions are explored in order to find better
solutions [
5
], [
6
]. To generate new solutions between selected random routes, genes
not present in one route are included in the other. The solution generated by the
path relinking process corresponds to the best individuals that could be obtained
by applying the crossover operator to the same random parents.
The GAPR terminates after a fixed number of generations (denoted by Ng),
or earlier if it converges. The GAPR result is the route in the final population
with the highest profit value. The basic structure of the GAPR is as follows:
compute initial population;
algLoop=0;
while algLoop< Ng do
algLoop++;
tournament grouping selection;
path relinking;
mutation;
if no improvements in last 100 iterations then break;
end;
return the route with the highest profit value;
Due to randomization, the GAPR is run several times during the tests. Each
successive repetition of the GAPR is independent of the others, so this is a prime
target for parallelisation. OpenMP [
13
], which is an API, is used in the algorithm
for parallel computations, which substantially reduce its execution time.
The application of genetic operators for selection, recombination and creation of
new individuals is described in more detail below.
4.1 Initialisation
In the approach presented a route is coded as a sequence of vertices. A population
of Psize routes is generated as follows. First the chromosome is initialized by
the s and e vertices. Then the following values are assigned sequentially to the
initialized vertices: arrivei - arrival time at vertex i, waiti - waiting time, if the
arrival at the vertex i is before opening time, starti and endi - starting and
ending service time at vertex i. Moreover, the maximum time the service of a
visit i can be delayed without making other visits infeasible is calculated for each
location in the route as follows [
25
]:
M axShif ti = M in(Ci
starti
Ti; waiti+1 + M axShif ti+1)
(7)
Let l be the predecessor of vertex e in the route. In the subsequent steps a
set of vertices is prepared. Each vertex v from this set is adjacent to vertex l
and vertex e and will satisfy the following conditions after insertion: (a) startv
and endv are within the range [Ov; Cv]; (b) the locations after v could be visited
in the route; and (c) the current travel length does not exceed the given tmax
(including consumption time to insert the vertex v between l and e). A random
vertex v is chosen from this set. The values arrivev, waitv, startv and endv are
calculated and the vertex v is inserted. After the insertion, the values arrivee,
waite, starte and ende are updated. Moreover, for each vertex in the tour (from
vertex e to s) the M axShif t value is updated as well. The tour generation is
continued for as long as locations that have not been included are present and
tmax is not exceeded.
4.2
Selection
We use tournament grouping selection, which yields better adapted individuals
than standard tournament selection [
9
]. In this method a set of Psize individuals
is divided into k groups and the tournaments are carried out sequentially in each
of the groups. tsize random individuals are removed from the group, the
chromosome with the highest value for the fitness function T otalP rof it3=T ravelT ime
is copied to the next population, and the tsize previously chosen individuals are
returned to the old group. After selection from the group currently analysed has
been repeated Psize=k times, Psize=k individuals are chosen for a new
population. Finally, when this step has been repeated in each of the remaining groups,
a new population is created, containing Psize routes.
4.3
Path relinking
First two random routes R1 and R2 are selected from the new population chosen
in the selection step. Let VR1 R2 be the set of vertices present in R1 and not
in R2 , and let VR2 R1 denote the set of vertices present in R2 and not in R1.
During PR(R1; R2) we attempt to insert vertices from VR2 R1 into R1 in the best
possible position. The total consumption time associated with inserting a vertex
j between vertex i and k is calculated as follows [
25
]: Shif tj = tij + waitj +
Tj + tjk tik. In addition, we check whether the shift resulting from the new
insertion exceeds the constraints associated with the previously calculated wait
and M axShif t values for the vertices located directly after the newly inserted
one. If the shift exceeds the constraints the vertices from VR1 R2 are removed to
restore the possibility of inserting new locations. For each vertex u from this set
a ratio is calculated as follows: RemovalRatio = (pu)2=(endu arriveu), with
the power 2 having been determined experimentally. After this computation
the vertex with the smallest value for RemovalRatio is removed. This removal
is repeated until we can insert some vertices into the path. Finally the vertex
u with the highest value for (pu)2=Shif t(u) and not exceeded the mentioned
constrains is selected for insertion. After u is inserted the values of arriveu,
waitu, startu and endu are calculated. For each location after u the arrival time,
waiting time, and start and end of service are updated. M axShif t values are
also updated for the vertices from the starting point to the ending point of the
route. As we can see, the insertion of one vertex from VR2 R1 into R1 is a
multistage process. The process is repeated for as long as tmax is not exceeded and
the set VR2 R1 is not empty. In addition, we perform PR(R2, R1) by inserting
vertices from VR1 R2 into R2. Two new routes are created as a result of PR(R1,
R2) and PR(R2, R1). If the fitness values of the new routes are higher than the
fitness value of R1 and R2, they replace them.
4.4
Mutation
In this phase a random route is selected from Psize individuals. Two types of
mutation are possible a gene insertion or gene removal (the probability of each
is 0.5). The mutation process is repeated on the selected route Nm times, where
Nm is the parameter. During the insertion mutation, all possibilities for inclusion
of each new vertex (not present in the route) are considered in the same way as
in the path relinking process. The locations before and after the inserted vertex
should be updated as in the case of the insertion process in the path relinking.
In the deletion mutation we remove a randomly selected gene (excluding the
first and last genes) in order to shorten the travel length. After the gene is
removed, all locations after the removed gene are shifted towards the beginning
of the route. Furthermore, the locations before and after the removed gene are
updated as in the insertion mutation.
5
Experimental Results
The GAPR was coded in C++ and run on an Intel Core i7, 1.73 GHz CPU (turbo
boost to 2.93 GHz). The algorithm was tested on Solomon [
20
] and Cordeau [
3
]
test instances for the OPTW. The number of vertices in the Solomon instances
is equal to 100 and different layouts for the vertices are considered: cluster (c),
random (r) and random-clustered (rc) classes. The Solomon benchmarks c200,
r200, rc200 and c100, r100, rc100 have the same coordinates of vertices, profits
and visiting times, but the c n r n rc200 instances have approximately three times
higher values of tmax and larger time windows than the c n r n rc100 instances.
The Cordeau instances vary between 48 and 288 vertices.
The parameters of the GAPR were determined by performing several tests
on a selected subset of Solomon and Cordeau instances. Preliminary tests
identified the following as good performing parameters: 150 for the initial population
size, 3 for the number of individuals chosen from the group in the tournament
selection, and 15 for the number of groups in the tournament selection. Based on
the tests described in [
10
], the Nm number of mutations repeated on the selected
route was set to 15.
Detailed results obtained by the GAPR on benchmark instances in
comparison with other methods are given in Tables 2 - 4. There are two columns for
the GAPR, denoted GAPR(I) and GAPR(II). The first reports the results
obtained by considering only PR(R1; R2) in the path relinking (in each iteration
of the algorithm). The second shows the results of the use of both PR(R1; R2)
and PR(R2; R1) during the path relinking. For comparison of the results, the
best known solution value (BK) (solutions obtained by GRASP ELS and ACS
algorithm [
12
], [
16
]), the GA (with crossover) [
10
] and ILS [
25
] are also reported.
In the BK columns the optimal values when are known are marked in italic. The
GAPR was tested by performing sixteen runs concurrently two runs each on
eight processor cores. The results of the GA were obtained with sixteen runs
of the algorithm (without concurrency) on the same computer used to run the
GAPR. The total time of the sixteen runs (expressed in seconds) and the
minimum, average, and maximum solutions are given in the tables for the GA and
the GAPR. The ILS (deterministic algorithm) results were obtained with one
run [
25
]. Tables 2 - 4 also show the average percentage gap between the best
known solution (BK) values and the average value of the GAPR, and for
comparison, the gaps between BK and the other methods mentioned. An empty cell
denotes a gap equal to 0.
The results presented in Tables 2 - 4 indicate that the GAPR outperforms
the ILS results on c n r n rc100, c n rc200 and the Cordeau instances. Only in the
case of r200 does the ILS perform slightly better than the GAPR (the ILS has a
smaller gap than the GAPR, by about 0.4%). The average gap between the BK
and the ILS results for all these instances is 3.6%, while the gaps between BK
and GAPR(I) and GAPR(II) are 2.4% and 2.5%, respectively. Because the use
of PR(R1, R2) and PR(R2, R1) results in faster convergence of the algorithm,
in some cases (e.g. rc200) the creation of two new routes in each iteration of
GAPR(II) yields worse results than calculation of only one route as in GAPR(I).
For comparison, the average gap between BK and the previous genetic algorithm
GA is 5.6%. The application of the path relinking stage in place of the crossover
significantly improves the GAPR results by about 6% in comparison to the GA.
As a result of the parallel computing, the GAPR is on average 22 times faster
than the GA and its execution time is comparable with the ILS. Moreover, the
GAPR provides several new best solutions on Cordeau instances p11, p15, p17
and p19, whose improved values are given in bold in Table 4. There are not an
known optimal values for these instances [
11
]. Examples of the best-generated
routes by GAPR for pr17 and pr15 are presented in Figure 2. Comparison the
GAPR with the GA and the ILS results for these benchmarks is presented in
Table 1.
The number of generations in the GAPR was experimentally set to 500 as the
stopping criterion. As seen in Figure 1 in the case of the pr11-20 the best routes
were generated earlier than 500 generations (the exception is the pr20, where
the result was only better about 2% after 620 generations). Therefore, for the
optimisation of the execution time, the algorithm was stopped earlier if were not
any improvements in the lengths of the routes by 100 generations.
6
Conclusions and Further Work
This paper presents the application of the genetic algorithm hybridised with
the path relinking method to the Orienteering Problem with Time Windows.
Using path relinking instead of crossover improves the results on benchmark
instances by about 6%. Moreover, the proposed GAPR algorithm outperforms
the results of the ILS heuristic, while the execution times of the two algorithms
are comparable. The ILS is very fast and is applied, for example, in mobile
tourist guide applications [
25
]. The proposed heuristic can also be adapted to
solve problems related to planning tourist routes.
Further research directions include improving the GAPR results by applying
path relinking operators between pairs of elite solutions (known as evolutionary
path relinking) and conducting tests on a realistic database. Moreover, we intend
to focus our research on developing effective heuristics for the Team Orienteering
Problem with Time Windows, which is an extension of the OPTW.
p15
p17
ILS
GA
ILS
GA
GAPR 68775GAPR 70955
Acknowledgements
69643
60801
70696
70324
346
353
360
method length of profit
the route
route
The authors gratefully acknowledge support from the Polish Ministry of
Science and Higher Education at the Bialystok University of Technology (grant
S/WI/1/2011 and W/WI/2/2013).
i G
w
)
I
K (
B R
p P
a A
g G
%A
1 i 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 2
t
e
s m .2 .2 .3 .3 .2 .2 .2 .3 .3 .2 .2 .2 .3 .3 .2 .2 .3 .4 .2 .3 .3 .2 .0 .2 .3 .3 .2 .2 .2 .2 .2 .8
’
i 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1
n t
o
4 5
eam r1p r2p r3p r4p r5p r6p r7p r8p r9p r01p : 1 1 r r r r r
1 2 31 14 15 16 17 r8 r9 r0
1 1 2 :
r r
m p p p p p p p p p p m
[1]
Campos
,
V.
,
Marti
,
R.
,
Sanchez-Oro
,
J.
,
Duarte
,
A.
:
Grasp with Path Relinking for the Orienteering Problem
.
Technical Raport
,
116
(
2012
)
[2] http://www.citytripplanner.com/en/home . Last access: June 29,
2013
[3]
Cordeau
,
J.F.
,
Gendreau
,
M.
,
Laporte
, G.:
A tabu search heuristic for periodic and multi-depot vehicle routing problems
.
Networks30
(
2
)(
1997
)
105
-
119
[4]
Garcia
,
A.
,
Vansteenwegen
,
P.
,
Arbelaitz
,
O.
,
Souffriau
,
W.
,
Linaz
,
M.
:
Integrating Public Transportation in Personalised Electronic Tourist Guides
.
Computers & Operations Research
.
40
(
2013
)
758
-
774
[5]
Glover
,
F.
:
A TemplateFor Scatter Search And Path Relinking
.
Lecture Notes in Computer Science
.
1363
(
1997
)
13
-
54
[6]
Glover
,
F.
,
Laguna
,
M.
:
TabuSearch
. Kluwer Academic Publishers. Boston (
1997
)
[7]
Kantor
,
M.
,
Rosenwein
,
M .:The Orienteering Problem with Time Windows
.
Journal of the Operational Research Society
.
43
(
1992
)
629
-
635
[8]
Karbowska-Chilinska
,
J.
,
Koszelew
,
J.
,
Ostrowski
,
K.
,
Zabielski
,
P.
:
Genetic algorithm solving orienteering problem in large networks
.
Frontiers in Artificial Intelligence and Applications
.
243
(
2012
)
28
-
38
[9]
Karbowska-Chilinska
,
J.
,
Koszelew
,
J.
,
Ostrowski
,
K.
,
Zabielski
,
P.:A Genetic Algorithm with Grouping Selection and Searching Operators for the Orienteering Problem. (under review)
[10]
Karbowska-Chilinska
,
J.
,
Zabielski
,
P.:A Genetic Algorithm Solving Orienteering Problem with Time Windows. (accepted for publication inSpringer series: Advances in Intelligent Systems and Computing)
[11]
Labadie
,
N.
,
Mansini
,
R.
,
Melechovsky
,
J.
,
WolflerCalvo
,
R.
:
The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search
.
European Journal of Operational Research
.
220
(
1
) (
2012
)
15
-
27
[12]
Labadie
,
N.
,
Melechovsk
,
J.
,
WolflerCalvo
, R.:
Hybridized evolutionary local search algorithm for the team orienteering problem with time windows
.
Journal of Heuristics
.
17
(
6
) (
2011
)
729
-
753
[13] http://openmp.org/wp/ .
Last access: June29
,
2013
[14]
Ostrowski
,
K.
,
Koszelew
,
J.:The comparison of genetic algorithm which solve Orienteering Problem using complete an incomplete graph
.
Zeszyty Naukowe, Politechnika Bialostocka. Informatyka8
(
2011
),
61
-
77
[15]
Montemanni
,
R.
,
Gambardella
,
L.M.:Ant colony system for team orienteering problems with time windows
.
Foundations of Computing and Decision Sciences
.
34
(
2009
)
[16]
Montemanni
,
R.
,
Weyland
,
D.
,
GambardellaL. M.:An Enhanced Ant Colony System for the Team Orienteering Problem with Time Windows
.
Proceedings of IEEE ISCCS 2011 The 2011 International Symposium on Computer Science and Society
, Kota Kinabalu,
Malaysia381
-
384
(
2011
)
[17]
Mansini
,
R.
,
Pelizzari
,
M.Wolfler
, R.:
A GranularVariableNeighborhood Search for the Tour Orienteering Problem with Time Windows
,
Technical Report of the Department of Electronics for Automation
, University of Brescia (
2006
)
[18]
Righini
,
G.
,
Salani
,
M.
:
New dynamic programming algorithms for the resource constrained elementary shortest path
.
Networks
.
51
(
3
) (
2008
)
155
-
170
[19]
Righini
,
G.
,
Salani
,
M.:Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming
.
Computers & Operations Research
.
36
(
2009
)
1191
-
1203
[20]
Solomon
,
M.
:
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
.
Operations Research35
(
2
) (
1987
)
254
-
265
[21]
Souffriau
,
W.
,
Vansteenwegen
,
P.
,
Vanden Berghe
, G.,
Van Oudheusden
,
D.
:
A Path Relinking approach for the Team Orienteering Problem
,
Computers & Operations Research
,
37
(
11
) (
2010
)
1853
-
1859
[22]
Tricoire
,
F.
,
Romauch
,
M.
,
Doerner
,
K. F.
,
Hartl
,
R. F.Heuristics for the multiperiod orienteering problem with multiple time windows
.
Comput. Oper. Res
.
34
(
2
) (
2010
)
351
-
367
[23]
Tsiligirides
,
T.
:
Heuristic methods applied to orienteering
.
Journal of the Operational Research Society
.
35
(
9
) (
1984
)
797
-
809
[24]
Vansteenwegen
,
P.
,
Souffriau
,
W.
, Vanden Berghe, G.,
Van Oudheusden
,
D.
:
The City Trip Planner: An expert system for tourists
.
Expert Systems with Applications
.
38
(
6
) (
2011
)
6540
-
6546
[25]
Vansteenwegen
,
P.
,
Souffriau
,
W.
, Vanden Berghe, G.,
Van Oudheusden
,
D.
:
Iterated local search for the team orienteering problem with time windows
.
Computers O.R
.
36
(
2009
)
3281
-
3290
[26]
Vansteenwegen
,
P.
,
Souffriau
, W.,
Van Oudheusden
,
D..The Orienteering Problem: A survey
.
European Journal of Operational Research
.
209
(
1
) (
2011
)
1
-
10
.
emP . 9 8 9 g 0 00 9 0 0 0 0 0 7 89 86 93 98 47 93 99 08 73 81 97 95 6 61 66 65 01 41 50 73 97 0l A v 26 0 0 4 4 6 7 8b G a 33 4 4 3 3 3 3 3 2 1 2 2 2 2 2 2 3 2 2 2 2 3 2 2 2 3 2 2 2 2 1 3 3 2 0 9 3in 20 60 00 00 40 40 60 70 80 7 89 86 93 97 47 93 99 03 70 81 97 95 5 61 66 65 97 41 49 71 88 9 9t P . 0c G ag 80 94 90 90 90 96 90 90 39 798 890 968 0142 859 0051 1031 1098 923 960 0119 016 707 900 936 0179 842 856 930 0134 7437n A v 62 6 7 0 0 2 5o 7 1 3inm 608 209 609 709 009 508 209 509 33 787 888 619 1042 849 999 1023 1080 920 960 1019 075 786 878 984 1077 838 856 916 10347432 0 7 1 1
mP .
4loo AG gav 608 209 579 689 009 199 309 409 93 677 858 699 3011 952 0071 1041 1074 927 944 0103 085 798 991 965 1123 842 859 948 0105 7244 7S 1r 0 5f inm 608 209 509 609 009 009 309 409 63 277 838 659 1031 900 996 1023 1057 903 933 1002 064 778 991 935 1123 842 857 946 1005 7243o 7 1e axm 608 209 409 709 009 109 309 409 73 287 928 809 5011 952 987 0122 1086 927 944 0107 006 749 923 923 1107 837 865 928 0132 7742 0l 7b A 1