A study of network location problems

One of the most important branches of logistics management is to investigate where to locate facilities in a given network so as to minimize the total cost of satisfying demands. This thesis focuses on studying the network location problems as follows: Demand points with certainty are taken to be at the nodes of the network, and to be served by their own nearest facilities, which are to be located anywhere in the given network. The objective is to locate a given number of facilities to minimize the ordered median function (OMf). The organization of this thesis is as follows:;Chapter 1 introduces a taxonomy of location problems and the definition of the ordered median problems (OMP), and describes two methodologies applied in this thesis. Chapter 2 presents a literature review of the network location models.;Chapter 3 deals with the multi-facility OMP in undirected networks, in which multiple point-shaped facilities are to be located. In this chapter we first characterize a finite dominating set (FDS) for a special convex OMP in general networks, which generalizes some previous results. Then, based on the FDS result, we are the first time to solve the problem confined to tree networks in polynomial time.;Chapter 4 is devoted to the multi-facility OMP in a strongly connected directed network. We first prove that the OMP has an FDS in the node set, extending the FDS result provided by Kalcsics et al. (2002), then show that the OMP can be solved efficiently based on the FDS result when the number of facilities is small, and present a 6⅔-approximation algorithm for the p-median problem for the large scale case.;Chapter 5 focuses on the OMP in networks, in which the facilities to locate are tree-shaped. We first prove the nestedness property for a special convex OMP in tree network, which extends some classical results concerning the nestedness property, then solve the problem in polynomial time, and finally provide one counter example to show that the nestedness property does not hold for the non-convex case.;Chapter 6 concludes the major findings of the thesis and suggests some directions for future research.