Un algoritmo metaheurístico híbrido para el problema de localización y ruteo con restricciones de capacidad



Document title: Un algoritmo metaheurístico híbrido para el problema de localización y ruteo con restricciones de capacidad
Journal: Dyna (Medellín)
Database:
System number: 000537762
ISSN: 0012-7353
Authors: 1
2
3
Institutions: 1Pontificia Universidad Javeriana, Departamento de Ingeniería Civil e Industrial, Cali. Colombia
2Universidad del Bío-Bío Concepción, Departamento de Ingeniería Industrial, Concepción. Chile
3Universidad Nacional de Colombia, Departamento de Ingeniería de Sistemas e Industrial, Bogotá. Colombia
Year:
Season: Ene-Feb
Volumen: 82
Number: 189
Pages: 243-251
Country: Colombia
Language: Español
Spanish abstract Este artículo considera el problema de localización y ruteo con restricciones de capacidad (CLRP), en el cual la meta es determinar los depósitos a ser abiertos, los clientes a ser asignados a cada depósito abierto y las rutas a ser desarrolladas para satisfacer la demanda de los clientes. El objetivo es minimizar la suma de los costos fijos de los depósitos abiertos, el costo del uso de los vehículos, y los costos variables asociados con la distancia recorrida por las rutas. En este artículo, una búsqueda tabú granular (GTS) con diferentes estrategias de diversificación contenida en una búsqueda iterativa local (ILS) es propuesta para resolver el CLRP. Un procedimiento de perturbación es aplicado cuando la mejor solución encontrada no se puede mejorar por un número determinado de iteraciones. Experimentos computacionales sobre instancias de benchmarking tomadas de la literatura muestran que el algoritmo propuesto es capaz de obtener, con tiempos computacionales reducidos, soluciones de alta calidad mostrando su efectividad.
English abstract This paper addresses the Capacitated Location-Routing Problem (CLRP) in which the aim is to determine the depots to be opened, the customers to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the cost of the open depots, of the used vehicle costs, and of the variable costs associated with the distance traveled by the performed routes. In this paper, a Granular Tabu Search (GTS) with different diversification strategies within a Iterated Local Search (ILS) is proposed to solve the CLRP. A shaking procedure is applied whenever the best solution found so far is not improved for a given number of iterations. Computational experiments on benchmark instances taken from the literature show that the proposed approach is able to obtain, within short computing times, high quality solutions illustrating its effectiveness.
Keyword: Problema de Localización y Ruteo (LRP),
Búsqueda Iterativa Local (ILS),
Búsqueda Tabú Granular (GTS),
Algoritmos Metaheuristicos
Keyword: Location Routing Problem (LRP),
Iterated Local Search (ILS),
Granular Tabu Search (GTS),
Metaheuristic Algorithms
Full text: Texto completo (Ver HTML) Texto completo (Ver PDF)