Document Type


Publication Date



Capacitated Vehicle Routing Problem, Monte Carlo Methods, Combinatorial Optimization, Heuristic Algorithms, Metaheuristic Algorithms


The Vehicle Routing Problem (VRP) is one of the combinatorial optimization problems most studied in Computer Science and of great relevance to the areas of logistics and transport. This paper presents a new algorithm for solving the Capacitated Vehicle Routing Problem (CVRP) using Monte Carlo methods. Monte Carlo methods are statistical methods that use random sampling to solve probabilistic and deterministic problems. The proposed algorithm was developed based on Monte Carlo simulations and Clarke and Wright Savings heuristic and demonstrated results comparable to the best existing algorithms in the literature, it overcomes previous work with Monte Carlo methods. The comparison, analysis and evaluation of the algorithm were based on existing benchmarks in the literature.


The paper is in Portuguese (Sistema para roteamento de veículos capacitados aplicando Métodos de Monte Carlo)