Mostrar el registro sencillo del ítem

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

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

dc.creatorToro-Ocampo, Eliana M.
dc.creatorDomínguez-Castaño, Andrés H.
dc.creatorEscobar-Zuluaga, Antonio H.
dc.date2016-01-30
dc.date.accessioned2021-03-18T21:06:44Z
dc.date.available2021-03-18T21:06:44Z
dc.identifierhttps://revistas.itm.edu.co/index.php/tecnologicas/article/view/593
dc.identifier10.22430/22565337.593
dc.identifier.urihttp://test.repositoriodigital.com:8080/handle/123456789/11683
dc.descriptionThe 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.en-US
dc.descriptionEl 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.es-ES
dc.formatapplication/pdf
dc.languagespa
dc.publisherInstituto Tecnológico Metropolitano (ITM)en-US
dc.relationhttps://revistas.itm.edu.co/index.php/tecnologicas/article/view/593/620
dc.relation/*ref*/K. F. Doerner and V. Schmid, “Survey: Matheuristics for rich vehicle routing problems,” in 7th International Workshop on Hybrid Metaheuristics, HM 2010, vol. 6373 LNCS, M. Blesa, C. Blum, G. Raidl, A. Roli, and M. Samples, Eds. Berlin: Springer, 2010, pp. 206–221. [2] J. R. Montoya-Torres, J. López Franco, S. Nieto Isaza, H. Felizzola Jiménez, and N. Herazo-Padilla, “A literature review on the vehicle routing problem with multiple depots,” Comput. Ind. Eng., vol. 79, pp. 115–129, Jan. 2015. [3] P. Cassidy and H. Bennett, “Vehicle System Scheduling,” OR Soc., vol. 23, no. 2, pp. 151–163, 2015. [4] M. Ball, B. Golden, and A. Assad, “Planning for Truck Fleet Size in the Presence of a Common-Carrier Option,” Decis. Sci., vol. 14, no. 1, pp. 103–120, 2007. [5] B. L. Golden and E. a. Wasil, “OR Practice--Computerized Vehicle Routing in the Soft Drink Industry,” Oper. Res., vol. 35, no. 1, pp. 6–17, 1987. [6] M. Fisher, R. Greenfield, R. Jaikumar, and J. Lester, “A computerized Vehicle Routing Application,” Interfaces (Providence)., vol. 4, pp. 42–52, 12AD. [7] W. J. Bell, L. M. Dalberto, M. L. Fisher, a. J. Greenfield, R. Jaikumar, P. Kedia, R. G. Mack, and P. J. Prutzman, “Improving the Distribution of Industrial Gases with an On-Line Computerized Routing and Scheduling Optimizer,” Interfaces (Providence)., vol. 13, no. 6, pp. 4–23, 1983. [8] A. G. G. Brown, C. J. Ellis, G. W. Graves, and D. Ronen, “of the dispatching are to minimize cost of delivered product, to balance the workload among the company trucks, and to load the maximum weight on a truck while adhering to all laws. The important,” vol. 17, no. 1, pp. 2–4, 1987. [9] J. Pooley, “Integrated Production and Distribution Facility Planning at Ault Foods,” Interfaces (Providence)., vol. 24, no. 4, pp. 113–121, 1994. [10] R. Baldacci and A. Mingozzi, “A unified exact method for solving different classes of vehicle routing problems,” Math. Program., vol. 120, no. 2, pp. 347–380, Sep. 2009. [11] N. Christofides, A. Mingozzi, and P. Toth, “Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations,” Math. Program., vol. 20, no. 1, pp. 255–282, Dec. 1981. [12] R. Baldacci, E. Bartolini, a. Mingozzi, and a. Valletta, “An Exact Algorithm for the Period Routing Problem,” Oper. Res., vol. 59, no. 1, pp. 228–241, 2011. [13] C. Contardo and R. Martinelli, “A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints,” Discret. Optim., vol. 12, pp. 129–146, May 2014. [14] S. Salhi and M. Sari, “A multi-level composite heuristic for the multi-depot vehicle fleet mix problem,” Eur. J. Oper. Res., vol. 103, no. 1, pp. 95–112, Nov. 1997. [15] E. M. Toro O., A. H. Escobar Z., and M. Granada E., “Literature Review On The Vehicle Routing Problem In The Green Transportation Context,” Luna Azul, vol. 42, no. 42, pp. 362–387, Dec. 2015. [16] I. D. Giosa, I. L. Tansini, and I. O. Viera, “New assignment algorithms for the multi-depot vehicle routing problem,” J. Oper. Res. Soc., vol. 53, no. 9, pp. 977–984, Sep. 2002.
dc.relation/*ref*/G. Nagy and S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” Eur. J. Oper. Res., vol. 162, no. 1, pp. 126–141, Apr. 2005. [18] C.-G. Lee, M. a. Epelman, C. C. White, and Y. a. Bozer, “A shortest path approach to the multiple-vehicle routing problem with split pick-ups,” Transp. Res. Part B Methodol., vol. 40, no. 4, pp. 265–284, May 2006. [19] B. Crevier, J.-F. Cordeau, and G. Laporte, “The multi-depot vehicle routing problem with inter-depot routes,” Eur. J. Oper. Res., vol. 176, no. 2, pp. 756–773, Jan. 2007. [20] G. Jeon, H. R. Leep, and J. Y. Shim, “A vehicle routing problem solved by using a hybrid genetic algorithm,” Comput. Ind. Eng., vol. 53, no. 4, pp. 680–692, Nov. 2007. [21] W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, “A hybrid genetic algorithm for the multi-depot vehicle routing problem,” Eng. Appl. Artif. Intell., vol. 21, no. 4, pp. 548–557, Jun. 2008. [22] G. Clarke and J. W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Oper. Res., vol. 12, no. 4, pp. 568–581, Aug. 1964. [23] P. Surekha and S. Sumathi, “Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms,” World Appl. Program., vol. 1, no. 3, pp. 118–131, 2011. [24] J.-F. Cordeau and M. Maischberger, “A parallel iterated tabu search heuristic for vehicle routing problems,” Comput. Oper. Res., vol. 39, no. 9, pp. 2033–2050, Sep. 2012. [25] T. Vidal and T. G. G. Crainic, “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems,” Oper. …, vol. 60, no. 3, pp. 611–624, 2012. [26] A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Comput. Oper. Res., vol. 40, no. 10, pp. 2519–2531, Oct. 2013. [27] J. W. Escobar, R. Linfati, P. Toth, and M. G. Baldoquin, “A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem,” J. Heuristics, vol. 20, no. 5, pp. 483–509, Oct. 2014. [28] A. C. Rencher, A Review Of “Methods of Multivariate Analysis, ,” vol. 37, no. 11. 2005. [29] S. Barreto, C. Ferreira, J. Paixão, and B. S. Santos, “Using clustering analysis in a capacitated location-routing problem,” Eur. J. Oper. Res., vol. 179, no. 3, pp. 968–977, Jun. 2007. [30] A. Subramanian, “Heuristic, Exact and Hybrid Approaches for Vehicle Routing Problems.” Universidade Federal Fluminense, Niteroi, Sao Pablo, pp. 60–69, 2012.
dc.rightsCopyright (c) 2017 Tecno Lógicasen-US
dc.sourceTecnoLógicas; Vol. 19 No. 36 (2016); 49-62en-US
dc.sourceTecnoLógicas; Vol. 19 Núm. 36 (2016); 49-62es-ES
dc.source2256-5337
dc.source0123-7799
dc.subjectCombinatorial optimizationen-US
dc.subjectclustering techniquesen-US
dc.subjectdistribution networken-US
dc.subjectiterated local searchen-US
dc.subjectMulti-Depot Vehicle Routingen-US
dc.subjectBúsqueda local iteradaes-ES
dc.subjectoptimización combinatoriaes-ES
dc.subjectruteo con múltiples depósitoses-ES
dc.subjectred de distribuciónes-ES
dc.subjecttécnicas de agrupamientoes-ES
dc.titleDesempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitosen-US
dc.titleDesempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitoses-ES
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.typeResearch Papersen-US
dc.typeArtículos de investigaciónes-ES


Ficheros en el ítem

FicherosTamañoFormatoVer

No hay ficheros asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem