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

Abstract

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.