Published Jan 18, 2018


Google Scholar
Search GoogleScholar

Andres Felipe Duque-Correa, MSc

María Gulnara Baldoquín-de la Peña, PhD



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.


Heuristics, logistics, clustering, allocation, periodic routinglogística, clustering, distribución, heurísticas, ruteo periódico

[1] M. L. Fisher and R. Jaikumar, “A generalized assignment heuristic for vehicle routing,” Networks, vol. 11, no. 2, pp. 109-124, Jun. 1981. doi: 10.1002/net.3230110205
[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.
How to Cite
Duque-Correa, A. F., & Baldoquín-de la Peña, M. G. (2018). Solving the assignment of customers to trucks and visiting days in a periodic routing real-world case. Ingenieria Y Universidad, 22(1), 53–76.
Industrial and systems engineering