Applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems | Posted on:2009-09-12 | Degree:Ph.D | Type:Dissertation | University:University of Maryland, College Park | Candidate:Wang, Xia | Full Text:PDF | GTID:1440390002990473 | Subject: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 |
| |
|