Soluciones comparativas de métodos exáctos y aproximados para el problema de los vendedores ambulantes
DOI:
https://doi.org/10.21501/21454086.3804Palabras clave:
Branch and Bound, Elimination-based Fruit Fly Optimization, Artificial Atom Algorithm, Traveling Salesman ProblemResumen
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
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
Cómo citar
Número
Sección
Licencia
Derechos de autor 2021 Lámpsakos
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
De conformidad con las normas nacionales e internacionales sobre derechos de autor, las políticas de publicación de la Universidad Católica Luis Amigó y de la revista Lámpsakos (indexada con ISSN: 2145-4086), yo(nosotros), manifiesto(amos):
1. El deseo de participar como articulista(s) y someter a las normas editoriales establecidas por la revista (nombre la revista) el artículo titulado (nombre del artículo),
2. El compromiso de no retirar el artículo hasta no terminar el proceso de edición del número de la revista en curso.
3. Que el artículo es original e inédito y no ha sido postulado o presentado conjuntamente en otra(s) revista(s); por tanto, los derechos del artículo en cuestión no han sido cedidos con antelación y sobre ellos no pesa ningún gravamen ni limitación en su uso o utilización.
4. La inexistencia de conflicto de interés con institución o asociación comercial de cualquier índole.
5. Haber incorporado las citas y referencias de otros autores, tendientes a evitar el plagio. En consecuencia, afirmo que de ser publicado el artículo, no se violarán derechos de autor, de propiedad intelectual o de privacidad de terceros. Así mismo, de ser necesario, existe forma de evidenciar los permisos respectivos sobre derechos de autor originales para los aspectos o elementos extraídos de otros documentos como textos de más de 500 palabras, tablas, gráficas, entre otros. En caso de presentarse cualquier tipo de reclamación o acción por parte de un tercero en cuanto a los derechos de autor sobre el artículo, el(los) autor(es) asumirán toda la responsabilidad, y saldrán en defensa de los derechos aquí cedidos. Por tanto, para todos los efectos, la revista Lámpsakos de la Fundación Universitaria Luis Amigó actúa como un tercero de buena fe.
6. Que en el evento de publicarse el artículo, cedo(emos) a título gratuito y con carácter de exclusividad la integridad de los derechos patrimoniales así como los derechos de impresión, reimpresión y de reproducción por cualquier forma y medio, sin ninguna limitación en cuanto a territorio se refiere, en favor de la revista Lámpsakos de la Universidad Católica Luis Amigó.
7. Reconocer como coautores y/o colaboradores, a todos quienes participaron en ese rol y no se ha omitido a ninguno.
