博士 / 國立臺灣大學 / 資訊管理研究所 / 89 / Fast evolving computer network technologies have enabled the new communication and way of life. In addition, new logistic network concept (such as supply chain network) could decrease the business transaction cost. As a result, different types of networks have widely been installed and operated. However, how to efficiently allocate the resource to satisfy the users’ quality-of-service is a difficult and important issue. In this dissertation, solution procedures based on rigorous mathematical programming and Lagrangean relaxation are proposed to solve a series of network planning and capacity management problems for computer and logistic networks. In computer networks, we consider the lightpath routing and wavelength assignment in WDM networks, access network design, backbone network design, operational support for in-service network. In logistic networks, the network planning for service network and supply chain network are addressed.
By using the WDM technique, we could multiplex more than one hundred wavelengths on a single fiber, such that the bandwidth could be increased enormously. However, under the constraint of wavelength continuity, it is difficult to perform lightpath routing and wavelength assignment on each fiber efficiently. We solve this problem by Lagrangean relaxation technique in conjunction with several optimization-based algorithms. From the computational experiment, we could obtain good solution quality for network size up to 26 nodes in minutes of computational time. In access network design, we consider the network design problem with the shared tree topology. The difficulty of this work lies in the multicast traffic, which will lead to the Steiner Tree problem. By using the sophisticated problem formulation, we could solve this problem without the necessity of solving Steiner Tree problem. The optimization-based algorithms that we propose could provide near-optimal solutions to this problem for network size up to 26 nodes in minutes of computational time. In backbone network design, we consider the design problem with the system and user specified QoS requirements. The objective is to minimize the installation cost for transmission links and network switching nodes. The system specified QoS considered in this work is the average delay requirement, and the user specified QoS include the end-to-end delay requirement and the k node disjoint path survivability requirement. The difficulty of this work lies in the integer and non-convexity mathematical structure. Algorithms based on Lagrangean relaxation and add-drop heuristic could provide efficient and effective solutions to the backbone network design problem. For any in-service network, daily increasing traffic demand will cause the inferior QoS perceived by the users; two approaches -- rerouting and sizing, are proposed to address this issue. For rerouting, we consider the optimization problem to address the system optimization and user fairness issue at the same time where the objective is to minimize the system (average) delay with the user specified end-to-end delay requirement. For sizing, we consider the optimization problem to minimize the network link capacity installation cost with the system (average) delay and users’ end-to-end delay requirement. Besides integrality constraints, the nonconvexity and concavity mathematical structure makes this problem difficult. Lagrangean relaxation in conjunction with a number of getting primal heuristics are proposed to address these two problems. By accessing the solution quality to the rerouting problem, we could provide near-optimal solutions to this problem for network size up to 26 nodes in minutes of computational time. In addition, by accessing the solution quality to the sizing problem, we propose efficient and effective optimization-based algorithms to solve this problem.
In service network design, we consider the location and capacity management problems of service centers. Capacity constraint and response time constraint make this problem more difficult than traditional location problem. Optimization-based algorithms based on Lagrangean relaxation could provide efficient and effective solutions to this problem for network size up to 350 nodes in minutes of computational time. In supply chain network design, besides capacitated location problem of distribution center, routing problems of transmission vehicles are considered. This problem is formulated as integer programming problem. Optimization-based algorithms based on Lagrangean relaxation could provide efficient and effective solutions to this problem.
| Identifer | oai:union.ndltd.org:TW/089NTU00396006 |
| Date | January 2001 |
| Creators | Hong-Hsu Yen, 顏宏旭 |
| Contributors | Yeong-Sung Lin, 林永松 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | en_US |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 132 |
Page generated in 0.0015 seconds