Hub Location Problems with Allocation Constraints

Introduction

Hub location problems, with the hub-and-spoke network structure, involve locating hub facilities, allocating the non-hubs (spokes) to the hubs, and determining the path for each origin-destination pair. In a pure hub-and-spoke network, all hubs, which act as intermediate switching or transshipment points for internodal flows, are fully interconnected and none of the non-hubs are directly connected (i.e., all flows must be routed through the hubs). Two types of allocations are commonly found in the literature. In the multiple allocation, each non-hub is allowed to be allocated to all the hubs (Figure 1). The single allocation restricts each non-hub to be allocated to a single hub (Figure 2). In real world situations, however, the allocation of the non-hubs to the hubs does not always fall under multiple allocation or single allocation. In many practical situations, each non-hub is restricted to be connected with a few hubs, perhaps two or three. In this chapter, we discuss hub location problems with such allocation constraints. Models for hub location problems with allocation constraints are presented. Data sets for these types of hub location problems are also described.

Figure 1.

An example of a multiple allocation hub-and-spoke network

Figure 2.

An example of a single allocation hub-and-spoke network

Background

In many telecommunication and transportation networks, connecting all pairs of nodes by direct links is very costly. Hence, hubs, which are chosen among the nodes in the network, are installed to serve as intermediate switching or transshipment points. The flows (such as data transmissions, mail, express packages, cargoes, or airline passengers) from the same origin with different destinations are collected on the allocated hub(s), where they are regrouped with other flows from different origins and leave the hub(s) either to other hubs or to their final destinations.

Hubs are fully interconnected and direct links between non-hubs are usually not allowed (i.e., all flows must be routed through the hubs). Since hubbing can reduce the overall transportation cost, there has been a rapid growth in the application of hub-and-spoke networks. Typical applications may be found in express package delivery companies (Kuby & Gray, 1993), passenger airlines (Bania et al., 1998), message delivery networks (Lee et al., 1996; Klincewicz, 1998), and trucking industry (Don et al., 1995). The challenge to the academics then is to design the hub-and-spoke network such that the total cost is minimized.

There are several variants of hub location problems (Campbell & O’Kelly, 2012; Farahani et al., 2013). In the p-hub median problem (p-HMP), the number of hubs p is predetermined. The objective is to locate the hubs, to allocate the non-hubs to the hubs, and to determine the path for each origin-destination pair such that the total transportation cost is minimized. The total cost includes (1) the collection cost incurred during the transportation from the non-hubs to their allocated hub(s); (2) the transfer cost incurred during the transportation between hubs; and (3) the distribution cost incurred during the transportation from the allocated hub(s) to the non-hubs.

The uncapacitated hub location problem (UHLP) is a different type of hub location problem. In the UHLP, the number of hubs is not given a priori and a fixed cost for installing a hub is included in the objective function. The capacitated hub location problem (CHLP) is another type of hub location problem, in which capacity constraints are enforced on the hubs and sometimes on the arcs as well. Two types of allocations are commonly found in the literature. In the multiple allocation, each non-hub is allowed to be allocated to all the hubs. The single allocation restricts each non-hub to be allocated to a single hub.