Revista ELECTRO
Vol. 46 – Año 2024
Artículo
TÍTULO
El Problema del Viajero: Aplicación para la Optimización Georeferenciada de Rutas de Cobradores
AUTORES
Vázquez-Rosas, C.D.; González-Huitrón, V.A.; Guzmán-Rivera, M.A.; Cruz-Díaz, C.
RESUMEN
En el presente trabajo se aborda el problema de optimización de rutas para cobradores de deuda aplicable a diversas industrias (cobro de deuda bancaria, deuda departamental, deuda de impuestos, etc.). Para afrontar este reto se propone utilizar el algoritmo de optimización del problema del agente viajero (TSP), modificando la función de peso para qu e el algoritmo propuesto busque una relación óptima entre distancia y monto de la deuda a cobrar. Además, dentro de la función de peso, también se considera la probabilidad de que un cierto deudor pague la deuda. El objetivo principal es brindar la ruta que debe seguir un cobrador para visitar “n” casas de deudores que maximice la cantidad de deuda recaudada.
Palabras Clave: Problema del viajero, Aprendizaje automático, Problema del viajero generalizado, optimización combinatoria
ABSTRACT
This work addresses the problem of optimizing routes for debt collectors on motorcycles, applicable to various industries (bank debt collection, departmental debt, tax debt, etc.). To address this challenge, the proposal is to use the optimization algorithm for the Traveling Salesman Problem (TSP), modifying the weight function so that the proposed algorithm seeks an optimal relationship between distance and the amount of debt to be collected. Additionally, within the weight function, the probability of a certain deb tor paying the debt is also considered. The main goal is to provide the route a collector should follow to visit 'n' debtors' houses that maximizes the amount of debt collected.
Keywords: Traveling Salesman Problem, Machine learning, Generalized traveling salesman problem, combinatorial optimization
CONTENIDO
REFERENCIAS
[1] K. L. Hoffman and M. Padberg, ‘Traveling Salesman Problem (TSP)Traveling salesman problem’, in Encyclopedia of Operations Research and Management Science, S. I. Gass and C. M. Harris, Eds. New York, NY: Springer US, 2001, pp. 849–853.
[2] O. Cheikhrouhou and I. Khoufi, ‘A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy’, Computer Science Review, vol. 40, p. 1003 69, 2021.
[3] M. Battarra, G. Erdoǧan, G. Laporte, and D. Vigo, ‘The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs’, Transportation Science, vol. 44, no. 3, pp. 383–399, 2010.
[4] C. Han and Y. Jang, ‘Effects of debt collection practices on loss given default’, Journal of Banking & Finance, vol. 37, no. 1, pp. 21–31, 2013.
[5] E. Storms and G. Verschraegen, ‘Time regimes in debt collection and mediation’, Time & Society, vol. 28, no. 4, pp. 1382–1408, 2019.
[6] V. Asudani, S. Uparkar, S. Upadhye, and M. Seth, ‘Application of the Traveling Salesman Model for Rural Development of the Vidarbha Region’, ECS Transactions, vol. 107, no. 1, p. 6725, 2022.
[7] Y. Shi and Y. Zhang, ‘The neural network methods for solving Traveling Salesman Problem’, Procedia Co mputer Science, vol. 199, pp. 681 –686, 2022.
[8] O. Nurdiawan, F. A. Pratama, D. A. Kurnia, Kaslani, and N. Rahaningsih, ‘Optimization of Traveling Salesman Problem on Scheduling Tour Packages using Genetic Algorithms’, Journal of Physics: Conference Series, v ol. 1477, no. 5, p. 52037, Mar. 2020.
[9] P. C. Pop, O. Cosma, C. Sabo, and C. P. Sitar, ‘A comprehensive survey on the generalized traveling salesman problem’, European Journal of Operational Research, vol. 314, no. 3, pp. 819–835, 2024.
[10] Z. Zhang, H. Liu, M. Zhou, and J. Wang, ‘Solving Dynamic Traveling Salesman Problems With Deep Reinforcement Learning’, IEEE Transactions on Neural Networks and Learning Systems, vol. 34, no. 4, pp. 2119–2132, 2023.
[11] C. Wu, X. Fu, J. Pei, and Z. Dong, ‘A No vel Sparrow Search Algorithm for the Traveling Salesman Problem’, IEEE Access, vol. 9, pp. 153456–153471, 2021.
[12] S. Liu, Y. Zhang, K. Tang, and X. Yao, ‘How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman Problem ’, IEEE Computational Intelligence Magazine, vol. 18, no. 3, pp. 14–28, 2023.
[13] M. Mosayebi, M. Sodhi, and T. A. Wettergren, ‘The Traveling Salesman Problem with Job-times (TSPJ)’, Computers & Operations Research, vol. 129, p. 105226, 2021.
[14] A. Santini, A. Vi ana, X. Klimentova, and J. P. Pedroso, ‘The Probabilistic Travelling Salesman Problem with Crowdsourcing’, Computers & Operations Research, vol. 142, p. 105722, 2022.
[15] N. Elgiriyewithana, ‘New York Housing Market’. 2024.
[16] Z. Ling, X. Tao, Y. Zhang, and X. Ch en, ‘Solving Optimization Problems Through Fully Convolutional Networks: An Application to the Traveling Salesman Problem’, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 51, no. 12, pp. 7475–7485, 2021.
[17] A. Di Placido, C. Archetti, and C. Cerrone, ‘A genetic algorithm for the close-enough traveling salesman problem with application to solar panels diagnostic reconnaissance’, Computers & Operations Research, vol. 145, p. 105831, 2022.
[18] S. Wang, M. Liu, and F. Chu, ‘Approximate and exact alg orithms for an energy minimization traveling salesman problem’, Journal of Cleaner Production, vol. 249, p. 119433, 2020.
[19] A. C. P. Mesquita and C. A. A. Sanches, ‘Air cargo load and route planning in pickup and delivery operations’, Expert Systems with App lications, vol. 249, Part B, 2024.
[20] P. Agarwal, R. P. Agarwal, and M. Ruzhansky, Special functions and analysis of differential equations. CRC Press, 2020.
CITAR COMO:
Vázquez-Rosas, C.D.; González-Huitrón, V.A.; Guzmán-Rivera, M.A.; Cruz-Díaz, C., "El Problema del Viajero: Aplicación para la Optimización Georeferenciada de Rutas de Cobradores", Revista ELECTRO, Vol. 46, 2024, pp. 31-36.
VERSIÓN PDF