File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/ICSSSM.2014.6874109
- Scopus: eid_2-s2.0-84906709262
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A tabu search based metaheuristic for the network design problem with relays
Title | A tabu search based metaheuristic for the network design problem with relays |
---|---|
Authors | |
Keywords | cycle-based neighborhood multicommodity network design relay tabu search |
Issue Date | 2014 |
Citation | 11th International Conference on Service Systems and Service Management, ICSSSM 2014 - Proceeding, 2014, article no. 6874109 How to Cite? |
Abstract | 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. © 2014 IEEE. |
Persistent Identifier | http://hdl.handle.net/10722/328719 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lin, Shaochong | - |
dc.contributor.author | Li, Xiangyong | - |
dc.contributor.author | Wei, Kai | - |
dc.contributor.author | Yue, Chongfang | - |
dc.date.accessioned | 2023-07-22T06:23:23Z | - |
dc.date.available | 2023-07-22T06:23:23Z | - |
dc.date.issued | 2014 | - |
dc.identifier.citation | 11th International Conference on Service Systems and Service Management, ICSSSM 2014 - Proceeding, 2014, article no. 6874109 | - |
dc.identifier.uri | http://hdl.handle.net/10722/328719 | - |
dc.description.abstract | 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. © 2014 IEEE. | - |
dc.language | eng | - |
dc.relation.ispartof | 11th International Conference on Service Systems and Service Management, ICSSSM 2014 - Proceeding | - |
dc.subject | cycle-based neighborhood | - |
dc.subject | multicommodity | - |
dc.subject | network design | - |
dc.subject | relay | - |
dc.subject | tabu search | - |
dc.title | A tabu search based metaheuristic for the network design problem with relays | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/ICSSSM.2014.6874109 | - |
dc.identifier.scopus | eid_2-s2.0-84906709262 | - |
dc.identifier.spage | article no. 6874109 | - |
dc.identifier.epage | article no. 6874109 | - |