Solving the Capacitated Vehicle Routing Problem with stochastic demands appling the Simulated Annealing algorithm

Resolviendo el Problema de Ruteo de Vehículos de Capacidad con demandas estocásticas aplicando el algoritmo Recocido Simulado

Publicación:
Entidad Editora:
Editor Técnico:
ISSN:
Ejemplar/Número:
Cateoría:
Páginas:
Colección:
Fecha de inicio:
Periodicidad:

Programación Matemática y Software
Universidad Autónoma del Estado de Morelos
Dr.Marco Antonio Cruz Chávez
2007-3283
Volumen 6, Número 2 /Junio del 2014
Artículo de Investigación
36-45
Computación
Junio del 2014
Cuatrimestral

Ernesto Liñán García, Linda Crystal Cruz Villegas, David S. González González

Facultad de Sistemas Universidad Autónoma de Coahuila Saltillo, Coahuila

Recibido: 6 febrero 2014 Aceptado: 25 mayo 2014 Publicado en línea: 30 junio 2014

Abstract. 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 Saving’s Algorithm and, is implemented to obtain results of several solomon’s instances of CVRP. This approach is named Simulated Annealing with Metropolis Cycle based on Saving’s Algorithm (SAMCSA). Simulated Annealing is a bio inspirited metaheuristic, an emulation of heating and cooling process of solids to solve optimization problems. On the other hand, Saving´s algorithm is a deterministic heuristic for solving CVRP. In order to generate high quality solutions of CVRP, this approach applies Saving´s algorithm into Metropolis Cycle of Simulated Annealing; initial solution of SA is also generated by Saving´s algorithm. This simple change has lead to increase the solution quality to CVRP with respect to the classical Simulated Annealing algorithm and classical Saving´s algorithm.

Resumen. Un nuevo algoritmo hibrido para resolver el problema de ruteo de vehículos capacitado con demanda estocástica es propuesto. Este nuevo enfoque combina el Recocido Simulado y el Algoritmo de Ahorro y es implementado para obtener resultados de varias instancias solomon del CVRP. El Recocido Simulado es una metaheúristica bio inspirada, 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.

Palabras clave: Algoritmo Recocido Simulado, Algoritmo de Ahorro, Problema de Ruteo de Vehículos, Metaheuristicas.