| Revista: | Programación matemática y software |
| Base de datos: | |
| Número de sistema: | 000573056 |
| ISSN: | 2007-3283 |
| Autores: | Liñán García, Ernesto1 Cruz Villegas, Linda Crystal1 González González, David Salvador1 |
| Instituciones: | 1Universidad Autónoma de Coahuila, Facultad de Sistemas, Arteaga, Coahuila. México |
| Año: | 2014 |
| Volumen: | 6 |
| Número: | 2 |
| Paginación: | 36-45 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| 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. |
| Disciplinas: | Ingeniería, Ciencias de la computación |
| Palabras clave: | Ingeniería mecánica, Procesamiento de datos |
| Keyword: | Mechanical engineering, Data processing |
| Texto completo: | Texto completo (Ver PDF) |
