Speaker:

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.