Air taxis are poised to be an additional mode of transportation in major cities suffering from ground transportation congestion. Among several potential applications of air taxis, we focus on their use within a city to transport passengers to nearby airports. Specifically, we consider the problem of determining optimal locations for skyports (enabling pick-up of passengers to airport) within a city. Our approach is inspired from hub location problems, and our proposed method optimizes for aggregate travel time to multiple airports while satisfying the demand (trips to airports) either via (i) ground transportation to skyport followed by an air taxi to the airport, or (ii) direct ground transportation to the airport. The number of skyports is a constraint, and the decision to go via the skyport versus direct ground transportation is a variable in the optimization problem. Extensive experiments on publicly available airport trips data from New York City (NYC) show the efficacy of our optimization method implemented using Gurobi. In addition, we share insightful results based on the NYC data set on how ground transportation congestion can impact the demand and service efficiency in such skyports; this emerges as yet another factor in deciding the optimal number of skyports and their locations for a given city.
The first mathematical formulations of HLP were proposed by O'Kelly @cite_4 while focusing on a study based on airline passenger networks. In the HLP literature, this formulation is referred to as a single allocation @math -hub median problem. The first linear integer programming formulation of this quadratic model was proposed by Campbell @cite_15 . Various linear models for HLP were later proposed by Ernst and Krishnamoorty @cite_25 , and Skorin Kapov @cite_24 . In addition to selection of hub locations, the allocation of demand is an important decision criterion in HLP. In this context, there are two major allocation strategies for hub location: (i) single allocation where each non hub node (, origin point in a network) is allocated to one hub, and (ii) multiple allocation where O-D flows can be transferred via different pairs of hubs ( @cite_15 @cite_33 @cite_23 ). The hub facilities can be further categorized as uncapacitated (where there is no capacity restriction), and capacitated (where there is a limit to the maximum flow passing through a hub) ( @cite_13 @cite_17 ). Farahani @cite_2 , Alumur and Kara @cite_37 provide brief review and classification of various models and approaches to HLP.
@cite_37 @cite_4 @cite_33 @cite_24 @cite_23 @cite_2 @cite_15 @cite_13 @cite_25 @cite_17
2128361327 2075942607 2015462215 2041867487 2037551729 2013064914 1992790175
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. Abstract This paper reports a new formulation of a general hub location model as a quadratic integer program. Non-convexity of the objective function makes the problem difficult. A variety of alternative solution strategies are discussed. Computational results from two simple heuristics are presented for the task of siting 2, 3 or 4 hubs to serve interactions between sets of 10, 15, 20 and 25 U.S. cities. The effects of different computational shortcuts are examined. Abstract The problem of locating hub facilities and allocating non-hub nodes to those hubs arises frequently in the design of communication networks, airline passenger flow and parcel delivery networks. In this paper we consider uncapacitated multiple and single allocation p -hub median problems. We develop new mixed 0 1 linear formulations with tight linear programming relaxations. The approach is tested on a well known and heavily used benchmark data set of real-world problems with resulting LP relaxations ranging from 10010 to 391 250 variables and from 2 101 to 31 901 constraints, which proved to be difficult linear programs. Yet, this approach proved to be very effective: in almost all instances the linear programming solution was integer. In cases with fractional solutions, the integrality was achieved by adding a small partial set of integrality constraints. Therefore, we extended the range of optimally solvable instances of these NP-hard hub location problems, which have defied researchers for the last ten years. As an additional result for the single allocation case we were able to establish optimality of all heuristic solutions obtained via tabu search algorithm from a previous study. For the more difficult single allocation p -hub median problem we also used the best known heuristic solution as a guidance in adding integrality constraints. This novel linkage between optimal and heuristic solutions has a potential impact in a number of other problem settings, where efficient heuristic solutions exist and are probably, but not provably optimal. 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. Abstract Hubs are facilities that serve as transshipment and switching points for transportation and telecommunication systems with many origins and destinations. This paper present integer programming formulations for four types of discrete hub location problems: the p -hub median problem, the uncapacitated hub location problem, p -hub center problems and hub covering problems. Hub median and uncapacitated hub location problems have received limited attention from researchers. This paper introduces discrete hub center and hub covering problems. Basic formulations and formulations with flow thresholds for spokes are presented. Abstract The main purpose of this paper is to introduce the capacitated hub-and-spoke network design problem in which hubs have limited capacity for channelling flows between the nodes served by the system. The problem is formulated under a networking policy allowing both direct (nonstop) and hub connected (one-hub-stop and two-hub-stop) services between the nodes. A branch and bound algorithm and a heuristic procedure partitioning the set of solutions on the basis of hub locations are presented. In both algorithms, after identifying a set of hub locations, the problem is reduced into a smaller routing problem. Subgradient optimization is then applied to a Lagrangian relaxation of the reduced problem. The model and the proposed algorithms were applied to the air transportation system using data on passenger flows between the top forty US cities in 1989 (accounting for 73.32 of the surveyed passenger flow). Computational results from 141 problems suggest that both algorithms are effective at finding good solutions to this problem. We present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. We develop a good heuristic algorithm for its solution based on simulated annealing (SA). We use the SA upper bound to develop an LP-based branch-and-bound solution method. We present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. We also benchmark our new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.