An adaptive large neighbourhood search algorithm for diameter bounded network design problems
dc.contributor.author | Garraffa, Michele | |
dc.contributor.author | Mehta, Deepak | |
dc.contributor.author | O'Sullivan, Barry | |
dc.contributor.author | Ozturk, Cemalettin | |
dc.contributor.author | Quesada, Luis | |
dc.contributor.funder | Seventh Framework Programme | en |
dc.contributor.funder | Science Foundation Ireland | en |
dc.date.accessioned | 2021-07-07T10:48:03Z | |
dc.date.available | 2021-07-07T10:48:03Z | |
dc.date.issued | 2021-06-23 | |
dc.date.updated | 2021-07-07T10:36:00Z | |
dc.description.abstract | This paper focuses on designing a diameter - constrained network where the maximum distance between any pair of nodes is bounded. The objective considered is to minimise a weighted sum of the total length of the links followed by the total length of the paths between the pairs of nodes. First, the problem is formulated in terms of Mixed Integer Linear Programming and Constraint Programming to provide two alternative exact approaches. Then, an adaptive large neighbourhood search (LNS) to overcome memory and runtime limitations of the exact methods in large size instances is proposed. Such approach is based on computing an initial solution and repeatedly improve it by solving relatively small subproblems. We investigate various alternatives for finding an initial solution and propose two different heuristics for selecting subproblems. We have introduced a tighter lower bound, which demonstrates the quality of the solution obtained by the proposed approach. The performance of the proposed approach is assessed using three real-world network topologies from Ireland, UK and Italy, which are taken from national telecommunication operators and are used to design a transparent optical core network. Our results demonstrate that the LNS approach is scalable to large networks and it can compute very high quality solutions that are close to being optimal. | en |
dc.description.sponsorship | Science Foundation Ireland (Grant numbers 12/RC/2289 (Insight P2); 16/SP/3804 (ENABLE); 16/RC/3918 (CONFIRM)) | en |
dc.description.status | Peer reviewed | en |
dc.description.version | Accepted Version | en |
dc.format.mimetype | application/pdf | en |
dc.identifier.citation | Garraffa, M., Mehta, D., O'Sullivan, B., Ozturk, C. and Quesada, L. (2021) 'An adaptive large neighbourhood search algorithm for diameter bounded network design problems', Journal of Heuristics. doi: 10.1007/s10732-021-09481-1 | en |
dc.identifier.doi | 10.1007/s10732-021-09481-1 | en |
dc.identifier.eissn | 1572-9397 | |
dc.identifier.issn | 1381-1231 | |
dc.identifier.journaltitle | Journal of Heuristics | en |
dc.identifier.uri | https://hdl.handle.net/10468/11543 | |
dc.language.iso | en | en |
dc.publisher | Springer Nature Switzerland AG | en |
dc.relation.project | info:eu-repo/grantAgreement/EC/FP7::SP1::ICT/318137/EU/The DIStributed Core for unlimited bandwidth supply for all Users and Services/DISCUS | en |
dc.relation.project | info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ | en |
dc.rights | © 2021, the Authors, under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature. This is a post-peer-review, pre-copyedit version of an article published in Journal of Heuristics. The final authenticated version is available online at: https://doi.org/10.1007/s10732-021-09481-1 | en |
dc.subject | Constraint programming | en |
dc.subject | Diameter bounded network design | en |
dc.subject | Large neighbourhood search | en |
dc.subject | Mixed integer linear programming | en |
dc.subject | Optical networks | en |
dc.title | An adaptive large neighbourhood search algorithm for diameter bounded network design problems | en |
dc.type | Article (peer-reviewed) | en |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Diameter_Bounded_Networks__Final_Version_ (4).pdf
- Size:
- 2.44 MB
- Format:
- Adobe Portable Document Format
- Description:
- Accepted Version
License bundle
1 - 1 of 1
Loading...
- Name:
- license.txt
- Size:
- 2.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: