Show simple item record

dc.contributor.advisorRaghavan, Subramanianen_US
dc.contributor.authorStanojevic, Daliborkaen_US
dc.date.accessioned2006-02-04T07:31:33Z
dc.date.available2006-02-04T07:31:33Z
dc.date.issued2005-12-05en_US
dc.identifier.urihttp://hdl.handle.net/1903/3194
dc.description.abstractWe present a study of two NP-hard telecommunications network design problems - the prize-collecting generalized minimum spanning tree problem (PCGMST) and the design of optical networks with wavelength division multiplexing. The first problem, the PCGMST problem, involves the design of regional backbone networks, where a set of local area networks (LANs) need to be connected by a minimum cost tree network using exactly one gateway site from each LAN. We present several polynomial time heuristics for the PCGMST problem and show that these algorithms, at best, provide only modest quality solutions. We also present two metaheuristics - a local search procedure and a genetic algorithm, and show that these procedures provide compelling high-quality results on a large set of test problems. Our study of the PCGMST problem is concluded by a presentation of two exact solution procedures that can be used to find optimal solutions in networks of moderate size. The second problem studied in this dissertation is a more complex network design problem that involves optical networks with wavelength division multiplexing (WDM). These networks provide an abundance of transmission bandwidth, but require the use of expensive equipment, which, in turn, mandates careful use of the resources available for their design. The novel aspect of WDM optical networks is that they require simultaneous design of two network layers. The first layer is the virtual topology that requires routing of logical paths over the physical layer of optical fibers. The second layer involves routing and grooming of traffic requests over the logical paths established in the virtual topology. This problem has been extensively studied in the last 10 years, but due to its notoriously hard nature, only few exact solution procedures for relaxed versions of this problem were developed so far. We propose one exact and two approximate branch-and-price algorithms for two versions of the WDM optical network design problem and present results of the computational study involving two different design objectives. Finally, we propose two classes of valid inequalities for our branch-and-price algorithms, and discuss applicability of our algorithms to different versions of the WDM optical network design problem.en_US
dc.format.extent798749 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleOptimization of Contemporary Telecommunications Networks: Generalized Spanning Trees and WDM Optical Networksen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentDecision and Information Technologiesen_US
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pquncontrolledtelecommunications networksen_US
dc.subject.pquncontrollednetwork designen_US
dc.subject.pquncontrolledgeneralized minimum spanning treesen_US
dc.subject.pquncontrolledWDM optical networksen_US
dc.subject.pquncontrolledmetaheuristicsen_US
dc.subject.pquncontrolledbranch-and-priceen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record