Full metadata record
DC FieldValueLanguage
dc.contributor.author徐嘉駿en_US
dc.contributor.authorHsu, Chia-Chunen_US
dc.contributor.author卓訓榮en_US
dc.contributor.author方述誠en_US
dc.contributor.authorCho, Hsun-Jungen_US
dc.contributor.authorFang, Shu-Cherngen_US
dc.date.accessioned2015-11-26T00:55:29Z-
dc.date.available2015-11-26T00:55:29Z-
dc.date.issued2014en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT079432511en_US
dc.identifier.urihttp://hdl.handle.net/11536/125809-
dc.description.abstractOptimization 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.zh_TW
dc.description.abstractOptimization 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.en_US
dc.language.isoen_USen_US
dc.subject路段不相交路徑zh_TW
dc.subject基因演算法zh_TW
dc.subject光路徑和光波長指派問題zh_TW
dc.subjectEdge-Disjoint Pathsen_US
dc.subjectGenetic Algorithmen_US
dc.subjectRouting and Wavelength Assignmenten_US
dc.title以基因演算法求解最大化路段不相交路徑問題與光路徑和光波長指派問題zh_TW
dc.titleA Genetic Algorithm for Maximum Edge-Disjoint Paths Problem and Its Extension to Routing and Wavelength Assignment Problemen_US
dc.typeThesisen_US
dc.contributor.department運輸與物流管理學系zh_TW
Appears in Collections:Thesis