A new Benders decomposition acceleration procedure for large scale multiple allocation hub location problems

H. Mokhtar, M. Krishnamoorthy, A. T. Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

4 Citations (Scopus)

Abstract

We consider the well-known uncapacitated multiple allocation hub location problem (UMAHLP). Hub location problems are widely used to model and solve problems that arise from network telecommunications, transport networks, and delivery systems. Due to the high complexity of hub location problems, different approaches have been employed to develop efficient algorithms. We apply a modified Benders decomposition method for solving large UMAHLP instances exactly. Since the derived subproblems possess an inherent high degeneracy, the implementation of Benders method for UMAHLP usually suffers from slow convergence. We adapt an existing state-of-the-art method in the literature, and apply a novel method of accelerating this approach. This is performed with a view to addressing the slow convergence issues. Our approach improves the current best results by more appropriately choosing parameters for the accelerated Benders method. Furthermore, as observed in the literature, the exact solution of subproblems can add an extra complexity to the Benders approach for UMAHLP. We reformulate the subproblems and solve them more efficiently using a minimum cost network flow algorithm. Our computational results show that our acceleration procedures together with our different approach to solve subproblems are computationally efficient. According to our computational results, we are able to solve larger UMAHLP instances with up to 200 nodes in less than 2 hours. On average, our approach improves computational times of around two third of tested instances by 44% over current approaches. Also it requires around 10% fewer Benders iterations in our computational experiment.

Original languageEnglish
Title of host publicationProceedings - 22nd International Congress on Modelling and Simulation, MODSIM 2017
EditorsGeoff Syme, Darla Hatton MacDonald, Beth Fulton, Julia Piantadosi
PublisherModelling and Simulation Society of Australia and New Zealand Inc. (MSSANZ)
Pages340-346
Number of pages7
ISBN (Electronic)9780987214379
Publication statusPublished - 2017
EventInternational Congress on Modelling and Simulation 2017: Managing cumulative risks through model-based processes - The Hotel Grand Chancellor, Hobart, Australia
Duration: 3 Dec 20178 Dec 2017
Conference number: 22nd
https://www.mssanz.org.au/modsim2017/index.html

Publication series

NameProceedings - 22nd International Congress on Modelling and Simulation, MODSIM 2017

Conference

ConferenceInternational Congress on Modelling and Simulation 2017
Abbreviated titleMODSIM 2017
CountryAustralia
CityHobart
Period3/12/178/12/17
OtherThe 22nd International Congress on Modelling and Simulation (MODSIM2017) will be held at The Hotel Grand Chancellor Hobart, Tasmania, Australia from Sunday 3 to Friday 8 December 2017.

ASOR will be joining us again, for the 25th National Conference of the Australian Society for Operations Research as will the DST Group led Defence Operations Research Symposium (DORS 2017).
Internet address

Keywords

  • Benders decomposition methods
  • Hub location problem
  • Minimum cost network flow problem

Cite this