A performance study on multi improvement neighborhood search strategy

Abstract

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.