Biased randomization of heuristics using skewed probability distributions: a survey and some applications

Abstract

Randomized heuristics are widely used to solve large scale combinatorial optimization problems. Among the plethora of randomized heuristics, this paper reviews those that contain biased-randomized procedures (BRPs). A BRP is a procedure to select the next constructive ‘movement’ from a list of candidates in which their elements have different probabilities based on some criteria (e.g., ranking, priority rule, heuristic value, etc.). The main idea behind biased randomization is the introduction of a slight modification in the greedy constructive behavior that provides a certain degree of randomness while maintaining the logic behind the heuristic. BRPs can be categorized into two main groups according to how choice probabilities are computed: (i) BRPs using an empirical bias function; and (ii) BRPs using a skewed theoretical probability distribution. This paper analyzes the second group and illustrates, throughout a series of numerical experiments, how these BRPs can benefit from parallel computing in order to significantly outperform heuristics and even simple metaheuristic approaches, thus providing reasonably good solutions in ‘real time’ to different problems in the areas of transportation, logistics, and scheduling.