A Hybrid Heuristic for the Team Orienteering Problem

In this work, we propose a hybrid heuristic in order to
solve the Team Orienteering Problem (TOP). Given a set of points (or
customers), each with associated score (profit or benefit), and a team
that has a fixed number of members, the problem to solve is to visit a
subset of points in order to maximize the total collected score. Each
member performs a tour starting at the start point, visiting distinct
customers and the tour terminates at the arrival point. In addition,
each point is visited at most once, and the total time in each tour
cannot be greater than a given value. The proposed heuristic combines
beam search and a local optimization strategy. The algorithm was
tested on several sets of instances and encouraging results were
obtained.

• Adel Bouchakhchoukha
• Hakim Akeb

• Team Orienteering Problem
• Vehicle Routing
• Beam Search
• Local Search.

[1] H. Bouly, D. C. Dang, and A. Moukrim, A memetic algorithm for the
team orienteering problem, 4OR, vol. 8, 2010, pp. 49-70
[2] S. Boussier, D. Feillet, and M. Gendreau. An exact algorithm for the team
orienteering problem, 4OR, vol. 5(3), 2007, pp. 211–230.
[3] S. E. Butt and D. Ryan, An optimal solution procedure for the multiple
tour maximum collection problem using column generation, Computers
& Operations Research, vol. 26(4), 1999, pp. 427–441.
[4] S. E. Butt and T. M. Cavalier, A heuristic for the multiple tour maximum
collection problem, Computers & Operations Research, vol. 21(1), 1994,
pp. 101–111.
[5] I. Chao, B. Golden, and E. Wasil, The team orienteering problem,
European Journal of Operational Research, vol. 88(3), 1996, pp. 464–474.
[6] G. A. Croes, A method for solving traveling salesman problems,
Operations Research, vol. 6, 1958, pp. 791–812.
[7] M. Desrochers, J. K. Lenstra, M. W. P. Savelsbergh, and F. Soumis,
Vehicle Routing with Time Windows: Optimization and Approximation,
Elsevier Science Publishers B.V. (North-Holland), 1988, pp. 65–84, in
B.L. Golden and A.A. Assad (Editors), Vehicle Routing: Methods and
Studies.
[8] Q. Hu and A. Lim, An iterative three-component heuristic for the team
orienteering problem with time windows, European Journal of Operational
Research, vol. 232, 2014, pp. 276–286.
[9] B. I. Kim, H. Li, and A. L. Johnson, An augmented large neighborhood
search method for solving the team orienteering problem, Expert Systems
with Applications, vol. 40(8), 2013, pp. 3065-3072.
[10] G. Laporte, The Traveling Salesman Problem: An overview of exact
and approximate algorithms, European Journal of Operational Research,
vol. 59, 1992, pp. 231–247.
[11] S. W. Lin, Solving the team orienteering problem using effective
multi-start simulated annealing, Applied Soft Computing, vol. 13, 2013,
pp. 1064–1073.
[12] P. Vansteenwegen, W. Souffriau, and D. V. Oudheusden, The
orienteering problem: A survey, European Journal of Operational
Research, vol. 209 (1), 2011, pp. 1-10.
[13] T. Vidal, T. G. Crainicc, M. Gendreau, and C. Prins, Heuristics
for multi-attribute vehicle routing problems: A survey and synthesis,
European Journal of Operational Research, vol. 231(1), 2013, pp. 1-21.