Esta página explica como el servicio Open Street utiliza herramientas matemáticas, especialmente la teoría de grafos para describir las problemáticas del comerciante viajero que se esconden detrás de cada cálculo de optimización.
Esta permite modelar y luego resolver los problemas tal y como usted los ingresa en nuestro servicio o nuestras API. Tomemos el ejemplo de un trayecto que debe pasar por París, Marsella, Lyon y Toulouse.
Este trayecto de cuatro ciudades es el ejemplo más simple posible, que puede ser descrito por una grafo compuesta por nudos y enlaces. Aquí los nudos están representados por los discos azules y los enlaces por líneas negras.
Grafo con 4 puntos
El grafo anterior esta muy simplificado porque en la práctica, todos los enlaces son dobles. De hecho, la distancia entre París y Toulouse no es exactamente la misma que entre Toulouse y París, debido principalmente a las calles de un solo sentido y cruces de autopistas asimétricas. Se dice en este caso que el gráfico está «orientado».
Así, la combinación indica que existen 24 rutas diferentes posibles. Al establecer una ciudad como punto de partida esta cifra se reduce a 6.
Combinaciones posibles para el problema del comerciante viajero
Para una cantidad tan limitada, podemos facilmente visualizar estas 6 posibilidades. Es un tablero de 6 por 4.
Tablero de posibilidades ilustrando el problema del comerciante viajero
Aumentemos a 40 la cantidad de ciudades a visitar. El gráfico correspondiente contendrá 40 nudos enlazados unos con otros por enlaces de doble sentido. La combinación indica que el número de posibilidades diferentes para efectuar el trayecto es astronómico. Existe en efecto 203 978 820 811 97 443 358 640 281 739 902 897 356 800 000 000.
El factor utilizado para calcular el número de posibles rutas para la optimización (40 puntos)
La representación en forma de tabla contiene 40 columnas y 2 1046 líneas. La comparación de todas estas posibilidades por el ordenador más potente del mundo tomaría siglos. En la práctica, es imposible a partir de algunas decenas de ciudades solamente.
Tablero de posibildiades para una optimización de 40 puntos
Sin embargo el servicio Open Street permite optimizar itineararios de hasta varias millares de ciudades. No tratamos de comparar todas los itinerarios posibles, pero utilizamos los algoritmos más sofisticados que podamos ofrecerle para su beneficio.
