The planar hub location problem: a probabilistic clustering approach

Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs. We propose a probabilistic clustering method for the planar hub-location problem which is analogous to the method of Iyigun and Ben-Israel (in Operations Research Letters 38, 207–214, 2010; Computational Optmization and Applications, 2013) for the solution of the multi-facility location problem. The proposed method is an iterative probabilistic approach assuming that all trips can be taken with probabilities that depend on the travel costs based on the hub locations. Each hub location is the convex combination of all data points and other hubs. The probabilities are updated at each iteration together with the hub locations. Computations stop when the hub locations stop moving. Fermat-Weber problem and multi-facility location problem are the special cases of the proposed approach.     

Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution

Hub and spoke networks are used to switch and transfer commodities between terminal nodes in distribution systems at minimum cost and/or time. The p-hub center allocation problem is to minimize maximum travel time in networks by locating p hubs from a set of candidate hub locations and allocating demand and supply nodes to hubs. The capacities of the hubs are given. In previous studies, authors usually considered only quantitative parameters such as cost and time to find the optimum location. But it seems not to be sufficient and often the critical role of qualitative parameters like quality of service, zone traffic, environmental issues, capability for development in the future and etc. that are critical for decision makers (DMs), have not been incorporated into models. In many real world situations qualitative parameters are as much important as quantitative ones. We present a hybrid approach to the p-hub center problem in which the location of hub facilities is determined by both parameters simultaneously. Dealing with qualitative and uncertain data, Fuzzy systems are used to cope with these conditions and they are used as the basis of this work. We use fuzzy VIKOR to model a hybrid solution to the hub location problem. Results are used by a genetic algorithm solution to successfully solve a number of problem instances. Furthermore, this method can be used to take into account more desired quantitative variables other than cost and time, like future market and potential customers easily.     

Proprietor and customer costs in the incomplete hub location-routing network topology

The hub location problem finds the location of hubs and allocates the other nodes to them. It is widely supposed the network created with the hub nodes is complete in the extensive literature. Relaxation of this basic supposition forms the present work. The model minimizes the cost of the proprietor, including the fixed costs of hubs, hub links and spoke links. Costs of hub and spoke links are contemplated as fixed cost or maintenance cost. Moreover, the model considers routing costs of customers who want to travel from origins to destinations. In this study, we offer a model to the multiple allocations of the hub location problems, under the incomplete hub location-routing network design. This model is easily transformed to other hub location problems using one or more constraints. No network format is dictated on the hub network. We suggest a set of valid inequalities for the formulation. Some lower bounds are developed using a Lagrangian relaxation approach and the valid inequalities. Computational analyses evaluate the performances of the lower bounding implementations and valid inequalities. Furthermore, we explore the effects of several factors on the design and solution time of the problem formulation.     

The p-hub center allocation problem

The p-hub center problem is to locate p hubs and to allocate non-hub nodes to hub nodes such that the maximum travel time (or distance) between any origin–destination pair is minimized. We address the p-hub center allocation problem, a subproblem of the location problem, where hub locations are given. We present complexity results and IP formulations for several versions of the problem. We establish that some special cases are polynomially solvable.     

Allocation strategies in hub networks

In this paper, we study allocation strategies and their effects on total routing costs in hub networks. Given a set of nodes with pairwise traffic demands, the p-hub median problem is the problem of choosing p nodes as hub locations and routing traffic through these hubs at minimum cost. This problem has two versions; in single allocation problems, each node can send and receive traffic through a single hub, whereas in multiple allocation problems, there is no such restriction and a node may send and receive its traffic through all p hubs. This results in high fixed costs and complicated networks. In this study, we introduce the r-allocation p-hub median problem, where each node can be connected to at most r hubs. This new problem generalizes the two versions of the p-hub median problem. We derive mixed-integer programming formulations for this problem and perform a computational study using well-known datasets. For these datasets, we conclude that single allocation solutions are considerably more expensive than multiple allocation solutions, but significant savings can be achieved by allowing nodes to be allocated to two or three hubs rather than one. We also present models for variations of this problem with service quality considerations, flow thresholds, and non-stop service.     

Network hub location problems: The state of the art

Hubs are special facilities that serve as switching, transshipment 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. In this paper we classify and survey network hub location models. We also include some recent trends on hub location and provide a synthesis of the literature.     

The Tree of Hubs Location Problem

This paper presents the Tree of Hubs Location Problem. It is a network hub location problem with single assignment where a fixed number of hubs have to be located, with the particularity that it is required that the hubs are connected by means of a tree. The problem combines several aspects of location, network design and routing problems. Potential applications appear in telecommunications and transportation systems, when set-up costs for links between hubs are so high that full interconnection between hub nodes is prohibitive. We propose an integer programming formulation for the problem. Furthermore, we present some families of valid inequalities that reinforce the formulation and we give an exact separation procedure for them. Finally, we present computational results using the well-known AP and CAB data sets.     

Avoiding local optima in thep-hub location problem using tabu search and GRASP

In the discretep-hub location problem, various nodes interact with each other by sending and receiving given levels of traffic (such as telecommunications traffic, data transmissions, airline passengers, packages, etc.). It is necessary to choosep of the given nodes to act as hubs, which are fully interconnected; it is also necessary to connect each other node to one of these hubs so that traffic can be sent between any pair of nodes by using the hubs as switching points. The objective is to minimize the sum of the costs for sending traffic along the links connecting the various nodes. Like many combinatorial problems, thep-hub location problem has many local optima. Heuristics, such as exchange methods, can terminate once such a local optimum is encountered. In this paper, we describe new heuristics for thep-hub location problem, based on tabu search and on a greedy randomized adaptive search procedure (GRASP). These recently developed approaches to combinatorial optimization are capable of examining several local optima, so that, overall, superior solutions are found. Computational experience is reported in which both tabu search and GRASP found optimal hub locations (subject to the assumption that nodes must be assigned to the nearest hub) in over 90% of test problems. For problems for which such optima are not known, tabu search and GRASP generated new best-known solutions.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

A hub covering network design problem for cargo applications in Turkey

Hub location problems involve locating hub facilities and allocating demand nodes to hubs in order to provide service between origin–destination pairs. In this study, we focus on cargo applications of the hub location problem. Through observations from the Turkish cargo sector, we propose a new mathematical model for the hub location problem that relaxes the complete hub network assumption. Our model minimizes the cost of establishing hubs and hub links, while designing a network that services each origin–destination pair within a time bound. We formulate a single-allocation hub covering model that permits visiting at most three hubs on a route. The model is then applied to the realistic instances of the Turkish network and to the Civil Aeronautics Board data set.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

Enumeration and Search Procedures for a Hub Location Problem with Economies of Scale

Within a communications or transportation network, in which a number of locations exchange material or information, hubs can be used as intermediate switching points. In this way, traffic can be consolidated on inter-hub links and, thus, achieve economies of scale in transport costs. Recently, O'Kelly and Brian in 1998 proposed a model (termed the FLOWLOC model) that treats these economies of scale by means of piecewise-linear concave cost functions on the interhub arcs. We show that, for a fixed set of hubs, the FLOWLOC model can be solved using the classic Uncapacitated Facility Location Problem (UFLP). This observation then motivates an optimal enumeration procedure for the FLOWLOC model, as well as some search heuristics that are based upon tabu search and greedy random adaptive search procedures (GRASP). These search procedures would be especially applicable for large-sized problems. Some computational experience is described.     

The hub covering flow problem

The hub covering flow problem (HCFP) seeks to find the minimal cost hub-and-spoke network by optimally locating hub nodes and assigning non-hub nodes to the hub nodes subject to a coverage constraint. The cost of establishing such a hub network is based on a fixed cost of opening hubs and the cost of transporting demand flow through the network. We also present an extension called the multi-aircraft HCFP. The results from computational experiments are presented and discussed.     

The hub location and network design problem with fixed and variable arc costs: formulation and dual-based solution heuristic

Many air, less-than-truck load and intermodal transportation and telecommunication networks incorporate hubs in an effort to reduce total cost. These hubs function as make bulk/break bulk or consolidation/deconsolidation centres. In this paper, a new hub location and network design formulation is presented that considers the fixed costs of establishing the hubs and the arcs in the network, and the variable costs associated with the demands on the arcs. The problem is formulated as a mixed integer programming problem embedding a multi-commodity flow model. The formulation can be transformed into some previously modelled hub network design problems. We develop a dual-based heuristic that exploits the multi-commodity flow problem structure embedded in the formulation. The test results indicate that the heuristic is an effective way to solve this computationally complex problem.     

Hub and spoke network design with single-assignment,capacity decisions and balancing requirements

In this paper, an extension of the capacitated single-allocation hub location problem is considered in which the capacity of the hubs is part of the decision making process and balancing requirements are imposed on the network. The decisions to be made comprise (i) the selection of the hubs, (ii) the allocation of the spoke nodes to the hubs, (iii) the flow distribution through the sub network defined by the hubs and (iv) the capacity level at which each hub should operate. In the latter case, for each potential hub, a set of available capacities is considered among which one can be chosen. The objective is to minimize the total cost, which includes the setup cost for the hubs as well as the flow routing cost. Economies of scale are assumed for the costs. Balancing requirements are imposed to the network. In particular, a value is considered for the maximum difference between the maximum and minimum number of spoke nodes that are allocated to the hubs. Two mixed-integer linear programming formulations are proposed and analyzed for this problem. The results of a set of computational experiments using an off-the-shelf commercial solver are presented. These tests aim at evaluate the possibility of solving the problem to optimality using such a solver with a particular emphasis to the impact of the balancing requirements. The tests also allow an analysis of the gap of the bounds provided by linear relaxation.     

Modeling congestion and service time in hub location problems

In this paper, we present a modeling framework for hub location problems with a service time limit considering congestion at hubs. Service time is modeled taking the traveling time on the hub network as well as the handling time and the delay caused by congestion at hubs into account. We develop mixed-integer linear programming formulations for the single and multiple allocation versions of this problem. We further extend the multiple allocation model with a possibility of direct shipments. We test our models on the well-known AP data set and analyze the effects of congestion and service time on costs and hub network design. We introduce a measure for the value of modeling congestion and show that not considering the effects of congestion may result in increased costs as well as in building infeasible hub networks.     

A capacitated hub location problem in freight logistics multimodal networks

In this paper we deal with a capacitated hub location problem arising in a freight logistics context; in particular, we have the need of locating logistics platforms for containers travelling via road and rail. The problem is modelled on a weighed multimodal network. We give a mixed integer linear programming model for the problem, having the goal of minimizing the location and shipping costs. The proposed formulation presents some novel features for modelling capacity bounds that are given both for the candidate hub nodes and the arcs incident to them; further, the containerised origin-destination (\(o-d)\) demand can be split among several platforms and different travelling modes. Note that here the network is not fully connected and only one hub for each \(o-d\) pair is used, serving both to consolidate consignments on less transport connections and as reloading point for a modal change. Results of an extensive computational experimentation performed with randomly generated instances of different size and capacity values are reported. In the test bed designed to validate the proposed model all the instances up to 135 nodes and 20 candidate hubs are optimally solved in few seconds by the commercial solver CPLEX 12.5.     

最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.     

Uncapacitated Euclidean Hub Location: Strengthened Formulation,New Facets and a Relax-and-cut Algorithm

The multiple allocation uncapacitated hub location problem is considered. This problem arises in transportation systems when several locations send and receive passengers and/or express packages and the performance of these systems can be improved by using transshipment points (hubs), where the passengers/packages are collected and distributed. An Integer Programming formulation, the one giving the best computational results until now, serves as a basis for the solution method. Using the fact that the transportation costs between hubs satisfy the triangle inequality, an analysis of the set of solutions that are not candidates to be optimal is carried out and, as a consequence, the formulation of the problem can be strengthened by means of powerful valid inequalities obtained through the study of the intersection graph of an associated set packing problem. The algorithm developed uses the most promising of these inequalities in a Lagrangian relaxation context to reduce the size of the branching tree and improve the computational times. This improvement is shown by means of a computational study, where a set of instances are optimally solved with low computational effort.