UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM
Consideramos 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 construidas para satisfacer las demandas de los clientes. El objetivo es mini...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de Medellín
2012-12-01
|
| Series: | Revista Ingenierías Universidad de Medellín |
| Subjects: | |
| Online Access: | http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1692-33242012000200012 |
| _version_ | 1818897753776848896 |
|---|---|
| author | John Willmer Escobar Rodrigo Linfati |
| author_facet | John Willmer Escobar Rodrigo Linfati |
| author_sort | John Willmer Escobar |
| collection | DOAJ |
| description | Consideramos 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 construidas para satisfacer las demandas de los clientes. El objetivo es minimizar la suma de los costos de abrir depósitos, de los costos de los vehículos usados, y de los costos variables asociados con la distancia recorrida por las rutas. En este paper, proponemos una metaheurística basada en simulado y recocido con espacio de búsqueda granular para resolver el problema CLRP. Experimentos computacionales en instancias de benchmarking tomadas de la literatura muestran que el algoritmo propuesto es capaz de obtener, dentro de tiempos computacionales razonables, soluciones de alta calidad mostrando su eficacia.<br>The article deals with the Capacitated Location Routing Problem (CLRP) where the goal is to determine the depots to be opened, the customers to be assigned to each deposit opened, and the routes to be constructed for fulfilling customers' demands. The objective is to minimize the sum of costs resulting from opening depots, costs resulting from used vehicles, and variable costs associated to the distance across the routes. In this paper, a metaheuristic based on simulated annealing with granular search space for solving the CLRP is proposed. Computational experiments on benchmarking instances taken from literature show that the proposed algorithm is able to obtain high-quality solutions within reasonable computational times, thus showing its efficiency. |
| first_indexed | 2024-12-19T19:21:11Z |
| format | Article |
| id | doaj.art-d3d45f82de064ceea106520aea1dfb59 |
| institution | Directory Open Access Journal |
| issn | 1692-3324 |
| language | English |
| last_indexed | 2024-12-19T19:21:11Z |
| publishDate | 2012-12-01 |
| publisher | Universidad de Medellín |
| record_format | Article |
| series | Revista Ingenierías Universidad de Medellín |
| spelling | doaj.art-d3d45f82de064ceea106520aea1dfb592022-12-21T20:08:59ZengUniversidad de MedellínRevista Ingenierías Universidad de Medellín1692-33242012-12-011121139150UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEMJohn Willmer EscobarRodrigo LinfatiConsideramos 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 construidas para satisfacer las demandas de los clientes. El objetivo es minimizar la suma de los costos de abrir depósitos, de los costos de los vehículos usados, y de los costos variables asociados con la distancia recorrida por las rutas. En este paper, proponemos una metaheurística basada en simulado y recocido con espacio de búsqueda granular para resolver el problema CLRP. Experimentos computacionales en instancias de benchmarking tomadas de la literatura muestran que el algoritmo propuesto es capaz de obtener, dentro de tiempos computacionales razonables, soluciones de alta calidad mostrando su eficacia.<br>The article deals with the Capacitated Location Routing Problem (CLRP) where the goal is to determine the depots to be opened, the customers to be assigned to each deposit opened, and the routes to be constructed for fulfilling customers' demands. The objective is to minimize the sum of costs resulting from opening depots, costs resulting from used vehicles, and variable costs associated to the distance across the routes. In this paper, a metaheuristic based on simulated annealing with granular search space for solving the CLRP is proposed. Computational experiments on benchmarking instances taken from literature show that the proposed algorithm is able to obtain high-quality solutions within reasonable computational times, thus showing its efficiency.http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1692-33242012000200012problema de localización y ruteosimulado y recocidobúsqueda granularalgoritmos metaheurísticoslocation routing problemsimulated annealinggranular searchmetaheuristic algorithms |
| spellingShingle | John Willmer Escobar Rodrigo Linfati UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM Revista Ingenierías Universidad de Medellín problema de localización y ruteo simulado y recocido búsqueda granular algoritmos metaheurísticos location routing problem simulated annealing granular search metaheuristic algorithms |
| title | UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM |
| title_full | UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM |
| title_fullStr | UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM |
| title_full_unstemmed | UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM |
| title_short | UN ALGORITMO METAHEURÍSTICO BASADO EN RECOCIDO SIMULADO CON ESPACIO DE BÚSQUEDA GRANULAR PARA EL PROBLEMA DE LOCALIZACIÓN Y RUTEO CON RESTRICCIONES DE CAPACIDAD A META-HEURISTIC ALGORITHM BASED ON THE SIMULATED ANNEALING WITH GRANULAR SEARCH SPACE FOR THE CAPACITATED LOCATION ROUTING PROBLEM |
| title_sort | un algoritmo metaheuristico basado en recocido simulado con espacio de busqueda granular para el problema de localizacion y ruteo con restricciones de capacidad a meta heuristic algorithm based on the simulated annealing with granular search space for the capacitated location routing problem |
| topic | problema de localización y ruteo simulado y recocido búsqueda granular algoritmos metaheurísticos location routing problem simulated annealing granular search metaheuristic algorithms |
| url | http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1692-33242012000200012 |
| work_keys_str_mv | AT johnwillmerescobar unalgoritmometaheuristicobasadoenrecocidosimuladoconespaciodebusquedagranularparaelproblemadelocalizacionyruteoconrestriccionesdecapacidadametaheuristicalgorithmbasedonthesimulatedannealingwithgranularsearchspaceforthecapacitatedlocationroutingproblem AT rodrigolinfati unalgoritmometaheuristicobasadoenrecocidosimuladoconespaciodebusquedagranularparaelproblemadelocalizacionyruteoconrestriccionesdecapacidadametaheuristicalgorithmbasedonthesimulatedannealingwithgranularsearchspaceforthecapacitatedlocationroutingproblem |