Show simple item record

Applications of Genetic Algorithms, Dynamic Programming, and Linear Programming to Combinatorial Optimization Problems

dc.contributor.advisorGolden, Bruce L.en_US
dc.contributor.authorWang, Xiaen_US
dc.date.accessioned2009-01-24T06:45:24Z
dc.date.available2009-01-24T06:45:24Z
dc.date.issued2008-10-16en_US
dc.identifier.urihttp://hdl.handle.net/1903/8778
dc.description.abstractCombinatorial optimization problems are important in operations research and computer science. They include specific, well-known problems such as the bin packing problem, sequencing and scheduling problems, and location and network design problems. Each of these problems has a wide variety of real-world applications. In addition, most of these problems are inherently difficult to solve, as they are NP-hard. No polynomial-time algorithm currently exists for solving them to optimality. Therefore, we are interested in developing high-quality heuristics that find near-optimal solutions in a reasonable amount of computing time. In this dissertation, we focus on applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems. We apply a genetic algorithm to solve the generalized orienteering problem. We use a combination of genetic algorithms and linear program to solve the concave cost supply scheduling problem, the controlled tabular adjustment problem, and the two-stage transportation problem. Our heuristics are simple in structure and produce high-quality solutions in a reasonable amount of computing time. Finally, we apply a dynamic programming-based heuristic to solve the shortest pickup planning tour problem with time windows.en_US
dc.format.extent1483792 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleApplications of Genetic Algorithms, Dynamic Programming, and Linear Programming to Combinatorial Optimization Problemsen_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.departmentMathematicsen_US
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pqcontrolledMathematicsen_US
dc.subject.pquncontrolledGenetic Algorithmen_US
dc.subject.pquncontrolledLinear Programmingen_US
dc.subject.pquncontrolledDynamic Programmingen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record