Archivo de la etiqueta: B_us

|DOCENCIA E INVESTIGACIÓN|, |PUBLICACIONES PROPIAS|, Viajes

De viaje a Viena para asistir a la TRA Conference 2018

Deja un comentario

Hace un par de semanas estuve en Viena para acudir a la TRA Conference 2018. No era mi primera vez en este congreso, ya acudí en 2016 a la edición que se celebró en Varsovia. En aquella ocasión, en mi empresa (junto a Tribalyte), estábamos inmersos en un proyecto europeo al que posteriormente dimos el nombre de B_us. El objetivo principal de este proyecto era avanzar en un nuevo modelo de movilidad en autobús cuyas rutas se decidieran en base a las necesidades de desplazamiento de los usuarios. Por entonces, teníamos desarrollada una app que permitía a los usuarios responder una encuesta acerca de sus orígenes, destinos y horarios. Nuestra idea inicial era actuar sobre el transporte regular (es decir, sobre las rutas de los servicios de transporte público). Pero, a medida que el proyecto avanzaba, vimos que debíamos buscar un nuevo nicho sobre el que actuar.

La decisión que tomamos estaba basada en la revisión bibliográfica realizada, en las limitaciones que teníamos en el proyecto y en las limitaciones de la técnica. La bibliografía hacía referencia al fracaso de muchos sistemas de transporte a la demanda cuando el número de viajeros aumentaba. Las limitaciones del proyecto nos impedían, por un lado, integrar un tracking en otras apps para tomar datos masivos de los usuarios y, por otro, nos condicionaban las posibilidades económicas para realizar una campaña publicitaria que permitiera alcanzar un número adecuado de usuarios para poder generar rutas en el algoritmo. Las limitaciones técnicas venían justo por el algoritmo (que está concebido para generar un camino mínimo a cada usuario a la vez que maximiza la ocupación del vehículo, algo clave para la empresa operadora). Aunque estaba paralelizado para permitir funcionar dentro del paradigma del Big Data, había un problema importante: sobrepasaba el número de consultas a la API de Google Maps que podíamos pagar.

Así pues, tuvimos que virar un poco el objetivo inicial y empezamos a trabajar en el desarrollo de una solución orientada al transporte discrecional. Inicialmente, como teníamos el apoyo institucional del Ayuntamiento de Madrid, de la EMT y del CRTM desde 2014 (nos apoyaron al realizar la propuesta del proyecto en la convocatoria frontierCities), fuimos a consultarles qué problemas podría haber en la ciudad de Madrid que fuera susceptible de ser resuelto por nuestro proyecto. Recibimos dos casos. El primero era el cambio de sede del Atlético de Madrid, que empezaba a jugar en unos meses en su actual estadio. Era un reto muy interesante pero no pudo concretarse por diversos motivos que no vienen al caso, aunque nos hubiera encantado realizar este caso. El segundo, que fue el piloto teórico que realizamos, consistía en generar un sistema de transporte para los trabajadores del Centro de Operaciones de Entrevías, que está situado en una bolsa de inaccesibilidad que dificulta a los trabajadores llegar a su puesto de trabajo en transporte público.

Por supuesto, una vez realizado este piloto, estábamos en disposición de publicar el resultado y eso es lo que presentamos a la TRA Conference 2018. Podéis ver el poster que presentamos aquí y espero que pronto podamos compartir el artículo completo que hemos mandado a una revista JCR.

Además, estando en Viena, se me ocurrió una nueva aplicación de B_us, relacionada con el alquiler de autocares. El último día, la TRA Conference 2018 acababa a mediodía, de modo que aprovechamos para visitar el Palacio de Schönbrunn, también conocido como el Versalles vienés. Teníamos mala combinación de transporte público y poco tiempo porque una de mis compañeras volaba en pocas horas y aún tenía que volver al hotel a por las maletas. Imaginemos que queremos visitarlo pero no queremos preocuparnos por el transporte ni a la ida ni a la vuelta a pesar de hacer un viaje a nuestra medida en lugar de un tour en grupo. Si hubiera en las webs del palacio o de los operadores la posibilidad de sacar billetes conjuntos, supondría una gran ventaja para el turista.

Vista de la ciudad de Viena desde los jardines del Palacio de Schönbrunn

También hay otras situaciones en las que tener un transporte en una combinación que es compleja o para un trayecto de última milla puede ser una ventaja y B_us puede resolver el problema al agrupar a los viajeros. Pero pongamos un ejemplo concreto que nos permita plasmar esta idea. Imaginemos que queremos hacer un viaje puerta a puerta en transporte público combinando un tren de Renfe y un autobús de alguno de los operadores locales, como Esteban Rivas. Puede que en el tren vayamos en grupo y nuestra opción sea recurrir a alquilar un autobús, algo muy común por ejemplo para bodas o eventos familiares. Pero puede que no sea así sino que varios desconocidos tengan, una vez bajados del tren, destinos próximos o que podrían enlazarse con un número de paradas que no penalice en exceso a los usuarios que vayan al destino más alejado. Es aquí donde B_us tendría un mayor potencial de aplicación.

Esperemos poder realizar alguno de estos proyectos o los que planteábamos en este vídeo que preparamos para una convocatoria de financiación para intentar avanzar en el desarrollo de B_us:

 

Y, por supuesto, si eso pasa, intentaremos seguir volcando nuestra experiencia en otras ediciones de la TRA Conference, como la que se celebrará en Helsinki en 2020.

En unos días espero volver a publicar por aquí. Esta vez será sobre uno de los eventos en los que participé dentro de la TRA Conference 2018, una visita al barrio piloto de Aspern. Me dejó sinceramente impresionado y espero poder plasmar en el texto la emoción que sentí al ver todos los interesantes temas que se están trabajando en el que es ahora mismo uno de los desarrollos urbanos más grandes y ambiciosos de Europa.

—

Recordad: para no perderos nada, podéis uniros al canal de Telegram de urbanismoytransporte.com para recibir contenidos interesantes tanto del blog como de otras cuestiones relacionadas con él: https://telegram.me/urbanismoytransporte

|DOCENCIA E INVESTIGACIÓN|, |PUBLICACIONES PROPIAS|, SmartCities

Técnicas utilizadas en la planificación (3). Algoritmos de caminos mínimos

Deja un comentario

Seguimos con la tercera entrega de la serie sobre “Técnicas utilizadas en la planificación”. En esta ocasión es el turno de los algoritmos:

Aunque parezca que en matemáticas nunca hay disensos porque es una ciencia estructurada, esto no es así del todo. Y una prueba de ello es que para el término algoritmo no existe una definición siquiera intencional (es decir, aquella que proporciona todas las propiedades que requiere un objeto para estar incluido en el término definido).

Sí que hay cierto consenso al señalar que los algoritmos responden a conjuntos prescritos de instrucciones o reglas bien definidas, ordenadas y finitas que permiten resolver un cálculo o, lo que es lo mismo, un número finito de pasos que convierten los datos de un problema (inputs) en una solución (outputs). Pero no está tan claro qué debe pasar entre medias para decidir qué es y qué no es un algoritmo.

Aunque dicho así suene muy complicado, pues permite tantos refinamientos como queramos, hay algoritmos tan sencillos como la suma y la resta, pues las operaciones son casos particulares de los algoritmos. Y además, aunque parezca algo muy abstracto, los algoritmos están presentes en nuestra vida cotidiana a través de gran parte de los objetos y aparatos que utilizamos cada día.

La descripción de un algoritmo usualmente se hace en tres niveles:

1. Descripción de alto nivel. Donde se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal y omitiendo detalles particulares. En algunos casos, también resulta adecuado representar diagramas de flujo que muestren los diferentes pasos para alcanzar la solución.

2. Descripción formal. Para ella se emplea lo que se denomina pseudocódigo y no es más que una descripción de la secuencia de pasos que se siguen para alcanzar la solución.

3. Implementación. Se desarrolla el algoritmo expresado en un lenguaje de programación específico.

Los algoritmos de caminos mínimos

El problema del camino más corto es el aquel que consiste en encontrar un camino entre dos nodos de manera que la suma de los costes de los nodos que lo constituyen es mínima. Por supuesto, este tipo de algoritmos permiten estudiar costes de trayecto diferentes, como la distancia, el tiempo de viaje, el coste generalizado, etc. Y no sólo eso, sino que es posible trabajar con matrices de adyacencias donde no sólo se representen costes medidos sino también ponderados. Un ejemplo clásico en el mundo del transporte es la penalización de cada modo de que se emplea en la 3ª etapa de los modelos de demanda de transporte (recordemos que son: 1) Generación de viajes,  2) Distribución de viajes; 3) Selección modal y 4) Selección de ruta. Por eso, se suele hablar de «modelos de cuatro etapas»).

Algoritmo

Los algoritmos más importantes para resolver este problema son:

Dijkstra: resuelve el problema de los caminos más cortos desde un único nodo origen hasta todos los otros nodos del grafo (aunque aplicando una regla de repetición del algoritmo, se puede automatizar la resolución del problema desde todos los nodos de origen hasta todos los nodos del grafo).

Bellman-Ford: resuelve el problema de los caminos más cortos desde un origen permitiendo que la ponderación de los nodos sea negativa.

Algoritmo de Búsqueda A*: resuelve el problema de los caminos más cortos entre un par de nodos usando la heurística para agilizar la búsqueda.

Algoritmo de Floyd-Warshall: resuelve el problema de los caminos más cortos entre todos los nodos.

Algoritmo de Johnson: resuelve el problema de los caminos más cortos entre todos los nodos y puede ser más rápido que el de Floyd-Warshall en grafos de baja densidad.

Algoritmo de Viterbi: resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada nodo.

El algoritmo Dijkstra

El algoritmo que más conozco es el de Dijkstra y es del que quiero comentar algunas cosillas. Su nombre se refiere a Edsger Dijkstra, quien lo describió hace ya más de medio siglo, en 1959. La idea que subyace consiste en ir explorando, a través de una estrategia de búsqueda especializada, el camino más corto que parte de un nodo origen y que llevan a todos los demás nodos de un grafo. Veamos en el siguiente vídeo cómo funciona:

Sin embargo, este algoritmo tiene algunas limitaciones, siendo la fundamental que no funciona en grafos con aristas de coste negativo puesto que se producen inestabilidades en la estrategia de búsqueda. Y otra importante es que no es directamente paralelizable, algo muy importante para los procesos que se engloban dentro del Big Data. Pero sí que permite formulaciones muy flexibles para modelizar problemas de transporte y la programación de sumideros para evitar el uso de pesos negativos. Además, pasa a ser paralelizable si empleas el ingenio y bastante tiempo de trabajo y tienes la suerte de que la inspiración de cómo salvar el problema te pilla o trabajando o con una libreta/un móvil a mano. Eso sí, ésta es la parte que ya no cuento porque ahí radica parte de la solución del proyecto de la UE en el que ando metido y con el que, mis compañeros y yo, pretendemos revolucionar la toma de datos de usuarios de transporte, así como el establecimiento de las líneas de deseo y de las rutas de transporte.

Espero que os haya gustado este post y ya irá habiendo más entregas de esta serie sobre “Técnicas utilizadas en la planificación”.