Variable neighbourhood search-based algorithm to solve the minimum back-walk-free latency problem
by Ha-Bang Ban
International Journal of Computer Applications in Technology (IJCAT), Vol. 65, No. 1, 2021

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.

Online publication date: Mon, 15-Mar-2021

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computer Applications in Technology (IJCAT):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com