Optimización del BMTSP

01 Resumen

Estudio experimental del Bounded Multiple Traveling Salesman Problem (BMTSP), variante NP-hard del TSP con múltiples vendedores y cotas de tamaño por ruta. Implementa y compara cuatro enfoques: un modelo exacto de programación entera mixta en AMPL/CPLEX, el solver heurístico LKH-3, una metaheurística propia de Sistema Inmune Artificial (AIS) y una heurística de Vecino Más Cercano con refinamiento 2-Opt. Los experimentos se automatizan en Python sobre cinco instancias clásicas de TSPLIB, con múltiples ejecuciones por instancia y resultados exportados a CSV.

02 Resultados

Cifras verificables en el repositorio y su documentación:

03 Aspectos destacados

• ✦Modelo matemático MIP del BMTSP formulado en AMPL y resuelto con CPLEX bajo límite de tiempo.
• ✦Metaheurística de Sistema Inmune Artificial implementada desde cero, con clonación, tres operadores de mutación y ejecución paralela.
• ✦Heurística propia de Vecino Más Cercano + búsqueda local 2-Opt como línea base constructiva.
• ✦Pipeline experimental automatizado sobre 5 instancias TSPLIB (berlin52, eil51, eil76, kroA100, rat99) con 10 ejecuciones por instancia.
• ✦Comparación cuantitativa de costos frente al benchmark estado del arte LKH-3, documentada en el README.

04 Capturas