El otro día me dio curiosidad saber cuál era la mejor ruta para visitar los 76 pueblos de la isla grande de Puerto Rico. Pensé que tal vez sería una aventura interesante visitar todas las plazas de pueblo con la familia. Ya sabes, crear una ruta nueva de turisteo. Como buen ingeniero industrial decidí modelar y resolver el problema – los detalles de lo que hicimos al final del post. El mapa abajo enseña la ruta óptima para visitar las plazas. Me quedé patidifuso al obtener los resultados; son aproximadamente 650 millas (965.606 kilómetros) para visitar todas las plazas. Según el reembolso por milla del IRS la vueltita costaría casi $375. Pongamos esta distancia en contexto. La competencia de ciclismo de tres días llamada La Vuelta a Puerto Rico que básicamente le da la vuelta a Puerto Rico por la costa es de aproximadamente 375 millas (603.5 km). O sea, que la distancia requerida para visitar las plazas de los 76 municipios es aproximadamente la misma que la requerida para darle una y tres cuartos de vuelta a la isla (1.75 vueltas). Si esto no es indicativo de que Puerto Rico tiene demasiados pueblos, no sé qué lo será. ¡Con razón  los políticos están un año completo haciendo campaña en Puerto Rico!

TSP_Puerto_Rico_hjcarlo

Para poder bajar la imagen de la ruta con una mejor resolución oprimir aquí. Al ser un ciclo, la ruta óptima en el mapa puede comenzar en cualquier pueblo. Arbitrariamente escojo Arecibo como comienzo de la ruta para describirla. Desde Arecibo la ruta va por los pueblos costeros hacia el Oeste hasta llegar a Añasco. De Añasco regresa a Moca para visitar los pueblos del centro-Oeste, moviéndose hasta Maricao antes de regresar a la costa de Mayagüez. El recorrido continúa hacia el Sur por la costa hasta Lajas donde entra a visitar San Germán y Sabana Grande. De Sabana Grande vuelve a circunnavegar la costa hasta Juana Díaz. En ese momento entra a Villalba y Coamo antes de regresar a la costa de Santa Isabel. El recorrido continúa por la costa hasta Humacao, donde entra a los pueblos del centro-Este y sale por Naguabo. De Naguabo continúa por la costa hasta Loíza donde visita Trujillo Alto, San Juan y Cataño. De Cataño vuelve al centro de la isla hasta salir por Dorado. Hay un movimiento interesante cuando de Dorado tiene que regresar al Este para tocar Toa Baja y luego continúa al Oeste hasta Barceloneta. De Barceloneta se visita la montaña y regresa a la costa de Arecibo donde comenzamos.

Como notarán, el mapa que les presente sólo les dice la secuencia más corta entre las plazas, pero no les dice qué ruta utilizar. La ruta entre plazas es la que sea más corta según su GPS. Gracias a Gabriela Salvat y Leonardo Rodríguez ahora tenemos un mapa con la localización geográfica de de todas las plazas para que puedan encontrar la ruta óptima con su GPS. Desafortunadamente, hay un pedazo entre Isabela y Añasco que no pudimos añadir a la ruta debido a limitaciones con los layers de Google Maps. Según Google Maps la ruta trazada suma 584 millas, lo que nos pone cerca del estimado de 650 millas usando las distancias de DTOP si le añadimos el pedazo que falta. Realmente no tengo idea de cuánto tardaría este recorrido en auto, pero considerando la velocidad y el tráfico en zonas urbanas me parece que esto no se puede hacer en un mismo día. Qué triste que nuestra isla de ~100×35 millas no se puede visitar completa en un solo día.

¿Cómo sabemos que esta es la ruta más corta?

Bienvenidos a una de las áreas de ingeniería industrial; optimización aplicada a logística. Si quieres aprender un poco más de lo que es logística visita este post. Uno de los problemas clásicos de la logística es el Problema del Agente Viajero, conocido como el TSP por sus siglas en inglés (“Traveling Salesman Problem”). El problema de TSP busca determinar la secuencia más corta para un viajero visitar n ciudades, comenzando con la ciudad donde vive el vendedor y regresar a la ciudad de origen. Este problema, aunque parece sencillo de resolver, es considerado uno de los problemas de optimización más complejos que existen. Para visitar las plazas de Puerto Rico usted sería el viajero y visitará n=76 ciudades. En total existen aproximadamente 1.88×10^111 (76!) posibles secuencias diferentes para visitar las 76 ciudades. Para los que no entendieron el número simplemente tome el número 188 y póngale 109 ceros a la derecha y ese es el número. Una de las posibles formas de visitar los pueblos es en orden alfabético, Adjuntas – Aguada – Aguadilla – … –Yabucoa – Yauco – Adjuntas (recuerda que tienes que regresar a la ciudad de origen); pero evidentemente esa no es la óptima.

Para obtener la secuencia óptima resolvimos un problema matemático. Para esto recluté a Franchelly Colón Rodríguez, estudiante sub-graduada de ingeniería industrial en la UPR de Mayagüez e integrante del Lean Logistics Lab. Para ser explícito y justo, yo le di la idea a Franchelly y ella hizo todo lo demás con muy poca intervención mía. Lo primero que hicimos fue buscar las distancias entre las plazas de Puerto Rico. Buscar todas las distancias entre los 76 pueblos son 5,776 distancias diferentes. Note que esto incluye la distancia desde Mayagüez hasta Humacao y desde Humacao a Mayagüez. Por tanto, dado que son demasiadas distancias sólo calculamos una distancia entre cada par de pueblos. O sea, sólo obtuvimos de Humacao a Mayagüez. En general, la distancia de Mayagüez a Humacao será bien cercana que la de Humacao a Mayagüez ya que la diferencia serán las calles “one-way.” No se engañen, obtener las 5,776/2 = 2,888 distancias sigue siendo una cantidad de trabajo oneroso. Para simplificar nuestro trabajo utilizamos la calculadora de millaje del Departamento de Transportación (DTOP). Lamentablemente, la calculadora de millaje de DTOP nos da la distancia entre dos pueblos, pero no nos da la tabla de todas las distancias. ¿Cuán difícil era para ellos simplemente dar una tabla de distancias desde-hasta con todas las distancias como esta? DTOP no especifica cómo se midieron sus distancias, pero validándolo con Google Maps la distancia entre pueblos es muy similar a la de plaza a plaza. Luego de tener las distancias entre pueblos utilizamos una súper computadora para resolver el TSP con un software especializado (no creas que revelaré el secreto de qué usamos). El resultado lo obtuvimos en tan solo 1.75 segundos de corrida con una garantía de que no hay mejor solución que la obtenida (i.e., solución óptima). Esto es maravilloso, para que entiendan cómo hemos avanzado, hace 15 años no podíamos ni resolver 20 ciudades y ahora podemos hacer tres veces eso en sólo segundos.

Aunque la tecnología de las computadoras continúa avanzando y cada vez podemos resolver problemas más grandes, pasarán muchos años antes que la tecnología de la transportación nos permita visitar todos los pueblos de nuestra isla en un solo día. Sin duda necesitamos reducir la cantidad de municipios en Puerto Rico mediante consolidación. ¿Cuántos municipios debemos tener en Puerto Rico? Mi propuesta es que la cantidad y localización de los nuevos municipios tenga como restricción que podamos visitarlos todos en menos distancia que lo requerido para darle la vuelta a Puerto Rico.

NOTA PARA PROFESORES DE ININ: Ya que tienen la matriz de distancias y la solución óptima al problema de TSP de Puerto Rico, aprovechen para explicarle a los estudiantes la complejidad del TSP, lo que son heurísticos y pídanles programarlos para que vean cuán buenos son los heurísticos comparado con la solución óptima.

RECOMENDACIONES PARA EL VIAJE: Hay tanta gente planificando el viaje que decidí añadir varios consejos basado en nuestro viaje familiar haciendo la ruta. El primer consejo es que bajen el libro electrónico gratuito del Dr. José A. Mari Mut para que aprendan de la historia y cultura de cada pueblo mientras manejan a las plazas. El segundo consejo es que hagan el viaje en grupo de hasta 12 personas alquilando un vehículo de hasta 15 pasajeros. Un vehículo más grande no será funcional para manejar por los pueblos. Planifiquen el viaje para visitar no más de 15 plazas por día. Eso les daría para ir a la plaza, tomarse fotos y seguir sin visitar museos, iglesias, etc. Por último, tagée tus fotos con #rutaoptimapr y disfruten el viaje. Pronto habrá un post sobre nuestro viaje familiar con información de cada plaza.

P.D. Si le gustó el post dele Like y compártalo en Facebook usando el botón de “Share this” que aparece debajo del anuncio. También puede copiar la dirección del webpage (url) en su Facebook y compartir con sus amigos – la foto le saldrá automáticamente en su mensaje. Puede buscar mis otros posts aquí. Por último, lo invito a que le de follow al blog usando el botón de “Follow” (está debajo de los comentarios) para que le notifiquen por email cada vez que posteo alguna reflexión en el blog (aproximadamente cada dos meses).