Resumen
Introducción: Este trabajo propone un modelo y dos algoritmos heurísticos para asignar clientes a camiones y días de visita como una primera fase en la solución de un problema de ruteo, que está estrechamente relacionado con el PVRP (Periodic Vehicle Routing Problem), aunque una decisión estratégica de la compañía impone la restricción adicional, de que cada cliente debe ser siempre visitado por el mismo camión. Métodos: el modelo propuesto tiene como objetivo agrupar a los clientes que son visitados el mismo día por el mismo camión lo más cerca posible por medio de clustering basado en centroides. La primera heurística propuesta tiene una etapa constructiva y tres heurísticas subyacentes de mejora, mientras que la segunda usa un algoritmo de programación lineal exacto. Resultados: los algoritmos son evaluados por instancias tomadas de la literatura y generadas, teniendo en cuenta las características presentadas en el caso real abordado.
[2] B. E. Gillett and L. R. Miller, “A heuristic algorithm for the vehicle-dispatch problem,” Operations Res., vol. 22, no. 2, pp. 340-349, Apr. 1974. doi: 10.1287/opre.22.2.340
[3] N. Suthikarnnarunai, “A sweep algorithm for the mix fleet vehicle routing problem,” in Proc. IMECS 2008, vol. 2, Hong Kong, 19-21 March, 2008.
[4] K. Shin and S. Han, “A centroid-based heuristic algorithm for the capacitated vehicle routing problem,” Comput. Informat., vol. 30, no. 4, pp. 721-732, 2011.
[5] I. Stankovianska, “An effective approach to routing problems,” Scient. Papers Univ. Pardubice. Series D, no. 10 (2006), pp. 148-151, 2006.
[6] 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, 2002.
[7] J. J. Miranda-Bront, B. Curcio, I. Méndez-Díaz, A. Montero, F. Pousa, and P. Zabala, “A cluster- first route-second approach for the swap body vehicle routing problem,” Ann. Oper. Res., vol. 253, no. 2, pp. 935-956, 2017. doi: 10.1007/s10479-016-2233-1
[8] R. Russell and W. Igo, “An assignment routing problem,” Networks, vol. 9, no. 1, pp. 1-17, 1979. doi:10.1057=palgrave.jors.2601426
[9] C. C. R. Tan and J. E. Beasley, “A heuristic algorithm for the period vehicle routing problem,” Omega, vol. 12, no. 5, pp. 497-504, 1984. doi: 10.1016/0305-0483(84)90050-1
[10] S. Coene, A. Arnout, and F. C. R. Spieksma, “On a periodic vehicle routing problem,” J. Oper. Res. Soc., vol. 61, no. 12, pp. 1719-1728, Dec. 2010. doi: 10.1057/jors.2009.154
[11] I. M. Chao, B. L. Golden and E. Wasil, “An improved heuristic for the period vehicle routing problem,” Networks, vol. 26, no. 1, pp. 25-44, Aug. 1995. doi: 10.1002/net.3230260104
[12] M. G. Baldoquin de la Peña, A. Escalera Fariñas, and R. Linfati, “A model and solution method for solving the real-world and complex problem of scheduling visits to customers,” J. Appl. Res. Technol., vol. 12, no. 3, pp. 333-342, Jun. 2014. doi: 10.1016/S1665-6423(14)71616-5
[13] A. Escalera Fariñas and M. G. Baldoquin de la Peña, “Sistema soporte a la decisión para el agrupamiento de clientes de brascuba sa,” Ing. Ind., vol. 34, no. 2, pp. 143-154, May-Ago. 2013.
[14] A. M. Campbell and J. H. Wilson, “Forty years of periodic vehicle routing,” Networks,vol. 63, no. 1, pp. 2-15, Jan. 2014. doi: 10.1002/net.21527.
[15] N. Christofides and J. E. Beasley, “The period routing problem,” Networks, vol. 14, no. 2, pp. 237-256, 1984. doi: 10.1002/net.3230140205.
[16] R. A. Russell and D. Gribbin, “A multiphase approach to the period routing problem,” Networks, vol. 21, no. 7, pp. 747-765, Dec. 1991. doi: 10.1002/net.3230210704.
[17] J. F. Cordeau, M. Gendreau, and G. Laporte, “A tabu search heuristic for periodic and multi-depot vehicle routing problems,” Networks, vol. 30, no. 2, pp. 105-119, Sep. 1997. doi: 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G
[18] V. C. Hemmelmayr, K. F. Doerner, and R. F. Hartl, “A variable neighborhood search heuristic for periodic routing problems,” Eur. J. Oper. Res., vol. 195, no. 3, pp. 791-802, Jun. 2009. doi: 10.1016/j.ejor.2007.08.048.
[19] O. Lum, C. Cerrone, B. Golden, and E. Wasil, “Partitioning a street network into compact, balanced, and visually appealing routes,” Networks, Vol. 69, no. 3, pp. 290-303, May. 2017. doi: 10.1002/net.21730.
[20] J. Pacheco and O. Valencia, “Análisis de nuevos métodos de clasificación. Un ejemplo ilustrativo de su uso en la agrupación de los municipios de Castilla y León,” Est. Econ. Apl., vol. 23, no. 3, pp. 711-729, 2005.
[21] É. D. Taillard, “Heuristic methods for large centroid clustering problems,” J. Heuristics, vol. 9, no. 1, pp. 51-73, Jan. 2003. doi: 10.1023/A:1021841728075
[22] P. Hansen and N. Mladenovic, “J-means: a new local search heuristic for minimum sum of squares clustering,” Pattern Recogn., vol. 34, no. 2, pp. 405-413, Feb. 2001. doi: 10.1016/S0031-3203(99)00216-2
[23] H-H. Bock, “Origins and extensions of the k-means algorithm in cluster analysis,” JEHPS, vol. 4, no. 2, pp. 48-49, Dec. 2008.
Una vez aceptado un trabajo para publicación la revista podrá disponer de él en toda su extensión, tanto directamente como a través de intermediarios, ya sea de forma impresa o electrónica, para su publicación ya sea en medio impreso o en medio electrónico, en formatos electrónicos de almacenamiento, en sitios de la Internet propios o de cualquier otro editor. Este uso tiene como fin divulgar el trabajo en la comunidad científica y académica nacional e internacional y no persigue fines de lucro. Para ello el autor o los autores le otorgan el permiso correspondiente a la revista para dicha divulgación mediante autorización escrita.
Todos los articulos aceptados para publicación son sometidos a corrección de estilo. Por tanto el autor /los autores autorizan desde ya los cambios sufridos por el artículo en la corrección de estilo.
El autor o los autores conservarán los derechos morales y patrimoniales del artículo.