Title: Variable neighbourhood search-based algorithm to solve the minimum back-walk-free latency problem

Authors: Ha-Bang Ban

Addresses: School of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, Vietnam

Abstract: The Minimum Back-Walk-Free Latency Problem (MBLP) is an extension of the Minimum Latency Problem (MLP). It aims to find a tour with minimum latency while ignoring the back-walking costs. One of the justifications for ignoring the back-walking costs is in applications of message broadcasting for mobile devices. Obviously, the MBLP is NP-hard problem because it is a particular variant of MLP. Therefore, metaheuristic needs to be developed to provide near-optimal solutions within a short computation time. However, the main issue of metaheuristics is that they fall into local optima in some cases since the search space of the problem is combinatorial explosion. To overcome the drawback, we propose a metaheuristic algorithm combined between the Variable Neighbourhood Search (VNS) and shaking technique to solve the problem. The aim of VNS is to generate diverse neighbourhoods by using various neighbourhood searches while the shaking technique guides the search towards an unexplored part of the solution space. Moreover, a technique called Adaptive Memory (AM) is applied to balance between diversity and intensification. The computational results show that the effectiveness and efficiency of the proposed algorithm are comparable with the state-of-the-art algorithms.

Keywords: MBLP; minimum back-walk-free latency problem; metaheuristic; VNS; variable neighbourhood search; adaptive memory.

DOI: 10.1504/IJCAT.2021.113642

International Journal of Computer Applications in Technology, 2021 Vol.65 No.1, pp.55 - 64

Received: 10 Sep 2019
Accepted: 30 May 2020
Published online: 15 Mar 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article