| This thesis studies two network design problems. The first problem is a districting problem while the second problem is for dealing with uncapacitated multi-commodity flow.; In some service-providing companies, such as vehicle breakdown service or emergency service, they have to provide on-site service in a reasonably short time. A typical way to achieve this is to zone the area into a certain number of districts. Each district is served by a mobile unit. Wherever location in the district needs service, the mobile unit should reach there within a reasonable short time and the mobile unit cannot go out of the district. The objective of solving the problem is to minimize the number of mobile units needed. We prove that the problem is NP-complete. We also develop an exact algorithm which is based on the algorithm of Peemöller for graph coloring. We also develop a ‘set-covering’-based heuristic algorithm. We compare the efficiency and accuracy of the two algorithms computationally.; Multi-commodity flow problems have lots of applications, especially in telecommunication and physical distribution. In this thesis, we concentrate on the uncapacitated multi-commodity network design problem with zero flow cost. Consider an undirected graph, in which we need to send k commodities from their source vertices to their sink vertices. To achieve this, we need to purchase some edges so that flows can pass through these edges. The objective is to minimize the purchasing cost such that each commodity can be sent from its source to its sink. Sastry [2001] has developed an O( n2) algorithm to solve optimality 2-commodity network design problem. Expending on Sastry's idea, we develop an O( n2) algorithm for the 3-commodity problem. Similarly, we show that the 4-commodity problem can be solved in O( n2). Finally, we generalized the idea to the K-commodity problem. For each K, the algorithm depends on identifying a list of ‘basic patterns’; the number of basic pattern grows exponentially in K. Thus, the K-commodity network design problem can be solved in O(n2) if K is fixed, otherwise, the time for solving the problem is exponential. |
