| This dissertation focuses mainly on facility location problems on networks with multiple types of facilities and multiple types of customers. There has been limited research on these problems in the literature.; Chapter 2 focuses on the minisum Collection Depots Location problem. In this problem, a server has to visit the node requesting service as well as one of several collection depots. We prove that there exists a dominating location set for the problem on a general network. The properties of the solution on some simple network topologies are discussed. To solve the problem on a general network, we suggest a Lagrangian Relaxation embedded in a branch-and-bound algorithm.; In Chapter 3, we discuss the minisum multi-purpose trip location problem with two types of facilities and three types of customers. For example, in the setting of simultaneously locating apparel and hardware stores, we can classify customers into three groups. The first type of customers only need to buy clothes, the second type of customers only need to buy hardware, and the third type of customers need to buy both apparel and hardware items. Therefore, the first two types of customers only need one type of service, while the third one needs both types of services in a single trip. The objective is to minimize the total weighted travel distance of all trips. For this minisum problem, we prove that there exists a dominating location set on a general network. The properties of optimal solutions on networks with simple topologies are also analyzed.; In Chapter 4, we study the problem having the same setting as above, but with the objective of maximizing coverage. First, we formulate the problem as a linear integer program. Then, we propose a method which often produces a tighter bound than the LP relaxation of the linear integer program. For the simplified problem on a path, we solve the problem in polynomial time through applying a dynamic programming algorithm.; In Chapter 5, we consider a location problem with single-type facilities. The objective is to locate undesirable facilities on a network so as to minimize the total demand covered subject to the requirement that no two facilities are allowed to be closer than a pre-specified distance. We prove that there exists a dominating location set and that it is a challenging problem to determine the consistency of the distance constraints. We compare several different mathematical formulations to solve the problem. |
