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

作者：Lin Shih Wei; Yu Vincent F^*

来源：Applied Soft Computing, 2015, 37: 632-642.

DOI：10.1016/j.asoc.2015.08.058

• Routing
• Multiconstraint team orienteering problem
• Multiple time windows
• Simulated annealing
• Cauchy function
• Restart strategy

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.

• 出版日期2015-12
• 单位长春大学