On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics / Juan, A. A. in Journal of the operational research society (JORS), Vol. 62 N° 6 (Juin 2011)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 62 N° 6 (Juin 2011) . - pp. 1085–1097 Titre : On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics Type de document : texte imprimé Auteurs : Juan, A. A., Auteur ; Faulin, J., Auteur ; Jorba, J., Auteur Année de publication : 2011 Article en page(s) : pp. 1085–1097 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Simulation Heuristics Probabilistic algorithms Vehicle routing Road transport Index. décimale : 001.424 Résumé : 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. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v62/n6/abs/jors201029a.html [article] On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics [texte imprimé] / Juan, A. A., Auteur ; Faulin, J., Auteur ; Jorba, J., Auteur . - 2011 . - pp. 1085–1097. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 62 N° 6 (Juin 2011) . - pp. 1085–1097 Mots-clés : Simulation Heuristics Probabilistic algorithms Vehicle routing Road transport Index. décimale : 001.424 Résumé : 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. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v62/n6/abs/jors201029a.html

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire