Journal
TOP
Volume 21, Issue 1, Pages 109-132Publisher
SPRINGER
DOI: 10.1007/s11750-011-0245-1
Keywords
Randomized algorithms; Combinatorial optimization; Vehicle routing problem; Biased random search; Heuristics
Categories
Funding
- Spanish Ministry of Science and Innovation [MTM2008-06695-C03-03, TRA2010-21644-C03, ECO2009-11307]
- Working Community of the Pyrenees [IIQ13172.R11-CTP09-R2, CTP09-00007]
- CYTED-IN3-HAROSA network
- Jeronimo de Ayanz network (Government of Navarre, Spain)
Ask authors/readers for more resources
This paper discusses the use of probabilistic or randomized algorithms for solving vehicle routing problems with non-smooth objective functions. Our approach employs non-uniform probability distributions to add a biased random behavior to the well-known savings heuristic. By doing so, a large set of alternative good solutions can be quickly obtained in a natural way and without complex configuration processes. Since the solution-generation process is based on the criterion of maximizing the savings, it does not need to assume any particular property of the objective function. Therefore, the procedure can be especially useful in problems where properties such as non-smoothness or non-convexity lead to a highly irregular solution space, for which the traditional optimization methods-both of exact and approximate nature-may fail to reach their full potential. The results obtained so far are promising enough to suggest that the idea of using biased probability distributions to randomize classical heuristics is a powerful one that can be successfully applied in a variety of cases.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available