Capacitated single allocation hub location problem—A bi-criteria approach

A different approach to the capacitated single allocation hub location problem is presented. Instead of using capacity constraints to limit the amount of flow that can be received by the hubs, we introduce a second objective function to the model (besides the traditional cost minimizing function), that tries to minimize the time to process the flow entering the hubs. Two bi-criteria single allocation hub location problems are presented: in a first model, total time is considered as the second criteria and, in a second model, the maximum service time for the hubs is minimized. To generate non-dominated solutions an interactive decision-aid approach developed for bi-criteria integer linear programming problems is used. Both bi-criteria models are tested on a set of instances, analyzing the corresponding non-dominated solutions set and studying the reasonableness of the hubs flow charge for these non-dominated solutions. The increased information provided by the non-dominated solutions of the bi-criteria model when compared to the unique solution given by the capacitated hub location model is highlighted.     

A hybridization of an evolutionary algorithm and a parallel branch and bound for solving the capacitated single allocation hub location problem

In this study, we propose a hybrid optimization method, consisting of an evolutionary algorithm (EA) and a branch-and-bound method (BnB) for solving the capacitated single allocation hub location problem (CSAHLP). The EA is designed to explore the solution space and to select promising configurations of hubs (the location part of the problem). Hub configurations produced by the EA are further passed to the BnB search, which works with fixed hubs and allocates the non-hub nodes to located hubs (the allocation part of the problem). The BnB method is implemented using parallelization techniques, which results in short running times. The proposed hybrid algorithm, named EA-BnB, has been tested on the standard Australia Post (AP) hub data sets with up to 300 nodes. The results demonstrate the superiority of our hybrid approach over existing heuristic approaches from the existing literature. The EA-BnB method has reached all the known optimal solutions for AP hub data set and found new, significantly better, solutions on three AP instances with 100 and 200 nodes. Furthermore, the extreme efficiency of the implementation of this hybrid algorithm resulted in short running times, even for the largest AP test instances.     

Uncapacitated single allocation p-hub maximal covering problem

The hub location problem is to find a set of hub nodes on the network, where logistics transportation via the hubs is encouraged because of the cost or distance savings. Each node that has a specified amount of demands can be connected to one of p hubs. The uncapacitated single allocation p-hub maximal covering problem is to maximize the logistics covered, where the logistics of demand is said to be covered if the distance between two nodes is less than or equal to the specified range in consideration of the distance savings between hubs. The aim of our model is to locate the hub, and to allocate non-hub nodes to the located hub nodes; the hub can maximize the demand covered by deadline traveling time. It is presented an integer programming formulation for the new hub covering model, and a computational study based on several instances derived from the CAB (Civil Aeronautics Board) data set. Two heuristics, distance based allocation and volume based allocation methods, are suggested with a computational experiment on the CAB data set. Performances of heuristics are evaluated, and it is shown that good solutions are found in a relatively reasonable computation time for most of instances.     

Star p-hub median problem with modular arc capacities

We consider the hub location problem, where p hubs are chosen from a given set of nodes, each nonhub node is connected to exactly one hub and each hub is connected to a central hub. Links are installed on the arcs of the resulting network to route the traffic. The aim is to find the hub locations and the connections to minimize the link installation cost. We propose two formulations and a heuristic algorithm to solve this problem. The heuristic is based on Lagrangian relaxation and local search. We present computational results where formulations are compared and the quality of the heuristic solutions are tested.     

A tabu-search based heuristic for the hub covering problem over incomplete hub networks

Hub location problems deal with finding the location of hub facilities and with the allocation of demand nodes to these located hub facilities. In this paper, we study the single allocation hub covering problem over incomplete hub networks and propose an integer programming formulation to this end. The aim of our model is to find the location of hubs, the hub links to be established between the located hubs, and the allocation of non-hub nodes to the located hub nodes such that the travel time between any origin–destination pair is within a given time bound. We present an efficient heuristic based on tabu search and test the performance of our heuristic on the CAB data set and on the Turkish network.     

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

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 p is 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) and explore alternative models and solution procedures.     

A branch-and-cut algorithm for the hub location and routing problem

We study the hub location and routing problem where we decide on the location of hubs, the allocation of nodes to hubs, and the routing among the nodes allocated to the same hubs, with the aim of minimizing the total transportation cost. Each hub has one vehicle that visits all the nodes assigned to it on a cycle. We propose a mixed integer programming formulation for this problem and strengthen it with valid inequalities. We devise separation routines for these inequalities and develop a branch-and-cut algorithm which is tested on CAB and AP instances from the literature. The results show that the formulation is strong and the branch-and-cut algorithm is able to solve instances with up to 50 nodes.     

Multi-product Capacitated Single-Allocation Hub Location Problems: Formulations and Inequalities

In this paper we extend the classical capacitated single-allocation hub location problem by considering that multiple products are to be shipped through the network. We propose a unified modeling framework for the situation in which no more than one hub can be located in each node. In particular, we consider the case in which all hubs are dedicated to handling a single-product as well as the case in which all hubs can handle all products. The objective is to minimize the total cost, which includes setup costs for the hubs, setup costs for each product in each hub and flow routing costs. Hubs are assumed to be capacitated. For this problem several models are proposed which are based on existing formulations for the (single-product) capacitated single-allocation hub location problem. Additionally, several classes of inequalities are proposed in order to strengthen the models in terms of the lower bound provided by the linear relaxation. We report results of a set of computational experiments conducted to test the proposed models and their enhancements.     

Hub network design problem in the presence of disruptions

The main issue in p-hub median problem is locating hub facilities and allocating spokes to those hubs in order to minimize the total transportation cost. However hub facilities may fail occasionally due to some disruptions which could lead to excessive costs. One of the most effective ways to hedge against disruptions especially intentional disruptions is designing more reliable hub networks. In this paper, we formulate the multiple allocation p-hub median problem under intentional disruptions by a bi-level model with two objective functions at the upper level and a single objective at the lower level. In this model, the leader aims at identifying the location of hubs so that minimize normal and worst-case transportation costs. Worst-case scenario is modeled in the lower level where the follower’s objective is to identify the hubs that if lost, it would mostly increase the transportation cost. We develop two multi-objective metaheuristics based on simulated annealing and tabu search to solve the problem. Computational results indicate the viability and effectiveness of the proposed algorithms for exploring the non-dominated solutions.     

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

Routing and scheduling decisions in the hierarchical hub location problem

Hubs are facilities that consolidate and disseminate flow in many-to-many distribution systems. The hub location problem considers decisions that include the locations of hubs in a network and the allocations of demand (non-hub) nodes to these hubs. We propose a hierarchical multimodal hub network structure, and based on this network, we define a hub covering problem with a service time bound. The hierarchical network consists of three layers in which we consider a ring-star-star (RSS) network. This multimodal network may have different types of vehicles in each layer. For the proposed problem, we present and strengthen a mathematical model with some variable fixing rules and valid inequalities. Also, we develop a heuristic solution algorithm based on the subgradient approach to solve the problem in more reasonable times. We conduct the computational analysis over the Turkish network and the CAB data sets.     

HubLocator: an exact solution method for the multiple allocation hub location problem

HubLocator is a new branch-and-bound procedure for the uncapacitated multiple allocation hub location problem. An existing optimal method developed by Klincewicz (Location Sci. 4 (1996) 173) is based on dual ascent and dual adjustment techniques applied to a disaggregated model formulation. These techniques have already successfully been used to solve the closely related simple plant location problem. However, due to the specific structure of the problem at hand, the success of these techniques in reducing the computational effort is rather restricted. Therefore, HubLocator additionally considers an aggregated model formulation enabling us to significantly tighten the lower bounds. Upper bounds which satisfy complementary slackness conditions for some constraints are constructed and improved by means of a simple heuristic procedure. Computational experiments demonstrate that optimal solutions for problems with up to 40 nodes can be found in a reasonable amount of time.Scope and purposeGround and air transportation networks, postal delivery networks, and computer networks are often configured as hub-and-spoke systems. Traffic between two locations is not transported directly between these locations, but routed via particular switching or consolidation points called hubs. Due to increased traffic on linkages between hubs, larger vehicles can be used or the capacity of existing vehicles can be utilized more efficiently, resulting in smaller per unit transportation costs. The exploitation of scale economies as a result of the reduced number of linkages, which have to be operated in a hub-and-spoke system, compared to a fully interconnected network is an important advantage of this type of system.Designing hub-and-spoke networks deals with the selection of hubs from a given set of potential locations and the routing of traffic. We consider a special type of such a hub location problem and adapt a successful technique developed to find an optimal solution for the well-known simple plant location problem.     

Path relinking approach for multiple allocation hub maximal covering problem

We consider the multiple allocation hub maximal covering problem (MAHMCP): Considering a serviced O–D flow was required to reach the destination optionally passing through one or two hubs in a limited time, cost or distance, what is the optimal way to locate p hubs to maximize the serviced flows? By designing a new model for the MAHMCP, we provide an evolutionary approach based on path relinking. The Computational experience of an AP data set was presented. And a special application on hub airports location of Chinese aerial freight flows between 82 cities in 2002 was introduced.     

Spatial Analysis of Single Allocation Hub Location Problems

Hubs are special facilities that serve as switching, transshipment and sorting nodes in many-to-many distribution systems. Flow is consolidated at hubs to exploit economies of scale and to reduce transportation costs between hubs. In this article, we first identify general features of optimal hub locations for single allocation hub location problems based on only the fundamental problem data (demand for travel and spatial locations). We then exploit this knowledge to develop a straightforward heuristic methodology based on spatial proximity of nodes, dispersion and measures of node importance to delineate subsets of nodes likely to contain optimal hubs. We then develop constraints for these subsets for use in mathematical programming formulations to solve hub location problems. Our methodology can also help narrow an organization’s focus to concentrate on more detailed and qualitative analyses of promising potential hub locations. Results document the value of including both demand magnitude and centrality in measuring node importance and the relevant tradeoffs in solution quality and time.     

A branch-and-cut algorithm for two-level survivable network design problems

This paper approaches the problem of designing a two-level network protected against single-edge failures. The problem simultaneously decides on the partition of the set of nodes into terminals and hubs, the connection of the hubs through a backbone network (first network level), and the assignment of terminals to hubs and their connection through access networks (second network level). We consider two survivable structures in both network levels. One structure is a two-edge connected network, and the other structure is a ring. There is a limit on the number of nodes in each access network, and there are fixed costs associated with the hubs and the access and backbone links. The aim of the problem is to minimize the total cost. We give integer programming formulations and valid inequalities for the different versions of the problem, solve them using a branch-and-cut algorithm, and discuss computational results. Some of the new inequalities can be used also to solve other problems in the literature, like the plant cycle location problem and the hub location routing problem.     

The q-Ad Hoc Hub Location Problem for Multi-modal Networks

This research proposes a spatial optimization problem over a multi-modal transportation network, termed the q-Ad-hoc hub location problem (AHLP), to utilize alternative hubs in an ad-hoc manner in the wake of a hub outage. The model aims to reorganize the spatial structure of disrupted networks: unaffected hubs are utilized as ad-hoc hubs through which alternative routes connect supply and demand nodes. As a case study, the AHLP is applied to a multi-modal freight transport system connecting international destinations with the United States. The models are utilized to establish a new ranking methodology for critical infrastructure by combining metrics capturing nodal criticality and network resilience and recuperability. The results show that the AHLP is both an effective and practical recovery approach for a hub network to respond to the potential disruptions of hubs and a novel methodology for ranking critical infrastructure.     

The uncapacitated hub location problem in networks under decentralized management

We propose a new hub location model defined by the minimization of costs. The main contribution of this work is to permit the analysis of a hub-and-spoke network operated under “decentralized management”. In this type of network, various transport companies act independently, and each makes its route choices according to its own criteria, which can include cost, time, frequency, security and other factors, including subjective ones. Therefore, due to the diversity of the various companies’ criteria, one can expect that between each origin–destination pair, a fraction of the flow will be carried through hubs and a fraction will be carried by the direct route. to resolve this problem, it becomes necessary to determine the probability that any network user will choose the hub route for each trip to be made (or for each load to be carried). We present an integer programming formulation, subject the new model to experiments with an intermodal general cargo network in Brazil and address questions regarding the solution of the problem in practice.     

Heuristics for a continuous multi-facility location problem with demand regions

We consider a continuous multi-facility location allocation problem where the demanding entities are regions in the plane instead of points. The problem can be stated as follows: given m (closed, convex) polygonal demand regions in the plane, find the locations of q facilities and allocate each region to exactly one facility so as to minimize a weighted sum of squares of the maximum Euclidean distances between the demand regions and the facilities they are assigned to.We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.     

A conditional p-hub location problem with attraction functions

We formulate the competitive hub location problem in which customers have gravity-like utility functions. In the resulting probabilistic model, customers choose an airline depending on a combination of functions of flying time and fare. The (conditional) follower's hub location problem is solved by means of a heuristic concentration method. Computational experience is obtained using the Australian data frequently used in the literature. The results demonstrate that the proposed method is viable even for problems of realistic size, and the results appear quite robust with respect to the leader's hub locations.     

Robust and fuzzy goal programming optimization approaches for a novel multi-objective hub location-allocation problem: A supply chain overview

In this paper, a novel multi-objective mathematical model is developed to solve a capacitated single-allocation hub location problem with a supply chain overview. Three mathematical models with various objective functions are developed. The objective functions are to minimize: (a) total transportation and installation costs, (b) weighted sum of service times in the hubs to produce and transfer commodities and the tardiness and earliness times of the flows including raw materials and finished goods, and (c) total greenhouse gas emitted by transportation modes and plants located in the hubs. To come closer to reality, some of the parameters of the proposed mathematical model are regarded as uncertain parameters, and a robust approach is used to solve the given problem. Furthermore, two methods, namely fuzzy multi-objective goal programming (FMOGP) and the Torabi and Hassini's (TH) method are used to solve the multi-objective mathematical model. Finally, the concluding part presents the comparison of the obtained results.