A single allocation p-hub median problem with general piecewise-linear costs in arcs

Armin Lüer-Villagra, H. A. Eiselt, Vladimir Marianov

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


Hubs are used in postal, air passenger transportation, and less-than-truckload (LTL) transportation industries to consolidate, sort, and classify the flows from multiple origins to multiple destinations (OD pairs). Hub-and-spoke networks are commonly designed to exploit economies of scale, and multiple cost functions have been proposed. Hub Location Problems have been used extensively to design hub-and-spoke networks. Notwithstanding the previous efforts in developing accurate cost functions in hub location problems, there is no as today a model flexible enough to represent various practical cost curves. To address this gap, we propose a single-allocation p-hub location problem, in which the cost of the flow on any arc of the network is modeled as a general piecewise-linear function. Inspired by the parcel delivery industry, we allow the existence of routes containing more than three arcs, i.e., any single route may use more than two hubs. The resulting model is hard to solve, even for small instances. We propose a math-heuristic (i.e., a heuristic with exact mathematical programming components), which allows us to solve instances with up to 200 nodes. We obtain solutions considering different cost functions, showing the stability and scalability of the model. Our experiments reveal the dependence between the cost function considered and both hub location and node allocation.

Original languageEnglish
Pages (from-to)477-491
Number of pages15
JournalComputers and Industrial Engineering
Publication statusPublished - 1 Feb 2019


  • Cost of congestion
  • Economies of scale
  • Hub location
  • Volume discounts

ASJC Scopus subject areas

  • General Computer Science
  • General Engineering


Dive into the research topics of 'A single allocation p-hub median problem with general piecewise-linear costs in arcs'. Together they form a unique fingerprint.

Cite this