Intensification-driven local search for the traveling repairman problem with profits

• Published in: Expert systems with applications 2022-09, Vol.202, p.117072, Article 117072
• Main Authors: Ren, Jintong, Hao, Jin-Kao, Wu, Feng, Fu, Zhang-Hua
• Format: Article
• Language: English
• Subjects: Amplification; Combinatorial optimization; Computer Science; Heuristics; Intensification-driven local search; K-exchange sampling based neighborhood; Local optimization; Lower bounds; Perturbation; Search algorithms; Time dependence; Traveling repairman problem with profits; Variable neighborhood search
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2022.117072

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 experiments are conducted to investigate the usefulness of the key components of the algorithm. •The traveling repairman problem with profits has many applications.•An intensification-driven local search is presented for solving the problem.•The K-exchange sampling based neighborhood is applied for the first time.•The algorithm is assessed on 140 benchmark instances.•36 improved best-known results (new lower bounds) are reported.