supply chain

Chapter 11 Hub Location Problem

Masoud Hekmatfar and Mirsaman Pishvaee

One of the novel topics in location problems is the hub location problem. There are plenty of applications for the hub location problem; therefore, this section is dedicated to introducing this problem to readers. The preface is composed of three parts: apprehensions, definitions, and classifications of the hub location problem.

In this chapter we discuss services such as, movement of people, commodities and information which occurs between an origin-destination pair of nodes (see A–B in Fig. 11.1 as an origin-destination pair). Each origin-destination pair needs a ser- vice different from other pairs. Thus, the commodities carried from i to j are not interchangeable with the commodities carried from j to i.

If we have N nodes and if each node can be either an origin or a destination, we’ll have N.N �1/ origin-destination pairs of nodes in a network which form a fully connected network (a network in which all nodes are connected together). Notice that i�j pair is different from j�i pair. A sample network with six nodes is presented in Fig. 11.1 (Daskin 1995).

Assuming that we have different traffic services in this network and that each vehicle can service five origin-destination pairs every day, with 18 vehicles, we will be able to service ten nodes every day.

If we set one of the nodes as a hub1 node and connect it to all of the other nodes, which are introduced as spoke, we will have 2.N �1/ connections to service all origin-destination node pairs. This network is presented in Fig. 11.2 (Daskin 1995). In this network, if there are different traffic services and if each vehicle can service five origin-destination pairs every day, with 18 vehicles, we will be able to service 46 nodes every day.

Thus, with fixed traffic resources, we can service more cities with a hub network than with a completely connected network2.

1 Hub means the ball in the center of a wheel and Campbell (1994) defined it as “the facilities that are servicing many origin-destination pairs as transformation and tradeoff nodes, and are used in traffic systems and telecommunications.” 2 This argument ignores vehicles’ capacity. It should be clear that the volume of goods or the number of people transported on each link in the hub-and-spoke network will be considerably greater than the number transported on each link of the fully connected network. This also ignores differences in the distances between nodes as it assumes that the number of origin-destination pair trips a vehicle can service is independent from the distances between the nodes.

R.Z. Farahani and M. Hekmatfar (eds.), Facility Location: Concepts, Models, 243 Algorithms and Case Studies, Contributions to Management Science, DOI 10.1007/978-3-7908-2151-2 11, c� Physica-Verlag Heidelberg 2009

244 M. Hekmatfar and M. Pishvaee

Fig. 11.1 A fully connected network with 6 nodes and 30 origin-destination pairs (Daskin 1995)

B

C

D

E

F

A

Fig. 11.2 A hub and spoke network with 6 nodes and 30 origin-destination pairs (Daskin 1995)

A

B C D E F

The main disadvantage of such system (regarding all nodes except the hub node) is that more than one trip is required to travel between each origin-destination pair since we have to pass the hub node to be able to travel from one non-hub node to another.

In multi hub networks, we assume that the hub nodes are completely connected to one another and that each non-hub node is connected to exactly (at least) one hub node such as Fig. 11.3 (Daskin 1995). In Fig. 11.3, there are 15 cities and three hubs. The number of passengers or commodities carried from one hub to another is greater than the number of passengers or commodities moved from each non-hub node to that hub; for example if the traffic between each origin-destination pair is ten units, there will be 140 traffic units between each non-hub city and the hub it is connected to, but there will be 250 traffic units between two hubs.

It is not reasonable to establish direct paths between every pair of nodes; for example assume that we establish direct paths between each pair of nodes in a con- nective network such as, a route network or a computer network (Camargo et al. 2008). Thus, hub nodes are used to resolve this problem. One of the advantages of using hubs is that we gain economic profits by establishing more qualitative paths between the hubs (Camargo et al. 2008). In road networks, when there are a large number of relationships between two nodes, it is economic to establish a highway with several lines between those two nodes, and obtain faster movement of vehicles, and less waste in fuel, and, thus, savings in time and cost.

In computer networks, fiber-optic cables are only used to connect hubs and it is not economic to use them to join any two nodes.

11 Hub Location Problem 245

Fig. 11.3 Example of a three- hub network (Daskin 1995)

A

D E

G

H

I J

L

M N

O

K

B

C

F

This chapter is organized as follows. In Sect. 11.1, some applications of hub loca- tion problem and its classifications are given, and Sect. 11.2 presents some models developed for the problem. Some relevant algorithms to solve hub models are given in Sect. 11.3. Finally, Sect. 11.4 represents some real world case studies with a short summary.

11.1 Applications and Classifications

Many applications of hub problem are given in the following:

� Airlines and air ports: Some works in this area are Toh et al. (1985), Shaw (1993), Aykin (1995), Jaillet et al. (1996), Bania et al. (1998), Sasaki et al. (1999), Martin and Roman (2003) and Adler and Hashai (2005). In Adler and Hashai (2005), airlines and transportations based on open sky policy are surveyed in the Middle East. It is interesting that based on their research, the four cities se- lected as optimized hub airports are, in order of utility, Cairo, Tehran, Istanbul, and Riyadh. Dubai which now works as an important center for airport trans- portation, is not an optimal hub airport. This means that, politic and economic problems have dominated over optimized location.

� Transportation and handling problems: Some works in this area are Don et al. (1995), Lumsdenk et al. (1999), Aversa et al. (2005), Baird et al. (2006), Cunha and Silva (2007), Yaman et al. (2007) and Eiselt (2007). In Eiselt (2007), find- ing the optimized land dump locations, with respect to garbage transportation stations, is discussed.

� Post delivery services and fast delivery packing companies: Kuby et al. (1993), Krishnamoorthy et al. (1994), Ernst and Krishnamoorthy (1996) and Ebery et al. (2000) represent models in this area.

246 M. Hekmatfar and M. Pishvaee

� Telecommunication systems and massage delivery networks: Some works in this area are Lee et al. (1996) and Klincewicz (1998).

� Emergency services: Hakimi (1964) and Berman et al. (2007) represented models in emergency services. Berman et al. (2007) discussed the location of a hub for rescue helicopters.

� Chain stores in supply chain (like Wall-Mart): A work in this area is Campbell et al. (2002).

� Productive companies in basis transportation correctly: Every assembly plant probably wants to find an optimized solution for its material storage and handling such that each production facility can receive its required materials effectively.

Some practical examples of hub problems are as follows:

� A classical example is Hungarian railway system with Budapest as its hub. � Two huge American airlines based in Atlanta and Chicago, use hub networks. � Dubai airport is a hub for many flights in the Middle East. The hub location problem has a short history. The first paper on hub location prob- lem was published by Toh et al. (1985). This paper was on the application of hub location problem in airlines and airports. Although Hakimi (1964) first published a paper on hub location, since next paper on this topic was not published until two decades later, it is assumed that the hub location problem has been first discussed in 1980s.

O’Kelly (1987) developed hub location models. He had an important role in de- veloping the first modeling of hub problems (O’Kelly 1987, 1992). Later, Campbell (1994) played a major role in completing hub modeling. His papers are among the most important papers on types of hub modeling (Campbell 1994, 1996). Also, some authors played important roles in improving this topic (Aykin 1994, 1995; Klincewicz 1991, 1992).

Many papers have been published on hub location problem so far (since1980s). Daskin (1995) has written a book on “Network and Discrete location” and only a brief section of this book is dedicated to hub location. Figure 11.4 shows that the number of papers has increased in recent years. The number of published papers on hubs shows a significant increase in 1996, which is presumably the time when the modeling of hub problems has reached maturity. The emphasis of papers was on modeling in the early years, on optimizing and completing the models in the follow- ing years, and, finally, on solution methods in recent years. Thus, hub location prob- lem is a rather new topic and a good area for research and development activities.

A classification of different types of hub problems and their properties is repre- sented as follows:

� Area solution: discrete, continual � Objective function: MiniMax, MiniSum � Determination of the number of hubs: exogenous, endogenous � Number of hubs: one hub, more than one hub � Hub capacity: unlimited (uncapacitated), limited

11 Hub Location Problem 247

Focus on primary Modeling

Focus on model optimization

Focus on large scale optimization and solution

algorithms

Papers

0 1 2 3 4 5 6 7 8 9

10 11 12

20 06

20 05

20 04

20 03

20 02

20 01

20 00

19 99

19 98

19 97

19 96

19 95

19 94

19 93

19 92

19 91

19 90

19 89

19 88

19 87

19 86

19 85

Year

N um

be r

Fig. 11.4 Revolution of Hub location problem papers3

� Cost of hub location: no cost, fixed cost, variable cost � Node connections to hub: to one hub, to more than one hub � The cost of connection to a hub: no cost, fixed cost, variable cost Researchers have worked on a variety of hub modeling problems. However, no re- search has been conducted on many types of hub modeling problems resulted from multiplying the above items. On the other hand, some of the new models do not have any applications in the real world and, therefore, are not really worth modeling.

Since most of the applications of hub problems in real world are discrete, the models developed so far are mostly discrete models.

11.2 Models

In this section we introduce hub models represented and developed as mathematical models.

11.2.1 Single Hub Location Problem (O’Kelly 1987)

O’Kelly (1987) was the first to introduce the single hub model which has only one hub node.

3 This information is based on Springer-Verlag and Elsevier (Science Direct) websites.

248 M. Hekmatfar and M. Pishvaee

11.2.1.1 Model Assumptions

Model assumptions of this model are as follows:

� The objective function is MiniSum. � The solution space is discrete and finite. � There is only one hub node. � All of the nodes are connected to the hub node and each non-hub node is con-

nected to every other non-hub node via the hub node. � The number of hub nodes is known (exogenous model). � The installation cost of the hub node is not considered. � The capacity of the hub node is unlimited (uncapacitated model). � All decision variables of the model are binary (0–1) variables.

11.2.1.2 Model Inputs

Model inputs of this model are as follows:

hij : demand or flow between origin i and destination j Cij : unit cost of local (non-hub to hub) movement between nodes i and j

11.2.1.3 Model Outputs (Decision Variables)

Model outputs of this model are as follows:

Xj D a hub is located at node j Yij D node i is connected to a hub located at node j

11.2.1.4 Objective Function and its Constraints

The objective function of this model and its related constraints are as follows:

Min X i

X j

X k

hik � Cij C Cjk

� yijykj: (11.1)

Subject to

X j

Xj D 1; (11.2)

Yij � Xj � 0 8i;j ; (11.3) Xj D 0;1 8j ; (11.4) Yij D 0;1 8i;j : (11.5)

11 Hub Location Problem 249

Equation (11.1) minimizes the total cost associated with the transport through the hub. Equation (11.2) ensures that we locate only one hub. Equation (11.3) ensures that demand node i cannot be connected to a hub at j unless we locate the hub at j . Equations (11.4) and (11.5) are standard integrity constraints.

11.2.1.5 Linearizing the Objective Function

The objective function is quadratic since it involves the product of decision vari- ables. However since there is only one hub, if node i is assigned to a hub at node j , then all nodes k.k ¤ i/ must be assigned to the hub at node j . Thus we can rewrite (11.1) as follows:

X i

X j

X k

hik � Cij C Cjk

� yijykj D

X i

X j

Cijyij

X k

hik

! C

X j

X i

Cjiyij

X k

hki

! D X i

X j

Cijyij .Oi C Di/; (11.6)

where Oi : the total outflow of node iI Di : the total inflow of node i. Having transformed (11.1)–(11.6), we can find the optimal 1-hub location with

minimum objective function value by total enumeration in O.N2/ time.

11.2.2 P-Hub Location Problem (O’Kelly 1987)

This model is referred to as single allocation P-hub location problem, since each non-hub node is assigned to one hub node (O’Kelly 1987).

11.2.2.1 Model Assumptions

Model assumptions are as follows:

� The objective function is MiniSum. � The solution space is discrete and finite. � All of the hub nodes are connected to one another and each non-hub node is

connected to (exactly, at least) a hub. � The number of hub nodes is known (exogenous). � To travel between two non-hub nodes, one or two hubs have to be passed, i.e.

two non hub nodes are never connected directly. � The installation cost of the hub nodes is not considered. � The capacities of the hub nodes are unlimited (uncapacitated model). � All decision variables of the model are binary variables (0–1).

250 M. Hekmatfar and M. Pishvaee

11.2.2.2 Model Inputs

We have all the inputs in previous model in addition to the following inputs:

˛ D discount factor for line-haul movement between hubs .0 � ˛ < 1/. As transportation cost between two hubs is less than transportation cost between

a hub node and a non-hub node, we multiply ˛ by Cij in calculating the movement cost between two hubs.

P D the number of hubs to locate.

11.2.2.3 Model Outputs (Decision Variables)

The outputs of this model are similar to the previous model.

11.2.2.4 Objective Function and its Constraints

The objective function of this model and its related constraints are as follows:

Min X i

X k

CikYik

0 @X

j

hij

1 A C X

k

X i

CkiYik

X J

hji

!

C˛ X i

X j

X k

X m

hijCkmyikyjm: (11.7)

Subject to

X j

yij D 1 8i; (11.8) X j

xj D P; (11.9)

yij � xj � 0 8i;j; (11.10) xj D 0;1 8j; (11.11) yij D 0;1 8i;j: (11.12)

Equation (11.7) minimizes the total cost associated with the P hubs locations and the assignment of nodes to the hubs. The first term is the cost of connecting all trips originating at node i to the hub k to which node i is attached. The second term is the cost of connecting all trips destined for node i to hub k, to which node i is

11 Hub Location Problem 251

attached (sum on all i, k). The third term is a hub-to-hub connection cost (sum of two hubs). Equation (11.8) ensures that each node i is assigned to exactly one hub. Equation (11.9) ensures that the number of hub nodes is P . Equation (11.10) states that demand node i cannot be connected to a hub at j unless we locate the hub at j . Equations (11.11) and (11.12) are standard integrity constraints.

11.2.3 Multiple Allocation P-Hub Location Model (P-Hub Median Location Model) (Campbell 1991)

The objective function of the previous model was nonlinear; so Campbell (1991) represented the following model with a linear objective function. He formulated this model like P-median problem and called it P-hub median location model. We dis- cuss P-hub median problems in which each non-hub node can be connected to more than one hub, and therefore, are called multiple allocation P-hub location problem. Notice that this property is not fixed, so we also discuss models with one allocation between each hub node and non-hub node (discussed in Sect. 11.2.5).

11.2.3.1 Model Assumptions

Model assumptions are similar to the ones of P-hub problem model except that the Zkmij variables is relaxed .Z

km ij � 0/ and each non-hub node can be connected to

more than one hub node.

11.2.3.2 Model Inputs

Model inputs are similar to P-hub problem model except that the Cij variables are defined as follows:

Ckmij D unit cost of travel between origin i and destination j when going via hubs at nodes k and m

C km ij D Cik C ˛Ckm C Cmj

: (11.13)

11.2.3.3 Model Outputs (Decision Variables)

The model outputs of this model are as follows:

Xj D a hub is located at node j Zkmij D flow from origin i to destination j uses hubs at candidates sites k and m.

252 M. Hekmatfar and M. Pishvaee

11.2.3.4 Objective Function and its Constraints

The objective function of this model and its related constraints are as follows:

Min X i

X j

X k

X m

Ckmij hijZ km ij : (11.14)

Subject to X k

xk D P; (11.15) X k

X m

Zkmij D 1 8i;j; (11.16)

Zkmij � xm 8i;j;k;m; (11.17) Zkmij � xk 8i;j;k;m; (11.18) Zkmij � 0 8i;j;k;m; (11.19) xk D 0;1 8k: (11.20)

Equation (11.14) minimizes the demand-weighted total travel cost. Equation (11.15) stipulates that exactly P hubs should be located. Equations (11.16) ensure that each origin-destination pair (i, j) must be assigned to exactly one hub pair. Equa- tions (11.17) and (11.18) stipulate that flow from origin i to destination j cannot be assigned to a hub at location k or m unless a hub is located at these candidate nodes (when we travel from one node to another node via one hub node, m and k are coincided with each other). Equations (11.19) are standard integrality constraints. Equations (11.20) are relaxed decision variable constraints.

One of the key difficulties associated with this hub location model should also be evident from this formulation. The number of assignment variables .Zkmij / can be extremely large. In fact, if every origin or destination node is a candidate hub, there will be O.N4/ of such variables. For a relatively small problem with 32 origins and destinations, we would have over one million such decision variables. In short, the size of these problems grows very quickly with the number of nodes in the problem unless some a priori means of eliminating candidate hub locations is used. The use of quadratic formulation (11.7) reduces the number of decision variables dramatically but does not make solving the problem any easier.

11.2.4 P-Hub Median Location Problem with Fixed Costs (O’ Kelly 1992)

P-hub median location model with respect to fixed cost of hub locations is repre- sented by O’ Kelly (1992).

11 Hub Location Problem 253

11.2.4.1 Model Assumptions

The model assumptions are similar to the ones of P-hub problem model except that there are two differences:

� The number of hub nodes is not known beforehand (endogenous). � A fixed cost of hub location is incorporated into the model.

11.2.4.2 Model Inputs

Model inputs are similar to the inputs of P-hub problem model in addition to two new variables:

B D a weight on the capital or fixed costs to allow exploration of the tradeoff between capital costs and transport (or operating) costs fk D the fixed cost of hub location in candidate node k

11.2.4.3 Model Outputs (Decision Variables)

The outputs are similar to P-hub problem model.

11.2.4.4 Objective Function and its Constraints

The differences between the objective function of this model and P-hub problem model are as follows:

� Equations (11.9) are eliminated � The following term is added to the objective function:

B X k

fxxk: (11.21)

11.2.5 Single Spoke Assignment P-Hub Median Location Problem (Single Allocation P-Hub Location Problem) (Daskin 1995)

Equation (11.14)–(11.20), P-hub median location model, allow each of the spoke nodes to be assigned to multiple hubs. Thus, for example, the assignment shown in Fig. 11.5 (Daskin 1995) is entirely possible as a result of solving this model. In this figure two origin-destination flows are shown: origin i to destination j1 and origin i to destination j2. Origin i is assigned to two different hubs: k1; k2.

254 M. Hekmatfar and M. Pishvaee

Fig. 11.5 Schematic repre- sentation of multiple spoke assignment (Daskin 1995)

m m

Hubs

j1 j2

k2k1

i

Fig. 11.6 Schematic rep- resentation of single spoke assignment (Daskin 1995)

m m m m

k1 k1k2

i i

k2

j1 j1j2 j2

In many cases, it is desirable (for operational reasons) to have each of the spoke nodes assigned to a single hub. This might result in one of the assignments shown in Fig. 11.6 (Daskin 1995).

The single spoke assignment P-hub median location model is formulated as Daskin (1995)’s model.

11.2.5.1 Model Assumptions

The assumptions of this model are similar to median P-hub model except that there are the two following differences:

� Each non-hub node is assigned to only one hub. � All of the variables are binary variables (0–1).

11.2.5.2 Model Inputs

Model inputs are similar to median P-hub model.

11 Hub Location Problem 255

11.2.5.3 Model Outputs (Decision Variables)

Model outputs are similar to median P-hub model in addition to the following deci- sion variables: Yik D non-hub node i is assigned to a hub node k

11.2.5.4 Objective Function and its Constraints

The objective function of this model and its related constraints are as follows:

Min X i

X j

X k

X m

Ckmij hijZ km ij : (11.22)

Subject to X k

Xk D P; (11.23) X k

X m

Zkmij D 1 8 i; j; (11.24)

Yik � Xk 8 i;k; (11.25)X k

Yik D 1 8i; (11.26)

Yik C Yjm � 2Zkmij � 0 8i;j;k;m; (11.27) Xk D 0;1 8k; (11.28) Yik D 0;1 8i;k; (11.29) Zkmij D 0;1 8i;j;k;m: (11.30)

Equation (11.22)–(11.24) are identical to those of (11.14)–(11.16). Equa- tions (11.25) ensure that spoke i cannot be assigned to a hub at location k unless we locate a hub at location k. Equations (11.26) are key constraints that stipulate that each spoke node i is assigned to exactly one hub. Equations (11.27) state that the flow from origin i to destination j cannot be routed through hubs at nodes k and m, unless spoke node i is assigned to a hub at k and spoke node m is assigned to a hub at j . Equations (11.28)–(11.30) are standard integrity constraints.

11.2.6 The Extension Model of Fixed Cost for Connecting a Spoke to a Hub (Campbell 1994)

Instead of forcing each spoke node to be assigned to a single hub, we may want to stipulate a fixed cost to any spoke/hub connection. Alternatively, we could incorpo- rate a fixed cost for connecting a spoke to a hub. Campbell (1994) shows how these extensions can be formulated.

256 M. Hekmatfar and M. Pishvaee

11.2.6.1 Model Assumptions

The assumptions of this model are similar to median P-hub model except that there is a fixed cost for connecting a spoke to a hub.

11.2.6.2 Model Inputs

Model inputs are similar to median P-hub model in addition to the following parameter:

gik: the fixed cost of connecting spoke node i to a hub at candidate location k.

11.2.6.3 Model Outputs (Decision Variables)

Model outputs are similar to single allocation median P-hub model.

11.2.6.4 Objective Function and its Constraints

The objective function is similar to median P-hub model in addition to the following term: X

i

X k

gikYik: (11.31)

11.2.7 Minimum Value Flow on any Spoke/Hub Connection Problem (Campbell 1994)

Instead of forcing each spoke node to be assigned to a single hub, we may want to stipulate that the flow along any spoke/hub connection exceed some minimum value. Campbell (1994) represented this model, which is similar to single allocation P-hub location problem.

11.2.7.1 Model Assumptions

The assumptions of this model are similar to median P-hub model except that there is a minimum flow for each spoke/hub connection.

11.2.7.2 Model Inputs

Model inputs are similar to median P-hub model in addition to the following parameter:

lik: the minimum flow between spoke i and hub k.

11 Hub Location Problem 257

11.2.7.3 Model Outputs (Decision Variables)

Model outputs are similar to single allocation median P-hub model.

11.2.7.4 Objective Function and its Constraints

The objective function is similar to median P-hub model except that the following constraints are added to median P-hub model’s constraints:

Yik C Yjm � 2Zkmij � 0 8i;j;k;m; (11.32)X m

X j

hijZ km ij C

X P

X s

hpiZ sk Pi � LikYik 8i;k: (11.33)

Equations (11.32) were explained before. The first term of constraints (11.33) are the flow from spoke node i to hub k and then from there to any hub/destination pair. The second term is the flow from any origin/hub pair to hub k and then from there to destination i. The sum of these two flows is the total flow between two nodes i, k.

11.2.8 Capacity Limitation of Hub Location Problem (Campbell 1994)

Capacity limitation of hub node means that the total flows, incoming or outgoing, must be less than or equal to a fixed value and is called capacitated hub location problem. This model is represented by Campbell (1994).

11.2.8.1 Model Assumptions

The assumptions of this model are similar to median P-hub model except that the capacities of the hub nodes are limited.

11.2.8.2 Model Inputs

Model inputs are similar to median P-hub model in addition to the following parameter:

k D the capacity of a hub at candidate node k.

11.2.8.3 Model Outputs (Decision Variables)

Model outputs are similar to median P-hub model.

258 M. Hekmatfar and M. Pishvaee

11.2.8.4 Objective Function and its Constraints

The objective function is similar to median P-hub model except that the following constraints are added to median P-hub model’s constraints:

X m

X i

X j

hijZ km ij C

X s

X i

X j

hijZ sk ij � kXk 8k: (11.34)

The left side of the above inequality shows the total incoming and outgoing flows of node k.

11.2.9 P-Hub Center Location Problem (Campbell 1994)

The center location problem is an important problem for its applications such as emergency facility location or the worst situation scenario. The P-hub center loca- tion problem is similar to P-center location problem. If an origin-destination pair in a hub location problem is introduced as a demand node in P-center problem, the meaning of a hub center problem is a set of hubs that minimizes the maximum cost of each origin/destination pair. This problem is used for decomposable goods or sensitive goods in a hub system. This model is represented by Campbell (1994).

11.2.9.1 Model Assumptions

The assumptions of this model are similar to median P-hub model except that Xk variables are relaxed and the objective function is MiniMax.

11.2.9.2 Model Inputs

Model inputs are similar to median P-hub model.

11.2.9.3 Model Outputs (Decision Variables)

Model outputs are similar to median P-hub model.

11.2.9.4 Objective Function and its Constraints

The objective function of this model and its related constraints are as follows:

Min Max n Ckmij hijZ

km ij

o : (11.35)

11 Hub Location Problem 259

Subject to

X k

Xk D P; (11.36) X k

X m

Z km ij D 1 8 i;j; (11.37)

Zkmij � Xk 8i;j;k;m; (11.38) Z km ij � X 8i;j;k;m; (11.39)

0 � Xk � 1 8k; (11.40) 0 � Zkmij � 1 8i;j;k;m: (11.41)

Equation (11.35) minimizes the maximum cost of transportation between each origin/ destination pair. Equations (11.36)–(11.41) are similar to Median P-hub location problem.

Campbell et al. (2007) represented a new optimization of P-hub center problems (P-HC) and analyzed the complexity of the model and then represented algorithms to solve them.

11.2.10 Hub Covering Location Problem (Campbell 1994)

This model can be used to solve P-hub center model. If an origin-destination pair in a hub location problem is introduced as a demand node in hub covering location problem, the meaning of a hub covering problem is:

The origin/destination pair (i, j) is covered by (m, k) pair of hub nodes, if the cost of i node to j node via m, k hubs is less than or equal to a certain fixed value (number).

Ckmij � �ij : (11.42) Campbell (1994) represented this model and we share this model to two models: hub set covering location model and hub maximal Covering location model.

11.2.10.1 Hub Set Covering Location Problem

Hub set covering location model is a special case of hub covering location model. We introduce this model as follows:

Model assumptions. The assumptions of this model are similar to median P-hub model except that the number of hubs is not known (endogenous) before solving and a fixed cost of hub location is incorporated in the model.

Model inputs. The model inputs of this model are as follows:

Fk D the fixed hub location cost in candidate node k

260 M. Hekmatfar and M. Pishvaee

Ckmij D transportation cost from origin i to destination j via hubs at candidate nodes k and m �ij D maximum cost for going from origin i to destination j (distance covering) V kmij D node hubs m, k cover the origin-destination i, j Model outputs (decision variables): Model outputs are similar to median

P-hub model. Objective function and its constraints. The objective function of this model and

its related constraints are as follows:

Min X k

FKXK: (11.43)

Subject to

Zkmij � Xk 8i;j;k;m; (11.44) Zkmij � Xm 8i;j;k;m; (11.45)X k

X m

V kmij Z km ij � 1 8i;j; (11.46)

0 � Xk � 1 8k; (11.47) 0 � Zkmij � 1 8i;j;k;m: (11.48)

Equation (11.43) minimizes the total hub location costs. Equations (11.46) ensure that all of origin-destination pairs are covered at least once. The other equations are similar to those of the previous models.

11.2.10.2 Hub Maximal Covering Location Problem

Hub maximal covering location model is a special case of hub covering location model. We introduce it as follows:

Model assumptions. The assumptions of this model are similar to median P-hub model except that the number of hubs is known (exogenous) before solving the model and that the fixed cost of hub location is not considered in the model.

Model inputs. The model inputs are as follows:

hij D the demand flow from origin i to destination j Model outputs (decision variables). Model outputs are similar to median

P-hub model. Objective function and its constraints. The objective function of this model and

its related constraints are as follows:

Max X i

X j

X m

hijZ km ij V

km ij : (11.49)

11 Hub Location Problem 261

Subject to

X k

Xk D P; (11.50) X k

X m

Z km ij D 1 8 i; j; (11.51)

Zkmij � Xk 8i;j;k;m; (11.52) Z km ij � Xm 8i;j;k;m; (11.53)

0 � Xk � 1 8k; (11.54) 0 � Zkmij � 1 8i;j;k;m: (11.55)

Equation (11.49) maximizes the covered demand value. The other equations of this model are similar to P-hub median model introduced before.

11.3 Solution Techniques

Many algorithms are represented to solve difference types of hub location problems. We review the related literatures and introduce some of the proposed associated algorithms.

11.3.1 Various Kinds of Algorithms

To solve small hub problems, integer programming optimization methods are used. However, for larger problems, heuristic methods or Meta heuristic methods are uti- lized.

In the past, few solving methods were proposed for hub location problems in which the number of hubs is a decision variable and the fixed cost of establishing a hub is considered. Nevertheless, with the growth of meta heuristic methods, number of methods to solve such problems has been increased.

� To solve the two-hub case, a procedure is given by Ostresh (1975) to solve the two-center location–allocation problem (location–allocation problem with no in- teraction between the sources where each destination is assigned to the closest source).

� O’Kelly (1987) formulated the P-hub median problem (P-HLMP) as a quadratic integer programming problem. He showed that the problem is NP-hard, and pro- posed two enumeration-based heuristics to solve it.

� Exchange clustering methods are presented by Klincewicz (1991). � Greedy search methods, Tabu search and Grab are given by Klincewicz (1992).

262 M. Hekmatfar and M. Pishvaee

� Tabu search methods are given by Skorin-Kapov and Skorin-Kapov (1994). � Genetic algorithm methods are given by Abdinnour-Helm and Venkataramanan

(1998). � A mixed method, Tabu search and genetic algorithm by Abdinnour-Helm (1998); � A mixed method, Simulated Annealing and Tabu search given by Chen (2007); � Genetic algorithm method given by Topcouglu et al. (2005); � Solving uncapacitated single allocation hub location problem with installed fixed

cost simulated annealing is represented by Aykin (1995). � Greedy Interchange, Alflo, Maxflo given by Campbell (1996); � Shortest Path method given by Sohn (1998); � Greedy Algorithm for one stop state (traveling form an origin to a destination

through only one hub node) given by Sasaki et al. (1999), are discussed in this section. Two networks are studied with 32 nodes and 2 or 5 hubs, and 50 nodes and 2 or 4 hubs, respectively. Comparisons between the greedy and branch and bound algorithms have shown that the greedy algorithm needs less machine time.

� Ebery et al. (2000) represented a heuristic algorithm with shortest path method to solve capacitated multiple allocation hub location problem (CHLP-M), and then used the gained upper bound in branch and bound procedure in basic linear programming.

� Ernst and Krishnamoorthy (1999) represented methods to solve capacitated sin- gle allocation hub location problem (CHLP-S).

� Aykin (1994) represented procedures based on Lagrangian relaxation to solve capacitated hub location problems (CHLP).

� Camargo et al. (2008) represented a bender decomposition method to solve un- capacitated multiple allocation hub location problem (UHLP-M).

� Canovas et al. (2007) represented a dual ascent method, and a heuristic method, to solve uncapacitated multiple allocation hub location problem (UHLP-M).

� Rodriguez et al. (2007) represented a solution method based on simulated an- nealing to solve capacitated hub location problem (CHLP). In this method each hub is assumed to be an M/M/1 queuing system and has solved for a network with 52 nodes.

� Martine Labbe et al. (2005) represented a solution method based on branch and cut algorithm to solve uncapacitated single allocation hub location problem (UHLP-S). In this method, the network connecting the hub nodes is called back- bone Network and the connected network of the terminal nodes is called access network.

� Marianov et al. (2003) represented Tabu search algorithm in airlines location in which each hub node is assumed to be an M/D/C queue. In this method, only a part of feasible solution is surveyed and the best neighborhood is selected as a new hub node with respect to continuous iterations on neighborhood nodes of former hub, even the target function gains a worse solution. This method works best for networks of up to 50 nodes with 4 or 5 hubs. However, the efficiency of method decreases as the number of nodes increases and reaching a feasible solution is guaranteed.

11 Hub Location Problem 263

� Wagner (2007) represented a clustering method using Tabu search and genetic algorithm. This method was used to solve traveling salesman problem (TSP).

� Pamuk et al. (2001) represented a single relocating heuristic by Tabu search to solve P-hub center problems (P-HLCP). Two single-allocation schemes were used in the evaluation phase of the algorithm. A greedy local search was em- ployed to improve the resulting allocations.

� Cunha and Silva (2007) represented an efficient hybrid genetic algorithm (GA) approach for the hub and spoke location problem for the less-than-truckload (LTL) services in Brazil. This problem can be seen as a modified version of the uncapacitated hub location problem with single allocation (UHLP-S), in which the discount factor on the hub to hub links is not constant but may vary according to the total amount of cargo between hub terminals.

� Thomadsen and Larsen (2007) represented branch-and-price algorithm or IP col- umn generation (the combination of column generation and branch-and-bound algorithm) to solve a two-layered network (a hierarchical network) consisting of clusters of nodes, each defining an access network and a backbone network. The two layers in the network are: the backbone network and the access networks. The backbone network connects disjoint clusters of nodes, each including an ac- cess network. The node connecting an access network to the backbone network is called a hub.

� Costa et al. (2008) represented a bi-criteria integer linear programming to solve the capacitated single allocation hub location problems (CHLP-S).

� Bollapragada et al. (2005) represented a new network-planning model and an effective greedy solution heuristic to solve a model that is most closely related to the capacitated hub maximum-covering location problem with multi allocations (CHMCLP-M).

� The quality of the heuristic algorithm is evaluated by comparing its coverage with the optimal (for small problems) or with an upper bound obtained by solving a linear-programming relaxation.

� Rodriguez-Martin et al. (2008) represented a mixed integer linear programming formulation and described two branch-and-cut algorithms based on decompo- sition techniques to solve a capacitated multi allocation hub location problem (CHLP-M)

� Yaman (2008) represented a heuristic algorithm based on Lagrangian relaxation and local search to solve P-hub location median single allocation problems (P- HLMP-S).

� Wagner (2008) represented LP-relaxation to solve uncapacitated multi allocation P-hub location median problems (P-HLMP-M).

� Kratica et al. (2007) represented two genetic algorithms for solving the uncapac- itated single allocation P-hub location median problem (P-HLMP-S).

A wide array of solution methods are represented in Table 11.1. It’s shown that methods lose their efficiency, need much time to be solved when the number of nodes is increased over 50.

264 M. Hekmatfar and M. Pishvaee

Table 11.1 Solution methods for hub location problem

Reference Problem Solving method Efficient number of nodes (number of hubs)

O’Kelly (1986) 1-HLP-S Nearest distance Ostresh (1975) 2-HLP Location–allocation

(shortest route) O’Kelly (1987) P-HLMP Nearest distance-quadratic

integer Klincewicz (1991) P-HLMP Clustering Klincewicz (1992) P-HLMP Tabu search and greedy

random algorithm Skorin-Kapov and Skorin-Kapov (1994)

P-HLMP-S Tabu search

Skorin-Kapov et al. (1996) P-HLMP-S & P-HLMP-M

Linear programming

Campbell (1991) P-HLMP-M Integer programming Campbell (1994) P-HLMP-M Integer programming O’ Kelly (1992) UHLP-S Heuristic algorithm Abdinnour-Helm and Venkataramanan (1998)

UHLP-S Genetic algorithm

Abdinnour-Helm (1998) UHLP-S Genetic algorithm and tabu search (GATS)

Chen (2007) UHLP-S Tabu search and simulated annealing

200

Topcouglu et al. (2005) UHLP-S Genetic algorithm 200 (5) Aykin (1995) UHLP-S Simulated annealing

(greedy interchange) B & B Campbell (1996) P-HLMP-M Greedy- interchange Sohn and Park (1998) P-HLMP-M Nearest distance 25 (3–4) Sasaki et al. (1999) P-HLMP-M B&B algorithm and greedy

algorithm 50 (2–4)

Ebery et al. (2000) CHLP-M Nearest distance – B & B 200 Ebery (2001) P-HLMP-S Mixed integer linear

programming 50 (2–3)

Aykin (1994) P-HLMP-S B & B (lagrangian relaxation)

Camargo et al. (2008) UHLP-M Benders decomposition 200 Canovas et al. (2007) UHLP-M Means of a dual ascent

technique- B & B 120

Rodriguez et al. (2007) CHLP-M Simulated annealing 52 Labbe et al. (2005) UHLP-S Branch & cut (B & C) Sung and Jin (2001) P-HLMP-M Clustering (dual-based

approach) Wagner (2007) UHLP-M Clustering (genetic

algorithm & Tabu search) Marin (2005) CHLP-M Integer linear programming 40 Marianov and Serra (2003) UHLP-M Tabu search 50 (4–5) Klincewicz (1996) UHLP-M Dual ascent and dual

adjustment techniques within a B & B scheme

(continued)

11 Hub Location Problem 265

Table 11.1 (continued)

Reference Problem Solving method Efficient number of nodes (number of hubs)

Mayer and Wagner (2002) UHLP-M Dual ascent approach Yaman et al. (2007) CHLP-S Tabu search (with greedy

algorithm) – B & C 49

Cunha and Silva (2007) UHLP-S Genetic algorithm 25 Pamuk and Sepil (2001) UHLP-M Tabu search (with greedy

local algorithm) 25 (5)

Thomadsen and Larsen (2007)

UHLP-M Branch and price (combination of column generation and B & B)

25

Costa et al. (2008) CHLP-S Bi-criteria integer linear programming

40

Bollapragada et al. (2005) CHMCLP-M (maximum covering)

Greedy algorithm

Rodriguez-Martin and Salazar-Gonzalez (2008)

CHLP-M Mixed integer linear programming with B & C based on decomposition method

25 (10)

Yaman (2008) P-HLMP-S Lagrangian relaxation and local search

81 (25)

Pirkul and Schilling (1998) P-HLP-S Lagrangian relaxation 25 Wagner (2008) P-HLMP-M LP relaxation 50 (5) Kratica et al. (2007) P-HLMP-S Genetic algorithm 200 (20)

11.3.2 Some Relevant Algorithms

O’Kelly (1987) represented two heuristic methods to solve uncapacitated single al- location hub location problem.

In the first heuristic method each demand node is allocated to the nearest hub node. It is known that when ˛ D 0, the third part of the nonlinear (11.7) will be zero and the problem is reduced to a P-Median Problem. This method works well when ˛ < 0:5.

In the second heuristic method all ways to allocate non-hub nodes to the nearest or second nearest hub nodes are analyzed. If we have N nodes to select P hubs, we will have N!/P!.N! ways. For each one of the N!/P!.N! ways, all of the 2N–P ways to allocate non-hub nodes to the nearest and second nearest hub nodes are studied. By increasing the number of nodes solution time is increased.

The second heuristic method results in better solution compared to the first heuristic method. Also, the second heuristic gives a tighter upper bound on the ob- jective function than the first one.

266 M. Hekmatfar and M. Pishvaee

11.3.2.1 Greedy Heuristic Algorithm

Greedy algorithm was first presented by Sasaki et al. (1999) to solve the 1-stop un- capacitated multiple allocation hub location problem. One stop means that to travel between each origin-destination pair, we have to pass only one hub node. The ap- plication of this method is for small networks such as Japan inner airlines network.

11.3.2.2 Genetic Algorithm

Topcuoglu et al. (2005) represented this algorithm to solve uncapacitated single allocation hub location problem with fixed cost of location.

A genetic algorithm (GA) is a search algorithm for finding the near-optimal so- lutions in large spaces, which is inspired from population genetics. The general idea was introduced by Holland (1975). Genetic algorithms have been applied to a large set of problems in various fields in the literature.

Two example sources for detailed information on GA are the books written by Goldberg (1989) and Mitchell (1998).

11.3.2.3 Benders Decomposition Method

Camargo et al. (2008) represented this method based on an old algorithm in 1962 which proposed a partitioning method for solving mixed linear and nonlinear inte- ger programming problems. Camargo et al. (2008) defined a relaxation algorithm for solving a problem through partitioning it into two simpler problems: an integer problem, known as MP, and a linear problem, known as SP.

The MP is a relaxed version of the original problem with a set of integer variables and its associated constraints, while SP is the original problem with the values of the integer variables temporarily fixed by the MP.

The algorithm solves each one of the two simpler problems iteratively, one at a time. At each iteration, a new constraint, known as Benders cut, is added to the MP. This new constraint is originated by the dual problem of the SP. The algorithm goes on until the objective function value of the optimal solution to the MP is equal to that of the SP, when it stops obtaining the optimal solution of the original mixed integer problem.

11.4 Case Study

In this section we will introduce some real-world case studies related to hub location problems.

11 Hub Location Problem 267

11.4.1 The Policy of Open Skies in the Middle East (Adler and Hashai 2005)

In Adler and Hashai (2005), airlines and transportations based on open sky policy were surveyed in the Middle East.

Conclusions drawn from this investigation may enable both researchers and pol- icy makers to develop a greater understanding of the social welfare impacts of deregulation in the regional air-transport industry and the economic benefits to in- dividual air carriers, countries and passengers alike, once peace restraints in the region. This analysis had led to the conclusion that the increase in both leisure and business air traffic due to the reduction in violence in the Middle East may lead to an increase of 51% in inter-country passenger flow under the assumption of dereg- ulation of the regional air-transport industry.

It is interesting that based on their research the four cities selected as optimized hub airports are, in order of utility, Cairo, Tehran, Istanbul, and Riyadh. Dubai which now works as an important center for airport transportation, is not an optimal hub airport. This means that, politic and economic problems have dominated over opti- mized location.

11.4.2 A Hub Port in the East Coast of South America (Aversa et al. 2005)

Aversa et al. (2005) formulated a mixed planning model for selecting a hub port, from eleven ports servicing to transportation demands, in the east coast of South America.

It was recommended that minimisation of transport costs, is often given un- warranted significance, usually by “awkward” river ports, such as Antwerp and Hamburg, while the importance of port costs, in these ports, is at the same time purposely downplayed.

In this research many ports were researched such as, ports in Brazil, Argentina and Uruguay. Their model consists of 3,883 variables and 4,225 constraints. After solving the model, port Santos, Brazil was chosen as the hub port.

11.4.3 A Hub Model in Brunswick, Canada (Eiselt 2007)

Eiselt (2007) represented an application of location models to the siting of landfills. The landfill and transfer station location problem was formulated similar to a hub location problem. The problem included a parameter that measures the discount factor of the transportation between transfer stations and landfills in comparison to the unit transportation cost between customers and transfer stations.

268 M. Hekmatfar and M. Pishvaee

The Province of New Brunswick was used to compare optimized facility loca- tions with facility locations that had been chosen by the planners. In order to make such comparison, the major towns and villages were chosen on the basis of the sta- tistical data available from the latest census. The result of the calculations was that, the optimized solutions were between 10 and 40% less costly as compared to the observed solutions. Still, the optimized locations of the landfills were quite close to those found in the optimization runs. The only exception was a case in which the planners deviated from their plan due to public opposition. Their first choice of location also appeared in some of the optimized runs. Some additional optimization was also performed on a smaller subset of the 93 points which were the basis of the optimization reported above.

11.4.4 A Hub/Spoke Network in Brazil (Cunha and Silva 2007)

Cunha and Silva (2007) represented the problem of configuring hub-and-spoke net- works for trucking companies that operate less-than-truckload services in Brazil. The problem consists of determining the number of consolidation terminals (also known as hubs), their locations and the assignment of the spokes to the hubs, aim- ing to minimize the total cost, which is composed of fixed and variable costs.

References

Abdinnour-Helm S (1998) A hybrid heuristic for the uncapacitated hub location problem. Eur J Oper Res 106:489–99

Abdinnour-Helm S, Venkataramanan MA (1998) Solution approaches to hub location problems. Ann Oper Res 78:31–50

Adler N, Hashai N (2005) Effect of open skies in the Middle East region. Transport Res 39:878–894

Aversa R, Botter RC, Haralambides HE, Yoshizaki HTY (2005)A mixed integer programming model on the location of a hub port in the East Coast of South America. Maritime Econ Lo- gist 7:1–18

Aykin T (1994) Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem. Eur J Oper Res 79:501–523

Aykin T (1995) Networking policies for hub-and-spoke systems with application to the air trans- portation system. Transport Sci 29(3):201–221

Baird AJ (2006) Optimizing the Container transshipment hub location in northern Europe. J Trans- port Geograph 14(3):195–214

Bania N, Bauer P, Zlatoper TU (1998) Air passenger service: A taxonomy of route network, hub location, and competition. Logist Transport Rev 34:53–74

Berman O, Drezner Z, Wesolowsky G (2007) The transfer point location problem. Eur J Oper Res 179(3):978–989

Bollapragada R, Camm J, Rao US, Wu J (2005) A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broad bound access. Oper Res Lett 33:134–142

Camargo RS, Miranda Jr G, Luna HP (2008) Benders decomposition for the uncapacitated multiple allocation hub location problem. Comput Oper Res 35(4):1047–1064

11 Hub Location Problem 269

Campbell JF (1991) Hub location problems and the p-hub median problem. Center for Business and Industrial Studies, University of Missouri, St. Louis, MO

Campbell JF (1994) Integer programming formulations of discrete hub location problems. Eur J Oper Res 72:387–405

Campbell JF (1996) Hub location and P-hub median problem. Oper Res 44(6):923–935 Campbell JF, Ernst A, Krishnamoorthy M (2002) Hub location problems. In: Drezner Z,

Hammacher H (eds) Facility location: applications and theory. Berlin, Springer Campbell AM, Lowe TJ, Zhang L (2007) The P-hub center allocation problem. Eur J Oper Res

176(2):819–835 Canovas L, Garcia S, Marin A (2007) Solving the uncapacitated multiple allocation hub location

problem by means of a dual-ascent technique. Eur J Oper Res 179:990–1007 Chen JF (2007) A hybrid heuristic for the uncapacitated single allocation hub location problem.

Omega 35(2):211–220 Costa MG, Captivo ME, Climaco J (2008) Capacitated single allocation hub location problem-A

bi-criteria approach. Comput Oper Res 35(11):3671–3695 Cunha CB, Silva MR (2007) A genetic algorithm for the problem of configuring a hub-and-spoke

network for a LTL trucking company in Brazil. Eur J Oper Res 179:747–758 Daskin MS (1995) Network and discrete location: Models, algorithms, and applications. Wiley,

New York Don T, Harit S, English JR, Whicker G (1995) Hub and spoke networks in truckload trucking:

configuration testing and operational concerns. Logist Transport 31:209–237 Ebery J (2001) Solving large single allocation p-hub problems with two or three hubs: Eur J Oper

Res 128:447–458 Ebery J, Krishnamoorty M, Ernst A, Boland N (2000) The capacitated multiple allocation hub

location problem: formulation and algorithms. Eur J Oper Res 120:614–631 Eiselt HA (2007) Locating landfills – optimization vs. reality. Eur J Oper Res 179(3): 1040–1049 Ernst A, Krishnamoorthy M (1996) Efficient algorithms for the uncapaciterted single allocation

P-hub median problem. Location Sci 4:139–154 Ernst A, Krishnamoorthy M (1999) Solution algorithms for the capacitated Single allocation hub

location problem. Ann Oper Res 86:141–159 Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-

Wesley, Reading, MA Hakimi SL (1964) Optimum location of switching centers and the absolute centers and medians of

a graph. Oper Res 12:450–459 Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press,

Michigan Jaillet P, Song G, Yu G (1996) Airline network design and hub location problems. Location Sci

4(3):195–212 Klincewicz JG (1991) Heuristics for the P-hub location problem. Eur J Oper Res 53:25–37 Klincewicz JG (1992) Avoiding local optima in the P-hub location problem using tabu search and

grasp. Ann Oper Res 40:283–302 Klincewicz JG (1996) A dual algorithm for the uncapacitated hub location problem. Location Sci

4(3):173–184 Klincewicz JG (1998) Hub location in backbone tributary network design: A review. Location Sci

6:307–335 Kratica J, Stanimirovic Z, Tosic D, Filipovic V (2007) Two genetic algorithms for solving the

uncapacitated single allocation p-hub median problem. Eur J Oper Res 182:15–28 Krishnamoorthy M, Mills G, Sier D (1994) Strategic configuration of the mail processing net-

work: location–allocation modeling-stage 1, CSIRO, Technical Report DMS-C94/9 Division of Mathematics and statistics CSIRO, Australia

Kuby MJ, Gray RG (1993) Hub network design problem with stoppers and feeders: Case of federal express. Transport Res 27:1–12

Labbe M, Yaman H, Gourdin E (2005) A branch and cut algorithm for hub location problems with single assignment 102:371–405

270 M. Hekmatfar and M. Pishvaee

Lee Y, Lim B, Park J (1996) A hub location problem in designing digital data service networks: Lagrangian relaxation approach. Location Sci 4:183–194

Lumsdenk, Dallari F, Ruggeri R (1999) Improving the efficiency of the hub and spoke system for the SKF European distribution network. Int J Phys Distrib Logist Manage 29:50–64

Marianov V, Serra D (2003) Location models for airline hubs behaving as M/D/c queues. Comput Oper Res 30:983–1003

Marin A (2005) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32:3093–3109

Martin JC, Roman C (2003) Hub location in the South-Atlantic airline market: A spatial competi- tion game. Transport Res A: Policy Pract 37(10):865–888

Mayer G, Wagner B (2002) Hub Locator: an exact solution method for the multiple allocation hub location problem. Comput Oper Res 29:715–39

Mitchell M (1998) An introduction to genetic algorithms. MIT Press, Cambridge, MA O’Kelly ME (1986) The location of interacting hub facilities, Transport Sci 20:92–106 O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur

J Oper Res 32:393–404 O’ Kelly ME (1992) Hub facility location with fixed costs. Papers in Regional Science 71:292–306 Ostresh LMJr (1975) An efficient algorithm for solving the two center location – allocation prob-

lem. J Region Sci 15:209–216 Pamuk FS, Sepil C (2001) A solution to the hub center problem via a single-relocation algorithm

with Tabu search. IIE Trans 33:399–411 Pirkul H, Schilling DA (1998) An efficient procedure for designing single allocation hub and spoke

systems. Manage Sci 44(12):235–242 Rodriguez V, Alvarez MJ, Barcos L (2007) Hub location under capacity constraints. Transport Res

Part E: Logist Transport Rev 43:495–505 Rodriguez-Martin I, Salazar-Gonzalez JJ (2008) Solving a capacitated hub location problem. Eur

J Oper Res 184(2):468–479 Sasaki M, Suzuki A, Drezner Z (1999) On the selection of hub airports for an airline hub-and-spoke

system. Comput Oper Res 26:1411–1422 Shaw SL (1993) Hub structures of major US passenger airline. J Transport Geograph 1(1):47–58 Skorin-Kapov D, Skorin-Kapov J (1994) On Tabu search for the location of interacting hub facili-

ties, Eur J Oper Res 73:502–509 Skorin-Kapov D, Skorin-Kapov J, O’Kelly M (1996) Tight linear programming relaxations of

uncapacitated p-hub median problems. Proc Natl Decis Sci Conf, Boston 94:582–593 Sohn J, Park S (1998) Efficient solution procedure and reduced size formulation for P-hub location

problem. Eur J Oper Res 108:118–126 Sung CS, Jin HW (2001) Dual-based approach for a hub network design problem under non-

restrictive policy. Eur J Oper Res 132:88–105 Thomadsen T, Larsen J (2007) A hub location problem with fully interconnected backbone and

access networks. Comput Oper Res 34:2520–2531 Toh RS, Higgins RC (1985) The impact of hub and spoke network centralization and route

monopoly on domestic airline profitability. Transport J 24:16–27 Topcuoglu H, Corut F, Ermis M, Yilmaz G (2005) Solving the uncapacitated hub location using

genetic algorithms. Comput Oper Res 32:467–984 Wagner B (2007) An exact solution procedure for a cluster hub location problem, Eur J Oper Res

178:391–401 Wagner B (2008) A note on location of hubs in a competitive environment. Eur J Oper Res

184(1):57–62 Yaman H (2008) Star P-hub median problem with modular arc capacities. Comput Oper Res

35(9):3009–3019 Yaman H, Kara BY, Tansel BC (2007) The latest arrival hub location problem for cargo delivery

systems with stopovers. Transport Res B 41:906–919