TSP Model to Route Planning in a Cleaning Services Company
DOI:
https://doi.org/10.46842/ipn.cien.v27n1a03Keywords:
transport route design, traveling salesman problem, process optimization, operations managementAbstract
This work is developed to support the decision-making of a service company. This company provides residential and commercial cleaning services. The company is located in San Diego CA. and the beginning of its operations was in 2008. Currently the company does not have a quantitative tool for the analysis or planning its routes, therefore it has the potential to optimized and improve its efficiency or expand its current capacity to respond the services demanded. The development and solution of a model proposed in this work is a solution to solve an instance corresponding to the application of the TSP model that implies a fixed origin and n processing destination nodes, there is a designed cleaning service for each node and that each node has to be visited only once except for the origin. According to the results, it was possible to identify a potential for improvement in terms of the execution times of the company's activities of 32% (percentage reduction), the result shows the benefit in terms of better use of current capacity of the company to meet the demanded services, and eventually additional capacity (obtained by optimization) could be assigned to meet non-scheduled services without the need to incur greater hiring or increase coverage of scheduled demand with the same operating resources (personal and vehicles).
References
U. Klanšek, “Using The Traveling Salesman Problem Solution for Optimal Route Scheduling in Construction Management,” Organ. Technol. Manag. Constr. An Int. J., vol. 3, no. 1, p. 7, 2011.
R. A. Hincapié et al., “Técnicas heurísticas aplicadas al problema del cartero viajante (TSP)”, Scientia Et Technica, vol. 10, núm. 24, mayo, 2004, pp. 1-6.
E. S. Hornig, N. R. Fuentealba, “Modelo aco para la recolección de residuos por contenedores,” Ingeniare, vol. 17, no. 2, pp. 236–243, 2009.
M. Monteón, “Aplicación del Modelo del Agente Viajero en la distribución de especias,” Lat. Am. J. Appl. Eng., vol. 3, no. 1, pp. 5–8, 2018.
P. M. Hariyadi, P. T. Nguyen, I. Iswanto, D. Sudrajat, “Traveling Salesman Problem Solution using Genetic Algorithm,” J. Crit. Rev., vol. 7, no. 1, pp. 56–61, 2020.
L. Sengupta, R. Mariescu-Istodor, P. Fränti, “Planning your route: where to start?”, Comput. Brain Behav., vol. 1, no. 3, pp. 252–265, 2018.
M. Dry, M. D. Lee, D. Vickers, P. Hughes, “Human performance on visually presented traveling salesperson problems with varying numbers of nodes,” J. Probl. Solving, vol. 1, no. 1, p. 4, 2006.
D. Lagos, R. Mancilla, P. Leal, F. Fox, “Performance measurement of a solution for the travelling salesman problem for routing through the incorporation of service time variability,” Ing. e Investig., vol. 39, no. 3, pp. 44–49, 2019.
Y. Shi, Y. Zhang, “The neural network methods for solving Traveling Salesman Problem,” Procedia Comput. Sci., vol. 199, pp. 681–686, 2022.
J. I. Pérez Rave, G. P. Jaramillo Álvarez, “Espacio literario relevante sobre el problema del vendedor viajero (TSP): contenido, clasificación, métodos y campos de inspiración,” Production, vol. 23, no. 4, pp. 866–876, 2013
Published
Issue
Section
License
Copyright (c) 2023 Instituto Politecnico Nacional
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
