Please use this identifier to cite or link to this item:
Title: Parallel deterministic local search heuristic for minimum latency problem
Authors: Yelmewad P.
Talawar B.
Issue Date: 2020
Citation: Cluster Computing Vol. , , p. -
Abstract: Minimum latency problem (MLP) is an NP-Hard combinatorial optimization problem. Metaheuristics use perturbation and randomization to arrive at a satisfactory solution under time constraints. The current work uses deterministic local search heuristic (DLSH) to identify a satisfactory solution without setting up metaheuristic parameters. A move evaluation procedure is proposed for the swap approach which computes a move in O(1) order. Additionally, GPU-based parallel deterministic local search heuristic (PDLSH) is also proposed. PDLSH parallelizes the solution improvement phase and solves MLP for larger instances than the state-of-the-art. The DLSH and PDLSH implementations are tested on the TRP and TSPLIB standard instances. DLSH reaches new best solutions for five TSPLIB instances, namely eil51, berlin52, pr107, rat195, and pr226. The proposed PDLSH achieves a speedup of up to 179.75 for the instances of size 10–11,849 nodes compared to its sequential counterpart. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Appears in Collections:1. Journal Articles

Files in This Item:
There are no files associated with this item.

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