Registro:
| Documento: | Tesis de Grado |
| Título: | Un algoritmo Branch-and-Cut para el AngTSP |
| Autor: | Pousa, Federico Javier |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2013 |
| Fecha en portada: | 2013 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel |
| Director Asistente: | Zabala, Paula Lorena |
| Jurado: | Feuerstein, Esteban Zindel; Marenco, Javier Leonardo |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000700_Pousa |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000700_Pousa.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000700_Pousa |
| Ubicación: | Dep.COM 000700 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Pousa, Federico Javier. (2013). Un algoritmo Branch-and-Cut para el AngTSP. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000700_Pousa |
Resumen:
El objetivo del trabajo es desarrollar un algoritmo exacto para el Problema del Viajante de Comercio Angular basado en un modelo de Programaci´on Lineal Entera. El AngTSP o Problema de Viajante de Comercio Angular consiste en, dada una serie de puntos en el plano, encontrar un ciclo simple que pase por todos los puntos minimizando tanto la distancia recorrida, como la suma de los ángulos de giro realizados. La función objetivo de este problema tiene dos parámetros alfa y beta para indicar qué importancia se le quiere dar a la minimización de las distancias, y que importancia se le quiere dar a la minimización de la suma de los ángulos. El AngTSP encuentra sus aplicaciones en situaciones donde el ángulo de giro es costoso o prohibitivo, siendo el ejemplo más emblemático el diseño de trayectorias en robótica en donde el tiempo de giro no es despreciable respecto del tiempo total de recorrido. Para diseñar un algoritmo para este problema se comenzó por estudiar los modelos presentes en la literatura para el Problema de Viajante de Comercio (TSP, travelling salesman problem), el cual es un caso particular del problema a tratar, que se obtiene cuando se le da total importancia a las distancias y ninguna importancia a los ángulos. Es por esta relación entre los problemas que es lógico creer que las formulaciones con buen desempeño para el TSP, también pueden tener buena performance en el AngTSP. Se realizaron pruebas de los diferentes modelos sobre varias instancias, para finalmente elegir, según ciertos criterios, el mejor modelo entre los estudiados. Una vez elegida la formulación preliminar se continuó con el diseño de un algoritmo branchand-cut, realizándose los siguientes pasos: Se generaron dos heur´ısticias iniciales y se combinaron con dos metameur´ısticas de b´usqueda local para obtener cotas primales de calidad para comenzar la ejecución del branch-and-cut. Se realizó un estudio poliedral sobre la formulación para conseguir una más ajustada. Se conjeturó una caracterización de las igualdades del sistema minimal de la cápsula convexa de las soluciones factibles y se desarrollaron varias familias de desigualdades válidas con sus respectivos algoritmos de separación. Se diseñaron tres heurísticas primales con dos variaciones posibles para cada una. Se analizaron diferentes opciones para la selección de branching y la selección de nodo en el árbol de branch-and-cut. En cada una de las secciones mencionadas se realizó un estudio cualitativo de las diferentes opciones barajadas para poder realizar una decisión sobre qué opción es más beneficiosa para el algoritmo. Por último, se evaluó la performance del algoritmo en diferentes instancias que muestran que la técnica propuesta es eficiente.
Citación:
---------- APA ----------
Pousa, Federico Javier. (2013). Un algoritmo Branch-and-Cut para el AngTSP. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000700_Pousa
---------- CHICAGO ----------
Pousa, Federico Javier. "Un algoritmo Branch-and-Cut para el AngTSP". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2013.https://hdl.handle.net/20.500.12110/seminario_nCOM000700_Pousa
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000700_Pousa.pdf
Distrubución geográfica
