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

N1 - Funding Information:
Armin Lüer-Villagra acknowledges the support from FONDECYT through grant 11160345 . Vladimir Marianov acknowledges the support by the Complex Engineering Systems Institute through grant CONICYT PIA FB0816 .

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

AN - SCOPUS:85059322517

SN - 0360-8352

VL - 128

SP - 477

EP - 491

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

ER -