Manual de usuario de la aplicación para la resolución de problemas del viajante de comercio o TSP
Introducción
El usuario podrá introducir los valores correspondientes a las distancias entre las ciudades que desee y visualizar, en forma de grafo etiquetado, la solución del Problema del Viajante de Comercio asociado a dichos datos.
Esta aplicación calcula la ruta más corta posible entre el conjunto de ciudades que hayan sido introducidas. Dicha ruta consiste en pasar por cada una de las ciudades en una sola ocasión, hasta acabar regresando a la ciudad de la que partimos inicialmente.
La estructura de la aplicación se organiza en cuatro pestañas:
- Información: en la que se detalla toda la información necesaria sobre la aplicación
- Datos: la cual muestra el conjunto de datos cargados en la aplicación
- Gráficos: dónde podremos contemplar de manera gráfica nuestra solución
- Solución: la cual muestra la solución del problema
Uso de la aplicación
En primer lugar, introduzca los datos en la aplicación. Estos datos deberán ser introducidos a partir de un fichero .csv, dicho archivo debe organizarse en cuatro columnas diferenciadas que se detallan a continuación:
- En la primera columna del fichero se incluirán, de forma ordenada, los nombres de cada una de las distintas ciudades.
- En las tres columnas restantes, se describirán cada uno de los distintos caminos que forman parte del problema.
Distribuido en filas, en cada una de ellas tendremos la siguiente información:
- El origen del camino, expresado por el número correspondiente a su posición, \( i \).
- El destino, con su posición correspondiente, \( j \).
- y la distancia de dicho camino, \( d \).
Una vez introducidos los datos, seleccione la acción que desee: cargar los datos o modificar aquellos que desee. Además también dispone de la opción de introducir nuevos valores.
Una vez seleccionada la acción, pulse Hacer, en cuyo caso la aplicación procederá a resolver el Problema del Viajante de Comercio asociado a los datos cargados.
En la pestaña Datos podrá visualizar el conjunto de datos que ha cargado.
Pulsando la pestaña Gráfico, visualizará el grafo correspondiente a la ruta solución del problema. Por ejemplo, para los datos anteriores, obtendrá:
En cada uno de los nodos, estará escrito el nombre de cada una las ciudades.
Por último, si pulsa la pestaña Solución, obtendrá la ruta solución del problema, ordenadas en la secuencia de visita.
Junto a la ruta, obtendrá el coste óptimo que nos da el Problema del Viajante de Comercio para nuestro conjunto de ciudades y distancias.
En el caso de que se tratase de un problema sin solución, la aplicación no devolverá ninguna solución, lo cuál se debe interpretar como que no existe una ruta entre las ciudades introducidas, o bien, podría modificar el conjunto de datos como se ha explicado anteriormente.
