Research On New Models Of Star Hub Location Problems

In transportation, postal and telecommunication networks, hubs are special facilitiesthat play an important role as switching, transshipment and sorting points. Hub locationproblems deal with locating hub facilities and allocating demand nodes to hubs so as toroute the trafc between origin-destination pairs. This paper focuses on the related prob-lems that the hub network is a star. First, we are concerned the case p=2of the starp-hub location problem in general networks, i.e., Star2-hub Median Problem and Star2-hub Center Problem. The former aims to minimize the total cost of the resulting net-work, and the latter aims to minimize the maximum distance of the path connecting anypair of distinct demand nodes. We design a polynomial time exact algorithm for them, re-spectively. Moreover, we perform our algorithms on a small instance. Then we study twogrouped star p-hub location problems. The aim of the first problem, called the GroupedStar p-hub Median Problem, is to find exactly one hub node from every group to minimizethe total routing cost. We devise a quadratic time exact algorithm for this problem. Theaim of the second problem, called the Grouped Star p-hub Center Problem, is to find ex-actly one hub node from every group to minimize the longest weighted distance betweendemand nodes. We give an O(np+2pp)-time exact algorithm for this problem. Moreover, weconsider the special case of the second problem with no trafc-amount input and designa cubic time exact algorithm. Finally, we present the results of a number of numericalexperiments on the well-known AP data set.The rest of this paper is organized as follows. In Chapter1, the introduction isgiven including the background and some existing results of the hub location problems,the definition of the p-hub tree and the new models of the star hub location problems.In Chapter2, we study Star2-hub Median Problem and Star2-hub Center Problem. InChapter3, we study Grouped Star p-hub Median Problem, Grouped Star p-hub CenterProblem. In Chapter4, we make a large number of numerical experiments to testify ouralgorithms. In Chapter5, we conclude the paper with some future research topics.