Soluciones comparativas de métodos exáctos y aproximados para el problema de los vendedores ambulantes

Autores/as

DOI:

https://doi.org/10.21501/21454086.3804

Palabras clave:

Branch and Bound, Elimination-based Fruit Fly Optimization, Artificial Atom Algorithm, Traveling Salesman Problem

Resumen

Hay dos métodos principales de optimización: Exact y aproximate. Un método exacto bien conocido, algoritmo de rama y atado (B&B) y métodos aproximados, el algoritmo de optimización de la mosca de la fruta basada en la eliminación (EFOA) y el algoritmo de átomo artificial (A3) se utilizan para resolver el problema del vendedor ambulante (TSP). Para 56 destinos, se compararán los resultados de la distancia total, el tiempo de procesamiento y la desviación entre el método exacto y el aproximado donde se encuentre la distancia entre dos destinos es una distancia euclídea y este estudio muestra que la distancia de B&B es 270, la EFOA es 270 y A3 es 288,38, lo que se desvía un 6,81%. Para el aspecto de procesamiento de tiempo, B&B necesita 12,5 días para procesar, EFOA necesita 36,59 segundos, A3 necesita 35,34 segundos. Pero para 29 destinos, el método exacto es más poderoso que el método aproximado.

Descargas

Los datos de descargas todavía no están disponibles.

Biografía del autor/a

Agung Chandra, Universitas Mercu Buana

Department of Industrial Engineering

Christine Natalia, Universitas Katolik Indonesia Atma Jaya Jakarta

Department of Industrial Engineering

Aulia Naro, Universitas Mercu Buana

Department of Industrial Engineering

Referencias

M. Gierszewski, and A. Kozlak, “The Impact of Congestion on The Cost of Public Transport in Starogard Gdanski”, Transport Economics and Logistics, vol. 84, pp. 7-18, 2019. https://doi.org/10.26881/etil.2019.84.01

L. Kavka, I. Dockalikova, Z. Cujan, and G. Fedorko, “Technological and Economic Analysis in Interior Parts Manufacturing”, Advances in Science and Technology Research Journal, vol. 14, no. 3, pp. 204-212, 2020. https://doi.org/10.12913/22998624/122062

F. Jorgensen, and J. Preston, “The Relationship between Fare and Travel Distance”, Journal of Transport Economics and Policy, vol. 41, no. 3, pp. 451-468, 2007.

P. Rietveld, B. Zwart, B. van Wee, and T. van den Horn, “On the Relationship between Travel Time and Travel Distance of Commuters”, European Congress of the Regional Science Association. Zurich, 2016.

J. D. Little, K. G. Murty, and D. W. Sweeney, “An Algorithm for the Traveling Salesman Problem”, Operations Research vol. 11, no. 6, pp. 972-989, 1963. https://doi.org/10.1287/opre.11.6.972

S. Saud, H. Kodaz, and I. Babaoglu, “Solving the Traveling Salesman Problem Using Optimization Algorithms”, IAIT Conference Proceddings. The 9th International Conference on Advances in Information Technology, vol. 2017, pp. 17-32.

I. Droste, “Algorithms for the Traveling Salesman Problem”, Thesis, Universiteit Utrecht. Facuteit Betawetenschappen. Netherland, 2017.

Chandra, A., Setiawan, B.,”Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method,” Jurnal Manajemen Transportasi dan Logistik Vol.05 no.2, 2018. Available at: http://ejournal.stmt-trisakti.ac.id/index.php/jmtranslog.

V. Dimitrijevic, and Z. Saric, “An Efficient Transformation of The Generalized Traveling Salesman Problem into The Traveling Salesman Problem on Diagraphs,” Information Sciences, vol. 102, Issues 1-4, pp. 105-110, 1997. https://doi.org/10.1016/S0020-0255(96)00084-9

P. Baniasadi, M. Foumani, K. Smith-Miles, and V. Ejov, “A Transformation Technique for The Clustered Generalized Traveling Salesman Problem with Applications to Logistics”, European Journal of Operational Research, vol. 285, no. 2, pp. 444-457, 2020. https://doi.org/10.1016/j.ejor.2020.01.053

E. G. Talbi, Metaheuristics; From Design to Implementation, New Jersey: John Wiley and Sons, 2009.

S. Bandaru, and K. Deb, “Metaheuristics Techniques”, In: Sengupta, R.N., Gupta, A., Dutta, J., Decision Science: Theory and Practices”, CRM Press, Taylor and Francis Group, 2016.

G. Zhukova, M. Ulyanov, and M. Fomichev, “Exact Time Efficient Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem”. Business Informatics, vol. 3, no. 45, pp. 20-28, 2018. https://doi.org/10.17323/1998-0663.2018.3.20.28

A. E. Yildirim, and A. Karci, “Application of Traveling Salesman Problem for 81 Provinces in Turkey Using Artificial Atom Algorithm”, 7th International Conference on Advanced Technologies, 2018.

L. Huang, G. C. Wang, T. Bai, and Z. Wang, “An Improved Fruit Fly Optimization Algorithm for Solving the Traveling Salesman Problem”, Frontiers of Information Technology and Electronic Engineering, vol. 18, pp. 1525-1533, 2017. https://doi.org/10.1631/FITEE.1601364

G. Dukic, V. Cesnik, and T. Opetuk, “Order Picking Methods and Technologies for Greener Warehousing” Strojarstvo, vol. 52, no. 1, pp. 23-31, 2010.

A. Chandra, and B. Setiawan, “Minimasi Jalur Distribusi di PT. XYZ dengan Metode Improved Cluster First Route Second”, Jurnal Metris, vol. 20, pp. 11-16, 2019, Available: http://ojs.atmajaya.ac.id/index.php/metris/article/view/1449

E. Balas, and P. Toth, “Branch and Bound Methods fo the Traveling Salesman Problem”, Management Science Research Report no. MSRR 488, 1983.

M. Mataija, M. R. Segic, and F. Jozic, “Solving the Traveling Salesman Problem Using the Branch and Bound Method”, Zbomik Veleucilista u Rjeci, vol.4, no.1, pp. 259-270, 2016.

A. E. Yilidirim, and A. Karci, “Application of Artificial Atom Algorithm to Small Scale Traveling Salesman Problem”, Journal of Soft Computing, vol. 22, pp. 7619-7631, 2017. https://doi.org/10.1007/s00500-017-2735-z

H. Iscan, and M. Gunduz, “Parameter Analysis on Fruit Fly Optimization Algorithm”, Journal of Computer and Communications, vol. 2, no. 4, pp. 137-141, 2014. https://doi.org/10.4236/jcc.2014.24018

E. Duka, “Traveling Salesman Problem Solved by Branch and Bound Algorithm in Lindo Programming”, 2018.https://dx.doi.org/10.2139/ssrn.3152830

Descargas

Publicado

05/13/2021

Cómo citar

Chandra, A., Natalia, C., & Naro, A. (2021). Soluciones comparativas de métodos exáctos y aproximados para el problema de los vendedores ambulantes. Lámpsakos (revista Descontinuada), (25), e–3804. https://doi.org/10.21501/21454086.3804

Número

Sección

Artículos Investigación Científica y Tecnológica