Models and solution methods for the uncapacitated r‐allocation p‐hub equitable center problem

• Date: 01 July 2018
• Author: Juanjo Peiró,Rafael Martí,Manuel Laguna,Ángel Corberán
• DOI: http://doi.org/10.1111/itor.12441
• Published date: 01 July 2018

Intl. Trans. in Op. Res. 25 (2018) 1241–1267

DOI: 10.1111/itor.12441

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Models and solution methods for the uncapacitated

r-allocation p-hub equitable center problem

Juanjo Peir´

oa,´

Angel Corber´

ana, Manuel Lagunaband Rafael Mart´

ıa

aDepartament d’Estad´

ıstica i Investigaci´

o Operativa, Facultat de Ci`

encies Matem`

atiques, Universitat de Val`

encia, Carrer

del Doctor Moliner, 50. 46100 – Burjassot,Valencia, Spain

bLeeds School of Business, University of Colorado Boulder, Boulder, CO 80309, USA

E-mail: juanjo.peiro@uv.es[Peir´

o]; Angel.Corberan@uv.es[Corber ´

an]; laguna@Colorado.EDU [Laguna];

rafael.marti@uv.es [Mart´

ı]

Received 12 July2016; accepted 13 June 2017

Abstract

Hub networks are commonly used in telecommunications and logistics to connect origins to destinations in

situations where a direct connection between each origin–destination (o-d) pair is impractical or too costly.

Hubs serve as switching points to consolidate and route traffic in order to realize economies of scale. The

main decisions associated with hub-network problems include (1) determining the number of hubs (p), (2)

selecting the p-nodes in the network that will serve as hubs, (3) allocating non-hub nodes (terminals) to up

to r-hubs, and (4) routing the pairwise o-d traffic. Typically, hub location problems include all four decisions

while hub allocation problems assume that the value of pis given. In the hub median problem, the objective

is to minimize total cost, while in the hub center problem the objective is to minimize the maximum cost

between origin–destination pairs.We study the uncapacitated (i.e.,links with unlimited capacity) r-allocation

p-hub equitable center problem (with 1 <r<p) and explore alternative models and solution procedures.

Keywords:facility location; r-allocation p-hub; quality of service; heuristic optimization

1. Introduction

Hub-and-spoke architectures (aka hub networks) are frequently used in transportation, telecom-

munications, and computer networks to route traffic between origins and destinations. In hub

networks, the number of routes used to connect a network with n-nodes is linear with respect to n,

resulting in a more efficient use of transportation or communication resources when compared to a

point-to-point network for whichthe number of routes is quadratic with respect to n. Hub networks

use transshipment, consolidation, and sorting facilities, generically known as hubs, to connect a

large number of origin-destination (o-d) pairs and achieve cost efficiencies due to: (1) a reduced

number of transportation/communication links, (2) centralized handling and sorting operations,

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1242 J. Pe ir ´

o et al. / Intl. Trans. in Op. Res. 25 (2018) 1241–1267

and (3) economies of scale through flow consolidation. Good surveys on this topic are the articles

by Alumur and Kara (2008), Campbell and O’Kelly (2012), and Farahani et al. (2013).

There are four main decisions associated with the design of a hub network: (1) termining tvalue

of p, the number of hubs, (2) selecting the pnodes that will be designated as hubs, (3) assigning

the non-hub nodes (terminals) to rhubs, (4) routing the traffic through the network to satisfy

the o-d pairwise demands. In transportation and telecommunication applications, the traffic may

consist of packages, passengers, consumer goods, or electronic data. In hub networks, some direct

communication may exist, for instance, when a hub happens to be the destination for a particular

demand. In general, however, it is not expected thatan o-d demand will reach its destination directly,

i.e., without going through at least one hub. Empirical evidence showsthat it is neither practical nor

economically viable to connect all origins and destinations of a network directly, e.g., airlines do

not use direct flights to move all of their passengers or internet providers do not physically connect

every pair of computers for data transmission. Instead, depending on the industry, hub networks

provide services such as:

rConnecting passengers from multiple origins to multiple destinations through hub airports like

Atlanta and Frankfurt.

rSending express packages via consolidating and sorting facilities (e.g., Memphis for FedEx).

rEnabling data transmission via switches, concentrators, and routers.

The hub network literature is divided into two main areas, location and allocation problems. In

general, location problems include all four aforementioned decisions. Allocation problems typically

assume that the first decision has been made and therefore operate with a fixed value ofp. Location

and allocation problems typically assume that hubs are connected by a complete network and that

terminals are not connected directly. Another key distinction among hub network design problem

relates to the functional form of the objective to be optimized:

rMedian: Minimize the total cost

rCenter: Minimize the maximum cost between origin-destination pairs

rCovering: Minimize the cost of covering the demand

Campbell (1994) presents several mixed-integer programming (MIP) formulations for two special

cases of these problems, one where r=1 (single allocation problem) and the other where r=p

(multiple allocation problem). Campbell recognized the advantage of the multiple allocationmodel

but at the same time realized thatthere is a cost associated with connecting a terminal to all hubs. He,

therefore, proposed mixed-integer programming models with minimum flow thresholds for traffic

between terminals and hubs and a fixed cost for using spoke links. Fixed costs are also charged

to hubs in the covering models. Ignoring the spoke-link fixed costs, the p-hub median model with

flow thresholds can be transformed to the single allocation p-hub median problem setting the flow

threshold between a terminal and a hub equal to the terminal demand. Likewise, the model can

be transformed to the multiple allocation problem by setting the flow thresholds to zero. Instead

of adding fixed costs or flow thresholds, Yaman (2011) introduced models for which 1 <r<p.

In particular, she defined the uncapacitated r-allocation p-hub median problem (UrApHMP) as

follows: “Given a set of nodes with pairwise demands, choose phubs and allocate each node to at

most rhubs to minimize the total routing cost.”

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies