Parallel deterministic local search heuristic for minimum latency problem

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.