A tabu search based metaheuristic for the network design problem with relays

The network design problem with relays arises in telecommunications and distribution systems where relay points are necessary. Given a network and a set of commodities, the problem consists of introducing a subset of edges and locating relays on a subset of nodes such that in the resulting network, the total cost (edge cost plus relay cost) is minimized, and there exists a route 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. The problem is an NP-hard problem. We present a tabu search based metaheuristic to quickly produce high-quality solutions within acceptable computational times. In the proposed metaheuristic, a cycle-based neighborhood is used. Neighboring operators generate neighboring solutions by replacing the subpath of the path of each commodity by a new path which is found by solving a shortest path problem between two node of the original path linking the origin and destination of each commodity. We evaluate our algorithm on a set of benchmark problems and compare it with other available algorithms. Computational results demonstrate that our algorithm is an efficient method for the network design problem with relays.