The ordered median tree of hubs location problem
- Miguel A. Pozo 1
- Justo Puerto 1
- Antonio M. Rodríguez Chía 2
- 1 Universidad de Sevilla, España
- 2 Universidad de Cádiz, España
ISSN: 1863-8279, 1134-5764
Année de publication: 2021
Volumen: 29
Número: 1
Pages: 78-105
Type: Article
D'autres publications dans: Top
Résumé
In this paper, we propose the Ordered Median Tree of Hub Location Problem (OMTHL). The OMTHL is a single-allocation hub location problem where p hubs must be placed on a network and connected by a non-directed tree. Each non-hub node is assigned to a single hub and all the flow between origin–destination pairs must cross at least one hub. The objective is to minimize the sum of the ordered weighted averaged collection and distribution costs plus the sum of the interhub flow costs. We present different MILP formulations for the OMTHL based on the properties of the Minimum Spanning Tree Problem, the ordered median optimization and on the different ways of modeling flow within the network. Given that ordered median hub location problems are rather difficult to solve, we have improved the OMTHL solution performance by introducing covering variables in two valid reformulations. In addition, we have developed two pre-processing phases to reduce the size of these formulations. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium-size instances on general random graphs.
Information sur le financement
The authors have been partially supported by projects MTM2016-74983-C02-01,02 (MINECO/FEDER), CEI-3-FQM331, US-1256951, “NetmeetData” (Fundación BBVA, 2019), P18-FR-1422 (Proyecto Frontera del conocimiento JJAA) and FEDER-UCA18-106895 (Junta de Andalucía/FEDER/UCA).Financeurs
-
Fundación BBVA
Spain
- P18-FR-1422
-
Ministerio de Economía y Competitividad
Spain
- US-1256951
- Junta de Andalucía Spain