Vol. 22 No. 1 (2018), Industrial and systems engineering
Vol. 22 No. 1 (2018)

Solving the assignment of customers to trucks and visiting days in a periodic routing real-world case

Industrial and systems engineering
Published 2018-01-18
Andres Felipe Duque-Correa, MSc
Universidad EAFIT
María Gulnara Baldoquín-de la Peña, PhD
Universidad EAFIT
PDF

Keywords

Heuristics
logistics
clustering
allocation
periodic routing

How to Cite

Solving the assignment of customers to trucks and visiting days in a periodic routing real-world case. (2018). Ingenieria Y Universidad, 22(1), 53-76. https://doi.org/10.11144/Javeriana.iyu22-1.sact
ACM ACS APA ABNT Chicago Harvard IEEE MLA Turabian Vancouver AMA

Download Citation

Endnote/Zotero/Mendeley (RIS) BibTeX
Almetrics
 
Dimensions
 

Google Scholar
 
Search GoogleScholar

Abstract

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.

PDF

[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.

This journal is registered under a Creative Commons Attribution 4.0 International Public License. Thus, this work may be reproduced, distributed, and publicly shared in digital format, as long as the names of the authors and Pontificia Universidad Javeriana are acknowledged. Others are allowed to quote, adapt, transform, auto-archive, republish, and create based on this material, for any purpose (even commercial ones), provided the authorship is duly acknowledged, a link to the original work is provided, and it is specified if changes have been made. Pontificia Universidad Javeriana does not hold the rights of published works and the authors are solely responsible for the contents of their works; they keep the moral, intellectual, privacy, and publicity rights.

Approving the intervention of the work (review, copy-editing, translation, layout) and the following outreach, are granted through an use license and not through an assignment of rights. This means the journal and Pontificia Universidad Javeriana cannot be held responsible for any ethical malpractice by the authors. As a consequence of the protection granted by the use license, the journal is not required to publish recantations or modify information already published, unless the errata stems from the editorial management process. Publishing contents in this journal does not generate royalties for contributors.