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_RSBF, uses Boltzmann function to determine the acceptance probability of a worse solution while the second version, SA_RSCF, accepts a worse solution based on the acceptance probability determined by Cauchy function. Results of the computational study indicate that both SA_RSBF and SA_RSCF 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. (C) 2015 Elsevier B.V. All rights reserved.