Published

2019-09-01

Performance measurement of a solution for the travelling salesman problem for routing through the incorporation of service time variability

Medición del desempeño de una solución del problema de agente viajero para ruteo a través de la incorporación de la variabilidad de los tiempos de servicio

Keywords:

Traveling salesmen problem (TSP), Performance, Discrete event simulation (DES), Service time (en)
Problema del agente viajero (TSP), Desempeño, Simulación de eventos discretos (DES), Tiempo de servicio (es)

Downloads

Authors

  • Dafne Consuelo Lagos Universidad Católica de Temuco https://orcid.org/0000-0001-7574-7748
  • Rodrigo Andrés Mancilla Universidad Católica de Temuco
  • Paola Elizabeth Leal Universidad Católica de Temuco
  • Franco Esteban Fox Without affiliation

This work assessed the performance of a solution to the problem of assigning service squads, incorporating the variability of service times. The initial problem was modelled as a Travelling Salesman Problem (TSP), whose solution was obtained by the ant colony algorithm, showing the efficient route to be followed by the squad. Assessment of the performance of the solution by discrete event simulation (DES) included the travel time and added the service time. The TSP solution indicated that up to six customer visits could be carried out in an 8hour working day. Validation by DES presented a stable behavior of the variance, regardless of the number of visit sites assigned along the route.

En este trabajo, se evaluó el desempeño de una solución del problema de asignación de brigadas al incorporar la variabilidad de los tiempos de servicio. La problemática inicial se modeló como un problema de agente viajero (TSP), cuya solución se obtuvo por medio del algoritmo colonia de hormigas y mostró la ruta eficiente que debe seguir una brigada. La evaluación del desempeño de la solución, a través de simulación de eventos discretos (DES), consideró el tiempo de recorrido y agregó el tiempo del servicio. La evaluación de desempeño de la solución del modelo TSP indicó que se pueden visitar hasta seis clientes en una jornada laboral diaria de 8 horas. El modelo de validación mediante DES presentó un comportamiento estable de la varianza, independientemente de la cantidad de puntos asignados a visitar dentro de la ruta.

Downloads

Download data is not yet available.

References

Alkaya, A. F., and Duman, E. (2010). A new generalization of the traveling salesman problem. Applied and Computational Mathematics, 9(2), 162-175. Retrieved from: https://hdl.handle.net/11376/1317

Anaya Fuentes, G. E., Hernández Gress, E. S., Seck Tuoh Mora, J. C., and Medina Marín, J. (2016). Solution of the job-shop scheduling problem through the traveling salesman problem. RIAI - Revista Iberoamericana de Automática e Informática Industrial, 13(4), 430-437. DOI: 10.1016/j.riai.2016.07.003

Arias-Rojas, J. S., Jiménez, J. F., and Montoya-Torres. J. R. (2012). Solving of school bus routing problem by ant colony optimization. Revista EIA, (17), 193-208. Retrieved from: http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S1794-12372012000100015&lang=es

Arnesen, M. J., Gjestvang, M., Wang, X., Fagerholt, K., Thun, K., and Rakke, J. G. (2017). A traveling salesman problem with pickups and deliveries, time windows and draft limits: Case study from chemical shipping. Computers and Operation Research, 77, 20-31. DOI: 10.1016/j.cor.2016.07.017

Bernardino, R., and Paias, A. (2018). Solving the family traveling salesman problem. European Journal of Operational Research, 267(2), 453-466. DOI: 10.1016/j.ejor.2017.11.063

Chen, S. H. (2015). Minimization of the total traveling distance and maximum distance by using a transformed-based encoding eda to solve the multiple traveling salesmen problem. Mathematical Problems in Engineering. DOI: 10.1155/2015/640231

Chládek, P., and Smetanová, D. (2018). Travelling Salesman Problem Applied to Black Sea Ports Used By Czech Ocean Shipping Companies. Nase More, 65(3), 141-145. DOI: 10.17818/NM/2018/3.2

Dong, X., Lin, Q., Xu, M., and Cai, Y. (2019). Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem. IET Intelligent Transport Systems, 13(10), 1483-1491. DOI: 10.1049/iet-its.2018.5359

Garg, H. (2018). Analysis of an industrial system under uncertain environment by using different types of fuzzy numbers. International Journal of Systems Assurance Engineering and Management, 9(2), 525-538. DOI: 10.1007/s13198-018-0699-8

González, G., and González, F. (2007). Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 2: algoritmo genético, comparación con una solución heurística. Ingeniería e Investigación, 27(1), 149-157. Retrieved from: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14795

Ko, S. Y., Cho, S. W., and Lee, C. (2018). Pricing and collaboration in last mile delivery services. Sustainability, 10(12), 4560. DOI: 10.3390/su10124560

Krushel, E. G., Stepanchenko, I. V., Panfilov, A. E., and Berisheva, E. D. (2014, September). An experience of optimization approach application to improve the urban passenger transport structure. In: Kravets A., Shcherbakov M., Kultsova M., Iijima T. (Eds.) KnowledgeBased Software Engineering. JKBSE 2014. Springer, Cham. DOI: 10.1007/978-3-319-11854-3_3

Li, J., Meng, X., and Dai, X. (2018). Collision-free scheduling of multi-bridge machining systems: A colored traveling salesman problem-based approach. IEEE/CAA Journal of Automatica Sinica, 5(1), 139-147. DOI: 10.1109/JAS.2017.7510415

Lynskey, J., Thar, K., Oo, T. Z., and Hong, C. S. (2019). Facility location problem approach for distributed drones. Symmetry, 11(1), 118. DOI: 10.3390/sym11010118

Meng, X., Li, J., Dai, X., and Dou, J. (2017). Variable neighborhood search for a colored traveling salesman problem. IEEE Transactions on Intelligent Transportation Systems, 19(4), 1018-1026. DOI: 10.1109/TITS.2017.2706720

Niu, Y., and Liu, Y. (2005). Performance optimization and simulation analysis of the railway communication network route search. Xitong Fangzhen Xuebao / Journal of System Simulation, 17(2), 468-471. http://en.cnki.com.cn/Article_en/CJFDTOTAL-XTFZ20050201K.htm

Osorio Gómez, J. C., Castrillón Montenegro, O. E., Toro Cardona, J. A., and Orejuela Cabrera, J. P. (2008). Hierarchical production planning model in flexible job shop including a preemption and sequence-dependent setup times. Ingeniería e Investigacióon, 28(2), 72-79. Retrieved from: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14896

Rubaiee, S., and Yildirim, M. B. (2019). An energy-aware multiobjective ant colony algorithm to minimize total completion time and energy cost on a single-machine preemptive scheduling. Computers and Industrial Engineering, 127, 240-252. DOI: 10.1016/j.cie.2018.12.020

Sabbani, I., Omar, B., and Eszetergar-Kiss, D. (2019). Simulation results for a daily activity chain optimization method based on ant colony algorithm with time windows. International Journal of Advanced Computer Science and Applications, 10(1), 425-430. DOI: 10.14569/IJACSA.2019.0100156

Tinarut, P., and Leksakul, K. (2019). Hybrid self-organizing map approach for traveling salesman problem. Chiang Mai University Journal of Natural Sciences, 18(1), 27-37. DOI: 10.12982/CMUJNS.2019.0003

Todosijevic, R., Mjirda, A., Mladenovic, M., Hanafi, S., and Gendron, B. (2017). A general variable neighborhood search variants for the travelling salesman problem with draft limits. Optimization Letters, 11(6), 1047-1056. DOI: 10.1007/s11590-014-0788-9

Vartdal, J. T., Qassim, R. Y., Mokliev, B., Udjus, G., and Gonzalez-Gorbena, E. (2019). Optimal configuration problem identification of electrical power cable in tidal turbine farm traveling salesman problem modeling approach. Journal of Modern Power Systems and Clean Energy, 7(2), 289-296. DOI: 10.1007/s40565-018-0472-7

Wang, Z., Guo, J., Zheng, M., and Wang, Y. (2015). Uncertain multiobjective traveling salesman problem. European Journal of Operational Research, 241(2), 478-489. DOI: 10.1016/j.ejor.2014.09.012

Xu, G., Wang, Y., Liu, S., and Wang, S. (2018). Tensioning-phase box girder deformation prediction model based on ant colony algorithm and residual correction. Mathematical Problems in Engineering. DOI: 10.1155/2018/1872578

Yen, C. T., and Cheng, M. F. (2018). A study of fuzzy control with ant colony algorithm used in mobile robot for shortest path planning and obstacle avoidance. Microsystem Technologies, 24(1), 125-135. DOI: 10.1007/s00542-016- 3192-9

Zhang, L., Mei, J., and Yan, B. (2018). A new test set compression scheme for circular scan. Eurasip Journal on Embedded Systems, 2018(1). DOI: 10.1186/s13639-018-0085-2

Zhang, S., and Zhang, Y. (2018). A hybrid genetic and ant colony algorithm for finding the shortest path in dynamic traffic networks. Automatic Control and Computer Sciences, 52(1), 67-76. DOI: 10.3103/S014641161801008X

Zhou, A. H., Zhu, L. P., Hu, B., Deng, S., Song, Y., Qiu, H., and Pan, S. (2019). Traveling-salesmanproblem algorithm based on simulated annealing and gene-expression programming. Information, 10(1). DOI: 10.3390/info10010007

License

Copyright (c) 2019 Dafne Consuelo Lagos, Rodrigo Andrés Mancilla, Paola Elizabeth Leal, Franco Esteban Fox

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:

1.    The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;

2.    The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;

3.    The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;

4.    The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.