| Revista: | Programación matemática y software |
| Base de datos: | |
| Número de sistema: | 000573056 |
| ISSN: | 2007-3283 |
| Autors: | Liñán García, Ernesto Cruz Villegas, Linda Crystal González González, David Salvador |
| Any: | 2014 |
| Volum: | 6 |
| Número: | 2 |
| Paginació: | 36-45 |
| País: | México |
| Idioma: | Español |
| Resumen en inglés | A new hybrid algorithm for solving the capacitated vehicle routing problem (CVRP) with stochastic demands is proposed. This new approach combines the simulated annealing (SA) with the savings algorithms and is implemented to obtain results of several Solomon"s instances of CVRP. This approach is named simulated annealing with metropolis cycle based on savings algorithm (SAMCSA). SA is a bio-inspired metaheuristic, an emulation of the heating and cooling processes of solids to solve optimization problems. On the other hand, the savings algorithm is a deterministic heuristic for solving CVRP. In order to generate high quality solutions of CVRP, this approach applies the savings algorithm into metropolis cycle of simulated annealing. An initial solution of SA is also generated by the savings algorithm. This simple change has lead to increase the solution quality for the CVRP with respect to the classical simulated annealing and savings algorithms |
| Resumen en español | Se propone un nuevo algoritmo híbrido para resolver el problema de ruteo de vehículos de capacidad (CVRP en inglés) con demanda estocástica. Este nuevo enfoque combina los algoritmos de recocido simulado (RS) y de ahorro y es implementado para obtener resultados de varias instancias Solomon del CVRP. El RS es una metaheúristica bioinspirada, una simulación del proceso de calentamiento y enfriamiento de los sólidos para resolver problemas de optimización. Por otro lado, el algoritmo de ahorro es una heurística determinística para resolver el CVRP. Con el objeto de generar soluciones de alta calidad del CVRP, este enfoque aplica el algoritmo de ahorro dentro del ciclo de metrópolis del recocido simulado; la solución inicial del algoritmo también es generada por el algoritmo de ahorro. Este simple cambio ha permitido incrementar la calidad de la solución del CVRP con respecto al recocido simulado clásico y al algoritmo de ahorro. |
| Paraules clau: | algoritmo de recocido simulado, algoritmo de ahorro, problema de ruteo de vehículos, metaheurísticas |
| Keyword: | simulated annealing, savings algorithm, vehicle routing problem, metaheuristic |
| Text complet: | Texto completo (Ver PDF) |
