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 an 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 experiments are conducted to investigate the usefulness of the key components of the algorithm.
» Read on@article{RHWFesa22,
author = {Jintong Ren and Jin-Kao Hao and Feng Wu and Zhang-Hua Fu},
doi = {10.1016/j.eswa.2022.117072},
journal = {Expert Systems with Applications (ESWA)},
pages = {117072},
title = {Intensification-driven local search for the traveling repairman problem with profits},
volume = {202},
year = {2022}
}