AN ANALYSIS OF THE GRASP WITH BLOOM FILTER TO PREVENT DUPLICATES EXPLOITATION APPLIED TO CVRP

Vol 56, 2024 - 309188
Complete Articles (CA)
Favorite this paper
How to cite this paper?
Abstract
Metaheuristics are efficient ways to solve high-complexity problems, however, due to the context of optimization problems it is very costly to store all the generated solutions for the high storage demand of the exponential space of solutions. Thus, many metaheuristics can reevaluate solutions that were already evaluated, applying again highly costly routines in already explored solutions. The Bloom filter is an efficient tool with low memory consumption to map big databases. In this work, we propose the use of the Bloom filter with GRASP metaheuristic applied to the Capacitated Vehicle Routing Problem (CVRP). Experiments presented that the strategy with the Bloom filter is efficient with low memory usage and low computational time. For alpha = 0.05 (a parameter with high usage in GRASP, that can also lead to many duplicates), the time gain reaches 93\% of the time without the filter.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Instituto de Computação - Universidade Federal Fluminense
Track
  • 12. L&T – Logistics and Transport
Keywords
Bloom Filter
GRASP
CVRP