A meta-heuristic algorithm combining between Tabu and Variable Neighborhood Search for the Minimum Latency Problem

Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we propose a meta-heuristic algorithm which combines Tabu search (TS) and Variable Neigh-borhood Search (VNS) for the MLP. In the proposed algorithm, the TS is used to prevent the search from getting trapped into cycles, and guide the VNS to escape local optima. In a cooperative way, the VNS is employed to generate diverse neighborhoods for the TS. We introduce a novel neighborhoods´ structure for the VNS, and indicate a sequential order to explore these neighborhoods such that the VNS can give best solutions. In order to reduce the time complexity of neighborhood search, we also propose a constant time algorithm for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with best meta-heuristic algorithms proposed in the literature show that the proposed algorithm is highly competitive, providing new best solutions for some instances.