Propuesta de valores en rutas desconocidas para el uso del algoritmo de Clarke – Wright y construcción de un algoritmo de ruteo. Caso practico

Published in: Global Partnerships for Development and Engineering Education: Proceedings of the 15th LACCEI International Multi-Conference for Engineering, Education and Technology
Date of Conference: July 19-21, 2017
Location of Conference: Boca Raton, FL, United States
Authors: Jonatan Rojas Polo, MS. (Pontificia Universidad Católica del Perú, PE)
Cesar Stoll Quevedo, PhD. (Pontificia Universidad Católica del Perú, PE)
Alexia Cáceres Cansaya, (Pontificia Universidad Católica del Perú, PE)
Jackeline Alva Zelada, (Pontificia Universidad Católica del Perú, PE)
Full Paper: #453

Abstract:

Esta investigación surgio mediante la búsqueda de la Mejora en el abastecimiento y recolección de materia prima en una empresa agroindustrial. En el transcurso de dicha investigación central, desviamos la atención en la optimización del ruteo de vehículos usando el algoritmo de Clarke y Wright, específicamente en los valores de ahorros generados entre cada par de puntos (sitios), el problema surge cuando no tenemos las distancia entre dos sitios y se asume como distancia un valor muy grande, M, dado que es un problema de minimización de la distancia a recorrer, en la factibilidad de la solución óptima no se tomará dicho valor. La propuesta de esta investigación aborda a redes (grafos) que no presenten un ciclo Hamiltonianos, o rutas desconocidas. Se usó dos tipos de artificios. El primero es un artificio en base al algoritmo de Dijkstra en las rutas desconocidas, lo cual implica de que existe una probabilidad de circular más de una vez en un lugar, no obstante ello es permitido para no caer en la Infactibilidad al hallar la solución óptima. El segundo artificio se centra en colocar un valor grande, no obstante aquí si se discrimina con la cercanía entre los sitios, es decir para las distancias no existentes se coloca M(n-1), siendo M un valor grande y n el mínimo número de sitios intermedios que existen en los dos sitios de interés. Finalmente se validó los dos tipos de artificios y se obtuvo un algoritmo más amigable y eficiente para Rutear vehículos.