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

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

Resultado de la investigación: Article

Resumen

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.

Idioma originalEnglish
Páginas (desde-hasta)477-491
Número de páginas15
PublicaciónComputers and Industrial Engineering
Volumen128
DOI
EstadoPublished - 1 feb 2019

Huella dactilar

Cost functions
Costs
Mathematical programming
Scalability
Industry
Air
Experiments

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Citar esto

@article{badd4f4d59cb4932879fbb137564c374,
title = "A single allocation p-hub median problem with general piecewise-linear costs in arcs",
abstract = "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.",
keywords = "Cost of congestion, Economies of scale, Hub location, Volume discounts",
author = "Armin L{\"u}er-Villagra and Eiselt, {H. A.} and Vladimir Marianov",
year = "2019",
month = "2",
day = "1",
doi = "10.1016/j.cie.2018.12.058",
language = "English",
volume = "128",
pages = "477--491",
journal = "Computers and Industrial Engineering",
issn = "0360-8352",
publisher = "Elsevier Limited",

}

A single allocation p-hub median problem with general piecewise-linear costs in arcs. / Lüer-Villagra, Armin; Eiselt, H. A.; Marianov, Vladimir.

En: Computers and Industrial Engineering, Vol. 128, 01.02.2019, p. 477-491.

Resultado de la investigación: Article

TY - JOUR

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

AU - Lüer-Villagra, Armin

AU - Eiselt, H. A.

AU - Marianov, Vladimir

PY - 2019/2/1

Y1 - 2019/2/1

N2 - 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.

AB - 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.

KW - Cost of congestion

KW - Economies of scale

KW - Hub location

KW - Volume discounts

UR - http://www.scopus.com/inward/record.url?scp=85059322517&partnerID=8YFLogxK

U2 - 10.1016/j.cie.2018.12.058

DO - 10.1016/j.cie.2018.12.058

M3 - Article

VL - 128

SP - 477

EP - 491

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

SN - 0360-8352

ER -