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

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Grasas, Àlex
• dc.contributor.author Juan, Angel A.
• dc.contributor.author Faulin, Javier
• dc.contributor.author De Armas, Jésica
• dc.contributor.author Ramalhinho-Lourenço, Helena
• dc.date.accessioned 2020-05-04T08:55:56Z
• dc.date.available 2020-05-04T08:55:56Z
• dc.date.issued 2017
• dc.description.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.en
• dc.description.sponsorship This work has been partially supported by the Spanish Ministry of Economy and Competitiveness and FEDER (TRA2013-48180-C3-P, TRA2015-71883-REDT), the Ibero-American Program for Science and Technology for Development (CYTED2014-515RT0489), and the Erasmus+ Program (2016-1-ES01-KA108-023465).
• dc.format.mimetype application/pdf
• dc.identifier.citation Grasas A, Juan AA, Faulin J, de Armas J, Ramalhinho H. Biased randomization of heuristics using skewed probability distributions: a survey and some applications. Comput Ind Eng. 2017 Jun 10;110:216-28. DOI: 10.1016/j.cie.2017.06.019
• dc.identifier.doi http://dx.doi.org/10.1016/j.cie.2017.06.019
• dc.identifier.issn 0360-8352
• dc.identifier.uri http://hdl.handle.net/10230/44395
• dc.language.iso eng
• dc.publisher Elsevier
• dc.relation.ispartof Computers and Industrial Engineering. 2017 Jun 10;110:216-28
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TRA2013-48180-C3-P
• dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TRA2015-71883-REDT
• dc.rights © Elsevier http://dx.doi.org/10.1016/j.cie.2017.06.019
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Heuristicsen
• dc.subject.keyword Biased randomizationen
• dc.subject.keyword Real-time decision makingen
• dc.subject.keyword Combinatorial optimizationen
• dc.subject.keyword Logisticsen
• dc.subject.keyword Transportationen
• dc.subject.keyword Productionen
• dc.title Biased randomization of heuristics using skewed probability distributions: a survey and some applicationsen
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/acceptedVersion