Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.12 No.3 pp.198-206
DOI : https://doi.org/10.7232/iems.2013.12.3.198

Solving the Team Orienteering Problem with Particle Swarm Optimization

The Jin Ai*, Jeffry Setyawan Pribadi, Vincensius Ariyon
Department of Industrial Engineering, Faculty of Industrial Technology, Universitas Atma Jaya Yogyakarta, Indonesia
(Received: January 17, 2013 / Revised: August 29, 2013 / Accepted: September 10, 2013)

Abstract

The team orienteering problem (TOP) or the multiple tour maximum collection problem can be considered as a genericmodel that can be applied to a number of challenging applications in logistics, tourism, and other fields. This problemis generally defined as the problem of determining P paths, in which the traveling time of each path is limited byTmax that maximizes the total collected score. In the TOP, a set of N vertices i is given, each with a score Si. The startingpoint (vertex 1) and the end point (vertex N) of all paths are fixed. The time tij needed to travel from vertex i to j isknown for all vertices. Some exact and heuristics approaches had been proposed in the past for solving the TOP. Thispaper proposes a new solution methodology for solving the TOP using the particle swarm optimization, especially byproposing a solution representation and its decoding method. The performance of the proposed algorithm is then evaluatedusing several benchmark datasets for the TOP. The computational results show that the proposed algorithmusing specific settings is capable of finding good solution for the corresponding TOP instance.

 

12-3-04 (198-206) Ai, Pribadi, and Ariyono.pdf314.8KB

1. INTRODUCTION

 The orienteering problem (OP) is a generic problem for determining a single path in order to maximize the total collected score by visiting some vertices through the path, in which a set of vertices is given, each with score; the starting and ending point of the path is given, the travel time from any vertex to any vertex (tij) is known, and the traveling time of the path is limited by Tmax. Tsiligirides (1984) mentioned that OP can be applied to a special case of the traveling salesman problem (TSP) in which the salesman does not have enough time to visit all possible cities. He knows the number of expected sales in each city and wants to maximize total sales, while keeping the total travel time limited to a day or a week. Souffriau et al. (2008) applied the OP for solving a tourist route problem. Since it is often impossible to visit all the tourist attractions in a region visited by the tourist, they have to select what they believe to be the most valuable attraction in the region.

 The team orienteering problem (TOP) is an OP with goal to determine several paths, each is limited by Tmax that maximizes the total collected score. Butt and Cavalier (1994) described a TOP application of athlete recruitment from high schools. A recruiter has to visit several schools, limited by number of days. He can assign a score for each school, based on its recruiting potential. Then, the TOP can help the recruiter to choose the schools to visit each day to maximize the total recruiting potential. The total number of paths in the TOP is corresponding to the total number of recruiting days, and each path in the TOP is corresponding to the recruiter daily route visiting the selected schools.

 Since the TOP is an NP-hard problem, some exact and heuristics approaches had been proposed in the past for solving the TOP. However, the capability of particle swarm optimization (PSO) has not been explored much in order to solve the TOP. Therefore, this paper tries to solve the TOP by using a PSO algorithm. The structure of this paper is as follows: Section 2 provides literature review on TOP. Section 3 describes the PSO for solving the TOP. Section 4 presents the computational result, and the last section concludes the paper and gives suggestions for further research.

2. LITERATURE REVIEW

 Some researchers in the past had proposed methodology for solving TOP as reviewed by Vansteenwegen et al. (2011) who summarized existing and up-to-date research on TOP. They listed several algorithms including heuristics, Tabu search, variable neighborhood search, ant colony optimization, and greedy randomized adaptive search procedure (GRASP) with path relinking that has been successfully applied to TOP.

 Chao et al. (1996a) presented the first heuristic algorithm for solving the TOP which is similar to their fivestep heuristic algorithm for OP (Chao et al., 1996b). They also contributed in collecting datasets of OP and TOP cases that are being used for comparing the performance of OP and TOP algorithms. It is noted that they organized the datasets into 7 sets.

 Tang and Miller-Hooks (2005) proposed a Tabu search heuristic (TMH) algorithm for solving the TOP. They compared the Tabu search method with the method of Chao et al. (1996a) and found that the Tabu search was able to produce better solution than the Chao et al. (1996a) method. Archetti et al. (2007) also proposed some variants of Tabu search and variable neighborhood search for solving the TOP, which are called Tabu search with penalty strategy (GTP), Tabu search with feasible strategy (GTF), fast variable neighborhood search (FVF), and slow variable neighborhood search (SVF).

 Another approach for solving TOP is proposed by Ke et al. (2008) by using ant colony optimization. Based on the method to construct feasible solutions, they proposed four variations of ant colony algorithm, which are sequential (ASe), deterministic-concurrent (ADC), random- concurrent (ARC), and simultaneous ant colony algorithms (ASi).

 Two contributions from Vansteenwegen et al. (2009a, 2009b) are able to solve the TOP within seconds of computational time. For solving the TOP, Vansteenwegen et al. (2009a) implemented the guided local search (GLS) and Vansteenwegen et al. (2009b) implemented skewed variable neighborhood search (SVNS).

 Souffriau et al. (2010) proposed two GRASP with path relinking algorithms for solving TOP, which are fast path relinking (FPR) and slow path relinking (SPR). The difference between these two algorithms is only the stopping criterion. The SPR requires more iterations than FPR. They also compared their algorithms with above mentioned methods for solving TOP including TMH, GTP, GTF, FVF, SVF, ASe, ADC, ARC, ASi, GLS, and SVNS using TOP benchmark datasets of Chao et al. (1996b) number 4 to 7 consist of 157 cases. Their comparison is reproduced here in Table 1. From Table 1, they claimed that that SPR is the best method for solving TOP, since it can produce 131 best known solution with average gap 0.06% from the best known results, consuming in average 212.4 seconds of computational time.

Table 1. Summary of results after Souffriau et al. (2010)

 Recently, Muthuswamy and Lam (2011) proposed a discrete particle swarm optimization (DPSO) for solving TOP. They used discrete version of PSO, in which the particle position is represented in the domain of integer number, combined with reduced variable neighborhood search and 2-opt as the local search method.

 This paper proposes a PSO algorithm for solving TOP, based on the simplest version of continuous PSO, in which the particle position is represented as real number and implemented purely from any local search. Therefore, the particle movement mechanism of this PSO that will be described in Section 3 is totally different with DPSO of Muthuswamy and Lam (2011). In order to do benchmarking, the result of Souffriau et al. (2010) will be referenced so that the result of proposed PSO can be placed in the performance of existing approaches completely, in which the similar TOP benchmark datasets number 4 to 7 of Chao et al. (1996b) will be used as the case problems. In addition, this paper also provides a comparison between the proposed continuous PSO with the existing DPSO for solving the TOP.

3. PSO FOR SOLVING TOP

3.1 Particle Swarm Optimization

 PSO is a population based stochastic optimization technique developed by Eberhart and Kennedy in 1995, inspired by social behavior of swarm organism such as flock of bird or school of fish (Hu, 2006).

 Clerc (2004) stated that the basic principle of PSO is a set of moving particles placed inside the search space. Each particle has the following characteristics:

1) It has a position (θ) and velocity (ω). Its positions are multi-dimensional, and can be translated or decoded into problem specific solution, which will evaluate its corresponding objective function for minimization or maximization. The particle is moving from a position into different position following its velocity. 

 2) It knows its position and the objective function value of this position, and it also remembers its best previous position or usually called as personal best or pbest (ψ).

3) It knows the best of all particles’ personal best or usually called as global best or gbest.

The movement of particle in certain period of time or iteration is driven by three different directions that are: 1) Follow its own way, 2) Go towards its personal best position, and 3) Go towards its global best position. Therefore the particle movement can be formulated as following equations:

 

 

where τ is iteration index, l is particle index, h is dimension index, u is uniform random number in interval [0, 1], w(τ) is inertia weight in the τth iteration, ωlh(τ) is velocity of lth particle at the hth dimension in the τth iteration, θlh(τ) is position of lth particle at the hth dimension in the τth iteration, ψlh is personal best position (pbest) of lth particle at the hth dimension, ψgh is global best position (gbest) at the hth dimension, cp is personal best acceleration constant, and cg is global best acceleration constant. 

 Eq. (2) shows that the particle position of next period is obtained from the sum of the current position with the velocity of the next period. Eq.(1) shows that the velocity of next period obtained from the sum of the multiplication of inertia, cognitive, or social weights (w, cp, and cg) with current velocity, pbest, and gbest. Generally, the algorithm of PSO is defined as follow:

 - Initialization: Determine the number of particles (N), the particle’s position (can be random or defined), and particle’s velocity.
 - Decode particles into solution.
 - Evaluate the particles, based on the objective function.
 - Update pbest value,
 - Update gbest value,
 - Update velocity and position for each particle,
 - If the stopping criterion is reached, stop. Otherwise return to decoding step.

 The PSO algorithm has been applied for solving various optimization problems, such as TSP (Clerc, 2004), protein motif discovery (Chang et al., 2004), as well as the vehicle routing with simultaneous pickup and delivery by Ai and Kachitvichyanukul (2009).

3.2 Solution Representation

 In a simple functional optimization, the dimension of particles in the PSO is represented by the number of variables used in the function, and can directly be decoded as a value of the variables. However, in this research, particle’s position cannot directly be decoded or represents the solution, because the solution of TOP is not just a value of variables, but is a sequence of vertices. Therefore, it needs a specific step to decode a particle position into a TOP solution that can be explained as follow:

1) The particle’s dimension represents number of vertices in TOP, dimension 1 represent vertex 1, and so on. 

 2) The particle’s position is a real number and represents priority of the vertex on the decoding step. The smaller the position will result in a higher priority on the vertex.

 3) Based on the priority, each vertex is evaluated to be inserted to the solution path.

 The first and last vertex are excluded from the priority setting of the vertex, since they are representing the starting and ending point of each path that cannot be changed. Figure 1 shows an illustration of the decoding process of the PSO for solving TOP with 10 vertices. In Figure 1, the sequence of the paths is simply constructed from the vertex priority. In this paper, before a vertex is permanently assigned to a path, it has to be evaluated based on the total service time of the path. If the time needed exceeds the limit (Tmax), the vertex cannot be inserted into that path.

Figure 1. Illustration of decoding process.

3.3 Initialization

 In the initialization stage, the initial position of the first particle is obtained from score of each vertex. The score from each vertex is copied and converted into variable SPar, by using equation:

 

 where range = max – min, min is the minimum x or y coordinate for all vertices, max is the maximum x or y coordinate for all vertices, and Sj = score for vertex j. The score is added by 1 to avoid division by zero. By using Eq. (3), vertex with higher score will be assigned in lower value of SPar. Those process will make higher score vertex has higher priority.

 The remaining particles are initialized with random positions in which the position is generated between the value of min and max. Figure 2 illustrates the initialization of the first particle.

Figure 2. Illustration of initialization.

3.4 Decoding Method

 The decoding method is divided into 2 steps, which are: construction of vertex’s priority and evaluation and assignment of vertex.

 Construction of vertex’s priority is very simple. The value of dimension in particle’s position is sorted in ascending order, with the smallest position will be the first priority (starting and ending point is excluded). The algorithm of the construction stage is:

 1. Copy the value of particle’s dimension to variable v, and dimension’s index to vp.
     vh = θlh, vph = h; h = 0, …, N-1.

 2. Compare the value of each dimension with another dimension.
     For i = 1 to N – 2, compare vi with vj: j = i + 1, …, N – 2

 3. If vi > vj, swap the value of vi and vj, vpi and vpj.

 4. Repeat step 2 until i = N – 2.

 where N = number of vertices, vph = hth priority of vertex, and θlh = value of hth dimension in particle l; h = 0, …, N – 1. Within the construction algorithm, vp represent the priority of vertices.

 The evaluation of vertex is a step to evaluate each vertex, one by one based on priority, to be assigned into a specific sequence in a path. The possibility of each vertex to be assigned into all paths and in all possible sequences in each path is evaluated. In each path, a sequence that gives the minimum additional service time is selected. This selected sequence then compared among other selected sequences from all possible path. Finally, the vertex is assigned into a path that gives the minimum additional time needed and does not exceed Tmax. The algorithm of this decoding stage is presented below:

 1. For each vertex (i = 1 to N – 2)
 2. For each path (j = 1 to P)
 3. For each sequence (l = 1 to cj + 1)
 4. Insert vertex i to sequence l in path j(stjl = vpi).
 5. Calculate the new total time needed for path j(ttj)
 6. Update the best new total time for path j(tbj), and its sequence (sbjl)
 7. Repeat step 4 until l = cj + 1
 8. If the best new total time for path j(tbj) is not exceed Tmax, calculate the additional time for path j(dj = tbj – tjj). Else, set dj as big number (i.e., as Tmax)
 9. Repeat step 3 until the last path.
 10. Compare the additional time for each path and chose the path that has minimum additional time and the time needed is not exceed Tmax.
 11. Update the sequence (sji) and time (tj) for the chosen path.
 12. Repeat step 2 until all vertex is evaluated.

 where, i is vertex priority index, N is number of vertices, j is path index, P is number of paths, l is sequence index, sji is vertex at ith sequence in path j, tj is time needed of path j, cj is number of vertex assigned in path j (excluded start and end point), stjl is temporary vertex at lth sequence in path j, vpi is ith priority of vertex, ttj is temporary time needed of path j, sbjl is best vertex at lth sequence in path j, tbj is temporary time needed of path j, and dj is additional time needed of path j. Figure 3 illustrates the decoding method.

Figure 3. Illustration of decoding method.

4. COMPUTATIONAL RESULT

 Computational experiments are conducted by applying the proposed algorithm for solving some benchmark dataset of TOP. As mentioned before, the case problems are the benchmark datasets number 4 to 7 of Chao et al. (1996b). The characteristic of the datasets are presented in Table 2.

Table 2. Characteristic of data set 4–7

 Each set has three groups (2, 3, and 4), which indicates number of paths in each case. The alphabet index indicates the Tmax of the case. The smallest index will result in the smallest Tmax. For example, case p7.4.a. has 102 vertices, 4 paths, and the smallest Tmax in the group 7.4, which is equal to 5. In contrast, case p7.4.j has 102 vertices, 4 paths, and Tmax of 50.

The algorithm is implemented in C# language using Sharp Develop 2.2 in a notebook with Intel Centrino Duo T2250 @1.73 GHz 2.5 GB RAM. PSO computational library called ET-Lib (Nguyen et al., 2010) is used here for expediting the implementation phase. For each case, 10 replications are tried. The PSO parameters are set based on the result of some preliminary experiments that carried out to observe the behavior of algorithm in different parameter setting. The PSO parameters are summarized in Table 3. It is noted that these parameters may not be the best parameter value set for TOP, however, our preliminary experiments indicate that these setting are able to provide consistent and better results among other settings in the experiments. 

Table 3. Summary of particle swarm optimization parameters

 Tables 4–6 compare the best obtained solutions for each dataset from the proposed algorithm with the summary of results from Souffriau et al. (2010), and the results of DPSO from Muthuswamy and Lam (2011). The results are then summarized in Table 7. For each approaches, the number of cases in which the best known solution are found and the average gap to the best known solution is given, as well as average CPU times in seconds.

Table 4. Results of data set 4

Table 5. Results of data set 5 and 6

Table 6. Results of data set 7

Table 7. Summary of results

 This proposed algorithm is able to obtain 65 cases in which the best known solution are found, with average gap of 1.83% from best known solution in 366.0 seconds of average CPU times. The quality of this result is still below the result obtained from SPR, ASe, and SVF, for example, SPR is able to find 131 of best known solution is found, with average gap of 0.06% in 212.4 seconds of average CPU times. It is noted that those algorithms a recombining more than one approach into single algorithm. However, the proposed algorithm gives competitive results compared to other basic algorithm, such as TMH, GLS, and DPSO. The TMH algorithm is able to find only 34 of best known solution, with average gap of 1.47% in 336.6 seconds of average CPU times. The GLS is able to find only 21 of best known solution, with average gap of 2.71% in 7.8 seconds of average CPU times. The DPSO is able to find only 39 of best known solution with average gap of 1.45%.

5. CONCLUSION AND FURTHER STUDY

 This paper proposed a new approach to solving TOP by using continuous PSO. The particle’s position is decoded into an order of vertex’s priority, which will be evaluated in each sequence in each path. Finally, the vertex will be assigned in a path that gives the minimum delta path and does not exceed Tmax.

 The result of this proposed algorithm is not as good as the best approach proposed in the past. The best approach, SPR, gave the minimum average gap from best known result, and the most best known solution is found.

 However, this paper concludes that continuous PSO algorithm can solve TOP with competitive result, especially for simple cases of TOP. This continuous PSO also gives better number of best solution found than other approaches that used basic algorithm, such as TMH, GLS, and DPSO.

 Further research can be conducted to improve the performance of this proposed algorithm, such as parameter optimization and decoding alternatives. Although the PSO parameter set used in this paper came from some preliminary experiments, it may not be the best one. A modification in algorithm, like multi-swarm methods, or a combination with other optimization algorithm, like local search, can be conducted to get better result. The improvement should address also the issue of shortening the computational times of the proposed method.

ACKNOWLEDGMENTS

 The authors express thanks to High Performance Computing Group at Asian Institute of Technology, Thailand, for providing the Object Library for Evolutionary Techniques (ET-Lib) version 1.0 used in this research.

Reference

1.Ai, T. J. and Kachitvichyanukul, V. (2009), A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery, Computers & Operations Research, 36(5), 1693-1702.
2.Archetti, C., Hertz, A., and Speranza, M. (2007), Metaheuristic for the team orienteering problem, Journal of Heuristics, 13(1), 49-76.
3.Butt, S. E. and Cavalier, T. M. (1994), A heuristic for the multiple tour maximum collection problem, Computers & Operations Research, 21(1), 101-111.
4.Chang, B. C. H., Ratnaweera, A., Halgamuge, S. K., and Watson, H. C. (2004), Particle swarm optimisation for protein motif discovery, Genetic Programming and Evolvable Machines, 5(2), 203-214.
5.Chao, I., Golden, B. L., and Wasil, E. A. (1996a), The team orienteering problem, European Journal of Operational Research, 88(3), 464-474.
6.Chao, I., Golden, B. L., and Wasil, E. A. (1996b), A fast and effective heuristic for the orienteering problem, European Journal of Operational Research, 88(3), 475-489.
7.Clerc, M. (2004), Discrete particle swarm optimization, illustrated by the traveling salesman problem. In: New Optimization Techniques in Engineering, Springer, Berlin, Germany, 219-239.
8.Hu, X. (2006), Particle swarm optimization, cited 2013 Sep 1, Available from: http://www.swarmintelligence.org.
9.Ke, L., Archetti, C., and Feng, Z. (2008), Ants can solve the team orienteering problem, Computers & Industrial Engineering, 54(3), 648-665.
10.Muthuswamy, S. and Lam, S. S. (2011), Discrete particle swarm optimization for the team orienteering problem, Memetic Computing, 3(4), 287-303.
11.Nguyen, S., Ai, T. J., and Kachitvichyanukul, V. (2010), Object Library for Evolutionary Techniques ET-Lib: User's Guide, High Performance Computing Group, Asian Institute of Technology, Thailand.
12.Souffriau, W., Vansteenwegen, P., Berghe, G. V., and Van Oudheusden, D. (2010), A path relinking approach for the team orienteering problem, Computers & Operations Research, 37(11), 1853-1859.
13.Souffriau, W., Vansteenwegen, P., Vertommen, J., Berghe, G. V., and Van Oudheusden, D. (2008), A personalized tourist trip design algorithm for mobile tourist guides, Applied Artificial Intelligence, 22(10), 964- 985.
14.Tang, H. and Miller-Hooks, E. (2005), A tabu search heuristic for the team orienteering problem, Computers &Operations Research, 32(6), 1379-1407.
15.Tsiligirides, T. (1984), Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35(9), 797-809.
16.Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Van Oudheusden, D. (2009a), A guided local search metaheuristic for the team orienteering problem, European Journal of Operational Research, 196(1), 118- 127.
17.Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Van Oudheusden, D. (2009b), Metaheuristics for tourist trip planning. In: Metaheuristics in the Service Industry, Springer, Berlin, Germany, 15-31.
18.Vansteenwegen, P., Souffriau, W., and Van Oudheusden, D. (2011), The orienteering problem: a survey, European Journal of Operational Research, 209(1), 1- 10.