From Exact Methods to Heuristics

journal article - other

English

In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound method and dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics) that define a general framework for computations and the user must find suitable problem-specific parameter settings and verify them using benchmarks. A genetic algorithm was found to work efficiently in many situations. It provides good results in a reasonable amount of time for hundreds of input parameters and tens of capacity constraints. Finally, we showed that using stochastic heuristics need not be the only way of solving NP-complete problems and proposed approaches based on geometric data structures such as Delaunay triangulation and Voronoi diagrams. They were applied in network optimisation to find a minimal Euclidean Steiner tree and in robotics to plan trajectories of a moving object in a scene with obstacles. While being able to provide good approximations of the optimum, the proposed deterministic heuristics do not require so much tuning as stochastic heuristics and, moreover, they run in a polynomial time. Therefore they are also applicable in real time computation. Using generalised Voronoi diagrams gives an efficient tool for robot motion planning and generates smooth trajectories in a scene with movable obstacles.

optimisation, NP-hard problems, heuristic methods, genetic algorithm, scheduling, robotics, computational geometry, Voronoi diagram, Delaunay triangulation

ŠEDA, M.

2008

15. 9. 2008

VUTIUM

Brno

1213-418X

Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy

2008

276

Czech Republic

1

40

40