Groupe d’études et de recherche en analyse des décisions


Team orienteering with time-varying profit

, , , et

This paper studies the team orienteering problem, where the arrival time and service time affect the collection of profits. Such interactions result in a non-concave profit function. This problem integrates the aspect of time scheduling into team orienteering and could be used in urban search and rescue or tourist trip planning. We formulate a mixed integer non-concave programming model for it and propose a Benders branch-and-cut algorithm, along with valid inequalities for tightening the upper bound. To solve it more effectively, we introduce a hybrid heuristic that integrates a modified coordinate search (MCS) into an iterated local search. Computational results show that valid inequalities significantly reduce the optimality gap and the proposed exact method is capable of solving instances where the mixed integer nonlinear programming solver SCIP fails in finding an optimal solution. In addition, the proposed MCS algorithm is highly efficient compared to other benchmark approaches whereas the hybrid heuristic is proven to be effective in finding high-quality solutions within short computing times. We also demonstrate the performance of the heuristic with the MCS using the instances with up to 100 customers.

, 34 pages