An iterated metaheuristic for the directed network design problem with relays
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 35-45 |
Journal / Publication | Computers & Industrial Engineering |
Volume | 113 |
Online published | 9 Sept 2017 |
Publication status | Published - Nov 2017 |
Externally published | Yes |
Link(s)
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.
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.
Research Area(s)
- Network design, Relay, Cycle-based neighborhood, Tabu search, Iterated metaheuristic
Citation Format(s)
An iterated metaheuristic for the directed network design problem with relays. / LI, Xiangyong; Lin, Shaochong; Chen, Si et al.
In: Computers & Industrial Engineering, Vol. 113, 11.2017, p. 35-45.
In: Computers & Industrial Engineering, Vol. 113, 11.2017, p. 35-45.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review