An adaptive large neighbourhood search algorithm for diameter bounded network design problems

Simple item page
dc.contributor.authorGarraffa, Michele
dc.contributor.authorMehta, Deepak
dc.contributor.authorO'Sullivan, Barry
dc.contributor.authorOzturk, Cemalettin
dc.contributor.authorQuesada, Luis
dc.contributor.funderSeventh Framework Programmeen
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2021-07-07T10:48:03Z
dc.date.available2021-07-07T10:48:03Z
dc.date.issued2021-06-23
dc.date.updated2021-07-07T10:36:00Z
dc.description.abstractThis 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.sponsorshipScience Foundation Ireland (Grant numbers 12/RC/2289 (Insight P2); 16/SP/3804 (ENABLE); 16/RC/3918 (CONFIRM))en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGarraffa, 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-1en
dc.identifier.doi10.1007/s10732-021-09481-1en
dc.identifier.eissn1572-9397
dc.identifier.issn1381-1231
dc.identifier.journaltitleJournal of Heuristicsen
dc.identifier.urihttps://hdl.handle.net/10468/11543
dc.language.isoenen
dc.publisherSpringer Nature Switzerland AGen
dc.relation.projectinfo:eu-repo/grantAgreement/EC/FP7::SP1::ICT/318137/EU/The DIStributed Core for unlimited bandwidth supply for all Users and Services/DISCUSen
dc.relation.projectinfo: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-1en
dc.subjectConstraint programmingen
dc.subjectDiameter bounded network designen
dc.subjectLarge neighbourhood searchen
dc.subjectMixed integer linear programmingen
dc.subjectOptical networksen
dc.titleAn adaptive large neighbourhood search algorithm for diameter bounded network design problemsen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Diameter_Bounded_Networks__Final_Version_ (4).pdf
Size:
2.44 MB
Format:
Adobe Portable Document Format
Description:
Accepted Version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles