:::
博碩士論文
論文名稱 | 以基因演算法求解最大化路段不相交路徑問題與光路徑和光波長指派問題 |
---|---|
年別 | 104 |
學位 | 博士 |
學校系所 | 交通大學運輸與物流管理學系 |
作者 | 徐嘉駿 |
指導教授 | 卓訓榮,方述誠 |
論文摘要 | Optimization problems concerning edge-disjoint paths in a given graph have attracted considerable attention for decades. Lots of applications can be found in the areas of call admission control, real-time communication, VLSI (Very-large-scale integration) layout and reconfiguration, packing, etc. The optimization problem that seems to lie in the heart of these problems is the maximum edge-disjoint paths problem (MEDP), which is NP-hard. In this dissertation, we developed a novel genetic algorithm (GA) for handling the problem. The proposed method is compared with the purely random search method, the simple greedy algorithm, the multi-start greedy algorithm, and the ant colony optimization method. The computational results indicate that the proposed GA method performs better in most of the instances in terms of solution quality and time. Moreover, a real-world application of the routing and wavelength assignment problem (RWA), which generalizes MEDP in some aspects, has been performed; and the computational results further confirm the effectiveness of our work. Compared with the bin-packing based algorithms and particle swarm optimization, the proposed method can achieve the best solution on all testing instances. Although it is more time-consuming than the bin-packing based methods, the differences of computational time become small on large instances. |
附件下載 | (電子檔於104-11-13後開放下載) |
檔案下載
- D03246-全文檔.zip下載次數:189
瀏覽人次:400