New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem

This article deals with the uncapacitated multiple allocation p-hub median problem, where p facilities (hubs) must be located among n available sites in order to minimize the transportation cost of sending a product between all pairs of sites. Each path between an origin and a destination can traverse any pair of hubs.     

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.     

Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm

In this paper, we develop a novel stochastic multi-objective multi-mode transportation model for hub covering location problem under uncertainty. The transportation time between each pair of nodes is an uncertain parameter and also is influenced by a risk factor in the network. We extend the traditional comprehensive hub location problem by considering two new objective functions. So, our multi-objective model includes (i) minimization of total current investment costs and (ii) minimization of maximum transportation time between each origin–destination pair in the network. Besides, a novel multi-objective imperialist competitive algorithm (MOICA) is proposed to obtain the Pareto-optimal solutions of the problem. The performance of the proposed solution algorithm is compared with two well-known meta-heuristics, namely, non-dominated sorting genetic algorithm (NSGA-II) and Pareto archive evolution strategy (PAES). Computational results show that MOICA outperforms the other meta-heuristics.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

This paper deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in an exact branch-and-bound framework. Besides, the heuristic provides the branch-and-bound algorithm with good lower bounds for the nodes of the branching tree. The results of the computational experience (with the classical CAB and AP data sets) are included, showing the great effectiveness of this approach: instances with up to 120 nodes are solved.     

Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems

This paper deals with a single allocation problem in hub-and-spoke networks. We present a simple deterministic 3-approximation algorithm and randomized 2-approximation algorithm based on a linear relaxation problem and a randomized rounding procedure. We handle the case where the number of hubs is three, which is known to be NP-hard, and present a (5/4)-approximation algorithm.The single allocation problem includes a special class of the metric labeling problem, defined by introducing an assumption that both objects and labels are embedded in a common metric space. Under this assumption, we can apply our algorithms to the metric labeling problem without losing theoretical approximation ratios. As a byproduct, we also obtain a (4/3)-approximation algorithm for an ordinary metric labeling problem with three labels.     

Optimizing fuzzy p-hub center problem with generalized value-at-risk criterion

In this study, we reduce the uncertainty embedded in secondary possibility distribution of a type-2 fuzzy variable by fuzzy integral, and apply the proposed reduction method to p-hub center problem, which is a nonlinear optimization problem due to the existence of integer decision variables. In order to optimize p-hub center problem, this paper develops a robust optimization method to describe travel times by employing parametric possibility distributions. We first derive the parametric possibility distributions of reduced fuzzy variables. After that, we apply the reduction methods to p-hub center problem and develop a new generalized value-at-risk (VaR) p-hub center problem, in which the travel times are characterized by parametric possibility distributions. Under mild assumptions, we turn the original fuzzy p-hub center problem into its equivalent parametric mixed-integer programming problems. So, we can solve the equivalent parametric mixed-integer programming problems by general-purpose optimization software. Finally, some numerical experiments are performed to demonstrate the new modeling idea and the efficiency of the proposed solution methods.     

The transfer point location problem

In this paper, we introduce the transfer point location problem. Demand for emergency service is generated at a set of demand points who need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of p helicopter pads and one facility. In this paper, we solve the special case where the location of the facility is known and the best location of one transfer point that serves a set of demand points is sought. Both minisum and minimax versions of the models are investigated. In follow up papers we investigate the general model using the results obtained in this paper.     

The capacitated p-hub median problem with integral constraints: An application to a Chinese air cargo network

Consolidation at hubs in a pure hub-and-spoke network eliminates partial center-to-center direct loads, resulting in savings in transportation costs. In this research, we propose a general capacitated p-hub median model, with economies of scale and integral constraints on the paths. This model requires the selection of a specific p among a set of candidate hubs so that the total cost on the resulting pure capacitated hub-and-spoke network is minimized while simultaneously meeting origin–destination demands, operational capacity and singular path constraints. We explored the problem structure and developed a genetic algorithm using the path for encoding. This algorithm is capable of determining local optimality within less than 0.1% of the Lagrangian relaxation lower bounds on our Chinese air cargo network testing case and has reasonable computational times. The study showed that designating airports with high pickups or deliveries as hubs resulted in a high percentage of origin–destination pairs (ODs) in direct deliveries. Furthermore, the more hubs there are, the higher the direct share and the less likely for double rehandles. Sensitivity analysis on the discount rate showed that the economies of scale on trunk lines of hub-and-spoke networks may have a substantial impact on both the operating costs and the route patterns.     

On the exponential cardinality of FDS for the ordered p-median problem

We study finite dominating sets (FDS) for the ordered median problem. This kind of problems allows to deal simultaneously with a large number of models. We show that there is no valid polynomial size FDS for the general multifacility version of this problem even on path networks.     

The capacitated single-allocation hub location problem revisited: A note on a classical formulation

In this paper a well-known formulation for the capacitated single-allocation hub location problem is revisited. An example is presented showing that for some instances this formulation is incomplete. The reasons for the incompleteness are identified leading to the inclusion of an additional set of constraints. Computational experiments are performed showing that the new constraints also help to decrease the computational time required to solve the problem optimally.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

An exact solution procedure for a cluster hub location problem

This paper proposes a new (MIP) model formulation and a new solution procedure for the hub network design problem under a non-restrictive policy introduced by Sung and Jin [Sung, C.S., Jin, H.W., 2001. Dual-based approach for a hub network design problem under non-restrictive policy. European Journal of Operational Research 132 (1), 88–105]. The model formulation contains significantly fewer variables so that optimal solutions for the LP-relaxation of the model can be determined for large instances using standard procedures for LP-models. Furthermore, the LP-relaxation provides very tight lower bounds. Computational results are given, which demonstrate that the new model formulation allows for solving much larger instances. It turned out that the new (exact) solution procedure, which utilises the new model formulation, is faster than the heuristic proposed by Sung and Jin (2001). It is also shown that the problem is np-hard.     

The p-median problem under uncertainty

Consider the need to currently locate p facilities but it is possible that up to q additional facilities will have to be located in the future. There are known probabilities that 0 ? r ? q facilities will need to be located. The p-median problem under uncertainty is to find the location of p facilities such that the expected value of the objective function in the future is minimized. The problem is formulated on a graph, properties of it are proven, an integer programming formulation is constructed, and heuristic algorithms are suggested for its solution. The heuristic algorithms are modified to reduce the run time by about two orders of magnitude with minimal effect on the quality of the solution. Optimal solutions for many problems are found effectively by CPLEX. Computational results using the heuristic algorithms are presented.     

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.     

Lagrangean duals and exact solution to the capacitated p-center problem

In this work, we address the capacitated p-center problem (CpCP). We study two auxiliary problems, discuss their relation to CpCP, and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly CpCP, based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.     

A linear program for the two-hub location problem

This paper considers the discrete two-hub location problem. We need to choose two hubs from a set of nodes. The remaining nodes are to be connected to one of the two hubs which act as switching points for internodal flows. A configuration which minimizes the total flow cost needs to be found. We show that the problem can be solved in polynomial time when the hub locations are fixed. Since there are at most ways to choose the hub locations, the two-hub location problem can be solved in polynomial time. We transform the quadratic 0–1 integer program of the single allocation problem in the fixed two-hub system into a linear program and show that all extreme points of the polytope defined by the LP are integral. Also, the problem can be transformed into a minimum cut problem which can be solved efficiently by any polynomial time algorithm.