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
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


checked on May 16, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.