BMTSP: optimización
Comparativa de cuatro enfoques de optimización para el Bounded Multiple TSP sobre instancias TSPLIB.
01 Problema y contexto
El Bounded Multiple TSP reparte un conjunto de ciudades entre varios viajantes que salen de un mismo depósito, con una cota inferior y otra superior por ruta. Es NP-difícil y traduce directamente a ruteo de flotas. Como ningún método domina a los demás, la pregunta útil no es cuál algoritmo lo resuelve, sino qué gana y qué pierde cada familia bajo un mismo presupuesto experimental.
El Bounded Multiple TSP reparte un conjunto de ciudades entre varios viajantes que salen de un mismo depósito, con una cota inferior y otra superior de ciudades por ruta. Es un problema NP-difícil que traduce directamente a ruteo de flotas, donde esas cotas representan la duración de una jornada y la capacidad de un vehículo. Como ningún método domina a los demás, la pregunta útil no es cuál algoritmo lo resuelve, sino qué gana y qué pierde cada familia de enfoques bajo un mismo presupuesto experimental.
02 Solución
Un protocolo experimental común a cuatro enfoques: un modelo MIP en AMPL/CPLEX como referencia exacta, LKH-3 como estado del arte, un Sistema Inmune Artificial implementado desde cero y una línea base de Vecino Más Cercano con 2-Opt. Cinco instancias de TSPLIB, diez ejecuciones independientes por instancia con las semillas registradas, y reporte de la dispersión completa en lugar de solo la mejor corrida.
- Formulación del modelo MIP del BMTSP en AMPL, resuelto con CPLEX bajo límite de tiempo, como referencia de solución exacta.
- Implementación desde cero de un Sistema Inmune Artificial: población de 50 anticuerpos, 10 clones por anticuerpo, tres operadores de mutación y penalización explícita de las soluciones que violan las cotas.
- Línea base heurística de Vecino Más Cercano seguida de búsqueda local 2-Opt, con verificación de factibilidad antes de reportar cualquier costo.
- Ejecución de LKH-3 sobre las mismas instancias, para medirse contra el estado del arte y no contra un rival débil.
- Protocolo experimental común a los cuatro métodos: cinco instancias TSPLIB (berlin52, eil51, eil76, kroA100, rat99) y diez ejecuciones independientes por instancia con semillas registradas.
- Registro por iteración del mejor fitness y del tiempo acumulado, consolidado con mínimo, máximo, media y desviación estándar.
03 Resultados
Cifras verificables en el repositorio y su documentación:
04 Cómo está construido
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.
05 Decisiones éticas
- La semilla de cada ejecución se guarda junto a sus resultados, de modo que cualquier corrida puede reproducirse y auditarse por separado.
- Se reportan las diez ejecuciones con su dispersión, no solo la mejor, para no presentar un resultado afortunado como comportamiento típico.
- La metaheurística propia se mide contra LKH-3, el mejor solver disponible, en lugar de contra una línea base cómoda.
06 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.
07 Limitaciones
Las instancias de TSPLIB son euclidianas, simétricas y de tamaño moderado, entre 51 y 100 nodos. Eso las hace comparables y reproducibles, pero deja fuera lo que hace difícil el ruteo real: calles de un sentido, tiempos que dependen de la hora, ventanas horarias y flotas de cientos de vehículos. Dos límites del método propio conviene declararlos: la penalización de infactibilidad es un valor fijo y muy alto, lo que desincentiva explorar la frontera de lo factible, y la línea base de Vecino Más Cercano con 2-Opt es determinista y corre una sola vez, así que no tiene dispersión propia contra la cual contrastar la varianza de la metaheurística.