To access the full text documents, please follow this link: http://hdl.handle.net/2117/17351

On the use of Monte Carlo simulation, cache and splitting techniques to improve the clarke and wright savings heuristics
Juan Pérez, Angel Alejandro; Faulín, Javier; Jorba, Josep; Riera, D; Masip Rodó, David; Barrios, Barry
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I
This paper presents the SR-GCWS-CS probabilistic algorithm that combines Monte Carlo simulation with splitting techniques and the Clarke and Wright savings heuristic to find competitive quasi-optimal solutions to the Capacitated Vehicle Routing Problem (CVRP) in reasonable response times. The algorithm, which does not require complex fine-tuning processes, can be used as an alternative to other metaheuristics—such as Simulated Annealing, Tabu Search, Genetic Algorithms, Ant Colony Optimization or GRASP, which might be more difficult to implement and which might require non-trivial fine-tuning processes—when solving CVRP instances. As discussed in the paper, the probabilistic approach presented here aims to provide a relatively simple and yet flexible algorithm which benefits from: (a) the use of the geometric distribution to guide the random search process, and (b) efficient cache and splitting techniques that contribute to significantly reduce computational times. The algorithm is validated through a set of CVRP standard benchmarks and competitive results are obtained in all tested cases. Future work regarding the use of parallel programming to efficiently solve large-scale CVRP instances is discussed. Finally, it is important to notice that some of the principles of the approach presented here might serve as a base to develop similar algorithms for other routing and scheduling combinatorial problems.
Peer Reviewed
Àrees temàtiques de la UPC::Matemàtiques i estadística::Probabilitat
Heuristic
Probabilities
Heurística
Probabilitats
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Article
         

Show full item record

Related documents

Other documents of the same author

Juan Pérez, Angel Alejandro; Barrios, Barry; González Martín, Sergio; Coccola, Mariana; Faulín, Javier; Bektas, Tolga
Juan Pérez, Angel Alejandro; Faulín, Javier; Jorba, Josep; Caceres, J; Marquès Puig, Joan Manel
Ionescu, Dragos; Juan Pérez, Angel Alejandro; Faulín, Javier; Ferrer Biosca, Alberto
Juan Pérez, Angel Alejandro; Simosa, Jorge; Faulín, Javier; Monteforte, Arai; Guo, Harry
 

Coordination

 

Supporters