An adaptive large neighbourhood search algorithm for diameter bounded network design problems
Loading...
Files
Accepted Version
Date
2021-06-23
Authors
Garraffa, Michele
Mehta, Deepak
O'Sullivan, Barry
Ozturk, Cemalettin
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature Switzerland AG
Published Version
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.
Description
Keywords
Constraint programming , Diameter bounded network design , Large neighbourhood search , Mixed integer linear programming , Optical networks
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
Link to publisher’s version
Copyright
© 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