Authors: Rios, Eyder
Ochi, Luiz Satoru
Boeres, Cristina
Coelho, Igor
Coelho, Vitor
Mladenović, Nenad 
Title: A performance study on multi improvement neighborhood search strategy
Journal: Electronic Notes in Discrete Mathematics
Volume: 58
First page: 199
Last page: 206
Issue Date: 1-Apr-2017
ISSN: 1571-0653
DOI: 10.1016/j.endm.2017.03.026
Among the methods to deal with optimization tasks, parallel metaheuristics have been used in many real-world and scientific applications to efficiently solve these kind of problems. This paper presents a novel Multi Improvement strategy for dealing with the Minimum Latency Problem (MLP), an extension the classic Traveling Salesman Problem. This strategy is embedded in a Graphics Processing Unit (GPU) local search procedure, in order to take advantage of the highly parallel processors from this architecture. In order to explore multiple neighborhoods simultaneously in a CPU/GPU heterogenous and distributed environment, a variant of the classic Variable Neighborhood Descent (VND) is also proposed, named Distributed VND (DVND). The DVND was inspired by a randomized version of the VND (called RVND) and a comparison was made, achieving competitive results in terms of solution quality. The variant of the DVND using two processes succeeded in achieving superlinear speedups up to 2.85, demonstrating that the DVND scalability and capability to explore both GPUs and CPUs. Finally, experiments demonstrate that the Multi Improvement is capable of finding better quality solutions in shorter computational times, when compared the classic Best Improvement strategy, motivating future applications in other hard optimization problems.
Keywords: DVND | GPU | minimum latency problem | multi improvement | neighborhood search
Publisher: Elsevier

Show full item record


checked on Feb 3, 2023

Page view(s)

checked on Feb 3, 2023

Google ScholarTM




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