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.     

Hub location for time definite transportation

Time definite motor carriers provide very reliable scheduled truck transportation service between specified terminals. They provide service competitive with airfreight carriers over continental-scale distances at a much lower cost. This paper provides time definite models for multiple allocation p-hub median problems and hub arc location problems. Service levels are imposed by limiting the maximum travel distance via the hub network for each origin–destination pair. Computational results are presented to demonstrate the effects of the time definite service levels on practical network design for truck transportation in North America.     

Hub location problems: A review of models,classification, solution techniques,and applications

Hub location problem (HLP) is a relatively new extension of classical facility location problems. Hubs are facilities that work as consolidation, connecting, and switching points for flows between stipulated origins and destinations. While there are few review papers on hub location problems, the most recent one (Alumur and Kara, 2008. Network hub location problems: The state of the art. European Journal of Operational Research, 190, 1–21) considers solely studies on network-type hub location models prior to early 2007. Therefore, this paper focuses on reviewing the most recent advances in HLP from 2007 up to now. In this paper, a review of all variants of HLPs (i.e., network, continuous, and discrete HLPs) is provided. In particular, mathematical models, solution methods, main specifications, and applications of HLPs are discussed. Furthermore, some case studies illustrating real-world applications of HLPs are briefly introduced. At the end, future research directions and trends will be presented.     

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.     

A 2-phase algorithm for solving the single allocation p-hub center problem

The single allocation p-hub center problem is an NP-hard location–allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin–destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.     

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.     

Single-allocation ordered median hub location problems

The discrete ordered median location model is a powerful tool in modeling classic and alternative location problems that have been applied with success to a large variety of discrete location problems. Nevertheless, although hub location models have been analyzed from the sum, maximum and coverage point of views, as far as we know, they have never been considered under an alternative unifying point of view. In this paper we consider new formulations, based on the ordered median objective function, for hub location problems with new distribution patterns induced by the different users’ roles within the supply chain network. This approach introduces some penalty factors associated with the position of an allocation cost with respect to the sorted sequence of these costs. First we present basic formulations for this problem, and then develop stronger formulations by exploiting properties of the model. The performance of all these formulations is compared by means of a computational analysis.     

Single-input/single-output transfer functions for a flexible slewing link

Truncated linear models based on constrained and unconstrained mode expansions for a flexible link with torque actuation at its hub led us to examine the behavior of the open-loop-zeros of five commonly used single-input single-output transfer functions. We arrive at new conclusions with regard to minimum- and non-minimum-phase zeros, and passivity of the transfer functions. The flexible-to-rigid inertia (FRI) ratio plays an important role in the determination of these characteristics. This article illustrates how the zero locations of some of the transfer functions are dramatically affected by the FRI ratio. We also investigate the performance of a hub angle, hub rate, and relative tip position static feedback controller based on a reduced-order constrained mode model when applied to both unconstrained and constrained mode models of the same dimension. Simulations indicate that the constrained model can be stable while the unconstrained model is not for high FRI ratios. Our findings can provide useful information to designers in cases where the controller is sensitive to the location of the plant's zeros.     

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.     

The Hub Number of Sierpiński-Like Graphs

A set Q⊆V is a hub set of a graph G=(V,E) if, for every pair of vertices u,v∈V∖Q, there exists a path from u to v such that all intermediate vertices are in Q. The hub number of G is the minimum size of a hub set in G. This paper derives the hub numbers of Sierpiński-like graphs including: Sierpiński graphs, extended Sierpiński graphs, and Sierpiński gasket graphs. Meanwhile, the corresponding minimum hub sets are also obtained.     

多分配枢纽站集覆盖问题的随机p- 鲁棒优化模型及算法

枢纽站选址是轴辐式网络优化设计的重要问题,枢纽站覆盖则是该问题的一个类型.考虑枢纽站建站成本和节点间运输距离的不确定性,结合随机优化和鲁棒优化方法,建立了完备轴辐式网络中多分配枢纽站集覆盖问题的随机-鲁棒优化模型;采用二进制编码,对量子粒子群算法进行改进,加入免疫思想,设计了免疫量子粒子群求解算法.最后通过算例对模型进行仿真计算,结果表明了该模型及算法的可行性和有效性.     

Exact optimal solutions of the minisum facility and transfer points location problems on a network

We consider hierarchical facility location problems on a network called Multiple Location of Transfer Points (MLTP) and Facility and Transfer Points Location Problem (FTPLP), where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p‐median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration‐based approach to solve the problems with a single facility.     

Solving the uncapacitated hub location problem using genetic algorithms

Hub location problems are widely studied in the area of location theory, where they involve locating the hub facilities and designing the hub networks. In this paper, we present a new and robust solution based on a genetic search framework for the uncapacitated single allocation hub location problem (USAHLP). To present its effectiveness, we compare the solutions of our GA-based method with the best solutions presented in the literature by considering various problem sizes of the CAB data set and the AP data set. The experimental work demonstrates that even for larger problems the results of our method significantly surpass those of the related work with respect to both solution quality and the CPU time to obtain a solution. Specifically, the results from our method match the optimal solutions found in the literature for all test cases generated from the CAB data set with significantly less running time than the related work. For the AP data set, our solutions match the best solutions of the reference study with an average of 8 times less running time than the reference study. Its performance, robustness and substantially low computational effort justify the potential of our method for solving larger problem sizes.     

A two‐stage hub location method for air transportation in Brazil

During the past decade, the Brazilian air passenger market has been growing at impressive rates suggesting the need for rationalization and the consistent use of the hub‐and‐spoke configuration. This research considers 135 airports, mostly extremely small, and the aim is to identify regional hubs that would accumulate traffic and feed a predefined restricted number of major hubs. The proposed approach is divided into two phases: the first phase considers all 135 existing commercial airports and using the p‐median problem identifies p airports that would play the role of regional hubs, and the second phase considers a problem with these p airports and solves the q‐hub location problem. Both phases are sequentially solved by the software AIMMS 3.9. The research has broad implications consistent with the publicized efforts to improve management practices, support a larger number of commercial airports, and face the expected peak demand in the upcoming international events. Given the growth in the air passenger market in Brazil, both phases may be seen as two independent objectives.     

Airline network design and hub location problems

Due to the popularity of hub-and-spoke networks in the airline and telecommunication industries, there has been a growing interest in hub location problems and related routing policies. In this paper, we introduce flow-based models for designing capacitated networks and routing policies. No a priori hub-and-spoke structure is assumed. The resulting networks may suggest the presence of “hubs”, if cost efficient. The network design problem is concerned with the operation of a single airline with a fixed share of the market. We present three basic integer linear programming models, each corresponding to a different service policy. Due to the difficulty of solving (even small) instances of these problems to optimality, we propose heuristic schemes based on mathematical programming. The procedure is applied and analyzed on several test problems consisting of up to 39 U.S. cities. We provide comments and partial recommendations on the use of hubs in the resulting network structures.     

Detecting False Matches in String-Matching Algorithms

Consider a text string of length n, a pattern string of length m, and a match vector of length n which declares each location in the text to be either a mismatch (the pattern does not occur beginning at that location in the text) or a potential match (the pattern may occur beginning at that location in the text). Some of the potential matches could be false, i.e., the pattern may not occur beginning at some location in the text declared to be a potential match. We investigate the complexity of two problems in this context, namely, checking if there is any false match, and identifying all the false matches in the match vector. We present an algorithm on the CRCW PRAM that checks if there exists a false match in O(1) time using O(n) processors. This algorithm does not require preprocessing the pattern. Therefore, checking for false matches is provably simpler than string matching since string matching takes time on the CRCW PRAM. We use this simple algorithm to convert the Karp—Rabin Monte Carlo type string-matching algorithm into a Las Vegas type algorithm without asymptotic loss in complexity. We also present an efficient algorithm for identifying all the false matches and, as a consequence, show that string-matching algorithms take time even given the flexibility to output a few false matches. Received January 28, 1995; revised January 17, 1996.     

A quadtree-based allocation method for a class of large discrete Euclidean location problems

A special data compression approach using a quadtree-based method is proposed for allocating very large demand points to their nearest facilities while eliminating aggregation error. This allocation procedure is shown to be extremely effective when solving very large facility location problems in the Euclidian space. Our method basically aggregates demand points where it eliminates aggregation-based allocation error, and disaggregates them if necessary. The method is assessed first on the allocation problems and then embedded into the search for solving a class of discrete facility location problems namely the p-median and the vertex p-center problems. We use randomly generated and TSP datasets for testing our method. The results of the experiments show that the quadtree-based approach is very effective in reducing the computing time for this class of location problems.     

Aggregation method experimentation for large-scale network location problems

We present demand point aggregation procedures for the p-median and p-center network location models. A coarse aggregation structure is initially obtained by partitioning the demand points according to a grid imposed over the demand region. A “row-column’’ aggregation algorithm is used to determine the spacing of rows and columns of the grid to exploit the problem structure. A second step involves locating aggregate demand points on the subnetworks induced by the cells of the grid partitioning. The aggregate demand point set so obtained then defines an approximating location model; alternatively, it may initialize an iterative network location–allocation procedure to find the aggregate demand points. We have tested our procedures on data sets based on maps from the TIGER/Line database of the United States Census Bureau, and report on our computational experience.     

Some q-rung orthopair uncertain linguistic aggregation operators and their application to multiple attribute group decision making

q-Rung orthopair fuzzy sets (q-ROFSs), originally presented by Yager, are a powerful fuzzy information representation model, which generalize the classical intuitionistic fuzzy sets and Pythagorean fuzzy sets and provide more freedom and choice for decision makers (DMs) by allowing the sum of the $q\mathrm{t}\mathrm{h}$ power of the membership and the $q\mathrm{t}\mathrm{h}$ power of the nonmembership to be less than or equal to 1. In this paper, a new class of fuzzy sets called q-rung orthopair uncertain linguistic sets (q-ROULSs) based on the q-ROFSs and uncertain linguistic variables (ULVs) is proposed, and this can describe the qualitative assessment of DMs and provide them more freedom in reflecting their belief about allowable membership grades. On the basis of the proposed operational rules and comparison method of q-ROULSs, several q-rung orthopair uncertain linguistic aggregation operators are developed, including the q-rung orthopair uncertain linguistic weighted arithmetic average operator, the q-rung orthopair uncertain linguistic ordered weighted average operator, the q-rung orthopair uncertain linguistic hybrid weighted average operator, the q-rung orthopair uncertain linguistic weighted geometric average operator, the q-rung orthopair uncertain linguistic ordered weighted geometric operator, and the q-rung orthopair uncertain linguistic hybrid weighted geometric operator. Then, some desirable properties and special cases of these new operators are also investigated and studied, in particular, some existing intuitionistic fuzzy aggregation operators and Pythagorean fuzzy aggregation operators are proved to be special cases of these new operators. Furthermore, based on these proposed operators, we develop an approach to solve the multiple attribute group decision making problems, in which the evaluation information is expressed as q-rung orthopair ULVs. Finally, we provide several examples to illustrate the specific decision-making steps and explain the validity and feasibility of two methods by comparing with other methods.     

On the logic of preference and judgment aggregation

Agents that must reach agreements with other agents need to reason about how their preferences, judgments, and beliefs might be aggregated with those of others by the social choice mechanisms that govern their interactions. The emerging field of judgment aggregation studies aggregation from a logical perspective, and considers how multiple sets of logical formulae can be aggregated to a single consistent set. As a special case, judgment aggregation can be seen to subsume classical preference aggregation. We present a modal logic that is intended to support reasoning about judgment aggregation scenarios (and hence, as a special case, about preference aggregation): the logical language is interpreted directly in judgment aggregation rules. We present a sound and complete axiomatisation. We show that the logic can express aggregation rules such as majority voting; rule properties such as independence; and results such as the discursive paradox, Arrow’s theorem and Condorcet’s paradox—which are derivable as formal theorems of the logic. The logic is parameterised in such a way that it can be used as a general framework for comparing the logical properties of different types of aggregation—including classical preference aggregation. As a case study we present a logical study of, including a formal proof of, the neutrality lemma, the main ingredient in a well-known proof of Arrow’s theorem.