Ejemplo resuelto y comentado de circuito por ciudades colombianas

Un viajante de comercio que vive en Las Lomitas parte de su casa y debe recorrer las ciudades: El Reyuno, San Homero, Cubillos, Dolores y Quilapaguay para hacer sus ventas. Finalmente, debe regresar a su casa. Como tiene varias alternativas para recorrer las ciudades, se quiere encontrar en qué orden debe hacer su recorrido para minimizar el trayecto total recorrido. La tabla a continuación da las distancias en kilómetros entre las ciudades cuando existe conexión entre ellas. Obsérvese que en este caso la matriz es simétrica.

Las LomitasEl ReyunoSan HomeroCubillosDoloresQuilapaguay
Las Lomitas834
El Reyuno8159
San Homero17221
Cubillos3573
Dolores
9235
Quilapaguay421335

Solución

Una vez tengamos abierta la aplicación se selecciona la acción "Cargar ejemplos" y se selecciona el ejemplo "ciudades_colombianas.csv". A continuación pinchamos en la pestaña ”Datos” y nos aparece lo siguiente:

Datos ciudades colombianas

Se observa que no se han puesto ni las distancias de una ciudad a sí misma, ni tampoco aquellos caminos imposibles. Si pinchamos en la pestaña ”Solución” nos aparece un mensaje con la secuencia de ciudades a visitar y el coste hace referencia a la distancia total. Es la distancia mínima.

Solución ciudades colombianas

Para el problema que nos atañe la ruta mínima sería de longitud 33 y la secuencia a visitar sería: Las Lomitas, Quilapaguay, Cubillos, San Homero, Dolores, El Reyuno y vuelta a Las lomitas. Para finalizar pinchamos en ”Gráfico” y nos aparece un grafo con el sentido del recorrido a realizar.

Solución gráfica ciudades colombianas

Última modificación: jueves, 9 de julio de 2015, 11:50