Cúmulos de Partículas para la Resolución del TSP

• Autores: Ricardo G. Campuzano, Alberto Gómez Gómez , Raúl Pino Díez , José Parreño Fernández
• Localización: XXX Congreso Nacional de Estadística e Investigación Operativa y de las IV Jornadas de Estadística Pública: actas, 2007, ISBN 978-84-690-7249-3
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • En este art¶³culo se propone una nueva t¶ecnica metaheur¶³stica para la resolu- ci¶on del problema del viajante de comercio basada en una b¶usqueda local guiada mediante c¶umulos de part¶³culas. La aportaci¶on m¶as importante de este trabajo consiste en el desarrollo de una estrategia basada en c¶umulos de part¶³culas para la resoluci¶on de problemas de optimizaci¶on combinatoria, y m¶as en concreto del TSP. Una vez determinada la forma de proceder del nuevo m¶etodo se comprue- ban los resultados proporcionados por el m¶etodo ante un conjunto de problemas de test sim¶etricos propuestos por distintos autores. Posteriormente se contrastan los resultados ofrecidos por el m¶etodo con los que se obtienen al aplicar algu- nas t¶ecnicas bien conocidas de b¶usqueda local no guiada, pudiendo observarse que el nuevo m¶etodo proporciona una mejora sobre estas tµEcnicas. Por ¶ultimo, se comprueba la aportaci¶on de los c¶umulos de part¶³culas sobre el proceso de b¶usqueda local observando una mejora respecto a los resultados obtenidos con una b¶usqueda local simple. Los resultados experimentales indican que el nue- vo m¶etodo ofrece buenos resultados en los problemas del viajante de comercio sim¶etricos. Esta comparaci¶on se realiza con un conjunto de problemas de test tomados de TSPLIB, en concreto se ha probado con los problemas de test: Gr17 Fri26 Att48 St70 Eil76 y se ha conseguir resolverlos de forma exacta en tiempos que oscilan entre los 2 y 3 minutos.