Parallel deterministic local search heuristic for minimum latency problem
- PDF / 1,041,484 Bytes
- 27 Pages / 595.276 x 790.866 pts Page_size
- 88 Downloads / 199 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Parallel deterministic local search heuristic for minimum latency problem Pramod Yelmewad1
•
Basavaraj Talawar1
Received: 1 April 2020 / Revised: 10 July 2020 / Accepted: 17 August 2020 Ó Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Deterministic local search heuristic Graphics processing unit (GPU) Minimum latency problem Speedup TRP TSPLIB
1 Introduction The minimum latency problem (MLP) is an NP-Hard [1–3] combinatorial optimization problem. The objective of MLP is to find a Hamiltonian path that minimizes the overall waiting time of nodes. Consider a simple, directed, weighted graph with n vertices, where n 1 vertices act as service requesting nodes and one vertex act as service providing node. Each service requesting node vi ð1 i\nÞ has to wait until it is served. This waiting period is also known as latency. The latency is a sum of distance or time required to reach from the service providing node v0 to the service requesting node vi : The latency of each node vi is calculated using Eq. 1. Objective of MLP is to determine a
& Pramod Yelmewad [email protected] Basavaraj Talawar [email protected] 1
System Parallelization & Architecture Research @ NITK (SPARK Lab), Department of Computer Science and Engineering, National Institute of Technology Karnataka, Surathkal, Mangalore, India
Hamiltonian path l(p) that has minimum latency (Eq. 2). Note that vertex v0 is considered a service-providing node, also called a depot node. lðvi Þ ¼
i X
Dðvj1 ; vj Þ;
where
1 i\n;
ð1Þ
j¼1
lðpÞ ¼
n X
lðvi Þ:
ð2Þ
i¼1
MLP is also known with other names, namely cumulative traveling salesman problem [4], delivery man problem [5], school bus driver problem [6], and traveling repairman problem [7]. MLP has several applications in real life, such as data retrieval in the computer network, delivery services, disk head scheduling, and logistics services for emergency reliefs, etc. [8, 9]. MLP and traveling salesman problem (TSP), though related, di
Data Loading...
