Skip to content

ON THE USE OF PROBABILISTIC ALGORITHMS IN COMBINATORIAL OPTIMIZATION.

Dragos Ionescu - 21/07/2010

Speaker:

Dragos Ionescu
Abstract:

This presentation discusses the use of probabilistic or randomized algorithms for solving combinatorial optimization problems. We propose the use of probability distributions, such as the Geometric or the Triangular ones, to add a biased random behavior to classical heuristics such as the Clarke and Wright Savings heuristic for the Vehicle Routing Problem or the NEH heuristic for the Flow Shop Scheduling Problem. By randomizing these heuristics, a large set of alternative good solutions can be quickly obtained in a natural way. Some specific examples of this technique are analyzed to illustrate the main ideas behind this approach.