کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777273 1632573 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A performance study on multi improvement neighborhood search strategy
ترجمه فارسی عنوان
یک مطالعه کارآزمایی چند راهکار بهبود مکان محله
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 58, April 2017, Pages 199-206
نویسندگان
, , , , , ,