Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos



Título del documento: Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos
Revue: TecnoLógicas
Base de datos: PERIÓDICA
Número de sistema: 000398308
ISSN: 0123-7799
Autores: 1
2
2
Instituciones: 1Universidad Tecnológica de Pereira, Facultad de Ingeniería Industrial, Pereira, Risaralda. Colombia
2Universidad Tecnológica de Pereira, Escuela de Tecnología Eléctrica, Pereira, Risaralda. Colombia
Año:
Periodo: Ene-Jun
Volumen: 19
Número: 36
Paginación: 49-62
País: Colombia
Idioma: Español
Tipo de documento: Artículo
Enfoque: Aplicado, descriptivo
Resumen en español El problema de ruteo de vehículos considerando múltiples depósitos es clasificado como NP duro, cuya solución busca determinar simultáneamente las rutas de un conjunto de vehículos, atendiendo un conjunto de clientes con una demanda determinada. La función objetivo del problema consiste en minimizar el total de la distancia recorrida por las rutas, teniendo en cuenta que todos los clientes deben ser atendidos cumpliendo restricciones de capacidad de depósitos y vehículos. En este artículo se propone una metodología híbrida que combina las técnicas aglomerativas de clusterización para generar soluciones iniciales con un algoritmo de búsqueda local iterada, iterated location search (ILS) para resolver el problema. Aunque en trabajos previos se proponen los métodos de clusterización como estrategias para generar soluciones de inicio, en este trabajo se potencia la búsqueda sobre el sistema de información obtenido después de aplicar el método de clusterización. Además se realiza un extenso análisis sobre el desempeño de las técnicas de clusterización y su impacto en el valor de la función objetivo. El desempeño de la metodología propuesta es factible y efectivo para resolver el problema en cuanto a la calidad de las respuestas y los tiempos computacionales obtenidos, sobre las instancias de la literatura evaluadas
Resumen en inglés The vehicle routing problem considering multiple depots is classified as NP-hard. MDVRP determines simultaneously the routes of a set of vehicles and aims to meet a set of clients with a known demand. The objective function of the problem is to minimize the total distance traveled by the routes given that all customers must be served considering capacity constraints in depots and vehicles. This paper presents a hybrid methodology that combines agglomerative clustering techniques to generate initial solutions with an iterated local search algorithm (ILS) to solve the problem. Although previous studies clustering methods have been proposed like strategies to generate initial solutions, in this work the search is intensified on the information generated after applying the clustering technique. Besides an extensive analysis on the performance of techniques, and their effect in the final solution is performed. The operation of the proposed methodology is feasible and effective to solve the problem regarding the quality of the answers and computational times obtained on request evaluated literature
Disciplinas: Ingeniería
Palabras clave: Ingeniería industrial,
Redes de distribución,
Ruteo de vehículos,
Búsqueda local iterada,
Optimización combinatoria,
Técnicas de agrupamiento
Keyword: Engineering,
Industrial engineering,
Distribution networks,
Vehicle routing,
Iterated local search,
Combinatorial optimization,
Clustering techniques
Texte intégral: Texto completo (Ver PDF)