Efficient solution approaches for the bi-criteria p-hub median and dispersion problem

Prasanna Ramamoorthy, Navneet Vidyarthi and Manish Verma

European Journal of Operational Research, 2024, vol. 314, issue 1, 79-93

Abstract: In this paper, we study the bi-criteria p-hub median and dispersion problem, that arises in the design of hub networks where the dispersion of hubs is desired to mitigate the risk of disruptions. The problem is formulated as a bi-objective mixed integer program, where the first objective is to minimize the total cost of routing the flows through p hubs and the second objective is to maximize the minimum distance (or dispersion) among the selected p hub locations themselves. We present two exact solution approaches that guaranteed to obtain the entire non-dominated Pareto frontier. The first is a cutting plane method in which a p-hub median problem with a particular dispersion distance is solved at each iteration. Three formulations of the problem, based on the different type of cuts and preprocessing, are presented. We study the dominance relationship among the three formulations. Through computational experiments, we show that the proposed cutting plane method is efficient in solving medium size instances of the problem and our strongest formulation is at least 40% computationally faster than the others. For solving large instances of the problem, we present a decomposition method where the p-hub median problem with dispersion distance is solved using an accelerated Benders decomposition approach. We present several problem specific enhancements to the algorithm such as starting with a better solution, efficient ways of solving decomposed subproblem and adding Pareto optimal Benders cuts to the master problem. The computational results on the Turkish network (TR81), US423, and Australian Post (AP) dataset show that the cutting plane algorithm with the proposed decomposition procedure is three to four times faster than the commercial solver.

Keywords: Location; p-hub median problem; Hub dispersion; Cutting plane method; Benders decomposition (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172300749X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:314:y:2024:i:1:p:79-93

DOI: 10.1016/j.ejor.2023.09.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().