Hub Location Allocation Problems and Solution Algorithms

Introduction

In this chapter, we discuss some services, such as database transaction, movements of people, commodities, information or unfinished parts that take place between an origin-destination pair of nodes. Such pairs of nodes can be found in the domain of a manufacturing site or spread along continents, as each origin-destination pair needs a service different from the other pairs.

Hub location problem is one of the most important topics of location problems. The facility location problem, also known as location analysis or k-center problem is a branch of operations research and computational geometry. Facility location problems try to reduce the costs of operations considering some set of constraints and relevant demands with locating different ranges of facilities. Making decisions for facility location are critically challenging regarding strategic planning for all types of business entities. Property acquisition and establishment are naturally costly so that one can consider facility location and relocation operations as long-term investments. Decision makers are challenging with different geographical, demographical and trending factors for selecting profitable sites. Thus, selection of robust facility locations is an important task, as far as future events are uncertain and unpredictable.

Hub location problem is an extension of the classical facility location problems. Hubs are facilities that operate as consolidating, connecting, and switching points for flows between the stipulated origins and destinations (Farahani et al., 2013). Hubs are also defined as special facilities that serve as switching, transshipping and sorting points in many-to-many distribution systems. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin–destination pairs (Alumur & Kara, 2008). Many applications are available for the hub location problem, and this section is primarily dedicated to introducing this problem to readers.

In this chapter, we have tried to fit what moves between an origin-destination pair of nodes, like information, people and commodities into the concept of HLP. Basically, each different pair of origin-destination node has to be serviced exclusively. For instance, people traveling from i to j are not interchangeable with those traveling from j to i. In order to have a fully connected network (a network in which all nodes are connected) with N nodes, in which each node can be either an origin or a destination, the number of pairs (i-j pairs which are different from j-i pairs) should be N (N-1). Fig.1 illustrates a network composed of nodes and connections.

Figure 1.

A regular full-connected network with connections between nodes

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 hub node and connect it to all the other nodes, which are introduced as spokes, we will have 2(n-1) connections to service all origin-destination node pairs. This network is presented in Figure 2 (Daskin, 1995).

Assume, if there are different traffic services, and if each vehicle can provide service for 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 network. Multi-hub network is another type of hub and spoke network that is a formation of two or several hubs and spoke networks in which all hubs are fully connected to each other.

Figure 2.

A hub and spoke network