Authors: | Pei, Jun Mladenović, Nenad Urošević, Dragan Brimberg, Jack Liu, Xinbao |
Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | Solving the traveling repairman problem with profits: A Novel variable neighborhood search approach | Journal: | Information Sciences | Volume: | 507 | First page: | 108 | Last page: | 123 | Issue Date: | 1-Jan-2020 | Rank: | M21a | ISSN: | 0020-0255 | DOI: | 10.1016/j.ins.2019.08.017 | Abstract: | The Traveling Repairman Problem with profits generalizes the Traveling Repairman Problem, by taking into account the variability of the repairman's profit over different time steps in order to maximize the total profit. In this paper, we first analyze the complexities of several neighborhood structures and the efficient updating of objective values of solutions from those neighborhoods. Then we present a new heuristic based on General variable neighborhood search, that uses a local search that combines those neighborhoods in an effective way. Detailed experiments on benchmark instances show that our new method outperforms all previous heuristics. Out of 60 instances tested, it was able to replicate the best known solutions in 20 of them and find new best solutions in the remaining 40. |
Keywords: | Combinatorial optimization | Heuristics | Traveling repairman problem with profits | Variable neighborhood search | Publisher: | Elsevier | Project: | National Natural Science Foundation of China (nos. 71871080, 71601065, 71690235, 71521001) Development of information technologies and systems for stimulation of personality’s sustainable development as one of the bases of development of digital Kazakhstan, Grant BR05236839 Mathematical Modelas and Optimization Methods on Large-Scale Systems Development of new information and communication technologies, based on advanced mathematical methods, with applications in medicine, telecommunications, power systems, protection of national heritage and education |
Show full item record
SCOPUSTM
Citations
41
checked on Sep 7, 2024
Page view(s)
3
checked on Sep 7, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.