An iterated metaheuristic for the directed network design problem with relays

Abstract

We study the directed network design problem with relays (DNDR), which arises in telecommunications and distribution systems where relay points are necessary. Given a directed network and a set of commodities, the DNDR consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. 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.