# Hub-and-Spoke Network Design Considering Congestion and Flow-Based Cost Function
## 1 Introduction  
Hub-and-spoke networks are a significant type of graph topology used in various industries, including transportation, telecommunication, air travel, postal delivery, and freight. In these networks, a few nodes act as hubs--often representing major airports or stations--while the remaining nodes are known as spokes. Hub networks originate in transportation and telecommunication systems in which several origin/destination nodes send and receive some flow. While the nodes may be connected to send/receive directly, joining a hub network to route the flow via \"hub\" nodes is preferred. This is to reduce the incurred cost as the consolidated flow among the hub network benefits from the economy of scale. The transportation network is a common example of an industry with such problems. It is preferred to include the congestion of a hub facility in hub location problems due to the effect of pandemics on travel behaviors. There are several reasons for such behavior, among which we can refer to the following:  
For passenger transportation, overcrowded facilities may not be preferred in the post-pandemic era due to health and safety concerns and regulations, as well as due to the higher chance of delays and cancelations in congested facilities. For cargo transportation companies, firms are eager to use their resources in a balanced manner. An overcrowded facility (even to transport cargo) may increase associated costs and complexities and make the working environment less desirable. For facility management at a hub, the congestion negatively impacts scheduling and planning, causing several delays and cancelations. Therefore, accounting for congestion while designing the network is extremely important [1]. There are three ways to address congestion in the hub-and-spoke model: (1) imposing classical capacity constraints on hub nodes for limiting the amount of flow entering the hubs, (2) incorporating costs of congestion effects explicitly into the objective function using a convex cost function that increases exponentially as more flows go through the hubs, and (3) accounting for congestion in hub nodes using queuing theory and calculating the waiting time of the flow in terms of congestion. Based on this, we incorporate the congestion of hub facilities into our mathematical model using the first method. This research considers the location problem faced by a transportation company to locate new facilities, considering the perceived utility of their customers, as well as the congestion in the hub facilities. In this work, the inter-hub cost coefficient may not be a fixed value for every route and would be a function of transported passengers on each route. In other words, we consider the economy of scale coefficient to be dependent on the flow of the associated link. This is to avoid assigning large discount factors to small inter-hub flows. We incorporate flow-based inter-hub cost coefficients into the network design formulation. That is, the perceived utility of different facilities by customers is considered as a set of given parameters. It should be noted that while the model incorporates the customers' perceived utility, the sole decision-maker of the model is the transportation company, not the customers. As a result, the customers from nodes with no facility may either travel to the nearby nodes with established facilities or would leave our service (which would be treated as \"lost demand\"). This travel cost (from no-facility nodes to the nearby node with facility) is not considered by the transportation company and thus the model, but the lost demand is included. It is also assumed that the potential demand values among different pairs of origin-destination (O-D) are known a priori, which is given by marketing studies or strategic studies. Based on this, the demand between O and D pairs is elastic: the demand is determined based on the location of spoke facilities and the perceived utility of the established facilities, as also discussed by [PERSON] et al. [2].