Tree decomposition introduced by Robertson and Seymour aims to decompose a problem into clusters constituting an acyclic graph. In a previous paper, we have introduced DGVNS (Decomposition Guided VNS) which uses the graph of clusters to manage the exploration of large neighborhoods. In this paper, we go one step further by proposing three new strategies that exploit the graph of clusters enabling a better intensification and diversification in DGVNS. Experiments performed on random instances (GRAPH) and real life instances (RLFAP, SPOT5 and tagSNP) show the appropriateness and the efficiency of our proposals.
展开▼
