Introduction: This work proposes a model and two heuristic algorithms to assign customers to trucks and visit days as a first phase in the solution of a real-world routing problem, which is closely related to the PVRP (Periodic Vehicle Routing Problem), but a strategic decision of the company imposes the additional constraint that every customer must always be visited by the same truck. Methods: The proposed model will group the customers that are visited the same day by the same truck as close as posible by means of centroid-based clustering. The first proposed heuristic has a constructive stage and three underlying improvement heuristics, while the second uses an exact linear programming algorithm. Results: The algorithms are evaluated by instances taken from the literature and generated, taking into account the characteristics presented in the real-world case.
logística, clustering, distribución, heurísticas, ruteo periódicoHeuristics, logistics, clustering, allocation, periodic routing
 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
 N. Suthikarnnarunai, “A sweep algorithm for the mix fleet vehicle routing problem,” in Proc. IMECS 2008, vol. 2, Hong Kong, 19-21 March, 2008.
 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.
 I. Stankovianska, “An effective approach to routing problems,” Scient. Papers Univ. Pardubice. Series D, no. 10 (2006), pp. 148-151, 2006.
 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.
 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
 R. Russell and W. Igo, “An assignment routing problem,” Networks, vol. 9, no. 1, pp. 1-17, 1979. doi:10.1057=palgrave.jors.2601426
 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
 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
 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
 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
 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.
 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.
 N. Christofides and J. E. Beasley, “The period routing problem,” Networks, vol. 14, no. 2, pp. 237-256, 1984. doi: 10.1002/net.3230140205.
 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.
 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
 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.
 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.
 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.
 É. 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
 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
 H-H. Bock, “Origins and extensions of the k-means algorithm in cluster analysis,” JEHPS, vol. 4, no. 2, pp. 48-49, Dec. 2008.