Solving the Capacitated Dispersion Problem with variable neighborhood search approaches: From basic to skewed VNS

Abstract

The topic of this paper is the Capacitated Dispersion Problem (CDP). To solve the problem, variable neighborhood search (VNS) based heuristics are proposed. The proposed heuristics are Basic VNS, General VNS and General Skewed VNS. Their performances are assessed on the benchmark instances from the literature and compared against the state-of-the-art ones. Comparing to the state-of-the-art results, it turns out that Basic VNS is able to provide competitive results, while General VNS and General Skewed VNS advance the state-of-the-art results by establishing 57 new best-known solutions on the data set of 100 instances. Twenty nine new best-known solutions are solely due to the proposed General Skewed VNS.