Optimizing Method Using the Network Structure in Two-objective Network Design Problem  

Oleh:

Takahashi, Natsumi ; Akiba, Tomoaki ; Yamamoto, Hisashi ; Shingyochi, Koji

Jenis: Article from Proceeding
Dalam koleksi: The 14th Asia Pacific Industrial Engineering and Management Systems Conference (APIEMS), 3-6 December 2013 Cebu, Philippines, page 1-9.
Topik: Network design proplem; Multi-objective optimization; Pareto solutions; Algorithm
Fulltext: 1047.pdf (432.61KB)

Isi artikel

There are many network systems in the world, for example, Internet, electricity network, telephone network and traffic network, etc. In this study, we consider two-objective network design problem with all-terminal reliability and construction/operational cost. These measures are important for evaluating network systems. However, in the general, there exists a trade-off between reliability and construction/operational cost, so it is a rare case that a solution (network system) makes both of all-terminal reliability and construction/operational cost optimal simultaneously. Therefore, the purpose of this study is to construct an algorithm for obtaining Pareto solutions efficiently. The reliability and cost problems for the network systems have been studied in a long period, and the numerous papers have been published. However, even if an algorithm for calculating all-terminal reliability for a network is efficient, existing algorithms for Pareto solutions are inefficient as we must calculate all-terminal reliabilities of all sub-networks. So, it takes much time to obtain Pareto solutions when the number of nodes and edges is large. For an efficient algorithm, we research the difference between the optimal networks, which become Pareto solutions, and the other networks. For instance, we researched relations between edges which tend to compose Pareto solutions and the other edges. By using such relations, we constituted the searching space in which sub-networks take close values to Pareto solutions. Based on the above, we propose a new algorithm for obtaining the subset of Pareto solutions. Finally, we evaluate our proposed algorithm in terms of precision and efficiency by numerical experiments, and the results of our numerical experiments show our proposed algorithm is efficient for the subset of Pareto solutions.

Opini Anda

Klik untuk menuliskan opini Anda tentang koleksi ini!

Kembali