Optimización numérica y combinatoria
Autores:
- Alejandro Gómez Franco
- Santiago Acevedo Cacua
- Jesus Miguel Porto Lopez
- Juan Felipe Cadavid Ruiz
Universidad: Universidad Nacional de Colombia
Resumen ejecutivo
Introducción
Parte 1: Optimización numérica
Funciones de prueba
Función de Rastrigin
La Función de Rastrigin es una función no convexa ampliamente utilizada como problema de prueba en optimización. Se caracteriza por ser multimodal, es decir, posee múltiples mínimos locales, lo que la convierte en un desafío para los algoritmos de optimización. Su mínimo global se encuentra en el origen, donde la función toma el valor cero.
Función de Rosenbrock
La función de Rosenbrock, también conocida como la función del valle o función de la banana de Rosenbrock, es una función no convexa utilizada frecuentemente como problema de prueba en optimización. Se caracteriza por tener un valle estrecho y curvado que conduce al mínimo global, lo que la convierte en un desafío para los algoritmos de optimización basados en gradiente con tasa de aprendizaje fija. Su mínimo global se encuentra en el punto (1, 1), donde la función toma el valor cero.
Metodos de optimización implementados
Descenso por gradiente
El descenso por gradiente es un método determinista que busca minimizar una función mediante actualizaciones iterativas en la dirección opuesta al gradiente. En donde se utilizaron los siguientes parámetros
- Función de Rastrigin
- Función de Rosenbrock
Algoritmo genético
Los algoritmos genéticos son métodos heurísticos inspirados en la evolución natural, donde una población de soluciones evoluciona mediante operadores de selección, cruce y mutación.
- Función de Rastrigin
- Función de Rosenbrock
Optimización de partículas (PSO)
La optimización por enjambre de partículas modela el comportamiento colectivo de un grupo de partículas que se mueven en el espacio de búsqueda guiadas por su mejor posición individual y global.
- Función de Rastrigin
- Función de Rosenbrock
Evolución diferencial (DE)
La evolución diferencial es un método heurístico basado en la combinación de soluciones mediante operaciones de mutación y recombinación para generar nuevas soluciones candidatas.
- Función de Rastrigin
- Función de Rosenbrock
Resultados
Dos dimensiones
- Función de Rastrigin
De igual forma, se tiene la animación correspondiente de la trayectoria que tuvo el dominio de la función para encontrar el valor de convergencia para cada método utilizado
- Función de Rosenbrock
En donde la trayectoria que tuvo cada función se puede evidenciar en el siguiente gráfico en escala logarítmica
Tres dimensiones
- Función de Rastrigin
En donde la trayectoria que tuvo cada función se puede evidenciar en el siguiente gráfico
- Función de Rosenbrock
En donde la trayectoria de convergencia de cada método se puede evidenciar en el siguiente gráfico
Dado que la función de Rosenbrock en tres dimensiones vive en un espacio de cuatro dimensiones, no es posible visualizar la superficie directamente. En cambio, se presentan las trayectorias de cada algoritmo en el espacio (x1,x2,x3), mostrando el camino recorrido desde la condición inicial hasta la solución encontrada en comparación con el óptimo global en (1,1,1).
¿Qué aportaron los métodos de descenso por gradiente y qué aportaron los métodos heurísticos?
El descenso por gradiente demostró ser competitivo únicamente cuando la función no presentaba mínimos locales relevantes, por ejemplo en Rastrigin no logra converger al mínimo global, mientras que en Rosenbrock 2D gradiente logra converger luego de múltiples iteraciones al mínimo de la función, esto indica que para funciones con un valle continúo hacia el óptimo de la función el gradiente navega adecuadamente como ocurrió con un valor de 0.095 comparado al evolutivo, con un 0.508. En Rosenbrock 3D por otro lado, el resultado de la gradiente fue el peor de todos los métodos, evidenciando que la geometría del valle en dimensiones altas va a superar su capacidad de convergencia.
Con esto, los métodos heurísticos mostraron una ventaja clara en Rastrigin gracias a la capacidad de exploración:
- PSO fue el más consistente, logrando alcanzar el mínimo local en Rastrigin 2D, Rastrigin 3D y Rosenbrock 2D.
- DE fue el más robusto en dimensiones altas, siendo el de mejor resultado en resultados en Rastrigin 3D y Rosenbrock 3D.
- El algoritmo evolutivo superó al gradiente, sin embargo fue el menos efectivo dentro de los métodos heurísticos, sin destacar en ninguno en particular.
Parte 2: Optimización combinatoria
Planteamiento del problema
El Problema del Vendedor Viajero (TSP, por sus siglas en inglés) es un problema clásico de optimización combinatoria en el que se busca encontrar el recorrido de menor costo que visita un conjunto de ciudades exactamente una vez y regresa al punto de partida (Dorigo & Stützle, 2004). En esta parte del trabajo, el TSP se aplica a las 32 capitales estatales de México, con Ciudad de México (CDMX) como punto de inicio y fin obligatorio.
La función de costo por tramo ij integra tres componentes reales del desplazamiento (Gómez Franco et al., 2026):
donde Pij es el costo de peajes en MXN, dij la distancia real en carretera en km, η la eficiencia del vehículo en km/L, pcomb el precio del combustible en MXN/L, tij el tiempo de conducción en horas, y w el salario por hora del vendedor en MXN/h.
El parámetro w se estudia en tres niveles que representan distintos perfiles del vendedor, tal como lo exige el enunciado del trabajo: salario mínimo ($26.50/h), salario medio ($88.75/h) y salario profesional ($200.00/h), basados en tarifas del IMSS e INEGI para 2025.
La Figura 20 muestra la distribución geográfica de las 32 capitales sobre el territorio mexicano. La densidad de ciudades en el centro del país y el aislamiento geográfico de La Paz (Baja California Sur) son características que influyen directamente en la estructura de las soluciones óptimas.
Metodología
Vehículo y parámetros de combustible
Se seleccionó el Toyota Corolla 2024 como vehículo de referencia, con una eficiencia de 25.0 km/L en carretera y gasolina Magna a $23.67 MXN/L, precio promedio nacional reportado por la Comisión Reguladora de Energía (CRE) para 2025.
Obtención de distancias reales: OSRM
Las distancias en carretera y los tiempos de conducción entre cada par de capitales se obtuvieron mediante el OSRM Table API (Open Source Routing Machine), un motor de ruteo de código abierto basado en datos de OpenStreetMap que calcula rutas óptimas para vehículos (Project OSRM, 2024). La consulta se realizó como una única petición HTTP con las 32 coordenadas simultáneamente, lo que devuelve la matriz completa de 32×32 pares sin costo y sin registro de usuario.
Corrección del ferry de Baja California Sur.
OSRM incluye la ruta del trasbordador Topolobampo–La Paz en su red vial pero no conoce el costo del boleto ni el tiempo real de espera. Para todos los pares que involucran La Paz, excepto La Paz–Mexicali (que cuenta con conexión terrestre continua por la carretera Transpeninsular), se añadieron $2,200 MXN al costo de peaje y 11 horas al tiempo de viaje (9 horas de travesía más 2 horas de espera de embarque), con base en las tarifas vigentes de Baja Ferries para 2025.
Obtención de peajes reales: CAPUFE
Los costos de casetas de cobro se obtuvieron de tarifascapufe.com.mx, el sitio oficial de información de la CAPUFE (Caminos y Puentes Federales). Mediante ingeniería inversa del código JavaScript del sitio, se identificó el endpoint AJAX interno get_polyline_googleAPI, que recibe coordenadas geográficas de origen y destino y devuelve en formato JSON la lista de casetas en la ruta, con sus costos en efectivo y con tag IAVE. Este enfoque evita la necesidad de automatización de navegador (Selenium), reduciendo el tiempo de recolección a aproximadamente 12 minutos para los 496 pares únicos. Los resultados se almacenaron en caché local para reproducibilidad.
Se consultaron los 496 pares únicos (32 x 31 / 2) correspondientes a las combinaciones de las 32 capitales. El 100 % de las consultas fue exitoso (496/496 pares con datos reales). Los estadísticos descriptivos de los peajes obtenidos se presentan en la Tabla 1, y las cuatro submatrices resultantes se visualizan en la Figura 21.
Las tres matrices de costo total C(i, j; w), una por nivel de salario, se presentan en la Figura 22. Se observa que al aumentar el salario el gradiente de color se intensifica para los pares más distantes, reflejando el mayor peso del componente de tiempo en la función objetivo.
Algoritmo de Colonia de Hormigas (ACO)
Se implementó el Ant System (AS) de Dorigo (1996), utilizando como base la librería de Berroa (2019) disponible en GitHub, con una extensión propia para registrar el mejor tour en cada iteración y habilitar el criterio de parada anticipada (early stopping). La probabilidad de que una hormiga en la ciudad i elija la ciudad j es:
donde τij son las feromonas, ηij la visibilidad heurística, y α, β los pesos de cada componente. Las feromonas se actualizan al final de cada iteración con evaporación ρ. Los hiperparámetros empleados se presentan en la Tabla 2.
Algoritmo Genético (GA)
Se implementó un GA con representación de permutación, siguiendo la estructura del notebook de referencia del curso (Ospina Arango, 2026): pob_inicial_perm, pob_eval_perm, mutacion_perm, cruzamiento_perm, next_gen_perm y mi_ga_tsp.
Los operadores se adaptaron al TSP con las siguientes decisiones de diseño:
- Cruzamiento Order Crossover (OX): el cruzamiento estándar de punto de corte genera permutaciones inválidas (ciudades repetidas) en el TSP. El OX preserva el orden relativo de las ciudades no incluidas en el segmento heredado del primer padre (Davis, 1985).
- Mutación por inversión de segmento: equivalente al movimiento 2-opt, invierte un sub-segmento aleatorio del tour, lo que tiende a eliminar cruces en la ruta.
- CDMX fija en posición 0: todos los tours se construyen comenzando en Ciudad de México. Los operadores de cruzamiento y mutación operan únicamente sobre las posiciones 1 a 31.
Resultados
Desempeño comparativo ACO vs. GA
La Tabla 3 resume los resultados obtenidos para los tres niveles de salario. Las figuras citadas en esta sección se encuentran en el repositorio del proyecto (Gómez Franco et al., 2026).
Las curvas de convergencia de ambos algoritmos se presentan en la Figura 23. Se observa que ACO alcanza soluciones de buena calidad en muy pocas iteraciones (convergencia en iteraciones 49–72), mientras que GA desciende gradualmente durante cientos de generaciones antes de estabilizarse.
Las mejores rutas encontradas por cada algoritmo se muestran en la Figura 24. Para los salarios mínimo y medio, las rutas de GA y ACO son estructuralmente similares aunque difieren en el orden de visita de algunas ciudades del centro del país. Para el salario profesional, donde el tiempo domina el costo, ambos algoritmos tienden a rutas más directas geográficamente.
Composición del costo de la solución óptima
La Figura 25 muestra la descomposición del costo total del tour óptimo en sus tres componentes para cada nivel de salario. El combustible es el componente dominante para el salario mínimo (46.3 %), mientras que el costo de tiempo escala hasta convertirse en el componente mayoritario para el salario profesional (61.9 %).
Comparación de costo y tiempo de ejecución
La Figura 26 presenta simultáneamente el costo del tour óptimo y el tiempo de ejecución de cada algoritmo. GA es consistentemente más rápido en tiempo de cómputo (0.8–1.7 s frente a 2.7–4.4 s de ACO), a pesar de requerir más iteraciones, porque cada generación del GA es computacionalmente más liviana que una iteración de ACO con 40 hormigas.
Discusión
Los resultados muestran que GA obtuvo la mejor solución en dos de los tres escenarios (salario mínimo y medio), mientras que ACO fue superior para el salario profesional. Las diferencias entre ambos algoritmos son pequeñas (de 0.4% a 2.4%), lo que sugiere que ambos convergen a regiones similares del espacio de soluciones, aunque por caminos distintos.
Un hallazgo relevante es el efecto del parámetro de salario sobre la estructura de la ruta óptima. Cuando el costo de tiempo pesa poco (salario mínimo, 18.3% del total), la ruta prioriza minimizar peajes y combustible, lo que puede llevar a desvíos que eviten casetas costosas. Cuando el salario es alto, el tiempo se vuelve el componente dominante (61.9% del costo total, Figura 6) y la ruta converge hacia el camino más rápido independientemente del número de casetas. Este resultado tiene implicaciones prácticas directas para empresas que decidan modelar el costo real de una fuerza de ventas en campo.
Respecto al comportamiento de los algoritmos (Figura 4), ACO exhibe convergencia prematura: encuentra soluciones de buena calidad rápidamente gracias al mecanismo de refuerzo de feromonas, pero la diversidad de la colonia se reduce y la búsqueda se estanca. GA mantiene diversidad poblacional durante más tiempo gracias al cruzamiento OX, lo que le permite seguir mejorando hasta generaciones tardías (308 - 649 según el nivel de salario). Esto explica por qué GA supera a ACO en los dos primeros escenarios a pesar de tener un tiempo de ejecución menor.
La corrección manual del ferry de Baja California Sur es una limitación metodológica reconocida: se asumió siempre la ruta Topolobampo - La Paz, que es la más corta, pero dependiendo del origen del recorrido podría ser más conveniente la ruta Mazatlán - La Paz. Una mejora futura sería modelar ambas opciones como aristas alternativas en la matriz de costos.
Prompts principales utilizados
Durante el desarrollo de la parte 1 del trabajo se utilizó como herramienta principal Chat GPT como apoyo de solución de errores, entendimiento de algunos métodos, organización de la información. Por otro lado, para la parte 2, se utilizó Claude bajo el mismo fin. En donde los prompt con más impacto fueron lo siguientes:
Prompt 1: “Como hago para que el número random sea fijo para que haya reproducibilidad”
Prompt 2: “¿Me puedes dar un código como para ver una gráfica de cómo se ven los tres métodos?”
Prompt 3: “Cómo puedo hacer un gif teniendo en cuenta cada método utilizado según la trayectoria que tuvo el dominio de la función”
Prompt 4: “Me puedes ayudar a organizar el docstring de las funciones que te voy a pasar para que quede más claro”
Prompt 5: “Como se ve en la imagen, actualmente varias de las mejores rutas tienen un trayecto directo de La Paz a Chihuahua. El problema es que esta ruta incluye un ferri, cuyo costo y tiempo no es tenido en cuenta. Además, Mexicali es la única ciudad que sí se conecta a La Paz en auto sin necesidad de ferri.”
Prompt 6: “¿Cual sería un early stop bueno para ACO y GA? [Se adjuntan datos de corridas iniciales, con early stop en 200 y max iteraciones/genes en 2000]”
Prompt 7: “Cómo puedo hacer un gif teniendo en cuenta cada método utilizado según la trayectoria que tuvo el dominio de la función, este gif debe tener de fondo el mapa de Mexico”
Prompt 8: “https://tarifascapufe.com.mx/. Puedes hacer un script para que extraiga desde esta página por medio de la api web scrapping para obtener la data necesaria para esto? [Se adjunta resumen del problema y explicación de la matriz de costos]’
Anexos
Anexo 1: Repositorio Github
Anexo 2: Colab
Anexo 3: Contribuciones
Santiago Acevedo Cacua
Alejandro Gómez Franco
Jesus Miguel Porto Lopez
Juan Felipe Cadavid Ruiz
Referencias
Anthropic. (2026). Claude (versión Sonnet 4.6) [Modelo de lenguaje de gran escala]. https://www.anthropic.com
Baja Ferries. (2025). Tarifas de pasaje y vehículos. https://www.bajaferries.com.mx
Berroa, J. (2019). Ant Colony Optimization [Software]. GitHub. https://github.com/johnberroa/Ant-Colony-Optimization
Caminos y Puentes Federales [CAPUFE]. (2025). Tarifas de casetas de cobro. https://tarifascapufe.com.mx
Comisión Reguladora de Energía [CRE]. (2025). Precios de gasolina y diésel. Gobierno de México. https://www.gob.mx/cre
Gómez Franco, A., Cadavid Ruiz, J. F., Porto López, J. M., & Acevedo Cacua, S. (2026). Optimización numérica y combinatoria. GitHub. https://github.com/jcadavid/RNABI_2026_1_P_1_Optimizacion_Heuristica
Instituto Mexicano del Seguro Social [IMSS]. (2025). Salarios mínimos y tarifas vigentes. https://www.imss.gob.mx
Instituto Nacional de Estadística y Geografía [INEGI]. (2025). Marco geoestadístico nacional: Capitales estatales. https://www.inegi.org.mx
OpenStreetMap contributors. (2024). OpenStreetMap [Base de datos geoespacial]. https://www.openstreetmap.org
Ospina Arango, J. D. (2026). Curso de Redes neuronales y Algoritmos Bioinspirados. Departamento de Ciencias de la Computación y de la Decisión, Universidad Nacional de Colombia.
Project OSRM. (2024). Open Source Routing Machine: Table service API (v5.24.0). https://project-osrm.org/docs/v5.24.0/api/#table-service
Toyota de México. (2024). Corolla 2024: Especificaciones técnicas. https://www.toyota.com.mx/corolla
Wikipedia. (2025, abril 20). Rastrigin function. https://en.wikipedia.org/wiki/Rastrigin_function
Wikipedia. (2025, octubre 20). Rosenbrock function. https://en.wikipedia.org/wiki/Rosenbrock_function
Comentarios
Publicar un comentario