Title The Solution Algorithm for Network Design
Year 2018
Degree Master
School Department of Transportation and Logistics Management National Chiao Tung University
Author
Summary Bi-level network design problem can be formulated as a nonlinear optimization problems with variational inequality (VI) constraints. It’s a mathematical programming problem with equilibrium constraints, which belongs to the Stackelberg game. The solution process must have reaction function of follower to the leader. But, it’s difficult to find the reaction function in the network. Cho (1988) used a first-order Taylor expansion to approximate the reaction function. The coefficient value was obtained by network sensitivity analysis. Tobin and Friesz (1988) relaxed Tobin (1986) VI sensitivity analysis condition. The solution must be unique. They used linear programming to solve a non- degenerate path flow solution such that sensitivity analysis can be applied to the network, but the non-degenerate conditions are too stringent. The general network can’t be directly applied. Cho et al. (2000) proposed the reduction method and relaxed non-degenerate condition. The method converts path-flow solution set to link-flow solution set and avoid the situation that the path-flow was not unique. This study discusses the limitations of the three sensitivity analysis methods by Tobin (1986), Tobin and Friesz (1988) and Cho et al.(2000), and the sensitivity analysis used the Tobin and Friesz (1988) method but doesn’t meet the conditions of the example. We apply the method of Cho (1988)(2000) to these examples that are not available for Tobin and Friesz.
The sensitivity information of this study is applied to bi-level network design problem. In the past, network design problem was solved by using Tobin and Friesz (1988) sensitivity analysis, but it was limited to the small network. Friesz et al. (1990) pointed out that Jacobian maybe encountered as a singular matrix while the network is large, so that the initial solution maybe an non-differentiable point. In this study, the first-order Taylor expansion equation is used to approximate the reaction function according to Cho (1988), and it is obtained by the sensitivity analysis of Cho et al. (2000). The reaction function coefficient avoids non-differentiable problem that the large network may not be able to obtain the sensitivity information, and quotes the different examples in the network design literature of Friesz et al. (1990), as well as the solution to the method of its use. This study adds a linear approximation method and observes difference solutions. We find the solution obtained by the linear approximation method is better than other methods when the number of link increases. Finally, this study applies the linear approximation method to a large network with 76 link and 552 OD. The process of solving the sensitivity information cannot encounter non-differentiate problem, and the solution obtained by LA is better than other method in the literature.
Hashtags
View count: 149