A Hybrid Heuristic for the Team Orienteering Problem

Authors: Adel Bouchakhchoukha, Hakim Akeb

Abstract:

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.

Keywords: Team Orienteering Problem, Vehicle Routing, Beam Search, Local Search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1094771

References:

[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.