Abstract | ||
---|---|---|
This paper introduces a Path Relinking metaheuristic approach for solving the Team Orienteering Problem (TOP), a particular routing problem in which a score is earned for visiting a location. The objective is to maximise the sum of the scores, while not exceeding a time budget T"m"a"x for travelling to the selected locations. In the case of the simple Orienteering Problem (OP), a single route connecting all selected locations should be followed; in TOP m routes are required and the length of each route is restricted to T"m"a"x. A fast and a slow variant of the approach are tested using a large set of test instances from the literature; they are compared to other state-of-the-art approaches. The fast variant achieves an average gap of 0.39% to the best known solutions in 5.0s of calculation time, while the slow variant achieves a 0.04% gap within 272.8s. Moreover, next to achieving most of the best known solutions for many testproblems, the slow variant improved the best known results in five instances. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1016/j.cor.2009.05.002 | Computers & OR |
Keywords | DocType | Volume |
average gap,Team Orienteering Problem,known result,selected location,calculation time,fast variant,metaheuristic approach,known solution,TOP m route,slow variant | Journal | 37 |
Issue | ISSN | Citations |
11 | Computers and Operations Research | 55 |
PageRank | References | Authors |
2.24 | 21 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wouter Souffriau | 1 | 750 | 28.50 |
Pieter Vansteenwegen | 2 | 1026 | 48.63 |
Greet Vanden Berghe | 3 | 1371 | 77.56 |
Dirk Van Oudheusden | 4 | 917 | 41.64 |