New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem

Sergio Garcia, Mercedes Landete*, Alfredo Marin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

This article deals with the uncapacitated multiple allocation p-hub median problem, where p facilities (hubs) must be located among n available sites in order to minimize the transportation cost of sending a product between all pairs of sites. Each path between an origin and a destination can traverse any pair of hubs.

For the first time in the literature, an integer programming formulation with O(n(2)) variables has been devised to approach this problem. Based on this formulation, a branch-and-cut algorithm has been developed which allows to solve larger instances than those previously solved in the literature. The proposed algorithm performs specially well for relatively large values of p. (C) 2012 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)48-57
Number of pages10
JournalEuropean Journal of Operational Research
Volume220
Issue number1
DOIs
Publication statusPublished - 1 Jul 2012

Keywords

  • FACETS
  • LOCATION-PROBLEMS
  • Hub location
  • Discrete location
  • Integer programming

Fingerprint

Dive into the research topics of 'New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem'. Together they form a unique fingerprint.

Cite this