查看文章

Abstract The Traveling Repairman Problem with Profits is to select a subset of nodes (customers) in a weighted graph to maximize the collected time-dependent revenues. We introduce an intensification-driven local search algorithm for solving this challenging problem. The key feature of the algorithm is an intensification mechanism that intensively investigates bounded areas around each very-high-quality local optimum encountered. As for its underlying local optimization, the algorithm employs an extended variable neighborhood search procedure which adopts for the first time a K-exchange sampling based neighborhood and a concise perturbation procedure to obtain high-quality solutions. Experimental results on 140 benchmark instances show a high performance of the algorithm by reporting 36 improved best-known results (new lower bounds) and equal best-known results for 95 instances. Additional …