With the rapid growth of international logistics market, one of the most important research issues is designing a large-scale distribution network. The question of large-scale distribution network design is also becoming central to globalization supply chain management. Distribution network design can be considered as two parts: locating manufacturing plants and distribution centers, and determine the best strategy for communications between manufacturing plants and distribution centers. In general, the location and network design problems have become more important and have been studied extensively during the last decade. In order to deal with different real-world applications in which the constraints and requirements appear in different scenarios, these problems can be formulated in various ways.
We study capacitated facility location in large-scale networks and its application to distribution network design. In a distribution network, each distribution center or client has associated with a demand, and each plant or facility has a capacity that specifies the maximum service the plant can provide to its distribution centers. Our aim is to select a subset of plants such that the demand requirement of each distribution center is satisfied, the plants capacities are not violated, and the total cost, including plant operating cost and service cost, which is usually based on the metric distance between plants and distribution centers, is minimized. The key challenge is that the computational complexity grows exponentially in the network size. Thus the concept of graph-based algorithms may be generalized to utility network design in location problems. We have considered the similar capacitated domination problem and presented a linear time algorithm for the unsplittable demand model. For the splittable demand model in trees, we show it is NP-complete even when the vertex capacity and demand are integers. Furthermore, based on our NP-completeness reduction, we develop a pseudo-polynomial time algorithm and further a combinatorial polynomial time approximation scheme (PTAS) for splittable demand model in trees. We also give a primal-dual approximation algorithm for weighted capacitated domination problem with splittable demand constraints in general graphs [1]. In addition, another k-tuple domination problem, that is, to find a minimum vertex subset such that every vertex in the graph is dominated by at least k vertices in this set, which has been investigated [2, 3] is also similar to the capacitated domination problem with k-splittable uniform demand model.
Comparison with most of the previous studies of small-scale networks, we would like to explore the large-scale distribution network design problem and find fast and provably accurate approximation algorithms. In addition, we also want to build a graphical user interface of capacitated facility location selection for the public and the proposed system will demonstrate its practical usefulness.
1. Mong-Jen Kao, Chung-Shou Liao, and D. T. Lee. Capacitated domination problem, Algorithmica, Vol. 60, Issue 2 (2011) pp. 274-300.
2. Chung-Shou Liao and G. J. Chang. k-Tuple domination in graphs, Inform. Process. Letters Vol 87, (2003) pp. 45-50.
3. Chung-Shou Liao and G. J. Chang. Algorithmic aspect of k-tuple domination in graphs, Taiwanese Journal of Math. Vol 6, No. 3 (2002) pp.415-420.