A Meta-Heuristic Algorithm Combining Between Tabu and Variable Neighborhood Search for the Minimum Latency Problem

Abstract

Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we investigate the global structure of the MLP solution space to propose a suitable meta-heuristic algorithm for the problem, which combines Tabu search (TS) and Variable Neighborhood Search (VNS). In the proposed algorithm, TS is used to prevent the search from getting trapped into cycles, and guide VNS to escape local optima. In a cooperative way, VNS is employed to generate diverse neighborhoods for TS. We also introduce a novel neighborhoods’ structure for VNS and present a constant time operation for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances.