About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Computers and Industrial Engineering
Paper
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.