Algoritmo del Plano de Corte en el Problema del Vendedor Viajero

Según lo descrito en el artículo Solución del Problema del Vendedor Viajero, una de las situaciones potenciales a la que nos podemos enfrentar es que la solución de asignación obtenida represente un subcircuito, lo cual naturalmente no da respuesta a la problemática que el modelo de agente viajero desea abordar. En este contexto existen diversas estrategias algorítmicas que permiten enfrentar esta situación entre las cuales destaca el Algoritmo de Plano de Corte.

La idea del Algoritmo del Plano de Corte es agregar un conjunto de restricciones que, cuando se incorporan al Problema de Asignación garanticen evitar la formación de un subcircuito. Consideremos un problema con n ciudades, asociar una variable continua u_{j}\geq 0 con las ciudades 2,3,…,n. A continuación definir un conjunto de restricciones adicionales de la siguiente forma:

restricciones-plano-de-cort

Estas restricciones al añadirse al Modelo de Asignación, eliminarán todas las soluciones de subcircuito de forma automática, pero no eliminarán alguna solución de circuito.

A modo de ejemplo consideremos nuevamente el problema de secuenciamiento de la producción donde nos interesa determinar el orden en el cual se deben producir 4 colores de pintura.

tabla-tiempos-setup-pintura

A continuación se define un modelo de optimización haciendo uso del lenguaje de programación matemática AMPL. Para ello se puede utilizar un editor de texto como Bloc de Notas o WordPad. La siguiente imagen muestra la sintaxis utilizada en la definición del modelo del ejemplo propuesto donde se incorpora las restricciones que evitan los subcircuitos. Notar que es importante guardar el archivo con el formato adecuado (.mod) para lo cual simplemente en el caso de utilizar Bloc de Notas seleccionamos «Archivo», seguido de «Guardar como …» y luego en «Nombre» se ingresa un nombre arbitrario seguido de .mod (por ejemplo, modelo.mod).

modelo-ampl-plano-de-corte

El siguiente paso es generar un nuevo archivo con los datos o parámetros del problema. Básicamente aquellos que resumen el tiempo (en minutos) necesarios para la limpieza al realizar un cambio de colores, según se describe al inicio de este artículo. Notar que para evitar aquellas asignaciones infactibles (como que a un color le precede el mismo en la secuencia) se asignan «constantes grandes» a los elementos en la diagonal. El archivo se procesa y guarda de forma similar al caso del modelo pero con la extensión .dat (por ejemplo, matriz.dat).

datos-ampl-plano-de-corte

Finalmente será necesario construir un tercer archivo con extensión .run que provee de instrucciones adicionales para efectos de la resolución computacional y que facilita la interpretación de los resultados (por ejemplo, solucion.run).

solucion-run-ampl-plano-de-

Una vez definido el modelo, datos y archivo run, podemos utilizar un solver de Programación Entera Mixta de los disponibles en el Servidor NEOS. En particular recomendamos utilizar el solver XpressMP donde se deberá adjuntar los archivos con extensión .mod, .dat y .run (respectivamente) según se muestra a continuación (recordar que el nombre asignado al archivo es arbitrario, no así su extensión).

xpressmp-neos

Luego seleccionamos «Submit to NEOS» y los resultados se mostraran en el navegador de Internet, además de recibir un informe de respuestas en la dirección de correo electrónico que ingresamos. La siguiente imagen muestra un extracto de dichos resultados:

solucion-ampl-plano-de-cort

Notar que XpressMP encuentra como recorrido óptimo la secuencia 1-2-4-3-1, es decir, corresponde a producir en el siguiente orden: Blanco, Amarillo, Rojo, Negro, con un tiempo total de setup de 98 minutos.