A simulated annealing heuristic for the multiconstraint team orienteering problem with multiple time windows

This study proposes a simulated annealing with restart strategy (SA-RS) heuristic for the multiconstraint team orienteering problem with multiple time windows (MC-TOP-MTW), an extension of the team orienteering problem with time windows (TOPTW). A set of vertices is given in the MC-TOP-MTW. Each vertex is associated with a score, a service time, one or more time windows, and additional knapsack constraints. The goal is to maximize the total collected score using a predetermined number of tours. We develop two versions of SA-RS. The first version, SA-RS_BF, uses Boltzmann function to determine the acceptance probability of a worse solution while the second version, SA-RS_CF, accepts a worse solution based on the acceptance probability determined by Cauchy function. Results of the computational study indicate that both SA-RS_BF and SA-RS_CF can effectively solve MC-TOP-MTW. Moreover, in several cases, they find new best solutions to benchmark instances. The results also show that SA with restart strategy performs better than that without restart strategy.