Font Size: a A A

Applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems

Posted on:2009-09-12Degree:Ph.DType:Dissertation
University:University of Maryland, College ParkCandidate:Wang, XiaFull Text:PDF
GTID:1440390002990473Subject:Operations Research
Abstract/Summary:
Combinatorial 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.
Keywords/Search Tags:Problem, Programming, Genetic algorithms, Dynamic, Optimization, Applications, Linear, Solve
Related items