File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.cie.2017.08.036
- Scopus: eid_2-s2.0-85029354851
- WOS: WOS:000418207900004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: An iterated metaheuristic for the directed network design problem with relays
Title | An iterated metaheuristic for the directed network design problem with relays |
---|---|
Authors | |
Keywords | Cycle-based neighborhood Iterated metaheuristic Network design Relay Tabu search |
Issue Date | 2017 |
Citation | Computers and Industrial Engineering, 2017, v. 113, p. 35-45 How to Cite? |
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. |
Persistent Identifier | http://hdl.handle.net/10722/328742 |
ISSN | 2023 Impact Factor: 6.7 2023 SCImago Journal Rankings: 1.701 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Li, Xiangyong | - |
dc.contributor.author | Lin, Shaochong | - |
dc.contributor.author | Chen, Si | - |
dc.contributor.author | Aneja, Y. P. | - |
dc.contributor.author | Tian, Peng | - |
dc.contributor.author | Cui, Youzhi | - |
dc.date.accessioned | 2023-07-22T06:23:33Z | - |
dc.date.available | 2023-07-22T06:23:33Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Computers and Industrial Engineering, 2017, v. 113, p. 35-45 | - |
dc.identifier.issn | 0360-8352 | - |
dc.identifier.uri | http://hdl.handle.net/10722/328742 | - |
dc.description.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. | - |
dc.language | eng | - |
dc.relation.ispartof | Computers and Industrial Engineering | - |
dc.subject | Cycle-based neighborhood | - |
dc.subject | Iterated metaheuristic | - |
dc.subject | Network design | - |
dc.subject | Relay | - |
dc.subject | Tabu search | - |
dc.title | An iterated metaheuristic for the directed network design problem with relays | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1016/j.cie.2017.08.036 | - |
dc.identifier.scopus | eid_2-s2.0-85029354851 | - |
dc.identifier.volume | 113 | - |
dc.identifier.spage | 35 | - |
dc.identifier.epage | 45 | - |
dc.identifier.isi | WOS:000418207900004 | - |