یک متا تئوری تکراری برای مسئله طراحی شبکه طراحی شده با رله

Since the DNDR is an NP-hard problem, we present an iterated metaheuristic based on tabu search, which iteratively solves the DNDR within two steps: generating paths for commodities, and determining optimal relay assignment associated with these paths. A cycle-based neighborhood is designed to generate neighboring solutions by replacing subpaths in commodities’ paths with new ones. Given one subpath, the new substituting subpath is found by solving a shortest path problem between its two endpoints, explicitly taking into account the impact of opening one subpath on the objective value. For each neighboring solution, the associated relay allocation is determined by exactly determined. With a set of benchmark instances and newly generated instances, we compare our approach with other available algorithms. Computational results demonstrate that our proposed algorithm is an efficient method for the DNDR.