mÁster de organizaciÓn industrial y gestiÓn de...

MÁSTER DE ORGANIZACIÓN

INDUSTRIAL Y GESTIÓN DE EMPRESAS

Tesis del Máster

DISEÑO DE REDES DE TRANSPORTE

PÚBLICO

Implementación del Sub-sistema de Recomendación de Itinerarios

Alumno: Ginés Campos Domínguez Tutor: David Canca Ortiz Sevilla, Julio de 2008

Capítulo 0 - Índice

3

0 Índice 0 Índice .................................................................................................................... 3 1 Introducción.......................................................................................................... 5

1.1 Redes de Transporte ..................................................................................... 5 1.2 Intermodalidad.............................................................................................. 7

1.2.1 Problemática que presenta el transporte intermodal............................. 8 1.2.2 Mejora del transporte intermodal ......................................................... 8

1.3 Sistemas ITS................................................................................................. 9 1.3.1 Clasificación de sistemas ITS............................................................. 10 1.3.2 Los sistemas ITS y su papel en el fomento de la intermodalidad....... 18

1.4 Resumen del proyecto ................................................................................ 19 2 Planteamiento del problema ............................................................................... 21

2.1 Descripción del problema........................................................................... 21 2.1.1 El problema desde el punto de vista del usuario ................................ 21 2.1.2 Acotación del problema...................................................................... 23

2.2 Modelado matemático ................................................................................ 24 2.2.1 Notación .............................................................................................24 2.2.2 Formulación........................................................................................ 25

2.3 Problemas de resolución............................................................................. 27 2.4 Problemas de implementación.................................................................... 28

3 Situación actual de la recomendación de itinerarios .......................................... 30 3.1 Métodos de resolución................................................................................30

3.1.1 Algoritmos de K caminos mínimos.................................................... 30 3.1.2 El Principio de Optimalidad ............................................................... 31 3.1.3 Árbol de caminos mínimos................................................................. 33 3.1.4 Comparativa de los distintos tipos de algoritmos............................... 43

3.2 Sistemas ATIS ............................................................................................ 43 3.2.1 SMS .................................................................................................... 43 3.2.2 Información del transporte público..................................................... 44

4 Método exacto de recomendación de itinerarios ................................................ 46 4.1 Construcción del grafo espacio-temporal ................................................... 47 4.2 Poda del grafo............................................................................................. 48

4.2.1 Paso 0: Eliminación de arcos de llegada al origen y de salida desde el destino................................................................................................. 48

4.2.2 Paso 1: Eliminación de información anterior a la salida .................... 49 4.2.3 Paso 2: Eliminación de salidas posteriores......................................... 50 4.2.4 Paso 3: Aseguramiento de la accesibilidad desde la ciudad origen.... 51 4.2.5 Paso 4: Aseguramiento de la conexión con la ciudad destino............ 52

4.3 Modelado de conexiones urbanas............................................................... 53 4.3.1 Unión con nodos de la misma parada................................................. 54 4.3.2 Unión con nodos del resto de paradas de la misma ciudad ................ 54

4.4 Creación de nodos origen y destino ficticios.............................................. 55 4.5 Aplicación del algoritmo de K-caminos mínimos...................................... 55

5 Implementación: Recomendación de itinerarios en movilidad .......................... 60 5.1 Planteamiento General del Proyecto .......................................................... 60 5.2 Análisis de requisitos.................................................................................. 61

5.2.1 Descripción de los Requisitos............................................................. 61 5.2.2 Resumen de los Requisitos................................................................. 63

5.3 Análisis General del Sistema...................................................................... 64

Capítulo 0 - Índice

4

5.3.1 Cálculo de recomendaciones .............................................................. 64 5.3.2 Interacción con los Usuarios............................................................... 65 5.3.3 Módulos auxiliares ............................................................................. 67 5.3.4 Esquema de Módulos y Funcionalidades Asociadas.......................... 67

5.4 Implementación del sistema ....................................................................... 69 5.4.1 Problemas de implementación............................................................ 69 5.4.2 Soluciones a los problemas de implementación ................................. 69 5.4.3 Descripción de la implementación ..................................................... 70

6 Conclusiones y líneas futuras ............................................................................. 81 6.1 Conclusiones............................................................................................... 81 6.2 Líneas futuras ............................................................................................. 82

7 Bibliografía y referencias ................................................................................... 84 7.1 Bibliografía................................................................................................. 84 7.2 Referencias Web......................................................................................... 90

8 Anexos................................................................................................................ 91 8.1 Proyecto Minerva ....................................................................................... 91 8.2 SOAP.......................................................................................................... 94 8.3 Índice de figuras ......................................................................................... 96 8.4 Índice de tablas ........................................................................................... 98

Capítulo 1 – Introducción

5

1 Introducción

Este trabajo presenta un enfoque nuevo para la recomendación de itinerarios intermodales, orientado a mejorar la movilidad de pasajeros y considerando principalmente el transporte público. Se implementa un algoritmo exacto al objeto de construir recomendaciones multimodo entre un origen y un destino, considerando transporte público, múltiples compañías con restricciones horarias y limitación de plazas. El método propuesto se basa en la teoría de grafos. La situación se modela mediante un grafo espacio-temporal que recoge todas las posibilidades de viaje. Este grafo se somete a procedimientos de reducción con el fin de disminuir el tiempo necesario para la obtención de rutas mínimas de acuerdo a diferentes criterios. Posteriormente se procede a la aplicación de un algoritmo de obtención de k-caminos mínimos que proporciona las recomendaciones requeridas. La idea del método es la de poder trabajar con redes extensas, por tanto es necesario realizar un podado del grafo así como un algoritmo de cálculo de rutas eficientes.

Finalmente se muestra un proyecto de Sistema de Información de Transporte Interurbano, actualmente en implantación, que permitirá a un usuario disponer de recomendaciones de viajes calculadas según sus preferencias. Estas recomendaciones se podrán obtener tanto a través de Internet como empleando las últimas tecnologías en movilidad, posibilitando el realizar reservas de las recomendaciones obtenidas. Asimismo, una vez que el usuario esté realizando el viaje, podrá recibir nuevas recomendaciones si se producen variaciones en la red de transporte que afecten a su viaje en curso, todo ello de forma automática.

1.1 Redes de Transporte El término genérico "red" hace referencia a un conjunto de entidades (objetos,

personas, etc.) conectadas entre sí. Dicha conexión entre entidades permite que circulen elementos materiales o inmateriales entre estas entidades, según reglas bien definidas.

Existen muchos tipos de redes (eléctricas, de telecomunicación, neurales, de cooperación). Este trabajo va a centrarse en las redes de transporte, que pueden definirse como un conjunto de infraestructuras, vehículos y sistemas usados para trasladar personas y bienes entre diferentes áreas geográficas. Cuando el objeto de transporte son las personas, se habla de redes de transporte de pasajeros.

Son muchos los investigadores que exponen en sus artículos y libros la función “lubricante” del transporte dentro del sistema económico, Button [15][16], Nijkamp y Vluegel [85][86]. Además, la industria del transporte juega un papel integrador entre la producción de bienes y servicios, Kammerer [65]. Estas son algunas de las razones que justifican el esfuerzo continuado de la UE en temas de transporte.

La iniciativa TEN (Trans-European Networks) ha significado una parte importante del esfuerzo de la UE para sintetizar diferentes objetivos:

• Reforzamiento de la cohesión económica y social entre centro y periferia. • Mejora de la seguridad a parir de la estandarización de corredores en la

geografía de la Unión.


6

• Asegurar una capacidad real de operación entre las fronteras europeas. • Recalibrar y ordenar el reparto modal en el transporte. • Mejorar lazos de transporte con la Europa del este. • Definir y poner en marcha una política comercial común para todos los

miembros de la Unión.

Los rasgos básicos del programa TEN, “cohesión e infraestructura”, son metas a largo plazo de la Comisión Europea, Ross [93], Turró [104].

La iniciativa TEN se ha orientado durante estos años de forma específica hacia la realización de proyectos individuales encaminados a los objetivos globales. En la actualidad, la filosofía de la comisión cambia en parte, intentando relacionar los diferentes grupos de investigación bajo el marco de las redes de excelencia.

Durante años, la construcción de infraestructuras ha sido una prerrogativa casi exclusivamente propia de cada uno de los países miembros. La atención de la Comisión Europea se ha centrado principalmente en el establecimiento de líneas comunes de investigación en los sucesivos programas marco.

Un enfoque mas reciente en relación a las necesidades del transporte se centra en la aplicación de las tecnologías emergentes, principalmente las telecomunicaciones, de forma especial en la dotación de medios para la mejora de la utilización de las carreteras. En este sentido hay que resaltar la importancia que en la actualidad están alcanzando los Sistemas Inteligentes de Transporte.

El transporte europeo se encuentra actualmente en una situación compleja. Por un lado, los sistemas de transporte deben responder a las múltiples demandas de movilidad de los ciudadanos europeos y contribuir al necesario desarrollo social y económico. Por otra parte, el transporte es el consumidor principal de combustibles fósiles no renovables, suponiendo el 31 % de consumo total de energía en la unión europea, afecta negativamente a la salud de ciudadanos, la economía y es causa importante del cambio climático.

Las costes externos del transporte de pasajeros por superficie suponen aproximadamente 317 billones EUR (según IWW, 2004; Para EU15) al año. Los efectos externos negativos de los viajes en vehículo privado (83 % de todos los kilómetros- pasajero en modos motorizados) son, por término medio, 2,5 veces superiores que los del autobús y del ferrocarril.

Para asegurar a todos los ciudadanos europeos un acceso de calidad a los sistemas de transporte de manera que se satisfagan sus necesidades de movilidad, la Comisión Europea ha promovido en los últimos años la realización de iniciativas de transporte intermodal, como queda recogido en su Libro Blanco “European transport policy for 2010: time to decide” [25].


7

1.2 Intermodalidad La intermodalidad es la propiedad de un desplazamiento entre dos puntos del

sistema de transporte, de forma que se vean implicados distintos y sucesivos modos de transporte (dos o más).

Figura 1: Transporte unimodal vs. multimodal

Cada modo de transporte tiene sus propias ventajas, por ejemplo capacidad potencial, altos niveles de seguridad, flexibilidad, bajo consumo de energía, bajo impacto medioambiental. El transporte intermodal permite a cada modo desempeñar su papel en la construcción de cadenas de transporte que, en conjunto, son más eficientes, de menor costo y sostenibles.

La intermodalidad mejora la sostenibilidad del transporte, aumenta la eficiencia de sistema de transporte (disminuyendo la congestión y reduciendo el tiempo de viaje), a la vez que disminuye efectos colaterales adversos como la siniestralidad en los desplazamientos, la contaminación, el ruido y el consumo de energía. Por todo ello, la mejora de la intermodalidad en el transporte de personas y mercancías se ha convertido en una de las grandes prioridades de la Comisión Europea en materia de transporte desde finales de la década de los 90, como se ve en [47][48][49].

Las redes de transporte Intermodal deben permitir un transporte intermodal de pasajeros libre de irregularidades con el fin de presentar alternativas atractivas frente el viaje sólo en vehículo privado. A este respecto, las cadenas intermodales pueden comprender todos los modos de transporte: modo peatonal, transporte público, bicicleta y uso del coche. Una organización eficiente de los viajes intermodales reduciría la confianza en el coche privado y permitiría el uso de otros modos ambientalmente amigables, con el consiguiente beneficio para todos los ciudadanos europeos y el medio ambiente.

A

B

C

D

A

B

C

D

UNIMODAL

MULTIMODAL


8

1.2.1 Problemática que presenta el transporte intermodal A día de hoy el cambio de modo supone un importante inconveniente para los

usuarios. Por tanto, es fundamental mejorar el proceso del viaje intermodal proporcionando al usuario información correcta y precisa y herramientas que aseguren la calidad requerida de este servicio multicompañía.

Los viajeros que desean realizar viajes intermodales se enfrentan hoy día a un mercado fragmentado y diverso. La multitud de diseños tarifarios y las condiciones para efectuar reservas y usar servicios son barreras significativas para el desarrollo de viajes intermodales. La falta de estandarización impide la prestación eficiente de servicios y dificulta la orientación en estaciones y vehículos. Los servicios y las estructuras administrativas se coordinan sólo a nivel local o regional. La coordinación a nivel nacional es escasa y prácticamente nula a nivel europeo. Evidentemente, esto acarrea una reducción importante del atractivo de los viajes intermodales de larga distancia nacionales e internacionales cuando se compara con el viaje en vehículo privado.

Una de las grandes dificultades para la puesta en marcha de prácticas de intermodalidad se debe a la diferente “percepción” que causan en los usuarios. Fundamentalmente como consecuencia de que mejoras globales no implican percepción de mejora a nivel individual, al menos de forma inmediata. Adicionalmente, la mejora de prácticas intermodales supone la puesta en marcha de un amplio conjunto de medidas que van desde la formación a la información. Es imposible adoptar prácticas de intermodalidad, tanto en el transporte de pasajeros como en el de mercancías, sin una información precisa, ordenada y sin la ayuda de sistemas de información desarrollados al efecto. Son numerosos los autores que ponen de manifiesto la importancia de los sistemas de información [22][50][99] en la gestión de cadenas logísticas, la cada vez mayor necesidad en la utilización integrada de estos sistemas mediante aplicaciones ERP [67] y el uso de Internet [114].

En la actualidad hay un claro predominio del modo único, cualquier cambio de modo de transporte en un trayecto supone al usuario una serie de inconvenientes como el desplazamiento en ciudades que en principio desconoce y un coste adicional debido al transporte público urbano. Por este motivo, el transporte intermodal no es competitivo respecto al transporte unimodal. Además hay otras razones: la falta de puntualidad y de regularidad, precios en ocasiones excesivos y las carencias en infraestructuras ferroviarias.

1.2.2 Mejora del transporte intermodal Para revertir la situación y que la intermodalidad vaya adquiriendo cada vez más

importancia es necesario el adoptar una serie de medidas. Entre ellas está el mejorar y adaptar las infraestructuras de transporte, construyendo estaciones multimodales y facilidades para el intercambio del modo de transporte, de forma que los cambios de un modo a otro puedan realizarse de forma rápida y cómoda. Asimismo, se precisa de un incremento del número de puntos de información integrada en las distintas estaciones.


9

De igual forma, hay que conseguir una política integrada de precios y sistemas de billetaje y facturación de equipaje, así como la disponibilidad del modo de transporte más adecuado en función del tipo de trayecto a realizar.

Para conseguir lo anterior, el papel de la Administración (local, nacional y a nivel europeo) es fundamental. En ese sentido, con el Libro Blanco, la Unión Europea se propone lograr la mejora de la competitividad de las alternativas para el transporte de la carretera: transporte marítimo de corta distancia, transporte por ferrocarril y transporte fluvial interior. Las acciones se enfocarán, por tanto, a fomentar las alternativas al transporte por carretera de larga distancia. Esto no sólo reducirá la congestión, sino que proporcionará además una mejora en la seguridad de las carreteras y contribuirá a la mejora del medio ambiente [100][103]. El objetivo de la política común de transportes de la UE es promover la movilidad sostenible, es decir, promover servicios de transporte eficientes, adecuados en costes, seguros, ambientalmente limpios y socialmente aceptados. Este concepto de transporte sostenible supone pasar de las tradicionales políticas unimodales, que consideraban cada modo de transporte de forma individualizada, a una concepción integral del sistema de transporte, que potencie las cadenas de transporte que usan en cada tramo el modo de transporte más adecuado, haciendo óptimo cada uno de los modos y la cadena en conjunto.

Además de lo anterior, es necesario disponer de mejores sistemas de información que permita a los usuarios el disponer de la información adecuada y conocer las distintas opciones y posibilidades, a la vez que le ayuden en su toma de decisiones a la hora de planificar sus viajes. La mejora en los sistemas también ha de ir encaminada a la unificación en la gestión de este entorno multicompañía. Aquí entran en escena los sistemas inteligentes de transporte (ITS).

1.3 Sistemas ITS El término ITS (Intelligent Transportation Systems) se refiere a un amplio

abanico de tecnologías enfocadas a la solución de problemas de transporte en su sentido más amplio de movilidad de personas y bienes.

Los nuevos sistemas ITS se basan en el creciente desarrollo de la electrónica, la informática y las telecomunicaciones [2][21][66]. En algunos casos se trata de aplicaciones novedosas a sistemas clásicos como el de la regulación y control del tráfico [13][52]. En otros casos se encuentran sistemas que han despertado el interés de la comunidad científica en los últimos años, como el guiado dinámico en ruta [2][3][31][55][74][78][79][119].

Se puede decir que la mayor novedad de estos sistemas es el planteamiento integrador que acoge los planos tecnológico, financiero y organizativo, extendiendo su radio de acción a los organismos públicos y privados que hacen realidad las diferentes aplicaciones.

En la actualidad se presencia la expansión de un mercado global ITS, impulsado en cada país por sociedades como ITS América, fundada por mandato del Congreso de los EE.UU., VERTICE en Japón, o ERTICO, encargada en Europa del proceso de normalización, desarrollo de mercados y fomento en general de los Sistemas Inteligentes de Transporte.


10

Los principales beneficios de la aplicación de los ITS probados en EE.UU. y

Japón se reflejan en la considerable disminución de los accidentes y tiempos de viaje, y en el aumento de la capacidad de las vías [56][58][113]. En general, la puesta en marcha de tecnología ITS se orienta a la mejora de la eficiencia del sistema de transporte, aumentando la movilidad, la comodidad y la seguridad y reduciendo el consumo de combustible y los efectos medioambientales indeseables [70].

1.3.1 Clasificación de sistemas ITS

Como se ha comentado antes, los Sistemas Inteligentes de Transporte abarcan un conjunto de tecnologías diversas y centradas en aspectos concretos del Transporte. A continuación se presenta una breve reseña de los sistemas más importantes.

1.3.1.1 Sistemas Avanzados de Gestión del Tráfico (ATMS) Estos sistemas permiten la monitorización del estado del tráfico rodado para la

gestión y el control de la circulación en carretera. Generalmente esta monitorización y control se realiza en distintos Centros de Gestión de Tráfico, que son los responsables de garantizar la circulación de la red de carreteras bajo sus competencias. Los Centros de Gestión de Tráfico se componen de los siguientes subsistemas:

• Subsistema de toma de datos de tráfico. Permite obtener información en tiempo

presente del estado del tráfico. Los principales sistemas utilizados para la captura de datos son:

o Equipos de toma de datos de tráfico con sensores de lazos inductivos o Estaciones Meteorológicas o Otros sistemas, como detectores de radar, detectores activos y pasivos de

infrarrojos, detectores ultrasónicos y detectores acústicos pasivos

• Subsistema de vigilancia. Mediante un circuito cerrado de cámaras de televisión (CCTV) este tipo de sistemas permite a los operadores de los CGT la visualización de la situación de las carreteras.

• Subsistema de señalización y presentación de información variable al conductor. Una

vez se ha detectado un incidente, se debe informar a los usuarios cercanos al mismo de su existencia y de los problemas que ocasiona, para ello se dispone de los paneles de señalización variable, capaces de mostrar diferentes pictogramas y textos.

• Subsistema de comunicaciones. Es el encargado de la comunicación de todos los

sistemas instalados en la carretera –detectores, estaciones meteorológicas, cámaras, paneles de mensaje variable- con el centro de gestión.

• Subsistema de gestión de datos. Este sistema es el encargado de la integración de la

información proporcionada por los diversos sistemas, su análisis y la posterior presentación de la misma al operador

• Otros: dependiendo de las características de la red de carreteras bajo el control del

CGT se pueden instalar diferentes sistemas para la mejora de la circulación y seguridad vial.


11

o Gestión de Túneles. Sistemas de detección de incidentes, de incendios, postes SOS, comunicaciones internas, etc. controlados desde el CGT.

o Carriles reversibles. Es necesaria la instalación de un sistema específico, con señalización vertical variable basada en paneles y señales aspa/flecha así como señalización luminosa empotrada en la calzada (hublots u ojos de gatos), para la gestión de carriles reversibles.

Figura 2: Sistemas ATMS

Para coordinar la acción de los diferentes Centros de Gestión de Tráfico, es necesario que el intercambio de los datos se realice de forma estandarizada. En este sentido destacan dos iniciativas europeas, DATEX y TRIDENT. DATEX es un sistema de codificación y transmisión de información estandarizada, de ámbito europeo, dedicado al intercambio de información entre centros de gestión e información de tráfico. El sistema integra, en una misma plataforma, la información de tráfico generada por las entidades involucradas. A partir de DATEX, se han desarrollado sistemas que mejoran la gestión y la información de tráfico. En la actualidad, el estándar Datex es utilizado por gran cantidad de entidades de tráfico en toda Europa. En la mayoría de los casos se trata de implementaciones propietarias, con funcionalidades extendidas según las necesidades de cada una de las entidades, pero que mantienen la comunicación por medio de DATEX. Por su parte, TRIDENT (TRansport Intermodality Data sharing and Exchange NeTworks) es un proyecto europeo enfocado en el intercambio y difusión de información multimodal de viaje (transportes públicos, privados, etc.). La mayoría de los sistemas para el intercambio de información son específicos de un dominio, pero TRIDENT pretender especificar y favorecer la definición de un protocolo en el dominio multimodal. TRIDENT es una nueva especificación para el intercambio de información. Ha tenido en cuenta la evolución de la información y las tecnologías aplicar, además de proveer nuevos puntos de vista a la hora de la difusión de la información.

Las ventajas de la gestión integrada del tráfico han quedado perfectamente documentadas mediante pruebas y operaciones reales. Entre ellas figuran la reducción mensurable de la congestión y de los índices de colisión, las mejores relaciones entre los


12

proveedores de servicios y el fortalecimiento de la economía gracias al aumento de la movilidad y de la accesibilidad a nuevos mercados.

1.3.1.2 Sistemas Avanzados de Asistencia al Conductor (ADAS) Los Sistemas Avanzados de Asistencia al Conductor promueven la mejora mediante aplicación de las tecnologías (de la información, mecánica, de equipamiento del vehículo y de las infraestructuras) de las capacidades del conductor y la conducción en general. Dichas mejoras implican por un lado un desarrollo de la habilidad del conductor durante la conducción (incluyendo en este caso productos y servicios como los frenos anti-bloqueo y la monitorización del propio conductor), tratándose por tanto de ADAS orientados o centrados en el conductor. Por otro lado, pueden englobarse también los sistemas que permiten mejorar la percepción del entorno por parte del usuario (sistemas de mejora de la visibilidad), y sistemas de asistencia al conductor en situaciones de riesgo (prevención de puntos o ángulos muertos, o incluso sistemas de ayuda a maniobras de aparcamiento). Asimismo, los ADAS tratan de mejorar también la interacción del vehículo con las infraestructuras o con los otros vehículos que circulan por éstas (incluyendo en este caso tecnologías como la adaptación automática de la velocidad o las tecnologías de prevención de colisiones) e incluso el propio funcionamiento y consumo del vehículo (aumento de la eficiencia en el consumo de combustible y adaptación de este a las condiciones de entorno), siendo por tanto funciones enfocadas al vehiculo. El uso de este tipo de tecnologías y servicios implica generalmente un análisis y monitorización continua del entorno de vehículo, y una evaluación de lo que el conductor está haciendo y lo que debería estar haciendo, así como de las actuaciones correctoras o informativas a llevar a cabo. Los sistemas y tecnologías ADAS más importantes comprenden las siguientes funcionalidades:

• Monitorización del Conductor • Mejora de la visibilidad • Control de la Velocidad y la Distancia • Prevención y Aviso de Colisiones

Por último es importante señalar que para una implantación adecuada des esta tecnología han de resolverse aspectos legales y socio-políticos para la integración de los distintos sistemas que necesitan de una mínima interacción. Estas iniciativas deben aunar los estudios de negocio de los fabricantes y su viabilidad con los intereses públicos y las competencias de las autoridades así como una legislación consistente. En este sentido se está comenzando a hacer estudios tanto en los EE. UU. como en Europa para aunar los esfuerzos de las administraciones y las compañías, y para proveer de un ámbito en el que estas tecnologías puedan desarrollarse con seguridad y lanzarse al mercado en el futuro.


13

1.3.1.3 Sistemas Avanzados de Transporte Público (APTS) Los Sistemas Avanzados de Transporte Público (APTS), son en realidad un conjunto de sistemas y tecnologías que aumentan la eficiencia y la seguridad de los sistemas de transporte público y ofrecen a los usuarios un mayor acceso a la información sobre la operación del sistema. La implantación de los sistemas APTS está transformando la manera de operar de los sistemas de transporte público y también está cambiando la naturaleza y calidad del servicio prestado. El objetivo de este tipo de sistemas es el de facilitar a los operadores del transporte público información de calidad, oportuna y confiable, para apoyar la toma de decisiones sobre el sistema y las operaciones; y por consiguiente mejorar el servicio a los usuarios. Se estima que en Estados Unidos, en un periodo de diez años (2000 y 2009), los beneficios generados por la implantación de tecnología APTS podrían alcanzar una cantidad entre 3.400 y 8.400 millones de dólares. Los sistemas APTS que intervienen, tienen incidencia y/o gestionan el transporte público se enumeran a continuación:

• Sistemas de Gestión de Flotas. Estos sistemas mejoran el servicio de transporte por medio de un mejor cumplimiento de los horarios. Esto se logra gracias al uso de tecnologías de monitorización de la efectividad de la flota en relación con la satisfacción de la demanda de usuarios, de la identificación de incidentes, gestión de respuesta y restauración del servicio en forma más efectiva. El disponer de más información mejora la eficiencia de la planificación, los horarios, y las operaciones. Esto supone habitualmente un incremento de la cantidad de usuarios que utilizan estos modos.

• Sistemas de Información al Viajero. Estos sistemas combinan las tecnologías de

computadores y comunicaciones para proveer de información vehicular a los viajeros en sus casas, en el trabajo, en la vía, o en las estaciones o paradas de buses, trenes o metro. La información le permite al viajero elegir el modo de viaje más eficiente y conveniente. Los viajeros pueden acceder en tiempo real a la información de itinerarios y congestión a través de teléfonos, televisión, letreros de mensaje variable, kioscos, o computadores personales.

• Sistemas de Pago Electrónico. Se emplean para efectuar el pago del pasaje de

una forma más conveniente y cómoda para los viajeros. Otra utilidad es la de que los proveedores de servicios de transporte hagan una recaudación de ingresos menos costosa. Estos sistemas combinan medios de pago (tales como tarjetas magnéticas o tarjetas inteligentes) con sistema de comunicaciones, computadoras para el procesamiento de información y sistemas de almacenamiento de datos con el objetivo de hacer más eficiente el proceso. Estos sistemas también pueden ser usados para informar en tiempo real de la demanda para una mejor planificación e itinerarios de los servicios.

• Sistemas de Gestión de la Demanda de Transporte. Comprenden un conjunto de

técnicas y programas empleados por los operadores, administradores u organizaciones de transporte, incluso por la comunidad, para manejar y utilizar


14

de forma más efectiva la capacidad de la infraestructura existente. El objetivo de la gestión de la demanda es maximizar la capacidad de la red de transporte existente para enfrentar el incremento de la demanda por los servicios de transporte. Las técnicas y programas utilizan tecnologías avanzadas para monitorizar la capacidad de la infraestructura y manejar el sistema en tiempo real, y también para proveer de información e incentivos a los viajeros a encontrar soluciones alternativas al viaje de solo una persona por vehículo.

1.3.1.4 Operación de Vehículos Comerciales (CVO) Las tecnologías ITS orientadas a la Operación de Vehículos Comerciales (CVO, en inglés) permiten la circulación libre y segura de camiones y autobuses por carreteras y caminos de una región, o de una nación, o entre naciones, a través de la automatización e informatización de las labores de regulación, fiscalización e inspección por parte de la autoridad de las prácticas de las empresas de transporte. Asimismo incorpora elementos que mejoran la seguridad de los vehículos y carreteras, y aumentan la productividad para las empresas de transporte. Estas tecnologías abarcan diversos ámbitos relacionados con los vehículos comerciales. Estos son:

• Seguridad • Administración de credenciales y documentos • Inspección y fiscalización • Operación de las empresas de transporte

Algunos sistemas que realizan las funciones descritas anteriormente son:

• Sistemas de gestión de flotas. Hacen posible la administración en tiempo real de los vehículos que forman parte de una determinada flota. Son utilizados por operadores de flotas comerciales, como empresas de reparto y proveedores de transporte público para simplificar las operaciones móviles y mejorar la productividad de sus flotas en el transporte de la carga. Así, proveen de herramientas efectivas para la planificación, programación y operación de la flota, monitoreo y localización de vehículos. Los vehículos de la flota están equipados con un dispositivo de localización móvil que radiodifunde su posición a un centro de control y tiene una realimentación del estado del sistema y de las operaciones en el momento. A través de un terminal telemático, reciben información para reajustar dinámicamente su itinerario y modificar sobre la marcha las recogidas y las entregas. Los Sistemas de Gestión de Flota se componen de los siguientes subsistemas o componentes:

o Sistemas de Localización Automática de Vehículo (AVL) o Software para operaciones del transporte o Sistemas de comunicaciones o Sistemas de Información Geográfico (SIG)


15

Figura 3: Sistema CVO

• Gestión de mercancías. Además de la gestión de flotas de vehículos de transporte de mercancías, resulta interesante monitorizar la localización y estado de la carga de origen al destino. Para ello se utilizan dispositivos de radiofrecuencia, que operan a bajas frecuencias y sin necesidad de baterías, que identifican y trazan las mercancías, incluso almacenando información el propio producto. El estándar para intercambio electrónico de datos (EDI), juega un importante papel al facilitar la transferencia de información entre diferentes agentes de la cadena de suministro de forma automática. EDI facilita procesos de negocio directos minimizando las fuentes de error, dado que la comunicación entre aplicaciones se realiza sin papel. El caso del transporte de materiales peligrosos requiere de un tratamiento especial, sobre todo en el sistema de gestión de incidentes. En particular se requiere de intercambio de información en un formato adecuado entre los transportistas (intermodales) y las entidades que corresponden a los primeros respondedores a este tipo de incidentes.

• Tacógrafo digital. Es un aparato de control que se instala a bordo de ciertos

vehículos de carretera, par indicar y registrar de manera automática o semiautomática, los datos relativos a la distancia recorrida por el vehículo, velocidad del vehículo, tiempo de conducción, otros tiempos de trabajo distintos a la conducción y de presencia en el trabajo a disposición de la actividad, interrupciones del trabajo y tiempos de descanso diario.

• Pesaje en movimiento. Es el proceso de pesar un vehículo mientras está en

movimiento en una carretera con el fin de estimar el peso estático equivalente del vehículo. Existen muchos factores que influyen sobre el pesaje de los vehículos en movimiento que deben ser atendidos para estimar precisamente el peso estático equivalente. Entre los factores que influyen es destacable la curvatura del camino, la inclinación del terreno, patrones de tráfico, la dinámica de los vehículos o situación y uniformidad de los sensores. La elección del lugar es crítica para un desempeño óptimo del sistema. El pesaje en movimiento es


16

una valiosa herramienta para los profesionales de la monitorización de tráfico. El peso de los vehículos influye en la especificación de los requerimientos de las nuevas infraestructuras tales como carreteras y puentes. Las diferentes normativas asociadas al transporte de vehículos pesados hacen necesario disponer de estaciones de pesado que permitan comprobar e imponer restricciones de paso cuando el peso de los vehículos exceda el valor permitido. Asimismo, el mantenimiento y construcción de nuevas infraestructura tales como la pavimentación de las carreteras o construcción de puentes están influidos por el peso de los vehículos que circularán por las vías. Estos sistemas facilitan la estimación de demanda de tráfico pesado en las nuevas infraestructuras, lo que permite el calcularlas y dimensionarlas adecuadamente.

1.3.1.5 Sistemas Avanzados de Información al Viajero (ATIS) Respecto a los sistemas ATIS (Advanced Traveler Information Systems), se

puede decir que engloban los procesos de adquisición de datos, traslado, presentación y uso de la información que se proporciona a los diferentes usuarios de las infraestructuras de transporte. El objeto de estos sistemas se resume en servir de ayuda al usuario en sus desplazamientos, de forma que mejore la seguridad, la eficiencia y la comodidad. El desarrollo de Internet en los últimos años ha ampliado las posibilidades de comunicación permitiendo una difusión rápida, mundial, cómoda y flexible de la información.

Dentro de los sistemas ATIS se encuentran a su vez distintos ámbitos, en

función de la información transmitida al usuario y del medio empleado para hacerlo. Algunos de ellos son:

• Información del tráfico. Permiten al usuario estar informado en tiempo real de la situación del tráfico, de forma que pueda tomar decisiones sobre la ruta a tomar en función del estado de congestión. La forma en la que puede llegar la información es mediante el empleo de tecnologías inalámbricas, debido a que el viajero se encuentra en movimiento. Algunas opciones empleadas son:

o RDS-TMC. El Canal de Mensajes de Tráfico (TMC) es una aplicación específica del Sistema de Datos de Radio (RDS) de FM usado para transmitir información de tráfico en tiempo real. Los mensajes de tráfico se reciben de forma silenciosa (no afectan al programa de radio que se esté escuchando), se decodifican por un equipo de radio con TMC o por un navegador dinámico y se muestran al usuario (visualmente o de forma hablada), en el lenguaje seleccionado por el usuario. Los mensajes TMC se pueden filtrar de modo que solo se muestren aquellos relevantes para el viaje, pudiendo ofrecer un guiado dinámico mediante un sistema de navegación – alertando de problemas en la ruta planeada y calculando una ruta alternativa para evitar los incidentes.

o SMS, e-mail y alertas por voz. El auge de las tecnologías inalámbricas ha permitido el acceso de nuevos tipos de dispositivos a Internet, como teléfonos móviles y PDA’s. El espectacular crecimiento del número de ventas de terminales móviles ha propiciado la expansión de servicios como los mensajes cortos (SMS). No obstante, los servicios de información anteriores no son adecuados para el acceso durante la conducción, ya que implican la utilización de interfaces gráficas que suponen un riesgo para la integridad del conductor y para el resto de


17

usuarios de la vía. El uso de cualquier teléfono móvil o dispositivo de comunicación que implique la utilización de las manos supone una situación de riesgo y debe evitarse. Por lo tanto, se hace necesaria la utilización de la voz para proporcionar un acceso a la información sin que implique un riesgo para la seguridad vial. La utilización de la voz como medio de recepción de la alerta permite acceder a la información incluso durante la conducción, utilizando para ello los dispositivos homologados. De esta forma es posible mantener a los conductores informados ante situaciones imprevisibles que afecten al tráfico y permitirles la posibilidad de variar su ruta durante la realización de la misma, evitando congestiones e incidentes innecesarios.

• Paneles de mensajes variables (PMV). Es considerado en estos momentos como

la herramienta clave con la que se puede llevar la información a conductores. Se pueden considerar como el sistema de información de tráfico más “democrático” ya que alcanza a todos los usuarios de la carretera donde esté situado, sin necesidad de adquirir equipamiento más o menos costoso por el viajero. Se trata de un equipamiento ITS que ha evolucionado bastante desde sus primeras instalaciones, lo que ha influido no solo en los sistemas instalados sino también en un uso diferente de la información que se proporciona a través de ellos. Además son muy diferentes sus características y uso dependiendo del entorno (urbano o interurbano) en que se encuentren. Finalmente, cabe destacar su discontinuidad a lo largo de una carretera (ya que se usan para informar en un punto determinado de lo que sucede o puede suceder más adelante).

Figura 4: Panel de mensajes variables (PMV)


18

1.3.1.6 Otros sistemas ITS • Postes SOS. Los postes de auxilio o postes SOS son un conjunto de elementos

de comunicación instalados a lo largo de una carretera y conectados con una Central, lugar donde se atienden y gestionan las llamadas. Tales elementos de comunicación proporcionan un enlace directo al conductor con un operador del Centro de Control de Tráfico en una situación de emergencia tras pulsar un botón. Los postes se pueden distribuir por parejas – maestro y esclavo - a ambos lados de la carretera o estar instalados de forma aislada en cuyo caso es el poste maestro el que se instala. El poste maestro tiene una conexión con el Centro de Gestión de Tráfico mediante cable de cuadretes, aunque también hay postes SOS conectados mediante fibra óptica o GSM. Presentan diversos sistemas de alimentación: panel solar, red, tele-alimentación y en todos los casos, los postes incorporan una batería interna que permite su funcionamiento durante 20 días.

Figura 5: Poste SOS

• e-Ticketing. Se trata de la expedición electrónica de billetes. Se ha demostrado

que un sistema sencillo de pago es crítico para un transporte público intermodal perfecto. Debido a los costes, las tarjetas inteligentes son útiles sólo para aplicaciones de multiviaje. Por otra parte, la mayoría de la gente dispone de teléfono móvil. El objetivo del e-Ticketing es desarrollar un sistema que permita a los usuarios pagar ciertos servicios de transporte como los peajes de autopista, transporte público y aparcamientos mediante un teléfono portátil (SMS, WAP y comunicaciones de corto alcance). Las operaciones de control de billetes se realizan mediante lectura de e-tickets vía SMS o mediante una función automática entre el dispositivo de control de los inspectores de transporte y los teléfonos móviles de los usuarios

1.3.2 Los sistemas ITS y su papel en el fomento de la intermodalidad En el ámbito de los sistemas inteligentes de transporte, los denominados,

Advanced Traveler Information Systems (ATIS), Advanced Public Transport Systems (APTS), Commercial Vehicle Operations (CVO) y Advanced Traffic Management Systems (ATMS) representan tecnologías prometedoras para la mejora de la eficiencia en la gestión de sistemas de transporte. Resulta evidente que el éxito de los proyectos dedicados a fomentar la intermodalidad está ligado de forma muy directa a las tres primeras categorías, ya sea desde el punto de vista de los usuarios como de las empresas


19

proveedoras de servicios en el ámbito del transporte, tanto de pasajeros como de mercancías.

Hasta el momento son importantes los esfuerzos desarrollados para la composición de viajes que combinen múltiples modos de transporte, generalmente orientados a la resolución de problemas concretos (transporte público urbano [11], transporte de mercancías a través de corredores específicos [40]. No obstante, quedan muchos esfuerzos por realizar para la generalización del procesamiento masivo de recomendación de itinerarios [62] (dificultades de computación), así como el propio diseño de las recomendaciones, a partir del refinamiento y la generalización de los métodos propuestos en trabajos como los de Liu et al. [75][76], incorporando soluciones a problemas como los debidos a la existencia de diferentes horarios de viajes para diferentes compañías en función del calendario (transporte público), multiplicidad de criterios de selección por parte de los usuarios, reserva de billetes, etc., o como en el diseño de sistemas de información que soporten los múltiples y complejos aspectos que involucra la intermodalidad.

1.4 Resumen del proyecto Con el presente trabajo se pretende presentar un método que permita la

elaboración de recomendaciones para el transporte intermodal, tanto en el transporte de mercancías corno en el de pasajeros. Con tal fin, este método se implementará en un sistema que habrá de garantizar la resolución de problemas multimodales complejos en tiempos de respuesta razonables.

El proyecto pretende abordar no sólo el proceso de composición de recomendaciones bajo diferentes criterios, sino también la problemática asociada tanto a la recepción de peticiones en entornos geográficamente distribuidos, como la difusión individualizada de este tipo de resultados a los usuarios. Todo ello aprovechando las últimas tecnologías en telecomunicaciones y las que nos proporciona Internet. Por tal motivo, un aspecto fundamental consiste en la integración de las recomendaciones con sistemas de información vía Internet (consulta de páginas Web, actualizaciones dinámicas del servidor) o a través de mensajes tipo SMS y MMS utilizando tecnologías móviles.

Todo esto se desarrolla en los siguientes capítulos de la forma que se describe a continuación. En el capítulo 2 se realiza un planteamiento general del problema desde el punto de vista del usuario. Posteriormente se acota el ámbito del problema y se modela matemáticamente. Finalmente se plantean los problemas que presentan tanto la resolución del modelo matemático como la implementación completa del sistema. En el capítulo 3 se describe el estado actual de la resolución del problema matemático, comparando diversas opciones así como diversas iniciativas existentes dentro del mundo de los sistemas ATIS, que constituyen la categoría en la que se ubica la implementación descrita en este trabajo. En el siguiente capítulo, el 4, se mostrará un método exacto para la recomendación de itinerarios, consistente en una transformación del grafo de la red de transporte en un grafo espacio-temporal. Se describen el proceso que seguirá dicho grafo hasta la obtención de varias recomendaciones de itinerarios calculadas en función de las preferencias manifestadas por el usuario. El capítulo 5 está dedicado a la implementación del método en un sistema útil para el usuario. Se parte del análisis de los requerimientos funcionales y los que ha de cumplir el sistema y se


20

describe cómo se está llevando a cabo la construcción de dicho sistema. Finalmente, se concluye la exposición con unas conclusiones y propuesta de líneas de trabajo futuras (capítulo 6), la bibliografía (capítulo 7) y los anexos (capítulo 8).

Capítulo 2 – Planteamiento del problema

21

2 Planteamiento del problema

2.1 Descripción del problema El hablar de redes de transporte intermodal de pasajeros puede abarcar muchos

aspectos, por lo que para acometerlo convenientemente hay que dividirlo y acotar el alcance de cada elemento. Con el presente capítulo se pretende plantear la problemática que presenta el diseño, la implementación y el uso de una herramienta que facilite a los usuarios de las redes de transporte de viajeros la planificación de viajes intermodales. El objetivo último de esta herramienta es el fomento de la intermodalidad para aprovechar las ventajas tanto individuales como sociales que presenta su uso.

2.1.1 El problema desde el punto de vista del usuario El planteamiento de un viaje suele diferir mucho en función de la distancia a

recorrer. Considérense por tanto tres tipos de viajes:

En los viajes de larga distancia generalmente los desplazamientos se realizan en avión. Probablemente hay viajes directos entre el origen y el aeropuerto próximo y entre el aeropuerto destino y la localidad destino final. Habitualmente, estos viajes que conectan los extremos con los aeropuertos se realizan empleando sólo un modo de transporte. En algunos casos, estos viajes antes y después del trayecto en avión pueden ser de media o larga distancia. Los viajes de larga distancia pueden reservarse mediante agencias de viajes o directamente empleando Internet.

De otro lado, para los viajes de media distancia no suele haber mucha información y habitualmente no existe la posibilidad de realizar el viaje de una sola vez. El viajero necesita combinar diferentes compañías y modos de transporte para alcanzar el destino. Por tanto, los usuarios suelen preferir hacer este tipo de desplazamiento mediante el coche particular.

Finalmente, los viajes de corta distancia suelen realizarse dentro de áreas metropolitanas, generalmente con un solo medio de transporte y una sola compañía. En el caso de grandes ciudades quizá se empleen dos compañías y/o modos de transporte. La información está perfectamente definida para este tipo de viajeros, que habitualmente son trabajadores en tránsito entre sus hogares y sus lugares de trabajo. Vamos a considerar el viaje de media distancia de la Figura 6. Un ciudadano quiere viajar desde la ciudad marcada como 1 a la localidad marcada como 2. Lo que él desea es poder reservar un viaje que tendrá lugar varias semanas más tarde. Ambas localidades son de pequeño tamaño, están alejadas bastantes kilómetros y no existe ninguna compañía de transporte con servicio directo entre ambas. No hay posibilidad de viajar por avión, ya que no hay aeropuertos cerca del origen o del destino o bien porque los ratios costo/distancia no hacen aconsejable el uso del avión.


22

Figura 6: Esquema de un viaje intermodal de ejemplo

El procedimiento normal que seguiría un viajero es reservar un billete en una primera compañía para viajar desde su ciudad hasta la localidad 3. Eso puede hacerlo fácilmente. Posteriormente deberá telefonear a una segunda compañía y comprar el ticket para la segunda etapa de su viaje, que discurre entre la localidad 3 y la 4. La cosa se complica más para al tercera etapa del viaje, que le llevará hasta su destino final (la ciudad 2). Es casi imposible desde la ubicación 1 adquirir un billete para esta última etapa. El viajero probablemente no podrá hacer trasbordo el mismo día y tendrá que hacer noche en la ciudad 3. Lo más normal es que no conozca ni los horarios ni las compañías que operan entre 4 y 2.

Como vemos, un problema fundamental es la dispersión de la información, que hace que resulte altamente complicado el poder determinar y seleccionar los viajes más adecuados. Asimismo, la falta de centralización también afecta a la hora de realizar las reservas de los diferentes trayectos que componen el viaje completo.

Otro problema que complica aún más al viajero ocurre cuando éste ya está realizando uno de los trayectos que componen su viaje y se produce un cambio en la red de transporte que le afecta (por ejemplo, cortes de carreteras o retrasos en los trenes que ha de tomar). En este caso, se suma a la dificultad para obtener información sobre los siguientes trayectos (al no estar centralizada), el que ya se esté desplazando, lo que agudiza el problema del acceso a la mencionada información y herramientas de reserva.

Se necesita un organismo central que gestione toda esta información y la almacene en una base de datos. Este organismo central debe ser el encargado de que las compañías actualicen los horarios de los servicios que prestan a los usuarios.

1

2 4 3


23

2.1.2 Acotación del problema A continuación se acota el problema al que se da respuesta en este trabajo. El

objetivo es definirlo completamente antes de proceder a su resolución.

Uno de los objetivos de este trabajo es proponer un método para la recomendación y reserva de viajes con las siguientes características:

• Viajes multimodales: Autobús (carretera), tren, transporte marítimo y fluvial • Múltiples compañías de transporte implicadas • Cada compañía tendrá una licencia pública de operación en un cierto territorio. • El usuario pretende reservar con antelación un determinado número de plazas a

lo largo de toda la cadena intermodal. • Cada compañía puede ofrecer diferentes viajes entre los mismos orígenes y

destinos. Por ejemplo, puede ofrecer viajes directos y viajes con diferentes paradas en la ruta.

• Cada compañía tiene establecido una serie de horarios que puede variar estacionalmente.

• Los diferentes medios de transporte tienen un número limitado de plazas (restricciones de capacidad).

• Los usuarios podrán seleccionar de entre un conjunto de propuestas multimodales calculadas según diferentes criterios independientes o simultáneos:

o Obtención de recomendaciones de mínimo coste o Mínimo tiempo de viaje o Mínima distancia a recorrer o Mínimo número de transbordos (entendidos como cambios de modo) o Descartando determinados modos de transporte (por ejemplo por miedo a

volar) o O una combinación ponderada de dos o más de esos criterios

En resumen, se tienen distintas compañías operando sobre distintos modos de transporte, cada una con sus viajes y horarios. Todas estas compañías actúan sobre una misma red de transporte compuesta por distintas ciudades y por las infraestructuras que las unen.

El otro objetivo fundamental es la descripción de la implementación del método citado en una herramienta que lo aplique y pueda resolver al usuario los problemas planteados.

En dicha herramienta se almacenará en una base de datos toda la información

relativa a la red de transporte, horarios, viajes y también se reserva espacio para almacenar los datos de clientes y reservas realizadas. Esta base de datos es la que da soporte al método de recomendación de viajes, que ante una petición de itinerario de usuario (ciudades origen/destino, fecha y hora de viaje, plazas y criterio de búsqueda) calcula las mejores posibilidades de viaje entre las ciudades y muestra el resultado al usuario final.


24

2.2 Modelado matemático

2.2.1 Notación Con el fin de poder acometer la tarea de resolución del problema, éste ha de ser

modelado. Una aproximación clásica a este tipo de problemas consiste en modelar las redes de transporte mediante grafos. Consideremos que las distintas estaciones o paradas de los diferentes medios de transporte sean los nodos del grafo, que conforman el conjunto N de nodos y que las conexiones entre esas paradas sean los arcos, la totalidad de los cuales formarán el conjunto A de arcos. Si i y j son nodos genéricos, (i,j) será el arco que une esos nodos. G={N, A} será el grafo que representa la red de transporte. Se define también el conjunto D(i) como el conjunto de nodos destino alcanzables directamente desde el nodo i, es decir, aquellos que son extremos de arcos que tienen como extremo inicial a i. De igual forma se define el conjunto A(j), como el conjunto de nodos antecesores de j. Expresado de otra forma, sería el conjunto de los nodos orígenes de los arcos que tienen a j como destino.

Asimismo sean c y c’ las compañías de transporte, el total de las cuales integran el conjunto C de todas las compañías. Sea también V(c) el conjunto de viajes programados por la compañía c. Por otra parte, sean n y r referencias de viajes pertenecientes a la empresa de transporte c.

Para indicar si un viaje concreto de una compañía usa un arco del grafo hará falta una variable binaria que los relacione. Esto permitirá la construcción de una matriz de datos que relaciona referencias de viajes y arcos y cuyos valores. Estas variables tendrán la forma siguiente:

1 si el viaje con referencia r de la compañía usa el arco ( , )

0 en otro caso crij

c i jδ

=

Debido a la naturaleza del problema es necesario disponer de una serie de datos

temporales, ya que los viajes tienen unos horarios determinados que habrá que tener en cuenta. Se toma ti

cn como el momento de llegada (o comienzo) del viaje de referencia n de la compañía c en el nodo i. Además del tiempo en realizar cada viaje habrá que tener en cuenta el tiempo empleado en realizar un transbordo en caso necesario, al que notaremos como ∆. Asimismo hay que considerar el momento concreto en el que un usuario desea iniciar el viaje (t*), así como el intervalo alrededor del citado momento en el que sigue siendo válido para el viajero el comienzo de su desplazamiento (∆S).

Un condicionante que se presenta es que el número de asientos en cada trayecto no es ilimitado. Se trata por tanto de un problema con restricciones de capacidad. Para modelar esto se empleará una variable que contenga el valor del número de asientos libres, en este caso Pij

cr , que indica el número de asientos libres en el viaje de referencia r de la compañía c en el arco (i,j). Se considera que el usuario actual desea reservar np plazas a lo largo de los diferentes trayectos que componen su viaje.


25

{ }, grafo (conjunto de nodos y arcos) que representa la red de transporte

, : nodos (paradas)

( , ) : arcos (trayectos)

( ) : conjunto de nodos directamente accesibles desde

( ) : conjunto de n

G N A

i j N

i j A

D i i

A j

=∈

∈

M

odos que alcanzan directamente a

: conjunto de compañías de transporte consideradas

, ' : compañías de transporte

( ) : conjunto de viajes programados por la compañía

, ( ) : referencias de viaj

j

C

c c C

V c c

n r V c

∈

∈ es pertenecientes a la compañía genérica

Variables:

1 si el viaje con referencia de la compañía que realiza el usuario usa el arco ( , )

0 en otro caso crij

c

r c i jX =

1 si el viaje con referencia r de la compañía usa el arco ( , )

0 en otro caso crij

c i jδ

=

Datos temporales:

: momento de llegada (o comienzo) del viaje de referencia de la compañía en el nodo

: tiempo medio de transbordo

*: m

cnit n c i

t

∆omento deseado para comenzar el viaje

S: intervalo de tiempo aceptable anterior y posterior al momento *

Otros datos:

: número de asientos libres en el viaje de referencia de la compañía en el crij

t

P r c

∆

arco ( , )

: número de plazas demandas por el usuario actual

: coste del trayecto ( , ) perteneciente al viaje de referencia de la compañía

: longitud del trayecto ( , )

: velocidad

crij

ij

crij

i j

np

C i j r c

l i j

s del modo usado en el viaje de referencia de la compañía en el arco ( , )

, ' : cotas superiores

r c i j

CS CS

Figura 7: Resumen de la notación empleada

2.2.2 Formulación El problema se plantea de la siguiente forma. Se trata de minimizar el tiempo de

viaje, o el coste del mismo o la longitud total recorrida. Además el viajero puede plantear una combinación de preferencias, lo que llevaría a un problema multiobjetivo, que puede plantearse y resolverse de muy diversas formas: Suma ponderada, programación por metas, métodos borrosos, etc.


26

( , ) ( ) ( )

( , ) ( ) ( )

( , ) ( ) ( )

Mínimo costo

Mínima longitud

Mínimo tiempo

cr crij ij

i j D A c C r V c

crij ij

i j D A c C r V c

cr crij ij

i j D A c C r V c

Min C X

Min l X

Min s X

∈ ∈ ∈

∈ ∈ ∈

∈ ∈ ∈

∑ ∑ ∑

∑ ∑ ∑

∑ ∑ ∑

Figura 8: Objetivos del problema

La consecución de los objetivos anteriores está sujeta a una serie de consideraciones derivadas tanto de la naturaleza de las redes como de condiciones particulares del problema en cuestión. Por un lado, se plantean las restricciones de conservación de flujo en las redes. El viajero sólo saldrá de una de las paradas de la red de transporte y sólo llegará a un destino (los sistemas de transporte actuales todavía no han resuelto el problema de la ubicuidad). Además se ha de cumplir que el viajero no pueda quedarse indefinidamente en las paradas intermedias (que se convertirían en sumideros), y que tampoco puedan crearse nuevas instancias del mismo viajero en dichas paradas. Es decir ha de cumplirse la ley de conservación de la masa. La formulación de estas restricciones se encuentra en la Figura 9.

( ) ( )

( ) ( )

1 donde es el nodo origen del viaje para el usuario actual

1 donde es el nodo destino del viaje para el usuario actual

cn cnoj oj

j D o c C n V c

cn cnid id

i A d c C n V c

cn cnik ik

n

X o

X d

X

δ

δ

δ

∈ ∈ ∈

∈ ∈ ∈

∈

=

=

∑ ∑ ∑

∑ ∑ ∑

( ) ( ) ( ) ( )

, , , con , cn cnkj kj

i A k c C V c j D k c C n V c

X i j k N k o k dδ∈ ∈ ∈ ∈ ∈

= ∀ ∈ ≠ ≠∑ ∑ ∑ ∑ ∑ ∑

Figura 9: Restricciones de conservación de flujo

Otro tipo de limitación que se encuentra en este problema es que el viajero determina la hora de salida de su viaje con un cierto intervalo, no siendo válidas aquellas soluciones que no cumplan con este condicionante. Esto determinará que se elija una compañía y un viaje de referencia en función de su horario.

( )

( )( )

( )

* 1 ; ( )

* 1 ; ( )

cn cno oj

j D o

cn cno oj

j D o

t S t X CS c n V c

t t S X CS c n V c

∈

∈

−∆ − ≤ − ∀ ∈

− −∆ ≤ − ∀ ∈

∑

∑

Figura 10: Restricción horaria de salida El parámetro CS de la Figura 10 es una cota superior.

En el caso de que sea necesario realizar transbordos, bien sean cambios de modo o cambios de compañía, el tiempo empleado no puede ser menor que el necesario para hacerlo. Igualmente, tampoco se puede comenzar un trayecto antes de haber finalizado el anterior. Esto deriva en la siguiente restricción:

' '

( ) ' ( )

( ) , ( ); , ' ; ( , ) ; ( , )cn rc nc c rij j j jk

k D j c C r V c

X t t X r n V c c c C i j A j k A∈ ∈ ∈

≤ − ∆ − ∀ ∈ ∈ ∈ ∈∑ ∑ ∑

Figura 11: Restricción de continuación del viaje


27

A lo anterior hay que sumar el hecho de que un viaje compuesto por una serie de

trayectos y que pueda resultar óptimo según los criterios del usuario, puede no ser realizado por éste si no quedan plazas libres en alguno de los mencionados trayectos. Por tanto, hay que modelar esta restricción de capacidad, que queda de la siguiente forma:

( )1 ' , ( ), ( , )cr c nij ijnp P X CS c n V c i j A− ≤ − ∀ ∈ ∈

Figura 12: Restricción de capacidad El problema completo formulado se refleja en la Figura 13.

( , ) ( ) ( )

( , ) ( ) ( )

( , ) ( ) ( )

Objetivo:

Mínimo costo del viaje ó

Mínima longitud del viaje ó

Mínimo tiempo de viaje ó

una combinaci

cr crij ij

i j D A c C r V c

crij ij

i j D A c C r V c

cr crij ij

i j D A c C r V c

Min C X

Min l X

Min s X

∈ ∈ ∈

∈ ∈ ∈

∈ ∈ ∈

∑ ∑ ∑

∑ ∑ ∑

∑ ∑ ∑

( ) ( )

(

ón de distintos objetivos, no siempre compatibles entre sí.

Sujeto a las siguientes restricciones

1 donde es el nodo origen del viaje para el usuario actual

:cn cnoj oj

j D o c C n V c

cn cnid id

n V

X o

X

δ

δ∈ ∈ ∈

∈

=∑ ∑ ∑

( ) )

( ) ( ) ( ) ( )

' '

( ) ' ( )

1 donde es el nodo destino del viaje para el usuario actual

, , , con ,

( )

i A d c C c

cn cn cn cnik ik kj kj

i A k c C n V c j D k c C n V c

cn rc nc c rij j j jk

k D j c C r V c

d

X X i j k N k o k d

X t t X

δ δ∈ ∈

∈ ∈ ∈ ∈ ∈ ∈

∈ ∈ ∈

=

= ∀ ∈ ≠ ≠

≤ − ∆ −

∑ ∑ ∑

∑ ∑ ∑ ∑ ∑ ∑

∑ ∑ ∑

( )

( )

( )

( )

( )

, ( ); , ' ; ( , ), ( , )

* 1 ; ( )

* 1 ; ( )

1 ' , ( ), ( , )

cn cno oj

j D o

cn cno oj

j D o

cr c nij ij

r n V c c c C i j j k A

t S t X CS c n V c

t t S X CS c n V c

np P X CS c n V c i j A

∈

∈

∀ ∈ ∈ ∈

−∆ − ≤ − ∀ ∈

− −∆ ≤ − ∀ ∈

− ≤ − ∀ ∈ ∈

∑

∑

Figura 13: Resumen de la formulación del problema.

2.3 Problemas de resolución La resolución del problema formulado es enormemente compleja. Para que el

problema pueda resolver las necesidades de los viajeros, ha de contemplar un número considerable de paradas, que pueden ser cientos. Si a esto le añade un número considerable de compañías de transporte y que los trayectos posibles y los horarios pueden ser miles, se ve que la magnitud del problema crece exponencialmente. Su


28

resolución por métodos analíticos se vuelve carísima desde el punto de vista computacional.

Otro asunto que complica aún más la resolución del modelo es la no linealidad del problema. En varias de las restricciones se encuentran productos de variables que rompen la deseada linealidad. A esto hay que sumarle la naturaleza de dichas variables, que no son continuas, sino binarias, pudiendo valer sólo 0 ó 1.

Además, cuando se formulan varios o todos de los objetivos, haciendo que el problema sea multiobjetivo, se da el caso de que la disminución de unos objetivos hace que otros se incrementen. Por ello la complejidad aumenta aún más. Habrá que determinar qué objetivos predominan sobre otros y en qué medida, así como plantear qué puntos del frente de Pareto convienen más al criterio del usuario.

El objetivo fundamental del apartado 2.2 ha sido la de plantear el problema para llegar a la conclusión de que la complejidad del mismo, mostrada en los párrafos precedentes, hace muy difícil la resolución analítica del problema. Hay un aspecto que no se ha modelado matemáticamente, que es la consideración de que el usuario puede no querer realizar cambios de modos de transporte o que el número de los mismos no supere una cantidad determinada. Esto hace necesaria la existencia de más variables y más restricciones, complicando todavía más el ya de por sí difícil reto que se ha planteado1.

La dificultad manifiesta del problema hace conveniente el plantear métodos de resolución del mismo basados en heurísticas particulares o metaheurísticas con el fin de ofrecer soluciones en tiempos razonables.

2.4 Problemas de implementación La problemática de la implementación pueda abordarse desde distintos puntos de

vista, pues puede verse afectado por diferentes elementos. Suponiendo que el problema de resolución se ha solventado mediante un método adecuado, éste ha de ser programado de tal forma que se aprovechen al máximo sus cualidades óptimas para dar respuestas rápidas. Para ello hay que seleccionar un lenguaje que optimice el cálculo (ha de ser lo más cercano posible al código máquina), pero que a la vez permita un rápido desarrollo.

Otro problema al que se ha de enfrentar el sistema que implemente el método citado es que ha de atender y ser capaz de soportar múltiple concurrencia, es decir, múltiples usuarios accediendo simultáneamente para obtener información y recomendaciones. Para que la concurrencia no ralentice de forma significativa el sistema, éste habrá de tener los suficientes recursos tanto de procesador como de memoria RAM para poder funcionar sin cuellos de botella por estos aspectos.

En el caso de que la demanda haga necesario instalar varios equipos informáticos (en cluster o mediante especialización de ordenadores) habrá que asegurar

1 No obstante, a pesar de no estar modelado matemáticamente, sí que se le dará solución en el método propuesto en el capítulo 4.


29

que la comunicación entre ellos sea rápida y fiable, lo que requiere protocolos y circuitería adecuada.

La exigencia de resolución en tiempos razonables es máxima ya que un usuario no va a esperar mucho tiempo una respuesta que no sabe si no llega porque no lo resuelve el sistema back end o porque ha habido algún problema de comunicación.

Los usuarios no sólo necesitan velocidad en las respuestas, tanto de recomendación de itinerarios como de información sobre la red de transporte y sus elementos. También requieren un fácil y cómodo acceso desde cualquier lugar2. Será por tanto necesario el establecimiento de interfaces adecuadas (front end) que permitan a los usuarios el acceso a los servicios demandados de una forma sencilla. Asimismo, habrá que hacer uso de los sistemas tecnológicos al alcance de los ciudadanos para permitirles acceder a las aplicaciones desde múltiples ubicaciones. Internet y la telefonía móvil se alzan como dos alternativas viables y al alcance de cualquiera para lograr este objetivo.

Finalmente, y no menos importante, la información y las recomendaciones que se han de proporcionar a los viajeros tienen que ser fiables. Para ello es necesario centralizar la información que puedan proporcionar los distintos agentes implicados en el transporte (gestores de infraestructuras, compañías de transporte y administraciones públicas). Habrá que habilitar mecanismos de recogida de toda esa información. Además, y quizá sea ésta la parte más complicada de todo el sistema, hay que implicar a dichos agentes para que proporcionen dicha información, bien mediante medidas legislativas, bien mediante incentivos. En cualquier caso, el papel de la Administración se torna fundamental.

2 Hay que recordar que uno de los problemas actuales es la dificultad para planificar y reservar un trayecto de media distancia que comience en un área lejana a la del trayecto inicial (véase el apartado2.1.1

Capítulo 3 – Situación actual de la recomendación de itinerarios

30

3 Situación actual de la recomendación de itinerarios

3.1 Métodos de resolución

El problema matemático formulado en la Figura 13 es un problema no lineal, con un gran número de variables y ecuaciones, por lo que la dificultad de su resolución es evidente. El requerimiento de que velocidad de respuesta sea máxima en un entorno de múltiple concurrencia hace que se tengan que desechar los intentos de resolución analítica que, aunque dan respuestas exactas, tardan mucho más tiempo del que es capaz de soportar el usuario. Por tanto, se plantea como algo necesario el emplear otros métodos que permitan el cumplimiento de las expectativas. Estos métodos pueden ser tanto los heurísticos como los metaheurísticos.

Los métodos heurísticos se suelen diseñar para resolver problemas específicos, de tal forma que no suele ser posible la aplicación del mismo método heurístico para resolver un problema distinto. Una ventaja de este tipo de métodos es que son mucho más rápidos que los analíticos, aunque generalmente van acompañados de una menor precisión en las soluciones obtenidas. La mayor utilidad de los métodos heurísticos se da cuando:

• No hay métodos exactos de resolución de un problema • La resolución exacta necesita mucho tiempo de procesamiento • Se dispone de datos poco fiables • No hace falta encontrar la solución óptima al problema • Como paso intermedio en la aplicación de otro método

Los métodos metaheurísticos en cambio, se constituyen como un marco general para

la creación de algoritmos, encontrándose a medio camino entre las heurísticas y los métodos analíticos. Entre los métodos metaheurísticos más habituales se encuentran:

• Los Algoritmos Genéticos • GRASP (Greedy Randomized Adaptive Search Procedure) • Redes Neuronales • Recocido Simulado • Búsqueda Tabú Otro enfoque que puede darse es la adaptación o transformación del problema en

otro del que se tenga un método de resolución ya implementado y por el que se obtenga una solución que lo resuelva de forma indirecta [5]. Este es el planteamiento que se ha adoptado y que se desarrollará con detalle en el Capítulo 4, que permitirá obtener soluciones exactas en un tiempo asumible. Partiendo de un grafo espacial se construirá otro con información espacio-temporal al que se aplicará un algoritmo para la obtención de K caminos mínimos que constituirán las diferentes recomendaciones de viaje a los usuarios. A continuación se hará un estudio de diferentes algoritmos de caminos mínimos para poder seleccionar el adecuado.

3.1.1 Algoritmos de K caminos mínimos El problema del camino mínimo es un problema clásico en programación de

flujo en redes y en el campo de la optimización en general, prueba de ello son los centenares de publicaciones que podemos encontrar sobre el tema. Sin embargo, el


31

problema de determinar no sólo el camino más corto, sino también el segundo más corto, el tercero, y así hasta el K-ésimo camino más corto, siendo también un problema clásico, no ha sido estudiado tan intensamente. Y esto a pesar de la multitud de aplicaciones prácticas en que puede encontrarse, y a que se puede considerar como una generalización del primero (con K=1 para el problema del camino mínimo). Se puede hacer la siguiente clasificación de algoritmos de K caminos mínimos:

• Algoritmos basados en principio de Optimalidad o Algoritmos de etiquetado o Algoritmos de supresión de caminos

• Algoritmos basados en árbol de caminos mínimos

Mientras los algoritmos de corrección de etiquetas determinan el conjunto de K caminos mínimos tras la ejecución de todas sus operaciones, en los algoritmos de asignación de etiquetas cada camino se determina conforme se va ejecutando el algoritmo.

3.1.2 El Principio de Optimalidad Los algoritmos de caminos mínimos de etiquetado están basados en el principio

de optimalidad, que básicamente enuncia que un camino mínimo está formado por subcaminos que son mínimos a su vez. Está demostrado que el problema del camino mínimo satisface el principio de optimalidad siempre que no existan ciclos con coste negativo en la red.

Este principio se puede generalizar tomando K > 1 si se desea poder aplicarlo en algoritmos para la obtención de K caminos mínimos. Se demuestra que si se asume que el coste de cualquier ciclo en la red es mayor o igual que cero, el K-ésimo camino mínimo está formado por J-ésimos caminos mínimos, siendo J menor o igual que K.

3.1.2.1 Algoritmos de etiquetado Estos algoritmos se caracterizan por el uso de una o más etiquetas para cada

nodo de la red. En el problema de camino mínimo, a cada nodo se le asigna una etiqueta simple, en el problema de K caminos mínimos, podemos tener una etiqueta simple o varias etiquetas asociadas a cada nodo.

En la forma general de los algoritmos de etiquetado, se usa una etiqueta compuesta por tres K-tuplas: πi, ξi y θi. El significado de cada elemento es el siguiente: π

ki es la k-ésima componente de πi, e indica la distancia del k-ésimo mejor camino desde

el nodo origen s, hasta el nodo i. ξki representa el nodo anterior al nodo i en el k-ésimo

mejor camino y θki indica su posición en ξi. Todas las componentes de πi se inicializan a

infinito excepto la correspondiente al nodo origen, que se inicializa a cero. Shier fue el primero en proponer algoritmos dentro de este grupo [29][30]. La forma general de estos algoritmos de etiquetado para K caminos mínimos es la que se muestra en la Figura 14:


32

// X subconjunto del conjunto de nodos {πi

1, ... , πik }�� {+∞∞∞∞, ... ,+ ∞∞∞∞}

πorigen1�0; no está usado

X � {origen} Mientras X ≠≠≠≠ 0 i � nodo de X X � X – {i} Para cada arco (i, j) de A Para cada k desde 1 hasta K tal que ππππi

k es finito y no está usado πi

k está usado Si (ππππi

k + cij < max{ππππj1, .. , ππππj

k }) l � índice del max{πj

1, .. , πjk } en {πj

1, .. , πjk }

πjl � πi

k + cij ; ξjl � i ; θj

l � k πj

1 no está usado Si j no pertenece a X X � X U {j} Fin Si Fin Si Fin Para Fin Para Fin Mientras

Figura 14: Forma general de los algoritmos de etiquetado

Estudiando a fondo el algoritmo anterior, se puede concluir que el proceso de etiquetado de tres K-tuplas no es eficiente. Entre otros motivos, se pueden destacar los siguientes:

- Sea i un nodo que se extrae del conjunto X y asumamos que la etiqueta del nodo i se actualiza posteriormente. De este modo, i se incluye de nuevo en el conjunto X y cuando se extrae de nuevo, algunos cálculos no pueden ser ejecutados por algunos valores finitos de πk

i aquellos que fueron usados antes de actualizar πi. Para conseguir esto se necesita una bandera asociada a cada nodo i. En este caso, la bandera de i podría ser una K-tupla cuyas K componentes se ponen a trae si y solo si πk

i ha sido usada anteriormente.

- También puede ocurrir que algunas componentes de las etiquetas se queden con el valor infinito al terminar el algoritmo. Esto ocurre cuando el número de caminos desde s a i es menor que K. En este caso, la memoria no se usa de un modo eficaz.

- Para asegurar que el algoritmo sea finito, la componente máxima de la etiqueta de distancia de un nodo j tiene que ser computada cada vez que un nodo i se extrae de X y para cada πk

i finito, lo que representa una gran cantidad de esfuerzo computacional.

El tratar con las etiquetas de tres K-tuplas que se usan en la forma general del algoritmo de etiquetado de K caminos mínimos es computacionalmente muy costoso. Además, también puede ocurrir que el valor de K sea desconocido, por ejemplo, cuando se quiere calcular los caminos mínimos que satisfacen algunas condiciones prefijadas. En este caso, el algoritmo anterior no puede usarse. De este modo, se ha de definir una versión distinta del algoritmo, donde a cada nodo se le asignan varias etiquetas. Cada componente de la etiqueta de distancia del nodo i, se considera como una etiqueta del nodo i ella misma. Para ello se amplia el conjunto de nodos N de la red, de tal forma


33

que a cada nodo se le asigna una única etiqueta. De esta forma, además de conseguir simplificar la notación, se comprueba que es más eficiente computacionalmente. Se define una función h, que asigna a cada nodo de la red un número natural. Como a cada nodo se le pueden asignar más de una etiqueta, la función h no tendría inversa, sin embargo, se define del siguiente modo, para hacer posible calcular qué números naturales le corresponden a cada nodo: h-1(i) = {k ∈ ℵ | h(k) =i}.

Señalar que el algoritmo de etiqueta única no funciona para valores desconocidos de K.

3.1.2.1.1.1 Algoritmos de corrección de etiquetas

En este tipo de algoritmos, las etiquetas asignadas a los distintos nodos de la red son modificadas durante la ejecución del algoritmo. El conjunto X se puede implementar como una cola FIFO. De este modo no hay elección a la hora de extraer o añadir un elemento i del conjunto X, dando lugar a una generalización del algoritmo de Bellman-Ford-Moore de camino mínimo. Es importante comentar que la complejidad teórica de este algoritmo no es polinomial en el peor caso, ya que no es posible calcular un tope de orden polinomial para las etiquetas que serán calculados para cada nodo. También hay que señalar que el conjunto de caminos mínimos se determina sólo tras la ejecución del algoritmo. En la Figura 15se describe una generalización del algoritmo de Bellman-Ford-Moore con etiquetas únicas.

3.1.2.1.1.2 Algoritmos de asignación de etiquetas

La eficiencia de los algoritmos de corrección de etiquetas puede ser mejorada fácilmente. Se trata de manipular X de tal manera que la etiqueta asignada al elemento tomado de X sea permanente, tal y como ocurre en el algoritmo de Dijkstra para problema del camino mínimo. Se puede enunciar por tanto una generalización del algoritmo de Dijkstra para el problema de los K caminos mínimos, que será desarrollado con más detalle en un apartado posterior.

Es importante destacar que el conjunto de caminos mínimos va siendo computado a lo largo de la ejecución del algoritmo. Se añade un nuevo camino al conjunto PK (conjunto de K caminos mínimos) cada vez que un elemento k es sacado de X para el que h(k)=t.

3.1.2.2 Algoritmos basados en la supresión de caminos Son algoritmos basados en el concepto de supresión de caminos de Martins [39].

Cada vez que se calcula el camino mínimo de la red, se elimina, y se vuelve a calcular el siguiente camino mínimo, que será por tanto el segundo camino mínimo. Se procede del mismo modo hasta encontrar los K caminos necesarios [36] [37].

3.1.3 Árbol de caminos mínimos Los algoritmos de cálculo de los K caminos mínimos que no se apoyan en el

principio de optimalidad suelen basarse en la construcción de un árbol de caminos mínimos y en la realización de variaciones sobre el mismo.


34

El árbol de caminos mínimos tiene la propiedad de representar el conjunto de k caminos mínimos desde un origen s a un des tino t sin repetir las partes de los mismos que son comunes. Además el árbol de caminos mínimos describe los distintos caminos mínimos en base a los distintos recorridos que se pueden realizar desde su nodo origen, que será el nodo s, y sus nodos hojas, que serán siempre el nodo t.

// X: Subconjunto del conjunto ampliado de nodos // contadori: número de caminos que han sido determinados desde el origen a i // elm: número de elemento del conjunto extendido de nodos contadori � 0 para todo i perteneciente al conjunto original de nodos elm � 1 h(elm) � origen; h-1(origen) � {elm} πelm � 0 X � {elm} Mientras X ≠≠≠≠ 0 k � primer elemento de X X � X – {k} i � h(k) Para cada arco desde i a j de la red Si contadorj = K

l � elemento de h-1(j) para el que πl = max{πx tal que x pertenece a h-1(j)}

Si ππππk + coste del arco de i a j <ππππl πl � πk + coste del arco de i a j ξl � k Si l no pertenece a X X � X U {l} y l será el último elemento de X Fin Si

Fin Si Si No /* contadorj < K */ elm � elm +1 πelm � πk + coste del arco de i a j ξelm � k contadorj � contadorj +1 h(elm) � j h-1(j)� h-1(j)U {elm} X � X U {elm} y l será el último elemento de X Fin Si Fin Para Fin Mientras Encontrar los k caminos mínimos a partir de la información de ξξξξ, h, h-1 y ππππ

Figura 15: Algoritmo de corrección de etiquetas

A continuación se ilustra lo anterior con un ejemplo: Sea una red con seis nodos donde el origen s es el nodo 1 y el destino t es el nodo 6. Sea el conjunto de K caminos mínimos (con K = 3) el conjunto P={p1, p2, p3}, con p1={1, 4, 6}, p2={1, 6} y p3={1,


35

4, 1, 6} (puede apreciarse como se está considerando el problema sin restricciones para los ciclos, ya que en este último caminos existe uno). El árbol de caminos mínimos sería el siguiente:

1

4

6

1

6

6

Figura 16: Ejemplo de árbol de caminos mínimos

Un algoritmo para la construcción del árbol de caminos mínimos T partiendo del conjunto de caminos P es el que se muestra en la Figura 17. Al nodo vk se le llamará nodo de desviación, ya que es el nodo a partir del cual el camino pk se desvía de los caminos ya existentes en el árbol T, y al camino k

tvkp lo llamaremos desviación del

camino pk respecto al árbol de caminos mínimos T.

// T – árbol de caminos mínimos T � ∅ k� 1 Mientras k < K Arco � primer arco de pk Destino � destino del arco Arco p� subcamino de pk desde el origen s hasta Destino Mientras p ∈∈∈∈ T Arco � siguiente arco de pk Destino � destino del arco Arco p� subcamino de pk desde el origen s hasta Destino

Fin Mientras vk� origen de Arco k

tvkp � subcamino de pk desde vk hasta t

ksvk

p � subcamino de pk desde s hasta vk

T � T ∪ ktvk

p /* de manera que pk = ksvk

p - ktvk

p sea un camino de T */

k � k +1 Fin Mientras

Figura 17: Algoritmo de creación del árbol de caminos mínimos


36

3.1.3.1 Algoritmo de Yen Generalizado Un algoritmo que hace uso de un árbol de caminos mínimos es el algoritmo de

Yen generalizado, que se describe a continuación (véase la Figura 18). En él se emplea un conjunto X de caminos candidatos al siguiente camino mínimo. Obviamente X se inicializará con el camino mínimo desde el origen s hasta el destino t.

En el k-ésimo paso del algoritmo, el k-ésimo camino mínimo pk es tomado del conjunto de candidatos X, y se incorpora a X un conjunto de nuevos candidatos al (k+1)-ésimo camino mínimo. Ya que pk coincide con algún camino mínimo pl con 1 ≤ l < k desde el nodo inicial s hasta el nodo de desviación vk, todos los nodos hasta vk han sido considerados para intentar generar nuevos candidatos. Por lo tanto, desde todos los nodos v de k

tvkp , el camino mínimo entre los nodos adyacentes a v hasta t cuyo primer

arco (v, x) no está en T será calculado. Este camino mínimo puede ser determinado de una manera muy simple si se ha calculado previamente el conjunto de caminos mínimos entre el nodo destino t y todos los demás nodos de la red, Tt, que se pueden calcular podemos calcular mediante algún algoritmo (Dijkstra, por ejemplo). En realidad (v, x) ∉T debe ser calculado de forma que se minimice el coste de pxt, de manera que a este camino mínimo se le denominará p*

xt, siendo éste el camino mínimo entre x y t, es decir el camino en Tt desde t hasta x.

Este es un algoritmo que se puede considerar una generalización del algoritmo de Yen, ya que en este algoritmo y a diferencia de lo que ocurre en el algoritmo original, se permitan ciclos.

// X: Conjunto de candidatos para el siguiente camino mínimo Calcular Tt p1� Camino mínimo desde s hasta t, donde p1 es un camino de Tt k � 1 X � {pk} T � {pk} Mientras k< K X � X – {pk} vk � nodo de desviación de pk Para cada nodo v ∈∈∈∈ k

tvkp

Calcular el arco (v,x) ∉ T tal que el camino mínimo desde x a t, p*xt, es mínimo

respecto a todos los posibles x /* p*xt es un camino de Tt */

q � ksvp - (v, x) - p*xt

X � X ∪ {q} qvt � (v, x) - p*xt T � T ∪ qvt /* De forma que k

svp - qvt ∈ T */

Fin Para k � k +1 pk � Camino mínimo en X Fin Mientras

Figura 18: Generalización del algoritmo de Yen


37

La complejidad computacional de la generalización del algoritmo de Yen es O(Km), tras la determinación de Tt.

3.1.3.2 Algoritmo MPS Mediante el uso de una estructura de datos apropiada para la representación de la

red, es posible conseguir un aumento en la eficiencia respecto al algoritmo anterior. De esta forma si el conjunto de arcos está agrupado por su nodo origen, y además en estos grupos se ordenan los arcos basándose en su coste reducido, la determinación del arco a escoger en el esquema usado por el algoritmo anterior es inmediata.

Los pasos del algoritmo MPS son prácticamente iguales a los de la generalización del algoritmo de Yen (Figura 19). Sin embargo la determinación de los nuevos caminos candidatos resulta más fácil, gracias a la estructura de datos.

La complejidad computacional del algoritmo MPS es O(m·log m + K n) tras la determinación de Tt. En realidad el cálculo de los costes reducidos y la construcción de la estructura de datos puede hacerse en O(m·log m), además en el peor caso, no más de n nodos diferentes deben ser considerados tras el nodo de desviación, por lo que por cada k, n nuevos caminos candidatos son generados, que pueden obtenerse en O(n).

// X: Conjunto de candidatos para el siguiente camino mínimo Calcular Tt

Calcular los costes reducidos para cada arco de la red Dados los costes reducidos anterior, reordenar y construir la estructura de datos de forma adecuada par una ejecución eficiente del algoritmo p1� Camino mínimo desde s hasta t /* p1 es un camino de Tt */ k � 1 X � {pk} T � {pk} Mientras k< K y X≠≠≠≠∅∅∅∅ X � X – {pk} vk � nodo de desviación de pk Para cada nodo v ∈∈∈∈ k

tvkp

Calcular el arco (v, x) ∉ T tal que el camino mínimo desde x a t, p*xt, es mínimo

respecto a todos los posibles x, basándose en la estructura de datos /* p*xt es un camino de Tt */ q � k

svp - (v, x) - p*xt

X � X ∪ {q} qvt � (v, x) - p*xt T � T ∪ qvt /* De forma que k

svp - qvt ∈ T */

Fin Para k � k +1 pk � Camino mínimo en X Fin Mientras

Figura 19: Algoritmo MPS


38

3.1.3.3 Algoritmo de Dijkstra y sus modificaciones El algoritmo original de Dijkstra data de 1959 [35] y resuelve el problema de

encontrar la ruta mínima en una red dada. El algoritmo calcula un árbol de caminos mínimos que parten del origen. Para la creación de este árbol, se apoya en el uso de etiquetas asignadas a cada nodo. El algoritmo no sólo calcula la mejor ruta entre un origen y un destino dados, sino que calcula el camino mínimo entre un origen y todos los posibles destinos.

// Las etiquetas πi van a representar la distancia del nodo correspondiente al nodo // origen. Se inician todas las distancias a infinito menos la del nodo origen que es // nula. X es un subconjunto de N P(i) contiene el nodo anterior a i en el camino X←{s} πs←0 πk←∞ para k≠s Mientras X≠Ø i ← nodo de X X ← X-{i} Para cada arco (i,j) de A Si (πi + cij < πj) πj← πi + cij

P(j) ← i Si (j ∉ X) X ← X ∪ {j} Fin Si Fin Si Fin Para Fin Mientras

Figura 20: Algoritmo Dijkstra de camino mínimo

Tomando como ejemplo la red de la Figura 21, la aplicación del algoritmo de Dijkstra en dicha red consigue la construcción del árbol de caminos mínimos en 9 iteraciones del algoritmo. En la Figura 22 se muestran dos pasos intermedios de la construcción del árbol (a y b) y el resultado final (c).

El algoritmo mostrado construye un árbol con el camino mínimo hacia cada nodo. Esto, que resulta muy útil en muchas aplicaciones, no cubre todas las necesidades del proyecto, pues se trata de ofrecer una serie de recomendaciones para dar al usuario la libertad de elegir entre ellas. Para conseguirlo hay que modificar el algoritmo, dando lugar al Algoritmo de Dijkstra de K caminos mínimos, que se describe continuación.


39

Figura 21: Red ejemplo para resolver algoritmos de k caminos mínimos

0

1 4

0

2 1

0

1 4

0

2 1

26 7 2

0

1 4

0

2 1

26 7 2

3

5

6 8

0

8 4 5

10 7

(a) (b) (c) Figura 22: Camino mínimo encontrado sobre la red ejemplo

Se asume sin pérdida de generalidad que cij≥0 para cualquier arco (i,j). Es un

algoritmo de asignación de etiquetas. El conjunto de caminos PK se va computando a medida que se va ejecutando el algoritmo. Cuando un elemento k se extrae del subconjunto de nodos X, tal que h(k) = t, un nuevo camino se añade al conjunto PK. Puede verse que para K=1 este algoritmo funciona del mismo modo que el algoritmo anterior.

Para este algoritmo el espacio de memoria requerido es O(km), de forma que usando una estructura de datos adecuada para representar X, el tiempo de ejecución requerido será O(km). Debido a que el número de etiquetas asignadas es muy elevado, se trata de un algoritmo poco eficiente en cuanto a espacio de memoria requerido. Se podría pensar en una variación del algoritmo, de modo que en X se almacenaran sólo los K caminos más cortos desde s a i, pero esto implicaría un incremento en el tiempo de ejecución.


40

// X subconjunto de N*, conjunto de nodos extendido //counti es el número de caminos que son determinados desde s a i //elm número de elementos de N* counti ← 0 para todo i del conjunto de nodos N elm ← 1 h(elm) ← s; h-1(s) ← {elm}; πelm ← 0 X ← {elm} PK ← Ø Mientras (countt < K) y (X ≠ Ø) k ← elemento de X que cumpla πk ≤ πx para cualquier x de X X ← X – {k} i ← h(k)

counti ← counti +1

Si (i=t) //Se ha encontrado un camino desde s a t p ← camino desde 1 a k PK ← PK ∪ {h(p)}

Fin Si

Si (counti ≤ K) Para cada arco (i,j) del conjunto A elm ← elm +1 πelm ← πk + cij; ξelm ← k h(elm) ← j; h-1(j) ← h-1(j) ∪ {elm} X ← X ∪ {elm} Fin Para

Fin Si Fin Mientras

Figura 23: Algoritmo Dijkstra de K caminos mínimos

La complejidad teórica de este algoritmo puede establecerse atendiendo al peor

caso de análisis. Asumiendo que p1, el camino más corto desde el origen s hasta el destino t, es un camino hamiltoniano, es decir, tiene n-1 arcos y es un camino sin bucles y además el arco (t,s) pertenece al conjunto de arcos A y tiene coste nulo, el K-ésimo camino más corto puede escribirse como sigue: p1 ◊ (t,s) ◊ p1 ◊ … ◊ (t,s) ◊ p1 , K veces, por lo tanto, a cada nodo se le asignan como máximo K etiquetas permanentes. El número de elementos que son generados desde cada etiqueta permanente del nodo i es exactamente el número de arcos para los cuales el nodo inicial es i, que como máximo será m, por lo tanto, X tiene como máximo Km elementos. Por lo tanto el espacio de memoria necesario es O(Km), además, si se usa una estructura de datos apropiada para almacenar X, la complejidad en tiempo es también O(Km).

Tomando la red de ejemplo de la Figura 21, se va a mostrar la resolución del

problema eligiendo como nodo origen el 0 y como nodo destino el 8, así como un valor de K=2. Algunos pasos se ven reflejados en la Figura 24.


41

0

1 4

1 2 7

0

21

2 6 2

0

1 4

1 2 7

0

2 1

2 6 2

2

2

6

6

6 8

4 5

0

1 4

1 2 7

0

2 1

2 6 2

2

2

6

6

6 8

4 5

...

...0

1 4

1 2 7

0

21

2 6 2

3 2

6

8

6 84

5

5 7 8

8

3

5 7 8

8 4

0

1 4

4

1 2 7

3

12

9139

8

89

11

1515

121410

15

121410

8

2

8

Figura 24: K caminos mínimos encontrados sobre la red ejemplo El conjunto de caminos resultante de la ejecución del algoritmo para la red dada es:

p1= < 0, (0,4), 4, (4,7), 7, (7,8), 8 > p2= < 0, (0,4), 4, (4,2), 2, (2,3), 3, (3,8), 8 >

Y el coste asociado a cada uno de ellos es:

c(p1)= 5 c(p2)= 12 Hasta ahora se han tratado algoritmos de camino mínimo en base a un único criterio

(la distancia o el peso asociado a cada arco del grafo). Una última modificación sería


42

necesaria entonces para poder aplicar el algoritmo al proyecto. Se trata de incluir los diferentes criterios de búsqueda que puede solicitar un usuario, algunos de ellos enfrentados entre sí. Para ello, a cada enlace (i, j) de A se le asocia un conjunto de R valores no-negativos y aditivos, wr(i,j), r = 1,2,…R. La función objetivo a minimizar será una combinación lineal de estos valores:

∑=

=R

rrr jiwajiw

10 ),(),(

En el algoritmo que se presenta a continuación se usa la función fij como combinación lineal de dos valores no-negativos y aditivos, que vamos a suponer que son el tiempo y del coste, ésta será la función que va a marcar el camino entre el origen y el destino: 2

21

1 ijijij cacaf ⋅+⋅=

// X: subconjunto de N*, que es el conjunto extendido de nodos // counti que contabiliza el número de caminos desde el nodo origen al nodo i // elm número de elementos de N* // a1, a2, factores multiplicativos asociados a los parámetros counti=0 para cualquier i de N elm = 1 h(elm) = s, h-1(s)={elm}, c1

elm= 0, c2elm= 0, πelm=0

X={elm} PK=Ø Mientras que (countt<K) && (X ≠ Ø) k=elemento de X tal que πk≤πx para cualquier valor de x que pertenezca a X X=X-{k} i=h(k) counti= counti+1 Si (i=t) // Hemos encontrado una ruta origen-destino p camino desde 1 a k PK= PK U {h(p)}

Si no // Si aún no hemos llegado al destino, seguimos buscando Si (counti ≤ K)

Para cada arco (i,j) de A elm = elm +1 fij= a1· c

1ij + a2· c

2ij

πelm= πk + fij, ξelm=k c1

elm = c1k + c1

ij c2

elm = c2k + c2

ij

h(elm) = j, h-1(j) = h-1(j) U {elm} X = X U {elm} Fin Para Fin Si Fin Si Fin Mientras

Figura 25: Algoritmo Dijkstra de K caminos mínimos multiobjetivo


43

3.1.4 Comparativa de los distintos tipos de algoritmos A continuación se presenta una tabla donde se recogen los órdenes de

complejidad de los algoritmos expuestos anteriormente:

Algoritmo Complejidad Generalización alg. Dijkstra O(Km) Generalización alg. Yen O(Km)3 Algoritmo MPS O(m·log m +Kn)3 Tabla 1: Complejidad de los algoritmos de k caminos mínimos

En la tabla anterior no se ha considerado el algoritmo de Bellman-Ford-Moore

al considerar que no puede competir en términos de eficiencia computacional con los anteriores, y que tiene prácticamente la misma eficiencia que un método de fuerza bruta.

En principio podría pensarse que la mejor opción a la hora de abordar problemas de ruta mínima es el algoritmo MPS, dado que su complejidad computacional teórica tiene un orden menor al de los otros algoritmos de la tabla. Sin embargo, hay que tener en cuenta la necesidad del cálculo del árbol, antes de la aplicación del algoritmo, el valor de las constantes en el orden de los algoritmos, y la dificultad de la implementación de cada uno de los algoritmos. Además, tal y como se ha escrito anteriormente, el algoritmo MPS basa su eficiencia en el uso de una estructura de datos avanzada para la búsqueda de los caminos y en el uso de los costes reducidos. Por tanto es posible que mediante la aplicación de estructuras de datos avanzadas en el algoritmo de Dijkstra generalizado se consiga también reducir el orden del mismo, o al menos, mejorar su eficiencia aplicada.

3.2 Sistemas ATIS El método de recomendación de itinerarios que se va a describir en el Capítulo 4

y otras funcionalidades adicionales van a implementarse en un sistema cuya función será la de informar al viajero. Por tanto, se puede considerar que entra dentro del ámbito de los sistemas avanzados de información al viajero (ATIS). A continuación se mostrará la situación de algunas de las tecnologías que lo componen y que ya fueron descritas en el Capítulo 1. Particularmente se tratará de dos directamente relacionadas con el proyecto en cuestión.

3.2.1 SMS Un servicio de alertas es una aplicación que es capaz de enviar notificaciones a usuarios informando de determinados eventos que, generalmente, suceden en tiempo real. Para este fin, el usuario necesita definir cuáles van a ser las características de la información que desea recibir. Una posibilidad es enviar una petición al sistema en el momento en que el usuario desea ser informado. Este sería el método utilizado en multitud de las aplicaciones actuales basadas en mensajes cortos (SMS), en las cuales el usuario envía un mensaje a cierto número de teléfono (generalmente un número corto fácilmente recordable) con una palabra clave, por ejemplo “tráfico Valencia”. En ese instante, el sistema le responde con la información solicitada. Otra posibilidad es la 3 Estos ordenes de complejidad son válidos teniendo precalculado en árbol Tt que puede ser calculado fácilmente mediante el algoritmo de Dijkstra en O(n2).


44

creación de un perfil de envío a través de alguna interfaz, mediante la cual el usuario indica cuándo desea recibir la información (días y horas), cómo desea recibirla (voz, e-mail, SMS u otro medio) y que tipo de información desea recibir (retenciones u obras y segmentos de carreteras, por ejemplo). Si el sistema detecta que una incidencia registrada cumple con el perfil del usuario, envía la notificación o alerta con información del suceso. El método basado en el envío de una petición al servidor (información bajo demanda o pull) tiene como ventaja que en todo momento el usuario controla el envío de las alertas, pero tiene el inconveniente de que es posible que el servidor no contenga ninguna información de interés y que, por lo tanto, la petición del usuario incurra en un coste sin necesidad. El método basado en la suscripción y recepción de eventos iniciados por el servidor (información de tipo push) aumenta la flexibilidad y la potencia del sistema, ya que permite la utilización de interfaces gráficas en la suscripción que pueden implementar mapas donde el usuario seleccione fácilmente su itinerario. Actualmente existen prototipos desarrollados que permiten el envío de mensajes de voz y correo electrónico, aunque no han alcanzado todavía la fase de explotación. Sin embargo, el auge de la tecnología de mensajes cortos (SMS) ha hecho posible la aparición de diversos servicios que ofrecen información del estado del tráfico mediante este tipo de eventos. Por otra parte, los actuales servicios de alertas e información bajo demanda convergen hacia los servicios de proximidad, donde el sistema es capaz de determinar la posición exacta del usuario, proporcionando información relativa a la misma, como gasolineras, hoteles, restaurantes o farmacias.

3.2.2 Información del transporte público En España, existen pocas soluciones en el campo la información intermodal/multimodal de viajeros y éstas no son definitivas. Normalmente sólo se tiene acceso a portales (estáticos) con información limitada sobre otros medios de transporte o con un ámbito territorial reducido a una ciudad4. Para encontrar soluciones más extensas dentro de Europa5 se debe ir a la ciudad de Londres, donde se desarrolló un portal dinámico de información multimodal / intermodal con los diferentes medios públicos (autobús, tren, metro, barcos por el Támesis)6, o en la región de Marsella y alrededores7. Otro referente a tener en cuenta en este sentido son los Estados Unidos8,

4 http://www.ctm-madrid.es/ . Sistema de información de transportes públicos de Madrid.

5 http://www.ul.ie/~infopolis/library/index.html . Informes de la Universidad de Limerick de proyectos sobre diferentes

medios europeos que ofrecen información al viajero (entre ellos intermodal/multimodal).

6 http://www.transportforlondon.gov.uk/tfl/ . Sistema de información de transportes públicos de la ciudad Londres y

alrededores.

7 http://www.lepilote.com/ . Sistema de información al viajero en la región de Marsella.


45

donde desde hace tiempo se viene investigando y trabajando en esta materia, sobre todo enfocado a los transportes de mercancías. A nivel de estandarización, es el objetivo de varias normas Europeas e internacionales. Varios grupos de trabajo, comités técnicos y comisiones están trabajando en este tema, tanto europeos (CEN) como internacionales (ISO). Considerando el gran interés internacional de estandarización, el auge de las nuevas tecnologías móviles y el posible interés comercial que puede aportar, el futuro de la publicación de la información de los medios de transporte parece alentador. En un corto plazo será posible por medio de un dispositivo móvil obtener toda la información de tráfico, transportes públicos y otra información interesante de viaje. Como se observa en algunos proyectos, como TPEG y TRIDENT la tendencia será la multimodalidad, es decir, la integración de todos los medios de transportes existentes en sistemas de información temáticos.

8 http://www.its.dot.gov/ . Un ejemplo se puede encontrar en el proyecto SWIFT (Seattle Wide-Area Information for

Travellers) o en el proyecto SmarTraveler (www.smartraveler.com), todos ellos en un contexto de desarrollo y evaluación de

un plan nacional de ITS en EEUU.

Capítulo 4 – Método exacto de recomendación de itinerarios

46

4 Método exacto de recomendación de itinerarios

En este capítulo se describe con detalle un método empleado para la resolución del problema matemático planteado anteriormente (Apartado 2.2). Lo más destacable del método es que se obtiene, para un problema muy complejo (NP-Hard), una solución exacta que es óptima y con un coste computacional completamente admisible para su implementación en aplicaciones de recomendación en tiempo real. Esto se consigue mediante la creación de un grafo espacio-temporal intermedio del que se eliminarán, mediante un algoritmo de poda, aquellos nodos y arcos que no intervengan en la recomendación solicitada. Finalmente, a este grafo podado se le aplicará un algoritmo de obtención de k-caminos mínimos que dará como resultado una serie de recomendaciones ordenadas en función de las preferencias manifestadas por el usuario final.

Con el fin de facilitar la comprensión de los distintos pasos para la obtención de la solución exacta, se va a partir de un ejemplo simplificado de red física de transporte que ilustrará todo el proceso. Se van a considerar cuatro ciudades con dos paradas cada una y con conexiones entre las mismas tal como muestra la Figura 26.

Figura 26: Red de transporte de ejemplo

Cada trayecto a realizar entre las distintas paradas se caracterizará por un arco,

mientras que las paradas se representarán mediante nodos.

Además de la información geográfica (i.e. espacial) que proporciona el grafo de la red de transporte, es necesario disponer de información temporal acerca de la realización de los viajes. Para ello se requiere disponer de la tabla completa de horarios


47

de toda la red considerada. Algunos horarios correspondientes a la red de ejemplo se muestran en la Tabla 2.

Origen Destino Ciudad Parada Hora salida Ciudad Parada Hora llegada

A 1 1 C 1 3 A 1 2 B 1 3 A 1 3 C 1 5 A 1 4 B 1 5 A 2 2 B 2 4 A 2 4 B 2 6 B 1 1 C 1 4 B 1 1 D 1 4 B 1 3 C 1 6 B 1 3 D 1 6 B 2 1 C 2 3 B 2 3 C 2 5

etc.,,,

Tabla 2: Horarios para el ejemplo

4.1 Construcción del grafo espacio-temporal El método exacto para la obtención de recomendaciones presentado aquí necesita

para su aplicación agrupar la información geográfica y de los horarios. Esto se consigue creando un grafo intermedio que aúne toda la información espacio-temporal disponible. En este grafo espacio-temporal, a diferencia del grafo de partida, los nodos representan un evento temporal referido a una parada, bien sea una llegada a la misma o bien una salida. Asimismo, estarán caracterizados por la estación de pasajeros que representan y por la ciudad a la que pertenecen. De igual forma, cada arco estará caracterizado por los siguientes parámetros:

• Distancia entre las paradas origen y destino. • Modo de transporte del arco, que será único. Si existe más de un modo de

transporte que pueda realizar el trayecto entre dos mismas paradas (por ejemplo, el caso en el que los extremos del arco sean estaciones intermodales), será necesario considerar un arco por cada modo.

• Duración del trayecto: tiempo en recorrerse la distancia entre los extremos a la velocidad del modo de transporte que realiza el viaje.

• Empresa de transporte que realiza el trayecto. • Precio del trayecto. • Número de viajeros con reserva en este trayecto. • Capacidad: número total de viajeros que caben en el medio de transporte

considerado. Este grafo tiene la característica de que incluye todos los posibles viajes de la red de transporte que están planificados por las diferentes compañías de transporte a lo largo de un periodo de tiempo. Un ejemplo simplificado del grafo correspondiente a la red de ejemplo se muestra en la Figura 27.


48

Figura 27: Grafo espacio-temporal

Las ciudades se representan en el eje vertical. Las diferentes estaciones en la

misma ciudad se representan mediante líneas paralelas. Los nodos se representan mediante círculos, estando los más tempranos hacia la izquierda y los más tardíos a la derecha. Un arco entre dos nodos representa un desplazamiento, generalmente una parte de un viaje de una sola compañía. Los arcos representan un desplazamiento en el tiempo, de forma que los viajes están ordenados de la derecha a la izquierda. Esto hace que el grafo espacio-temporal sea dirigido y que, debido a que el tiempo no puede recorrerse en sentido inverso, no existan bucles.

4.2 Poda del grafo Debido a que el grafo recoge todos los posibles viajes a lo largo de un intervalo

de tiempo, para el cálculo de recomendaciones de viajes entre dos ciudades habrá muchos nodos y arcos que no serán necesarios. Por tanto, para aumentar la eficiencia del cálculo será necesaria una poda previa para tener en consideración sólo aquellos elementos del grafo que sean relevantes.

La reducción del grafo dependerá de la ciudad origen, de la ciudad destino y del intervalo temporal deseado relativo a la salida o llegada. Por simplicidad se explicará el método considerando que el usuario fija un intervalo de tiempo para la salida, pues el caso de fijar la llegada es equivalente y no aportaría información relevante respecto al método descrito.

A continuación se explica cómo se descompone el proceso total de la poda del grafo en una serie de pasos con el objetivo de realizarla de manera eficaz. La finalidad de esta descomposición es doble. Por una parte se facilita su explicación y compresión. Por otra, resulta más sencilla la implementación de su algoritmia.

4.2.1 Paso 0: Eliminación de arcos de llegada al origen y de salida desde el destino

Tras la construcción inicial del grafo, lo habitual es que haya arcos que tengan como destino nodos de la ciudad origen y otros que tengan como origen nodos de la ciudad destino. Aunque dichos arcos no vayan a desvirtuar el resultado final del


49

algoritmo de caminos mínimos, entre otros motivos porque el grafo es dirigido, sí que pueden ralentizar el cálculo de los mismos. Por ello es conveniente eliminar ambos tipos de arcos en los estadios iniciales del proceso de poda.

4.2.2 Paso 1: Eliminación de información anterior a la salida Debido a que se van a estudiar los viajes a partir de una fecha (y/u hora) de salida desde la ciudad origen, todos los viajes anteriores no se tendrán en consideración, por lo que habrán de suprimirse. Para ello se eliminan los nodos cuyos horarios sean anteriores al límite inferior del rango del horario de salida establecido por el usuario. Asimismo, se quitan del grafo los arcos de entrada y salida de dichos nodos. Todo esto se muestra en la Figura 28.

Figura 28: Supresión de información anterior a la salida

Al suprimir estos nodos y arcos pueden quedarse nodos huérfanos, es decir, sin arcos de entrada ni de salida. Éstos también se eliminan al no aportar información útil (Figura 29).

Figura 29: Supresión de nodos aislados


50

4.2.3 Paso 2: Eliminación de salidas posteriores En la ciudad Origen hay que eliminar los nodos con horario posterior al límite

superior marcado por el usuario, así como los arcos de salida de los mismos, pues tampoco influirán en la decisión final. Los nodos destino de éstos arcos de salida serán candidatos a formar parte de un conjunto auxiliar de nodos que contendrá el nodo de cada parada con horario más bajo. El podado se continuará a partir de los elementos de dicho conjunto.

Figura 30: Supresión de salidas posteriores

Los nodos candidatos aparecen rodeados por un círculo discontinuo en la Figura 31. De estos nodos marcados sólo pasarán a formar parte del conjunto auxiliar aquellos que tengan el menor horario correspondiente a su parada. En el ejemplo considerado formarán parte B1-11, B2-12, y C1-11.

Figura 31: Nodos candidatos a pertenecer al conjunto auxiliar

Del conjunto auxiliar se toma el nodo de menor horario para emplearlo como

base para seguir podando y le denominaremos “nodo base”. Se toman ahora el nodo base y los nodos de su misma parada que tienen un horario mayor que él. De estos nodos se miran sus arcos de salida y se conserva sólo el primer arco al resto de paradas,


51

eliminándose el resto de arcos. Una vez hecho esto se elimina el nodo base del conjunto auxiliar, se añaden al conjunto auxiliar los nodos destino de los arcos eliminados y se repite el proceso. El procedimiento continúa hasta que el conjunto auxiliar de nodos quede vacío.

En el ejemplo, al haber dos nodos con horario 11 (B1 y C1), tomamos el primero (B1-11). De él no sale ningún arco y tampoco de los nodos de mayor horario de su parada (B1-13), por lo que lo eliminamos del conjunto auxiliar. Se toma como nodo base C1-11 y se mantiene el único arco que sale de él. El resto de nodos posteriores no tienen arcos de salida. Igual se hace con el tercer nodo del conjunto auxiliar.

Figura 32: Grafo tras finalizar el paso 2 de la poda

Los nodos que queden aislados han de eliminarse del grafo, quedando el grafo

del ejemplo tal como lo muestra la Figura 32.

4.2.4 Paso 3: Aseguramiento de la accesibilidad desde la ciudad origen

Para asegurar que una ciudad distinta de la ciudad origen pueda ser accesible desde ésta, su primer nodo ha de tener arcos de llegada. Si no tiene se eliminará dicho nodo, así como sus arcos de salida. Si una ciudad tiene varios nodos con el menor horario se eliminarán aquellos que no tengan arcos de entrada.


52

Figura 33: Supresión de primeros nodos sin arcos de entrada

Esto se hace sucesivamente hasta conseguir que el primer nodo de todas las ciudades distintas de la de origen tenga arcos de llegada. Los nodos huérfanos que hayan podido quedar se eliminan también. El grafo espacio-temporal queda, al finalizar este paso tal como muestra la Figura 34.


4.2.5 Paso 4: Aseguramiento de la conexión con la ciudad destino Al igual que con el paso 3 de la poda se busca el que las ciudades puedan ser

accesibles desde la ciudad origen, con el paso 4 se pretende que el grafo quede libre de aquellos nodos y arcos que no servirán para poder alcanzar la ciudad destino. Una condición necesaria para que el destino sea alcanzable desde una ciudad (directa o indirectamente) es que el último nodo de ésta tenga al menos un arco de salida. Por tanto, este paso de la poda consiste en eliminar aquellos nodos no pertenecientes a la ciudad destino, que tienen mayor horario y que carecen de arcos de salida, así como los arcos que les llegan.


53

Figura 35: Supresión de nodos sin arcos de salida

Como consecuencia de la eliminación de los arcos mencionados puede ocurrir

que haya nodos que anteriormente tenían arcos de salida y ahora carezcan de ellos. Es necesario eliminarlos también por lo que la aplicación de este paso de la poda es recursiva. El resultado de esta eliminación, que es análoga a la del paso 3, se expone en la Figura 36.


4.3 Modelado de conexiones urbanas Tras el proceso completo de la poda pueden quedar algunos nodos no pertenecientes a la ciudad origen que carecen de arcos de entrada. Asimismo tampoco es extraño que se dé el caso de que haya otros nodos que carezcan de arcos de salida. Aparentemente esto contradice lo buscado con los pasos 3 y 4 de la poda, pues se busca el que haya caminos en el grafo que unan el origen con el destino. No obstante, lo que aseguran dichos pasos es que no haya ciudades que no pertenezcan a caminos entre ambos. Para asegurar la continuidad del grafo hay que unir los nodos internos de cada ciudad.


54

Por tanto, para terminar de conformar el grafo hacen falta modelar tanto los tiempos de espera en las paradas como el trayecto urbano entre paradas de la misma ciudad (sean mediante transporte público o a pie). Para ello, cada nodo de una ciudad se ha de unir con los siguientes nodos de su misma ciudad. Se distinguen dos casos: unión con nodos de la misma parada y unión con nodos de distintas paradas. Estos dos tipos de uniones no se van a añadir en la ciudad origen puesto que, dependiendo de las preferencias de los usuarios, se partirá de una u otra parada. Por tanto, no se calculan tránsitos dentro de la ciudad origen. De igual forma, tampoco se añaden a la ciudad destino, pues se considera que se alcanza el final del cálculo de la recomendación cuando se ha llegado a dicha ciudad, independientemente de la parada de la misma en la que se haga.

4.3.1 Unión con nodos de la misma parada La unión entre nodos de la misma parada conforma el tiempo de espera en la

misma. La forma de realizarlo es añadiendo un arco que una cada nodo con el siguiente nodo de la misma parada siempre que haya entre ellos un tiempo mínimo por seguridad. Dicho margen de seguridad especifica un tiempo de traslado dentro de la misma parada y es útil en el caso de viajes en los que haya un cambio de vehículo. El poner arcos de longitud temporal menor puede acarrear, por ejemplo, que se recomiende un viaje con trasbordo que el viajero no pueda realizar en la práctica por falta de tiempo para cambiar de un vehículo a otro.

Este tipo de arco implica un tiempo pero no un coste, por lo que se le asignará un coste cero. Con ellos modelamos el tiempo de espera en la parada (Figura 37).

Figura 37: Modelado de tiempos de espera en cada parada

4.3.2 Unión con nodos del resto de paradas de la misma ciudad En este caso, cada nodo se une con el siguiente nodo de las otras paradas de la

misma ciudad, dejando un margen temporal de seguridad. Este margen corresponde ahora al tiempo necesario para desplazarse por el interior de la ciudad hasta llegar a la parada correspondiente. A diferencia del tipo de arco anterior, que modela el tiempo de


55

espera en una parada, sí tiene asociado un coste, que equivale al del transporte público urbano.

Figura 38: Modelado de conexiones urbanas entre paradas

4.4 Creación de nodos origen y destino ficticios Para la aplicación del algoritmo que proporcionará las recomendaciones de

itinerarios al usuario que las solicitó es necesario un último paso. El algoritmo está basado en el propuesto por Dijkstra para la resolución de caminos mínimos y parte de un nodo único. Por tanto, es necesario crear un nodo ficticio que se tome como punto de partida de aplicación del algoritmo y que aglutine las posibles salidas desde la ciudad origen del viaje. Para ello se añade al nodo ficticio origen unos arcos de unión con coste y tiempo nulos que lo una con cada uno de los nodos de salida de la ciudad origen.

Asimismo, se puede crear un nodo ficticio, similar al descrito, pero para la ciudad destino, que servirá para determinar el final del algoritmo de ruta mínima. De forma equivalente al caso del nodo origen ficticio, se unirá con todas las paradas de la ciudad destino mediante arcos de costo y longitud temporal nulos. Otra manera de comprobar que se ha llegado a la ciudad destino es determinar si el nodo considerado pertenece a dicha ciudad, en vez de comprobar si se ha llegado al nodo destino ficticio. Ambos nodos ficticios realizan una función meramente auxiliar. De ahí que tanto el costo económico como el temporal de los arcos que salen de él y los que llegan respectivamente sean nulos. Siguiendo con el ejemplo considerado, los nodos y arcos ficticios añadidos se muestran en la Figura 39.

4.5 Aplicación del algoritmo de K-caminos mínimos Con la aplicación de los pasos de poda descritos anteriormente, se consigue un

grafo espacio-temporal que dispone de la información relevante para poder resolver de forma eficiente el problema planteado. Sobre este grafo es sobre el que se va a aplicar el algoritmo de múltiples caminos mínimos.

El algoritmo que se utiliza para el cálculo de caminos mínimos es una variante del algoritmo de Dijkstra de K caminos mínimos desarrollado por Queirós y Margarida.


56

Se va a implementar una versión del algoritmo que incluye la búsqueda en función de distintos criterios y que se adapta a las características del grafo creado. El algoritmo que se presenta busca distintas rutas mínimas entre dos puntos, pudiendo minimizar tanto el tiempo de viaje como el coste asociado a la ruta, o una combinación lineal de ambos, así como el número de transbordos necesarios para llevar a cabo el viaje. Los pasos del algoritmo ya se vieron en el Capítulo 3 y son los que se presentan en la Figura 25.

Figura 39: Grafo listo para la aplicación del algoritmo de caminos mínimos

Independientemente del criterio de búsqueda de caminos mínimos, se calcula

para cada camino el tiempo de viaje, el coste y el número de transbordos. El diagrama de flujo del algoritmo es el mostrado en la Figura 40. En la Figura 41 se presenta un grafo sencillo a modo de ilustrar el comportamiento del algoritmo. Dicho grafo es más simplificado que el de la Figura 39 por motivos didácticos. En el ejemplo, se buscan los posibles itinerarios para desplazarse desde la ciudad D hasta la ciudad A. Los dos valores que aparecen sobre los arcos son el tiempo de desplazamiento y el coste respectivamente. Los nodos 10, 11 y 12 se corresponden con la ciudad destino, por lo que alcanzando cualquiera de ellos se logra el objetivo.


57

inicio

a1, a2, criterio

counti=0 para cualquier i de N; elm = 1

h(elm) = s, h-1(s)={elm}, c1elm= 0, c2

elm= 0, πelm=0

viajeelm=-1, transbordoselm=0

X={elm}; PK=Ø

(countt<K) && (X ≠ Ø)

k=elemento de X tal que

[πk≤πx si criterio≠transbordos], o

[(transbordosk<transbordosx) o (transbordosk=transbordosx)&&(πk≤πx) si

criterio=transbordos]

X=X-{k}; i=h(k); counti= counti+1

(i=t)

(counti ≤ K)

p camino desde 1 a k

PK= PK U {h(p)}

Para cada arco (i,j) de A

elm = elm +1

fij= a1· c1ij + a2· c

2ij; πelm= πk + fij, ξelm=k

c1elm = c1

k + c1ij; c

2elm = c2

k + c2ij

viajeelm= viaje del arco (i,j)

transbordoselm = transbordosk

h(elm) = j, h-1(j) = h-1(j) U {elm}

X = X U {elm}

(viajek ≠ -1) && (viajeelm ≠ viajek)

&& (viajeelm ≠ -1)

transbordoselm ++

Fin

SI

NO

SI

SI

NO

SI NO

NO

Se comprueba que el arco no sea de la forma

(S,s) ni (t,T), ya que estos arcos no son reales

y no contabilizan transbordos y si se cambia

de viaje con respecto al arco anterior

Bloque de inicialización

Se necesita el criterio de búsqueda

especificado por el usuario y los

coeficientes que van a multiplicar a

los distintos parámetros de los arcos

Se toma de X el elemento cuya

distancia al origen sea menor,

en el caso de que se quiera

minimizar tiempo y/o coste, y se

toma el elemento con menor nº

de transbordos si se quiere

minimizar transbordos

Se ha encontrado un camino desde

el nodo origen al nodo destino

Si no se cumple, ya tenemos K caminos

a este nodo y no necesitamos buscar

más rutas a partir de él

Figura 40: Diagrama de flujo del algoritmo de K caminos mínimos multiobjetivo


58

1

9

1210

8

6

11

5

24

3

7

2, 15

1, 4

3, 0

3, 02, 3

3, 0

2, 4

1, 3

0,0

2,8

3,18

2,15

NODO INICIO

A

B

C

D

Figura 41: Grafo espacio-temporal de ejemplo

El algoritmo recorre el grafo, analizando todos los nodos y arcos y explora las distintas posibilidades. Se crea un árbol de rutas mínimas que parten desde el nodo origen (ver la Figura 42) y se toman aquellas alternativas que hagan óptimo el criterio elegido por el usuario. Si el criterio elegido por el usuario es el tiempo, se toman aquellos caminos que tengan un tiempo de viaje menor, que son los señalados en amarillo en la Figura 43.

1

9

12

10

8 6

11

5

2 43

7

1, 10

3, 25

3, 13

4, 10

6, 41

7, 37

6, 25

6

11

9

12

7 9

12

7

9

12

6, 25

7, 37

2, 8

5, 26

3, 11

5, 26

6, 37

1, 10

3, 25

4, 374, 37

Figura 42: Árbol para la obtención de caminos mínimos


59

Si hay dos caminos con el mismo tiempo, se toma aquel que haga mínimo el

resto de parámetros, en este caso el coste. Si se elije como criterio tanto el tiempo como el coste, habrá que establecer un coste único que sea función lineal de ambos criterio y que pondere adecuadamente cada uno para evitar el efecto de la diferencia de unidades de medida de ambos.

En el ejemplo se han considerado que han de calcularse 4 recomendaciones, es

decir, K = 4. La información de los distintos trayectos que compone cada uno de los caminos es la que habrá que pasarse al usuario como respuesta a su solicitud de recomendación de itinerarios.

Figura 43: Caminos mínimos obtenidos

Capítulo 5 – Implementación: Recomendación de itinerarios en movilidad

60

5 Implementación: Recomendación de itinerarios en movilidad

La implementación de una herramienta ATIS que facilite la realización de viajes

intermodales de pasajeros se está desarrollando dentro del marco del Proyecto Minerva con el título “Recomendación de Itinerarios de Viajes en Movilidad”. El sistema ha de permitir a un usuario planificar un viaje empleando distintos medios (i.e. modos) de transporte (autobús, tren, barco, avión). También posibilitará la recepción, en etapas intermedias del viaje, de información acerca del estado de la red de transporte, y la obtención del resultado del recálculo de recomendaciones sobre la ruta que le resta hasta su destino final. Todo esto en función de las preferencias manifestadas por el viajero. Para ello se empleará el método de recomendación explicado en el capítulo 4. Esta herramienta permitirá, gracias a las ventajas de la movilidad y a la capacidad de determinar la ubicación del usuario, responder en tiempo real frente cambios en la red global de transporte. Una vez desarrollada, se dotará a la herramienta de capacidades para que sea de utilidad a personas con discapacidad visual.

5.1 Planteamiento General del Proyecto

El objetivo del proyecto es que un usuario que vaya a realizar un viaje comunique a un servidor el origen, el destino y una serie de preferencias (duración máxima, número máximo de transbordos a lo largo del camino, precio). En base a la información suministrada y a la que posee sobre la red de transporte, el servidor le devolverá una serie de alternativas, con posibilidad de reservar billetes. Una vez que comienza el viaje seleccionado, que típicamente consistirá en una serie de trayectos entre paradas, recorridos mediante distintos modos de transporte, pueden producirse incidencias en la red de transporte (congestiones en carreteras, retrasos en las llegadas de aviones, cortes en las vías de ferrocarril por inclemencias climáticas, etc.) que motiven alteraciones en el plan inicialmente calculado. Aprovechando las posibilidades de localización que proporciona la red de telefonía móvil, se puede calcular en qué punto del viaje se encuentra el usuario, determinar si se ve afectado por la incidencia y comunicárselo, así como proporcionarle una serie de alternativas basadas en sus preferencias9. También puede el usuario modificar esas preferencias a lo largo del viaje para un nuevo cálculo de los trayectos que le restan.

Un aspecto novedoso de todo el proceso es el aprovechamiento de las posibilidades de obtención de la ubicación del usuario con el fin de determinar, en tiempo real, si el viaje que está realizando transcurre según lo previsto. Asimismo proporciona una facilidad de adaptarse a nuevas circunstancias de la red de transporte o a un cambio de preferencias del viajero.

9 Evidentemente, siempre que el usuario disponga de un terminal móvil.


61

Figura 44: Ejemplo de la funcionalidad del proyecto

5.2 Análisis de requisitos

El presente apartado pretende recoger el resultado del análisis de los requisitos que ha de satisfacer todo el sistema para que cumpla su función de la forma más adecuada. El punto de partida consiste en estudiar y analizar las necesidades y expectativas del usuario final para ajustar todo el sistema de forma que se satisfagan de la mejor manera dichas necesidades.

5.2.1 Descripción de los Requisitos Lo que un viajero espera de este tipo de herramientas se puede dividir en dos grandes grupos de requerimientos. Por un lado, el usuario pide que el sistema le proporcione información útil. De otra parte, la interacción con la herramienta ha de ser fácil y cómoda.

En relación a la obtención de información útil, el viajero querrá que las recomendaciones que obtenga sean precisas. Por tanto, es necesario que el sistema haga un cálculo de las distintas opciones de viajes basándose en algoritmos exactos. Generalmente, los algoritmos exactos en problemas que involucran tantas combinaciones como éste son muy caros computacionalmente. Asimismo, el sistema ha de ser capaz de responder a múltiples peticiones simultáneas de distintos viajeros. Una elevada concurrencia dificulta aún más el trabajo que ha de desarrollar el sistema de

Viaje previsto

Viaje alternativo propuesto 1


Incidencia: Vuelo con retraso

Ubicación del viajero en el momento de la incidencia

ORIGEN DESTINO

Ferrocarril

Barco

Avión

Autobús

Ciudad

Viaje previsto





ORIGEN DESTINO

Ferrocarril

Barco

Avión

Autobús

Ciudad

Viaje previsto





Viaje previsto





ORIGEN DESTINO

Ferrocarril

Barco

Avión

Autobús

Ciudad

ORIGEN DESTINOORIGEN DESTINO

Ferrocarril

Barco

Avión

Autobús

Ciudad

Ferrocarril

Barco

Avión

Autobús

Ciudad


62

cálculo de recomendaciones. Ambos factores redundan en un mayor riesgo de lentitud a la hora de proporcionar respuestas a los usuarios. Si el sistema es lento, los viajeros no harán uso de este sistema, por lo que se impone la necesidad de implementar algoritmos eficientes, rápidos y que soporten altos niveles de concurrencia.

Una ventaja de la herramienta a desarrollar será la posibilidad de emplear recomendaciones con distintos modos de transporte, para lo cual ha de recoger y proporcionar información de diferentes compañías de transporte. Esta información ha de ser exhaustiva para poder ofrecer al usuario la posibilidad de establecer un viaje entre el origen y el destino que desee10. La información recopilada ha de abarcar no sólo trayectos (origen y destino), horarios y modos, sino también precios. Aunque en un principio el proyecto no trata de la creación de un sistema de facturación único, sí puede servir de punto de partida, ya que aquél constituye un desarrollo natural a partir del mismo.

La gran cantidad de información recopilada debe permitir al usuario una elección lo más libre posible, en base a sus preferencias personales (precio que está dispuesto a gastarse en el viaje, tiempo a emplear en los trayectos, modos de transporte preferidos o evitados y/o combinaciones de las anteriores). Esta multiplicidad de opciones ha de facilitar la obtención de diversas recomendaciones de viajes ordenadas en función de las preferencias manifestadas por el viajero. No obstante, demasiadas opciones pueden llegar a saturar al usuario, haciendo confuso de uso de la herramienta. Esta situación hay que evitarla para que los viajeros no desistan del empleo de este sistema.

El sistema ha de permitir, por un lado, la planificación de un viaje antes de su comienzo. El resultado de una planificación correcta de un viaje puede hacerse inviable si se producen cambios posteriores en la red de transporte (retrasos en aviones, vías de comunicación cortadas, averías en trenes, etc.). Por tanto, es necesario dotar al usuario de herramientas que le proporcionen información sobre estos cambios y le permitan actuar en consecuencia. La información puede ser suministrada a petición del usuario o de forma automática cuando se produzca. Por otro lado, el usuario ha de poder solicitar un recálculo del viaje que tenga en cuenta el cambio de la red. Aprovechando la posibilidad de localización que dan los terminales móviles, el recálculo puede ser automático en cuanto se produzca la anomalía en el sistema de transportes. Esto proporcionará al usuario que ya está realizando el viaje diferentes opciones de continuación del mismo en función del momento y lugar del viaje en que se encuentre actualmente. La libertad de cambio de un viaje en curso no ha de quedar restringida al caso de cambios en la red de transporte: Por ejemplo, un viajero que haga desplazamientos por temas de negocios y que cambie el destino por cancelación de una reunión también podrá hacer uso de esta facilidad.

10 Una de las grandes ventajas de la intermodalidad es justamente la posibilidad de aprovechar cualquier medio de transporte para salir y llegar desde prácticamente cualquier punto, puesto que la capilaridad del sistema intermodal de transporte resulta de la conjunción de las capilaridades de cada sistema independiente.


63

5.2.2 Resumen de los Requisitos A continuación de muestran de forma esquemática las condiciones que ha de satisfacer el sistema para que cumpla su función de forma eficaz y útil a los usuarios finales.

5.2.2.1 Requisitos desde el punto de vista de los Usuarios

• Facilidad de uso (interfaz amigable).

• Ha de obtener respuestas precisas y en tiempo razonable

• Flexibilidad a la hora de establecer preferencias pero sin saturar al usuario.

• Ha de proporcionar diversas opciones de viajes ordenadas en base a las preferencias manifestadas

• Ha de permitir el uso de distintos modos de transporte.

• Ha de poder seleccionar entre muchos puntos de origen y destino.

• Ha de simplificarle la gestión de viajes con distintas compañías, facturación de billetes y sistemas de información

• Flexibilidad para cambiar viajes establecidos.

• Ha de permitir:

o Planificación de viajes antes de realizarlos

o Modificación de viajes en curso a petición del usuario debido a cambio en sus preferencias

5.2.2.2 Requisitos que ha de satisfacer el Sistema

Basándonos en las necesidades de los usuarios, los requisitos que ha de cumplir la herramienta serán los que permitan satisfacer los requerimientos manifestados para los usuarios. Son los siguientes:

• Ha de proporcionar respuestas rápidas.

• Ha de proporcionar respuestas con precisión.

• Soportará concurrencia elevada para dar servicio a múltiples usuarios, sorteando problemas de computación.

• Ha de ser capaz de manejar información diversa (horarios, compañías de transporte, modos de transporte, estado de red de transporte).

• Ha de ser capaz de obtener datos de diversas fuentes (transportistas y gestores de infraestructuras).

• Ha de contener información exhaustiva.

• Capaz de integrar todos los datos para convertirlos en información útil para los usuarios.


64

• Capaz de entregar la información al usuario de la manera más cómoda y eficaz empleando distintos medios (Internet, terminales móviles, etc.).

5.3 Análisis General del Sistema

Una vez claros los requisitos que ha de satisfacer el sistema, se procederá a una descripción sistemática de los elementos que han de componer la herramienta a desarrollar. Se ha de tener en cuenta que el sistema ha de cumplir con las necesidades mostradas en el análisis de requerimientos del apartado 5.2.

Como se ha comentado, el sistema tiene como función la de calcular diferentes alternativas de viajes intermodales de pasajeros y de comunicarlos a los usuarios finales. Por tanto, se puede dividir conceptualmente en dos grandes bloques de elementos: De una parte los relativos al cálculo de recomendaciones y por otra parte los referentes a la interacción con los usuarios. No obstante, como se verá más adelante, estos bloques están íntimamente relacionados, de tal forma que habrá módulos que participen de estas dos funcionalidades. A pesar de ello, esta diferenciación servirá para facilitar conceptualmente una aproximación al desglose en módulos menores.

5.3.1 Cálculo de recomendaciones El bloque encargado del cálculo necesitará dos tipos de información:

• Sobre las preferencias y necesidades de los usuarios

• Sobre la red de transporte.

Los datos sobre la red son de naturaleza diversa (horarios, compañías de transporte, modos, etc.). Una de las prioridades consiste en agrupar todos los datos. Para ello se implementará una base de datos que recogerá toda la información sobre la red de transporte. Otra característica que poseen los datos acerca de la red es que provienen de diversas fuentes, principalmente empresas de transporte y gestores de infraestructuras (Vg. DGT, ADIF, AENA, Autoridades Portuarias). La existencia de la base de datos (que poseerá una estructura definida) como contenedor único de información, obliga a una normalización de los datos que se han de comunicar al sistema, independientemente de donde vengan. Evidentemente, distintos agentes proveerán distinta información (un gestor de infraestructuras no tiene por qué dar horarios de compañías de transporte que hacen uso de esas infraestructuras), pero sí tendrán elementos comunes que habrán de ser homogeneizados para poder integrarse en el conjunto de datos.

No basta solo con tener muchos datos, sino que hay que dotarles de significado (en definitiva, convertirlos en información propiamente dicha) para poder proporcionar respuestas útiles a los usuarios. Por tanto se necesita de un módulo que sea capaz de interpretar la información subyacente de la base de datos y transformarla de manera que el módulo encargado de realizar el cálculo de recomendaciones pueda completarlo de forma eficiente. Esta transformación dará como resultado un grafo espacio-temporal que recogerá la información imprescindible para la obtención de recomendación de itinerarios. En investigaciones anteriores se ha visto que el proceso de construcción del


65

grafo cada vez que hay que realizar un cálculo es muy caro computacionalmente, ya que hay que acceder a la base de datos, obtener los elementos de interés y dotarlos de la estructura del grafo. Esto pone en peligro la satisfacción del requerimiento de rapidez en la respuesta, especialmente en situaciones de alta concurrencia de usuarios solicitando el servicio. La solución que se plantea para resolver estos problemas (velocidad y concurrencia) es la de mantener permanentemente un grafo en memoria, con información sobre toda la red durante un periodo relativamente largo de tiempo, que se irá actualizando día a día y conforme se vayan produciendo cambios en el sistema de transporte. Las sucesivas peticiones por parte de los usuarios motivarán que se extraigan los subgrafos relevantes para cada viajero, que suponen un menor coste computacional. Siendo concisos, el módulo al que denominaremos “actualizador del grafo” se encargará de construir el grafo en memoria y de actualizarlo periódicamente y bajo demanda.

Los agentes la red de transporte (gestores y transportistas) se comportarán para la herramienta que se está desarrollando como entidades colaboradoras. Por ello, una solución para facilitarles la forma de comunicar la información será la implantación de una extranet. Una solución sencilla para conseguirlo puede ser la configuración de un servidor Web. Su función será doble: Por un lado será el encargado de centralizar la recopilación de información de las distintas fuentes. Por otro, actuará de interfaz con la base de datos, que será donde se almacenen los datos recibidos.

Para que las recomendaciones de viajes proporcionadas por el módulo calculador sean rápidas y precisas es necesario implementar un algoritmo que solvente la dificultad de la obtención de itinerarios cuando se presentan tantas alternativas. Una primera tarea a realizar en ese sentido es la acotación de la información. Para ello, del grafo permanente construido en memoria se extraerá un subgrafo solamente con la información relevante para la petición en cuestión. Con ello se consigue una aceleración en los cálculos. Con el fin de realizar el cálculo en sí, se desarrollará una heurística ya probada, obtenida a partir de investigaciones anteriores y que da como resultado no sólo una buena aproximación a las soluciones óptimas, sino dichas soluciones óptimas. Esta heurística obtiene una serie de recomendaciones para cada solicitud, no solamente una, ordenadas en función de las preferencias manifestadas por el usuario.

5.3.2 Interacción con los Usuarios Los viajeros que deseen planificar un itinerario entre dos ciudades tendrán que poder hacerlo independientemente del lugar en el que se encuentren. La forma más sencilla es el acceso a través Internet, que permitirá el acceso al sistema desde cualquier lugar del mundo. Implementando el servicio mediante el empleo de un servidor Web se facilitará la puesta a disposición del público, sin requerir más que la tenencia de cualquier navegador Web. El portal de recomendaciones habrá de ser de fácil navegación y uso pero sin descuidar el que ha de proporcionar las opciones necesarias para que los viajeros manifiesten sus preferencias. Para asegurar el correcto funcionamiento de la aplicación con independencia del navegador empleado, el portal habrá de ser diseñado empleando estándares Web.


66

Una de las ventajas del empleo de la Web es que facilita el acceso desde cualquier elemento que disponga de navegador: Ordenadores fijos, portátiles y terminales móviles. Esto hace que pueda consultarse incluso estando en viaje. No obstante, a muchas personas les resulta incómodo o caro el acceso a Internet mediante el móvil. Además, los terminales móviles de gamas más bajas no disponen de navegador, lo que les imposibilita el acceso a la aplicación vía Web. Para solventar estos problemas se ha de desarrollar una aplicación que permita el empleo de otros medios de acceso. La popularidad y coste de los mensajes SMS hacen de ellos los candidatos ideales a ser empleados para facilitar la interacción entre los usuarios móviles y el sistema de recomendación de itinerarios. Para ello, habrá que hacer uso de la plataforma Red Box e implementar las rutinas necesarias para la recepción de mensajes, su tratamiento y la devolución de respuestas.

En una primera fase, el usuario puede emplear el envío de SMS con los códigos y el formato de mensaje correspondientes al servicio solicitado. No obstante, esto implica la existencia de un manual de funcionamiento que el viajero habrá de llevar siempre o bien recibir vía SMS o MMS. Para facilitar la labor al usuario, habrá que implementar en el terminal móvil una aplicación (en Java), que sea amigable y que abstraiga al usuario del tedio de manejar los mensajes de forma independiente.

Una información que puede resultar de mucha utilidad, especialmente al viajero en tránsito, es su localización. Las redes de telefonía móvil posibilitan la localización, de forma más o menos precisa, de terminales enlazados a sus estaciones base. El empleo de esta facilidad puede facilitar la automatización del recálculo de itinerarios cuando se produzcan incidencias en la red que puedan afectar a viajeros en camino. Habrá por tanto que gestionar la información de localización e integrarla tanto en el cálculo de recomendaciones como en la información disponible para el usuario.

La localización del terminal móvil puede facilitar también el empleo de la herramienta al poder servir como origen del viaje a planificar. Esto último resulta de especial interés para personas con dificultades visuales, pues habrán de introducir menos información para el cálculo de recomendaciones. Esta ventaja se hará definitiva mediante la incorporación de las tecnologías IP para la transmisión de voz empleando la integración ofrecida mediante IMS. La idea es que tanto la petición de recomendaciones como la comunicación de los resultados se puedan realizar mediante la voz, constituyendo una audioguía que facilite realización de viajes sin necesidad de asistencia. Esto redundará en una mayor integración de las personas con deficiencias visuales. Para poder hacer esto será necesario el desarrollo de aplicaciones en el lado del subsistema de cálculo de recomendaciones que hagan la conversión entre la información vocal útil para el usuario y la información que necesita el módulo de cálculo. Además habrá que implementar en el terminal móvil un módulo que sirva para que el usuario interactúe con el sistema.

Esta diversidad de formas de comunicación entre los usuarios y el sistema sirve para satisfacer la necesidad de flexibilidad. Un diseño correcto y amigable de los interfaces hará que la aplicación resulte potente y versátil permitiendo la introducción de varias preferencias. Además hará que el sistema sea de fácil uso.


67

5.3.3 Módulos auxiliares Además de las relaciones entre los módulos anteriormente vistos, que hacen que varios de ellos no puedan adscribirse sólo a uno de los bloques en que hemos dividido las funcionalidades, es necesario otro más: El que denominaremos “vigilante”.

Es fundamental en este proyecto la obtención de las mejores respuestas a las solicitudes planteadas por los usuarios, siendo preferible avisar cuando no se puedan dar esas respuestas antes que dar información errada a los viajeros. Por tanto es necesaria la implantación de un módulo que esté vigilando continuamente el estado de los módulos que componen el sistema. No todo funcionamiento anómalo implicará bloqueo total del sistema. Por ejemplo, problemas con la localización de los usuarios vía LBS no afectan a la planificación de un viaje solicitado vía Web. Pero sí será necesario bloquear (y avisar a los usuarios) la parte relativa al recálculo de recomendaciones de viajes en curso. El vigilante por tanto se encargará de comprobar el correcto funcionamiento de todo el sistema, avisar de anomalías y bloquear parte del sistema o todo el mismo en caso necesario.

5.3.4 Esquema de Módulos y Funcionalidades Asociadas

Se expone ahora de forma esquemática un resumen de los módulos y funcionalidades considerados anteriormente.

Módulo Funciones

Base de datos

• Contener toda la información sobre la red de transporte

• Forzar la normalización de la información a transferir al sistema

Grafo en memoria

• Almacenar información útil para el cálculo de recomendaciones

• Acelerar el proceso del cálculo al no tener que construirse un grafo cada vez.

Actualizador grafo en memoria

• Creación del grafo espacio-temporal

• Actualización del grafo diariamente o cuando se produzca una incidencia en la red.

• Recibir la notificación de incidencias en la red.

Subgrafos en memoria

• Mantener temporalmente la información relevante para la respuesta a una solicitud de recomendación de itinerarios.

Cálculo de rutas

• Obtención de subgrafos a partir del grafo en memoria.

• Producción de la información útil de forma precisa empleando heurística exacta.


68

Vigilante

• Vigilar el correcto estado de las aplicaciones.

• Avisar de anomalías y bloquear el uso del sistema en caso necesario.

Servidor Web

• Centraliza recogida de información sobre la red de transporte

• Sirve de interfaz entre la base de datos y los agentes

• Actúa de interfaz entre el sistema y los usuarios, recogiendo sus solicitudes y mostrando las respuestas

Aplicaciones de terminal móvil

• Interfaz de SMS/MMS

• Interfaz IMS

RedBox

• Intercambio de mensajes SMS y MMS entre el usuario y el subsistema de cálculo

• Obtención de información de localización mediante LBS

IMS • Interfaz audio entre el usuario y el sistema de cálculo

Tabla 3: Módulos y funcionalidades del sistema de recomendación

Figura 45: Diagrama de bloques del sistema de recomendación

IMS

VODAFONE

GRAFO

COMPLETO

EN MEMORIA

Base de

Datos

WEB

Subgrafo para

cada usuario

(1)

ACTUALIZA

GRAFO

COMPLETO

(2)

Calcula rutas

para cada

usuario

(3)

Vigilante

Terminal fijo

Terminal móvil

Estación Base /

Nodo B

Red Vodafone

Módulos a

implementar

Relación funcional

a implementar

Comunicación

con usuarios

LEYENDA


69

5.4 Implementación del sistema

Tras el análisis del sistema realizado, de carácter teórico-práctico, queda el describir cómo se implementan los módulos y soluciones descritos.

5.4.1 Problemas de implementación A la hora de implementar el método heurístico explicado en el capítulo 4 y los

módulos descritos en el apartado 5.3, se han de tener en cuenta una serie de consideraciones computacionales que se comentan a continuación. Algunas de ellas ya se comentaron en el apartado 2.4, aunque con otro nivel de detalle. Esto es necesario para realizar un diseño realista y que dé una solución eficaz a los problemas de recomendación de itinerarios planteados.

Por un lado, la construcción de un grafo espacio-temporal que abarque tres meses (periodo que puede considerarse razonable para poder reservar a futuro viajes de media distancia) es una tarea que puede resultar bastante costosa computacionalmente, especialmente en redes con un gran número compañías de transporte, de ciudades y de horarios de viajes entre ellas. Asimismo, la aplicación de los algoritmos de poda sobre el mencionado grafo y de obtención de k-caminos óptimos en función de las preferencias del usuario puede resultar también muy exigente desde el punto de vista computacional.

Otro problema de índole práctico es la velocidad de lectura desde la base de datos que almacena la información sobre la red de transporte. Como hay que acceder a la misma para construir el grafo espacio-temporal cada vez que hay una petición, se añaden retrasos que pueden llegar a ser considerables en función del tamaño de la información que haya que extraer.

De otra parte, el sistema ha ser capaz de soportar una elevada tasa de concurrencia de usuarios a la vez que se garantice que el tiempo de respuesta a cada uno de ellos sea breve. En la práctica, el tiempo de cálculo no podrá ser superior unos pocos segundos.

La conjunción de lo anterior puede llegar hacer inviable el proyecto, ya que n lecturas sobre la base de datos, la construcción de n grafos (de longitud temporal tres meses), la poda de los mismos y el cálculo de n respuestas de k caminos para n usuarios simultáneamente puede colapsar el sistema o dar unos tiempos de respuesta inasumibles para unos valores de n elevados, siendo n el número de usuarios concurrentes.

5.4.2 Soluciones a los problemas de implementación Para resolver los problemas expuestos anteriormente se plantean dos enfoques

que pueden ser complementarios (y deben serlo en la medida de lo posible). Uno de ellas aborda la reducción del tiempo aumentando la potencia de cálculo del equipamiento que ha de realizar dichos cálculos. Esto se consigue con unas mejoras sobre los recursos informáticos disponibles. Estas mejoras pueden consistir en:

• Aumento de la memoria


70

• Aumento de la velocidad del procesador

• Aumento del número de procesadores por equipo

• Instalación de equipos diferentes especializados en tareas concretas

En cualquier caso, una mejora en cualquiera de los aspectos anteriores requiere de una inversión económica que hay que valorar convenientemente y contrastar con los recursos disponibles (no siempre abundantes) para poder tomar una decisión.

El otro enfoque para solucionar los problemas planteados consiste en realizar mejoras sobre el método que permitan la reducción de los tiempos de cálculo. A grandes rasgos, las mejoras que se han adoptado son:

• Mantenimiento en memoria de un grafo espacio-temporal.

• Actualización diaria de dicho grafo

• Compartición de dicho grafo por todos los usuarios.

• Extracción de un subgrafo reducido para cada usuario

Las mejoras aplicadas y las ventajas que se consiguen con ellas se explicarán con más detalle en los apartados siguientes.

5.4.3 Descripción de la implementación

Un esquema genérico de la implementación sobre el sistema planteado se muestra en la Figura 46. A grandes rasgos, el sistema se compone de una serie de módulos y procesos que interactúan entre sí para proporcionar la funcionalidad demandada. En la mencionada figura, se distinguen tres grandes ámbitos: el sistema ATIS, Internet y la red móvil.

El primero de ellos es el elemento a desarrollar con este proyecto y consiste en aquellos elementos que almacenan la información sobre la red de transporte, reciben las peticiones por parte de los usuarios, calculan las mejores recomendaciones y les devuelven la respuesta solicitada.

Gracias a la facilidad de uso, a que no está sujeto a horarios y a que una gran mayoría de la población puede tener un fácil acceso al mismo11,12, Internet es el medio más idóneo para realizar las peticiones de recomendación desde ubicaciones fijas. De hecho es un medio empleado habitualmente para búsqueda de información sobre viajes, así como para realizar reservas de viajes de avión, hecho que se potenciará según las

11 El número de líneas de acceso a Internet en España ascendía a 8.263.691 a finales de diciembre de 2007. Fuente CMT. 12 Según datos del Ministerio de Industria, Turismo y Comercio (Observatorio Red.es) el 33,9% de los hogares españoles dispone de acceso a Internet, y el 37,8% de los ciudadanos de 15 ó más años han accedido a Internet en el último mes, datos correspondientes al primer trimestre de 2006, XI Oleada “Las TIC en los hogares españoles”.


71

directrices de la International Air Transport Association (IATA), que ha llevado a la eliminación de los billetes en papel en detrimento del billete electrónico13.

Finalmente, la red móvil se constituye como un elemento más de acceso a la información, bien sea a través de Internet, bien mediante servicios propios como la mensajería corta (SMS), mensajería multimedia (MMS), etc. La penetración de la telefonía móvil ha sido tan espectacular que resulta difícil recordar como era nuestra vida antes de la llegada de estos pequeños terminales, algo similar a lo que ha sucedido con Internet. La evolución tecnológica de los teléfonos y redes móviles, así como el desarrollo de nuevos tipos de servicios multimedia, han permitido que los móviles se utilicen para mucho más que hablar. El móvil se está convirtiendo así en un compañero cada vez más imprescindible, con el que se puede hacer casi de todo en cualquier momento y, lo que lo diferencia de otros sistemas, desde cualquier lugar. Asimismo, la propia red de telefonía móvil dispone de la funcionalidad de localización geográfica de los terminales bajo su cobertura denominada Location Based Services (LBS). Esta localización depende de la densidad de estaciones de telefonía móvil, pudiendo dar errores considerables14 en el caso del medio rural, donde las antenas están muy separadas entre sí. No obstante, la aplicación de localización no necesita de la ubicación exacta del viajero, sino tan sólo una localización aproximada, por lo que este sistema cumple con la funcionalidad demandada.

Figura 46: Implementación del sistema de recomendación de itinerarios 13 Fuente IATA 14 Los errores pueden llegar a ser del orden de kilómetros.


72

Un elemento importante que hay que instalar es el firewall o cortafuegos. Esta aplicación, que puede estar implementado mediante un software en un servidor frontera o bien en un equipo hardware específico, restringe las comunicaciones que llegan desde el exterior hacia el sistema de recomendaciones, protegiendo al mismo de accesos no deseados y contra posibles ataques que se produzcan desde el exterior.

En la Figura 46 se muestran también protocolos de comunicación entre los distintos elementos. A efectos de desarrollo, se implementan todos los servidores del sistema (base de datos, portal Web, servidor de recomendaciones y servidor de aplicaciones) en la misma máquina, pero programados de forma independiente y de forma que la comunicación entre los mismos sea mediante TCP/IP. Esto facilita que la puesta en producción de cada servidor en computadores distintos sea prácticamente inmediata.

En los siguientes subapartados se detalla la implementación del sistema ATIS, cuya finalidad es ofrecer los siguientes servicios a los usuarios:

• Información sobre viajes y compañías de transporte mediante (Web y SMS). • Información y reserva de viajes (intermodales o no) entre dos ciudades,

manifestando preferencias (tiempo, costo, etc.) (Web y SMS). • Recepción de incidencias en red de transporte (SMS). • Recálculo de rutas alternativas (aprovechando geolocalización móvil con LBS)

para un viaje intermodal en curso (SMS).

5.4.3.1 Servidor de cálculo de recomendaciones Este servidor contendrá los siguientes módulos funcionales, que aparecen mostrados

en la Tabla 3: • Grafo en memoria • Actualizador grafo en memoria • Subgrafos en memoria • Cálculo de rutas

5.4.3.1.1 Construcción y actualización del grafo en memoria

Como se ha comentado anteriormente, el tener el grafo completo en memoria supone mejoras a la hora de aumentar la velocidad de respuesta a los usuarios. Este planteamiento consiste en leer una sola vez la información sobre la red de transporte disponible en la base de datos y construir el grafo espacio-temporal. Este grafo debe abarcar unos tres meses de viajes a partir del día presente, que es un tiempo que se considera razonable para planificar un viaje de media distancia. Evidentemente, esta longitud temporal de tres meses ha de ser configurable y se podrá ajustar a los valores que se consideren oportunos en cada implementación. El grafo espacio-temporal resultante será compartido por todas los usuarios que soliciten un cálculo de recomendaciones.

Por otro lado, es necesario que el grafo se actualice periódicamente, con el fin de que no quede obsoleto con el transcurso de los días, ya que la idea es tener siempre


73

operativo el sistema. Una buena opción, que es la que se ha implementado, es actualizarlo diariamente. Al finalizar cada día, se eliminan los nodos del día finalizado, los arcos que parten de ellos y los nodos futuros que hayan podido quedar aislados con la eliminación de arcos. Asimismo hay que añadir nodos y arcos correspondientes al día que se añade al final del grafo y que representan los posibles viajes a realizar ese día. Esta es una tarea automática que es ejecutada en el servidor. Por tanto, el grafo siempre representa la situación comenzando por el día presente (el motivo es que los usuarios no pueden reservar tickets para días pasados) y tienen un horizonte de m meses. El parámetro m es un parámetro de diseño y, como se ha mencionado, tiene un valor de tres en nuestro caso. Con esta implementación, el tamaño del grafo permanece aproximadamente constante15.

Una ventaja de este planteamiento es que ya no hay que construir el grafo cada vez que haya que realizar un cálculo de recomendación, pues ya se dispone de esa información en la memoria. Simplemente habrá que extraer la parte correspondiente a la solicitud realizada, lo que redunda en una mayor velocidad de respuesta. Además, el coste computacional de la actualización (eliminar y añadir un día) es mínimo comparado con el de la construcción completa del grafo. Otra ventaja es que los accesos a la base de datos se reducen al mínimo. A diferencia del método inicial, ya no es necesario leer de ella cada vez que llega una solicitud recomendación, ya que la información ya está en memoria. Sólo se accederá a la hora de actualizar el grafo (una vez al día). De nuevo, esto redunda en una mayor rapidez de respuesta percibida por el usuario.

5.4.3.1.2 Extracción del subgrafo correspondiente a una solicitud

Para cada solicitud de recomendación que llega desde un usuario, es necesario extraer la parte del grafo espacio-temporal en memoria que concierne a la petición realizada. Es decir, habrá que construir un subconjunto del grafo principal. El que no haya que acceder a la base de datos aumenta la velocidad a la hora de entregar los resultados a los usuarios.

Evidentemente, cuando el grafo se está actualizando es necesario bloquear el acceso al mismo para evitar que los subgrafos tengan información no válida o inconsistente. No obstante esto no suele suponer un inconveniente grave pues, debido al poco tiempo empleado para la actualización, las peticiones pueden mantenerse en espera sin que varíe mucho la percepción del usuario sobre el tiempo de cálculo.

Cuando llega petición, una tarea residente en memoria realiza una extracción de una porción del grafo, correspondiente a la fecha de viaje solicitada más una serie de días antes y después. Los días previos que se toman (típicamente uno) son para dar cierta flexibilidad a la hora de realizar el cálculo y no eliminar posibles soluciones. Los días posteriores han de abarcar el tiempo en realizar el viaje más largo más otros días de margen (también suele ser uno), por motivos de flexibilidad.

Para ello se copian todos los nodos y arcos que se encuentran entre las fechas inicial y final determinadas. De todos ellos, se eliminan los arcos de entrada a los nodos 15 En función de si los viajes tienen todos el mismo horario o si hay diferencias entre días laborales y festivos


74

de la ciudad origen, así como los arcos de salida desde los nodos de la ciudad destino. Asimismo se suprimirán todos los nodos que queden aislados debido a la extracción y a esta última eliminación.

5.4.3.1.3 Cálculo de rutas óptimas

El subgrafo resultante del proceso anterior, que suele abarcar cuatro o cinco días,

dependiendo de la red de transporte considerada, es procesado entonces. La reducción que ha sufrido el grafo del que se extraerán las recomendaciones es enorme, quedando con un tamaño de un 5,5% del tamaño inicial16, por lo que la carga computacional para cada recomendación queda reducida drásticamente.

Como más de un usuario puede estar accediendo a la aplicación al mismo tiempo, es necesario podar un subgrafo diferente para cada usuario. Tras la extracción, cada subgrafo se poda empleando el método explicado en el capítulo 4 y finalmente se aplica el algoritmo de cálculo para obtener los k caminos mínimos que se pasarán al usuario correspondiente como respuesta a su solicitud.

5.4.3.2 Base de datos La función principal de la base de datos es la de servir de contenedor de toda

aquella información para caracterizar la red de transporte y que resulte relevante para el cálculo de recomendaciones de itinerarios para viajeros. Asimismo, guardará tanto información relativa a las reservas realizadas por los viajeros en cada trayecto como información sobre los mismos viajeros. Una tarea implícita adicional que desempeña es la de forzar la normalización de la información intercambiada entre el sistema y los agentes responsables del sistema de transporte de pasajeros, fundamentalmente los gestores de infraestructuras y las compañías de transporte. Por tanto, el diseño ha de permitir dar cabida a información relativa a horarios, caminos posibles, estaciones, diferentes modos de transporte, empresas concesionarias, reservas de viajes, etc. Su implementación ha de ser tal que permita agrupar y relacionar datos muy diversos y que facilite su posterior tratamiento. Adicionalmente y dado que el grupo de investigación en el que se desarrolla el proyecto no se centra exclusivamente en el transporte de pasajeros, sino que tiene líneas abiertas relacionadas con el tráfico intermodal de mercancías, se ha aprovechado esta tarea para hacer una base de datos aún más general y que permita recoger datos particulares de dicho tipo de transporte. Aunque las tablas adicionales no serán empleadas en el proyecto actual sí servirán de base para posteriores aplicaciones y no ralentizan ni estorban a la herramienta que se está desarrollando bajo el marco del Proyecto Minerva. Por tanto, el modelo de base de datos desarrollado intenta recoger todas las relaciones posibles unificando transporte de mercancías y de pasajeros. El diagrama entidad-relación diseñado se muestra en la Figura 47. Para acceder a las bases de datos es mucho más útil usar un sistema de gestión de bases de datos (SGBD) que se trata de un software que hace las funciones de intérprete entre éstas y las aplicaciones y usuarios. El uso de un SGBD tiene una serie de ventajas, entre las que podemos mencionar las siguientes:

16 Para un grafo principal de tres meses y un subgrafo de 5 días


75

• Acceso a las bases de datos de forma simultánea por varios usuarios y/o aplicaciones.

• Seguridad, en forma de permisos y privilegios. Determinados usuarios tendrán permiso para consulta o modificación de determinadas tablas. Esto permite compartir datos sin que peligre la integridad de la base de datos o protegiendo determinados contenidos.

• Potencia: SQL es un lenguaje muy potente para consulta de bases de datos, usar un motor nos ahorra una enorme cantidad de trabajo.

• Portabilidad: SQL es también un lenguaje estandarizado, de modo que las consultas hechas usando SQL son fácilmente portables a otros sistemas y plataformas. Esto, unido al uso de C/C++ proporciona una portabilidad enorme.

El sistema implementado hace uso de uno de los SGBD más populares, MySQL. MySQL es un sistema de gestión de base de datos relacional, multihilo y multiusuario con más de seis millones de instalaciones. Además de las ventajas que disponen todos los SGBD, usar MySQL tiene ventajas adicionales:

• Escalabilidad: es posible manipular bases de datos enormes, del orden de seis mil tablas y alrededor de cincuenta millones de registros, y hasta 32 índices por tabla.

• MySQL está escrito en C y C++ y probado con multitud de compiladores y dispone de APIs para muchas plataformas diferentes.

• Conectividad: es decir, permite conexiones entre diferentes máquinas con distintos sistemas operativos. Es corriente que servidores Linux o Unix, usando MySQL, sirvan datos para ordenadores con Windows, Linux, Solaris, etc. Para ello se usa TCP/IP, tuberías, o sockets Unix.

• Es multihilo, con lo que puede beneficiarse de sistemas multiprocesador. • Permite manejar multitud de tipos para columnas. • Permite manejar registros de longitud fija o variable.

El acceso a la información desde los distintos módulos de la aplicación se realiza mediante el Lenguaje de Búsqueda Estructurado (SQL).


76

Figura 47: Diagrama entidad-relación de la base de datos implementada

5.4.3.3 Servidor Web y servidor de aplicaciones Tanto el servidor de aplicaciones como el servidor Web se encargan de actuar de

interfaz entre los usuario y la parte central del sistema ATIS, constituida por la base de datos y el servidor de recomendaciones. Debido a esto podrían agruparse formando una unidad, pero se ha preferido mantenerlos por separado porque son interfaces con sistemas diferentes y además, en función de la carga que soporten, puede convenir separarlos en distintas máquinas. Esto último se facilita si se diseñan desde un principio como unidades independientes.

5.4.3.3.1 Servidor Web

El servidor Web desempeña la función de actuar de intermediario entre los usuarios que realizan consultas a través de Internet y el núcleo del sistema ATIS. Aparte de ofrecer una interfaz gráfica atractiva17, permite por un lado que los usuarios puedan realizar consultas sobre horarios, compañías de transporte, precios, etc. y por otro que puedan realizar reservas de viajes.

Tanto la labor puramente informativa hacia los usuarios como la inserción de reservas no requieren ningún tipo de cálculo, pues toda se encuentra almacenada en la base de datos. Por tanto, deberá existir comunicación directa entre el servidor Web y dicha base de datos.

Otra función que desempeña el servidor Web es el de actuar de intermediario entre el servidor de recomendaciones y los usuarios cuando éstos solicitan un cálculo sobre las mejores rutas a seguir. Los usuarios introducen sus preferencias a través de

17 Cuanto mejor sea la apariencia más fácilmente serán atraídos los usarios a la Web y motivados a usarla.


77

formularios habilitados a tal efecto y reciben las respuestas mediante páginas HTML creadas dinámicamente. En este caso debe existir también comunicación directa entre ambos servidores.

La implementación del servidor Web se ha hecho utilizando el servidor Web Apache. El servidor HTTP Apache es un software de código abierto para plataformas Unix (BSD, GNU/Linux, etc.), Windows, Macintosh y otras, que implementa el protocolo HTTP/1.1 y la noción de sitio virtual. Apache presenta entre otras características mensajes de error altamente configurables, bases de datos de autenticación y negociado de contenido. Apache tiene amplia aceptación en la red: desde 1996, Apache, es el servidor HTTP más usado. Entre las ventajas de Apache se encuentran que es:

• Modular • Open source • Multi-plataforma • Extensible • Popular (fácil conseguir ayuda/soporte) • Gratuito

Evidentemente, aparte de la información puramente estática del portal

proporcionada por el código HTML, es necesario que las páginas servidas sean capaces de responder las peticiones individuales de cada usuario, que normalmente serán distintas entre sí. Esto requiere que las páginas mostradas por el servidor Web sean dinámicas, es decir, cambien en función de las solicitudes de cada usuario. Para implementar este dinamismo en las páginas, se emplea en este proyecto el lenguaje PHP. PHP es un lenguaje interpretado de propósito general ampliamente usado y que está diseñado especialmente para desarrollo Web y puede ser embebido dentro de código HTML. Generalmente se ejecuta en un servidor Web, tomando el código en PHP como su entrada y creando páginas Web como salida. Puede ser desplegado en la mayoría de los servidores Web y en casi todos los sistemas operativos y plataformas sin costo alguno. PHP se encuentra instalado en más de 20 millones de sitios Web y en un millón de servidores, aunque el número de sitios en PHP ha declinado desde agosto de 2005. Es también el módulo Apache más popular entre las computadoras que utilizan Apache como servidor Web. PHP dispone de numerosas ventajas que han motivado su elección para este proyecto. Destacan entre ellas:

• Es un lenguaje multiplataforma. • Capacidad de conexión con la mayoría de los manejadores de base de datos que

se utilizan en la actualidad, destacando su conectividad con MySQL • Capacidad de expandir su potencial utilizando módulos (llamados extensiones). • Posee una amplia documentación en su página oficial (www.php.net), • Es libre, por lo que se presenta como una alternativa de fácil acceso para todos. • Permite las técnicas de Programación Orientada a Objetos. • Biblioteca nativa de funciones sumamente amplia e incluida. • No requiere definición de tipos de variables. • Tiene manejo de excepciones.

El uso de PHP es el que posibilita que se puedan tanto solicitar información de la base de datos y el cálculo de recomendaciones al servidor de aplicaciones, como mostrar el resultado de ambos tipos de solicitudes.


78

5.4.3.3.2 Servidor de Aplicaciones

El servidor de aplicaciones se constituye como el punto de entrada único de información proveniente de los distintos agentes implicados en la red transporte (compañías, gestores de infraestructuras y administraciones públicas). A través de este servidor dichos agentes podrán enviar la información concerniente a su ámbito con el fin de tener actualizado el conocimiento sobre la red de transporte. En definitiva y gracias al servidor de aplicaciones, podrán acceder a la base de datos para informar de cambios de horarios, retrasos, cortes en líneas de comunicación, etc. La comunicación podría hacerse directamente entre equipos de los agentes de transporte y la base de datos, pero se prefiere centralizar el acceso a la base de datos por motivos de seguridad.

La modificación de la información sobre la red de transporte no requiere ningún tipo de cálculo, pues toda se encuentra almacenada en la base de datos. De ahí la necesidad de que exista comunicación directa entre el servidor de aplicaciones y dicha base de datos.

La otra función clave del servidor de aplicaciones es que sirve como punto de enlace entre el sistema ATIS y la red de telefonía móvil. Por un lado será capaz de recibir las solicitudes de recomendación de viajes por parte de los usuarios que accedan mediante el Sistema de Mensajes Cortos (SMS) y Sistema de Mensajes Multimedia (MMS). También recibirá los datos de localización de los terminales que lo soliciten (LBS). Por otra parte, será el encargado de iniciar las comunicaciones en sentido contrario: Será el encargado de enviar las respuestas a los usuarios mediante los SMS y MMS correspondientes, así como solicitar a la red que localice a los terminales.

La comunicación del servidor de aplicaciones con la red de telefonía móvil se realiza intercambiando información con lo que Vodafone denomina Red Box.

Red Box es una plataforma que integra servicios de SMS (Short Message System), MMS (Multimedia Message System) y LBS (Location Based System) permitiendo el desarrollo y gestión de servicios y contenidos multimedia innovadores. Con Red Box es posible la movilización de aplicaciones posibilitando la recepción y el envío de mensajes de cualquier tecnología (MMS, SMS y LBS) de forma masiva, a una base de usuarios autorizados de clientes, proveedores o empleados de la empresa basándose en una arquitectura modular, flexible y fiable.

Figura 48: Esquema de RedBox

RedBox provee un punto único de acceso a diferentes servicios de red (SMS, MMS, LBS), independizando las aplicaciones de los servicios de red y permitiendo el


79

envío y recepción de grandes volúmenes de mensajes cortos, multimedia o peticiones de localización.

RedBox aporta al proyecto Minerva la conectividad a la plataforma de Vodafone a través de las APIs necesarias para el desarrollo de servicios innovadores utilizando las capacidades tecnológicas de la plataforma.

Los servicios que la plataforma RedBox ofrece a los proyectos adscritos a Minerva, como el del presente trabajo, están implementados como servicios Web. Para facilitar la integración con el resto de aplicaciones, dispone de un descriptor estándar de servicios Web (WSDL), basados en el estándar SOAP18. Dicho descriptor simplifica la integración con las aplicaciones, pues las versiones más recientes de los entornos de desarrollo permiten la creación automatizada de bibliotecas a partir de un WSDL. Asimismo, los mensajes procedentes de la red móvil son entregados por RedBox mediante conexiones HTTP.

Debido a lo anterior, la implementación más inmediata del módulo de comunicación con RedBox se realiza mediante la programación y configuración de servicios Web en el Servidor de Aplicaciones. Con el fin de mantener una coherencia y homogeneidad tecnológica (en la medida de lo posible), se emplea PHP para programar dicho módulo, ya que se empleó también para el servidor Web.

5.4.3.4 Aplicaciones de usuario Con el fin de simplificar al usuario el acceso al sistema de recomendaciones así

como para solucionar el problema del acceso desde casi cualquier lugar, el desarrollo del proyecto se hace pensando en que los usuarios no necesiten aplicaciones ni equipamiento adicionales a los de su vida cotidiana.

El portal Web implementado en el servidor correspondiente facilita que, desde cualquier equipo informático con acceso a Internet, el usuario que pretenda planificar su viaje pueda emplear su navegador habitual para informarse y realizar la reserva de los billetes correspondientes.

Hoy en día, con el despliegue masivo de las nuevas redes de telefonía móvil, preparadas para la transmisión de datos con velocidades razonables, es fácil acceder a Internet desde cualquier terminal móvil que disponga de navegador. Esta forma de acceso puede presentar dos problemas: de una parte estos terminales con navegador suelen ser de gama alta; de otra, el despliegue de redes 3G con mayores capacidades de transmisión de datos no está completado y tiene menos cobertura que los sistemas de telefonía móvil GSM.

Para solucionar los inconvenientes anteriores se emplea RedBox, que permite el que los usuarios puedan hacer uso del sistema ATIS enviando mensajes SMS, que es un servicio básico de la red de telefonía móvil GSM que se mantiene en las nuevas redes y es soportado por todos los terminales móviles.

18 Véase la descripción de SOAP que se encuentra en el apartado 8.2


80

SMS tienen una limitación en cuanto al número de caracteres que puede enviarse en cada mensaje (160 como máximo), por lo que será necesario un número más o menos grande de mensajes a intercambiar entre el sistema ATIS y el usuario. Con el fin de facilitar aún más el uso de este sistema, se implementa una aplicación Java que será la encargada de servir de interfaz más amigable y de abstraer al viajero de estar escribiendo los mensajes. Esto puede redundar también en un menor número de mensajes intercambiados si éstos se codifican adecuadamente, lo que se traduce en un menor costo por envío de mensajes. El motivo de emplear Java es que la mayoría de los teléfonos móviles lo soportan y no es necesario el programar una aplicación por cada modelo de terminal o sistema operativo. El único inconveniente es que la aplicación habrá que descargársela del portal Web e instalarla en el teléfono antes de poder utilizarla.

Otra ventaja de SMS respecto al acceso a Internet desde el móvil es que la información puede llegar sin necesidad de solicitarlo cada vez. Cuando haya un cambio en red de transporte el usuario podría recibir información automáticamente de dichos cambios a través de un SMS, sin necesidad de andar continuamente preguntando. Esto no requiere ningún tipo de desarrollo en el terminal del usuario.

Finalmente, la funcionalidad de localización (LBS) reside en la red, por lo que no hay que implementar nada en el terminal de usuario.

Capítulo 6 – Conclusiones y líneas futuras

81

6 Conclusiones y líneas futuras

6.1 Conclusiones Se debe fomentar la intermodalidad para usar modos de transporte que dañen en

menor medida el medio ambiente. El ferrocarril y las vías navegables son medios de transporte poco contaminantes, pero sus infraestructuras no se distribuyen por todo el territorio. Se debe facilitar el acceso a estas infraestructuras, con estaciones de buses cercanas y aparcamientos, para que el usuario realice el trasbordo de la forma más cómoda posible.

Un conjunto de infraestructuras que ayuden el desarrollo de un transporte intermodal es esencial, pero su implantación requiere costes elevados y bastante tiempo. Como medida para fomentar el cambio de modos, se necesita un buen sistema de información que ponga a disposición de los usuarios las distintas posibilidades de viaje existentes. Un sistema de información que indique de forma detallada los desplazamientos y transbordos que se deben realizar para llegar desde la ciudad origen a la ciudad destino, aporta seguridad al viajero a la hora de realizar transbordos. Se podrían indicar los distintos medios de transporte urbano que dispone la ciudad, así como las paradas próximas a la estación de destino para completar la información proporcionada.

El problema de un sistema de información de estas características es que, para que sea realmente eficiente, se debe contar con una base de datos continuamente actualizada por parte de las empresas de transporte. De este modo, el sistema de información aportará en todo momento horarios e itinerarios actualizados. Asimismo, ha de poder recoger modificaciones y alteraciones temporales que se produzcan sobre la red de transporte Para ello es fundamental el papel que ha de desempeñar la Administración Pública y los demás agentes implicados en el transporte (compañías de transporte y gestores de infraestructuras).

El presente trabajo describe una aplicación que se está desarrollando y que pretende cubrir un hueco existente en el mercado del transporte de pasajeros. Implementa un método que proporciona al usuario una serie de recomendaciones exactas en un tiempo razonable. Además proporciona información sobre horarios, compañías de transporte, etc. Una ventaja de este sistema, es que el acceso al mismo puede hacerse desde cualquier lugar, incluyendo el caso de un viaje ya en curso, gracias a tecnologías como Internet y los servicios móviles. Precisamente esta última característica, el empleo de tecnologías móviles (SMS, MMS, IMS y acceso a Internet móvil), ha posibilitado que el desarrollo se produzca bajo el paraguas del Proyecto Minerva (véase el anexo 8.1).

Los trabajos previos se expusieron en la 22nd European Conference On Operational Research, que tuvo lugar en Praga en Julio de 2007, dentro de la sesión Transportation and Logistic III, con el título “An exact method for the recommendation of intermodal itineraries in public transport” [64].

Asimismo, una presentación del proyecto en un estado más avanzado del desarrollo del mismo tuvo lugar en Diciembre de 2007, en la Escuela de Ingenieros de Sevilla, dentro de las Jornadas ITS en Andalucía, organizadas por la Universidad de


82

Sevilla e ITS España. El título de la ponencia fue “Recomendación de Itinerarios Intermodales en el Transporte Público de Pasajeros” [33].

6.2 Líneas futuras

El proyecto desarrollado puede verse como una primera aproximación a la obtención de un sistema de recomendación de itinerarios a nivel nacional. Un objetivo más ambicioso es la integración en el mismo de información relativa a un espacio supranacional.

Con el fin de agilizar las consultas, la implementación del sistema, actualmente en un único servidor que realiza todas las funciones, debería hacerse distribuida. Esto implica la existencia de distintos servidores, cada uno con una función determinada. Debido a la forma de implementación, que ya ha tenido en cuenta esta posibilidad, el desdoblamiento de las funciones es prácticamente inmediato.

Dependiendo de la carga que tenga que soportar el sistema una vez puesto en producción, puede ser necesario el que cada unidad funcional tenga que desempeñarla un conjunto de servidores en cluster. Esto añade la ventaja de disponer de balanceo y redundancia en el sistema, lo que aumenta la garantía de funcionamiento al incrementar la disponibilidad.

Otra posible mejora para una reducción del tiempo de respuesta ante una petición puede ser el estudiar previamente qué nodos y arcos no intervienen en el cálculo de las distintas recomendaciones. Una manera de hacerlo sería dividir la red de transportes en sectores, de manera que pueda hacerse discriminación sectorial en función de las ciudades origen y destino, no incluyendo por tanto en el grafo aquellas ciudades que seguro que no forman parte del camino mínimo. Además, podría hacerse el estudio de las rutas más solicitadas para tener precalculado lo máximo posible. Por ejemplo, se podrían almacenar en memoria subgrafos complementarios al principal: aquellos se emplearían para las rutas más demandadas y éste para el resto.

Como línea de desarrollo futuro, se encuentra también la recomendación de modificación de viajes en curso de forma automática en base a cambios en la red de transporte. Ahora se está implementando bajo demanda del usuario. Esto podría hacerse de dos formas:

• Mediante una aplicación en el terminal que vaya haciendo polling cada cierto tiempo o cuando se calcule que ha llegado al final de un trayecto.

• Mediante implementación en el servidor de un mecanismo que haga que, cuando llegue una modificación de la red, compruebe los usuarios que están en viaje, si se éstos se ven afectados por la modificación y les mande el recálculo del trayecto si es necesario.

Se puede emplear la plataforma IMS de la red móvil para dotar de contenidos

multimedia a las comunicaciones entre el sistema de recomendación y los usuarios.

Finalmente, como un complemento al sistema descrito, la aplicación que devuelve la información al usuario y que le permite establecer los parámetros de su viaje y sus


83

preferencias podría disponer de una extensión que permita su uso para aquellas personas con discapacidad visual, dotándolas de un mayor grado de autonomía en sus desplazamientos de larga distancia. Esto puede implicar la utilización de la plataforma IMS para suministrar información para deficientes visuales e información adicional en su caso con contenidos multimedia.

Capítulo 7 – Bibliografía y referencias

84

7 Bibliografía y referencias

7.1 Bibliografía [1] A.W. Brander y M. C. Sinclair . “ A Comparative Study of K Shortest Paths

Algorithms ”. Dpto. of Electronic Systems Engineering, University of Essex. [2] Adler J. L. and Blue V. J., “Toward the Design of Intelligent Traveler

Information Systems”, Transportation Research Part C: Emerging Technologies, Volume 6, Issue 3, pp. 157-172. 1998.

[3] Adler J. L., “Investigating the Learning Effects of Route Guidance and Traffic Advisories on Route Choice Behaviour, Transportation Research Part C: Emerging Technologies, Volume 9, Issue 1, pp.1-14, 2001.

[4] Ahuja R. K., Magnanti T. L. and Orlin B. “Network flows: Theory, Algorithms, and Applications”. Prentice-Hall, 1993.

[5] Albiach J, Sanchisa J M, Soler D. “An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation”. European Journal of Operational Research. 2008

[6] “Are we moving in the right direction? Indicators on transport and environment integration in the EU”. TERM 2000

[7] Asakura V., “Origin-Destination Matrices Estimation Model Using Automatic Vehicle Identification Data and Its Application to the Han-Shin Expressway Network”, Transportation 27(4), pp. 419-438, 2000.

[8] Ashok K. and Ben-Akiva M., “Alternative Approaches for Real-Time Estimation and Prediction of Time-Dependent Origin-Destination Flows,” Transportation Science 34, pp. 21-36, 2000

[9] Azarm S., Reynolds B. J. Narayanan S. “Comparison of two multiobjective optimization techniques with and within genetic algorithms”, Proceedings of the 1999 ASME Design Engineering Technical Conference, Sptember 1999.

[10] Azevedo, José Augusto, Santos Costa,Maria Emília O., Silvestre Madeira, Joaquim João E.R. and Vieira Martins, Ernesto Q. “An algorithm for the ranking of shortest paths” 1993

[11] Bae S. “An Advanced Public Transportation Systems Applications: Feasibility Study Of Bus Passenger Information Systems Operational Test In The Town Of Blacksburg”. Proc. 6th Vehicle Navigation and Information Systems Conference, pp. 408-4 13. 1995.

[12] Barceló J., Ferrer J., García D., Grau R., Forian M., Chabini I. and Le Saux E., “Microscopic Traffic Simulation for ATT Systems Analysis, A Pararell Computing Version “.Contribution to the 25th Anniversary of CRT. Centre de Recherche sur les Transports, University of Montreal. 1998.

[13] Ben-Akiva M., Koutsopoulos M. H. and Mukundam. “Dynamic Traffic Model System for ATMS/ATIS Operations”. IVHS Journal. Vol. 12. 1994.

[14] Blackhurst J., Wu T. and OGrady P. PCDM: a decision support modelling methodology for supply chain, product and process design decisions. Journal of Operations Management 23 (2005) pp. 325-343.

[15] Button, K. J. “Transport Economics” (2nd Edition). Edward Elgar, Aldershot, 1993.

[16] Button, K. J. “Transport policy-ways into Europe’s future”. Berstelsmann Foundation, Gutersloh, 1994.

[17] Button, K. Transport Economics. Edward Elgar Publishing Company, 1993.


85

[18] Cachon, G., Fischer, M.. “Supply chain inventory management and the value of shared information”. Management Science 46 (8), 1032-1048. 2000

[19] Cascetta E. and Postorino M.N., “Fixed Point Approaches to the Estimation of O/D Matrices Using Traffic Counts on Congested Networks,” Transportation Science 35, pp. 134-147. 2001.

[20] Charnes A., Cooper W.W. and Rhodes E. “Measuring the Efficiency of Decision Making Units” European Journal of Operations Research 2:6 (November) 429-444, 1978.

[21] Choosing the Route to Traveler Information Systems Deployment. Decision factors for creating Public-Private business plans. An Action Guide. ITS America Society. Roger Gilroy, Robert Puentes and Ric Schuman Eds. 1998.

[22] Chouinard M., D’Amours S. and Alt-Kadi D. Integration of reverse logistics activities within a supply chain information system. Computers in Industry, Volume 56, Issue 1, January 2005, Pages 105-124

[23] Coello C. A. Christiansen A. D. Two new GA-based methods for multiobjective optimization, Civil Engineering Systems, vol. 5, 13, pp. 207-243, 1998.

[24] Comisión del Mercado de las Telecomunicaciones. “ESTADÍSTICAS DEL SECTOR. IV TRIMESTRE 2007”

[25] Comisión Europea. “European transport policy for 2010: time to decide”. Libro Blanco del Transporte. 2002

[26] Craig Larman. “UML y Patrones”. Prentice Hall. 2002 [27] Creación de un portal Web para la gestión de una compañía de transporte

interurbano de pasajeros y reserva on line de billetes / autor, Mónica Gimeno del Valle ; tutor, J. David Canca Ortiz (2003)

[28] D. Eppstein. “ Finding the k shortes t paths ”. S I AM Jour nal of computing, 28: 652-673, 1998.

[29] D. Shier. Interactive methods for determining the k shortest paths in a network. Networks, 6:151-159, 1976

[30] D. Shier. On algorithm for finding the k shortest paths in a network. Networks, 9:195-214,1979

[31] D’Arcier B. F., “Stated Adaptation Surveys and Choice Process: Some Methodological Issues”, Transportation 25(2), pp. 169-185, 1998.

[32] Daganzo, C., Logistics Systems Analysis. Springer-Verlag Berlin Heidelberg, 1996.

[33] David Canca Ortiz, Ginés Campos. “Recomendación de itinerarios intermodales en el transporte público de pasajeros”. ESI. JORNADA SOBRE ITS EN ANDALUCIA. Diciembre 2007"

[34] Deb K. Multiobjective optimization using Evolutionary Algorithms, Wiley, 2001.

[35] E. Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1:395-412, 1959

[36] E.Q.V. Martins and J.L.E. Santos. A new improvement for a K shortest path. Investigaçao Operacional, Nov, 1999

[37] E.Q.V. Martins and J.L.E. Santos. A new shortest paths ranking algorithm. Investigaçao Operacional, 20:(1):47-62, 200

[38] E.Q.V. Martins, M.M.B. Pascoal y J.L.E. Santos. The K shortest paths problem. Universidad de Coimbra, Portugal. Junio 1998

[39] E.Q.V. Martins. An Algorithm for ranking paths that may contain cycles. European Journal of Operational Research 18, (1984), 123-130


86

[40] Elkins P. J. “Service Management Systems For Public Transport — The German Approach”. Proc. lEE Colloquium on Vehicle location and fleet management Systems. Pp. 401-410. 1993.

[41] Enrique Hernández Orallo y José Hernández Orallo. “Programación en C++”. Paraninfo. 1993

[42] Ernesto de Queirós Viera Martins , Mar ta Margar ida Braz Pascoal y Jos é Luis Es teves dos Santos . “ A new improvement for K shor tes t paths algor ithm ”. Centr o de I nformática y S is temas . Depar tamento de matemática, Univer s idad de Coimbra. 1999.

[43] Ernesto de Queirós Viera Martins , Marta Margarida Braz Pascoal y José Luis Esteves dos Santos. “ Deviation Algorithms for ranking shortest paths ”. Departamento de matemática, Universidad de Coimbra. 1999.

[44] Ernesto de Queirós Viera Martins , Marta Margarida Braz Pascoal y José Luis Esteves dos Santos. “ T he K shor test paths problem”. Depar tamento de matemática, Univers idad de Coimbra. 1998.

[45] Esser J., Neubert L., Wahle J. and Schreckenberg M., “Microscopic Online Simulation of Urban Traffic”, in Proc. of the 14th ITS, ed. Ceder A. (Pergamon), pp. 535-554, 1999.

[46] Esther Álvarez González et al.“Manuales Plan Avanza. La Casa Digital”. Red.es y Colegio Oficial de Ingenieros de Telecomunicación. 2006

[47] European Commission, Directorate General for Transport, COST 321, Urban Goods Transport. 1997

[48] European Commission, Market of Intermodal Transport, IMPULSE Project documentation. Deliverable D2, 1997.

[49] European Commission. Directorate General for Energy and Transport, COST 328, Integrated Strategic Transport Infraestructure Network in Europe, Final Report, 1998, ISBN 92-828-4573-7.

[50] Fiala P. Information sharing in supply chains. Omega, Volume 33, Issue 5, October 2005, Pages 419-423

[51] Francisco Falcone, José Manuel Huidobro y Ramón Millán.“Manuales Plan Avanza. Ciudadanía móvil”. Red.es y Colegio Oficial de Ingenieros de Telecomunicación. 2008

[52] Gartner N.H., Stamatiadis C. and Tarnof P.J., “Development of Advanced Traffic Signal Control Strategies for Intelligent Transportation Systems: Multilevel Design”. Transportation Research Road 1494 Traffic Operations, Traffic Signal Systems and Freeway Operations, TRB, Washington D.C. USA., pp. 98-105, 1995.

[53] Giesy D. P. “Calculation of Pareto optimal solutions to multiple objective problems using threshold of acceptability constraints”. IEEE transactions on Automatic Control, vol AC-23, n. 6. 1978

[54] Gupta, S., Krishnan, V., 1999. Integrated component and supplier selection for a product family. Production and Operations Management 8 (2), 163-182.

[55] Hickman M. D. and Bernstein D., “Transit Service and Path Choice Models in Stochastic and Time-Dependent Networks”. Transportation Science 31, pp. 129-146. 1997.

[56] Hickman M., Weissenberger S. and Dahlgren J., “Assessing the Benefits of a National ITS Architecture”, Proceedings of the Third World Congress on Intelligent Transportation Systems, Orlando, October 1996.


87

[57] Horn J. Nafpliotis N. Goldberg D. E, “Multiobjective optimization using the niched Pareto genetic algorithm, Technical Report, IIIiGA1 Report 93005, University of Illinois, Urbana, 1993.

[58] ITS Benefits: Continuing Successes and operational Test Results. US Department of Transportation. Federal Higway Administration, Washington, DC, 1997.

[59] J. Boyar, K.S. Larsen, The seat reservation problem, Algorithmica 25 (1999) 403–417.

[60] J. Boyar, S. Krarup, N.Nielsen, Seat Reservation Allowing Seat Changes. Department of Mathematics and Computer Science. University of Southern Denmark, 2001.

[61] J. Y. Yen. Shortest path network problems. Mathematical Systems in Economics, Heft 18, Hain (1975)

[62] Jing K., Huang Y.-W. y Rundensteiner E. “A Hieralchical Encoded Path Views For Path Query Processing: An Optimal Model And Its Performance Evaluation”. IEEE Transaction on Knowlegde and Data Engineering, pp. 10 (3) 409-432. 1998.

[63] John Leo. “ T ime-Varying K S hor test Paths Algor ithm ”. Matsushita Communication I ndus tr ial, Ltd. 1993.

[64] José David Canca Ortiz, Ginés Campos Domínguez, Enelis Palma Carrasquilla, Gabriel Villa Caro:"An Exact Method for the Recommedation of Intermodal Itineraries in Public Transport". Proceedings of the XXII Euro Conference on Operational Research. Praga. Informs. 2007. Pag. 94-95

[65] Kammerer, K. “The integration of Systems and Non-Systems — EC — 92- and the West German Transportation Carriers”, The technical challenges and opportunities of a united Europe, ed. Michael S. Steinberg. 28-41, Pinter, London, 1990.

[66] Kanninen B. J., “Intelligent Transportation Systems: An Economic and Environmental Policy Assessment”, Transportation Research Part A: Policy and Practice, Volume 30, Issue 1, pp. 1-10, 1996.

[67] Kelle P. and Akbulut A. The role of ERP tools in supply chain information sharing, cooperation, and cost optimization.Intemational Journal of Production Economics, Volumes 93-94, 8 January 2005, Pages 41-52

[68] Keney R.L. and Rafia H. Decisions with Multiple Objectives: Preferences and Value Tradeoff, Cambridge University Press, 1993.

[69] Kitamura R., “Micro-Simulation of Daily Activity-Travel Patterns for Travel Demand Forecasting”, Transportation 27(1), pp. 25-51, 2000.

[70] Knospe W., Santen L., Schadschneider A. and Schreckenberg M., “Towards a Realistic Microscopic Description of Highway Traffic”, J. Phys. A: Math. Gen. 33 L477-L485, 2000.

[71] Knowles, Richard D. Transport shaping space: differential collapse in time–space 2006

[72] Kosonen I. “HUTSIM - Urban Traffic Simulation Model: Principles and Applications”. Manuscript of D.Sc. (Tech.) thesis, Helsinki University of Technology, Transportation Engineering. Otaniemi. 1998.

[73] La intermodalidad en el transporte de personas. Encuentro Intermodalidad de pasajeros, Noviembre 2004

[74] Liping Fu, “An Adaptive Routing Algorithm for In-Vehicle Route Guidance Systems with Real-Time Information”, Transportation Research Part B: Methodological, Volume 35, Issue 8, pp. 749-765, 2001.


88

[75] Liu C.-L., Pai T.-W. y Tang C.-T. “IRIS: Integrated Route Information Service For Multi Modal Public Transportation Systems”. Proc. Taiwan’s International Conference & Exibition on Intelligent Transportation Systems, pp. 186-196. 2000.

[76] Liu C.-L., Pai T.-W., Tang C.-T. y Hsieh C.-M.. “Path Planning Algorithms For Public Transportation Systems”. Proc. 4th International IEEE Conference on Intelligent Transportation Systems. 2001.

[77] M. Gendreau, F. Guertin, and E. Taillard, “Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching,” Transportation Science 33, pp. 381-390, 1999.

[78] M. Gendreau, F. Guertin, and E. Taillard, Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching,” Transportation Science 33, pp. 381-390, 1999.

[79] Mahmassani H. S., “Traveler Behavior and Intelligent Transportation Systems”, Transportation Research Part C: Emerging Technologies, Volume 7, Issues 2-3, PP. 73-74, 1999.

[80] Manuel Alberdi Caus se. Proyecto fin de car rera: “ Diseño e implementación de un s is tema de as ignación del transpor te público”. E.T .S .I .I . de Sevilla. 2002.

[81] May A. 0., “Optimal Transport Strategies for European Cities”, Transportation 27(3), pp. 285-315, Jan 2000

[82] Miettinen K. M. Nonlinear Multiobjective Optimization. Kluwer Academic, Dordrecht, 1999.

[83] Ministerio de Fomento. PEIT (Plan Estratégico de Infraestructuras y Transporte). 2004

[84] Nicolai M. Josuttis. “The C++ Standard Library: A Tutorial and Reference”. Addison Wesley. 1999

[85] Nijkamp P. and Vluegel J. “In Search Of Sustainable Transport Systems”, European Transport and Communications, Networks, eds. Banister, Capello and Nijkamp, 287-300, John Wiley, Chichester, 1995.

[86] Nijkamp P. and Vluegel J. “Transport Infraestructure and European Union Development”, European Transport and Communications, Networks, eds. Banister, Capello and Nijkamp, 3-30, John Wiley, Chichester, 1995.

[87] Nobis, C. Multimodality: Facets and causes of sustainable mobility behavior 2007

[88] Novak, S., Eppinger, S., 2001. Sourcing by design: product complexity and the supply chain. Management Science 47 (1), 189-204.

[89] Odgen, K. W., Urban Goods Movement. Ashgate Publishing Company, 1992.

[90] Plan estratégico de infraestructuras y el transporte (PEIT). Ministerio de Fomento.

[91] R. Timothy Marler and Jasbir S. Arora. “REVIEW OF MULTI-OBJECTIVE OPTIMIZATION CONCEPTS AND ALGORITHMS FOR ENGINEERING”. Technical Report Number: ODL-01.04. College of Engineering The University of Iowa 2004)

[92] Reflexiones sobre la intermodalidad de viajeros. Rodrigo Filiberto Herrera. TAU Consultora Ambiental

[93] Ross J. F. Linking Europe. Policies and Politics in the European Union. Praeger. Westport Connecticut, 1998.


89

[94] Rossetti, R. 3. F. “A Software Environment to Suppoit Urban Traffic System Simulation”. Master’s Thesis (in Portuguese). Computer Science Post-Graduate Program, Universidade Federal do Rio Grande do Sul, Brazil, 1998.

[95] Sakawa M. Genetic Algorithms and Fuzzy Multiobjective Optimization, KLuwer Academic, Dordrecht, 2002.

[96] Srinivas N., Deb K. “Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms”, Technical Report. Department of Technical Engineering, Indian Institute of Technology, Kampur, 1993.

[97] Tabak D. “Computer based experimentation with multicriteria optimization problems”, IEEE Transactions on Systems, Man and Cybernetics, volume SMC9, n. 10, pp. 676-679, 1979.

[98] Tavares G. “A bibliography of Data Envelopment Analysis (1978-2001). RUT-COR Research Report RRR 01-02 (January), Rutgers University Pistcatway, NJ. 2002.

[99] Themistocleous M., Irani Z. and. Love P. Evaluating the integration of supply chain information systems: A case study. European Journal of Operational Research, Volume 159, Issue 2, 1 December 2004, Pages 393-405

[100] Towards Passenger Intermodality in the EU Report 1 (Final Version). Analysis of the Key Issues for Passenger Intermodality for the EUROPEAN COMMISSION. DG ENERGY AND TRANSPORT. Unit G 3. Motorways of the Sea and Intermodality Dortmund, July 2004.

[101] Towards Passenger Intermodality in the EU Report 3 (Final Version). Recommendations for Advancing Passenger Intermodality in the EU for the EUROPEAN COMMISSION DG ENERGY AND TRANSPORT. Unit G 3. Motorways of the Sea and Intermodality Dortmund, December 2004.

[102] Towards Passenger Intermodality in the EU. Recommendations for Advancing Passenger Intermodality in the EU. Diciembre 2004.

[103] Towards Passenger Intermodality in the EU. Report 2 (final version). Analysis of the National Inventories on Passenger Intermodality for the EUROPEAN COMMISSION DG ENERGY AND TRANSPORT. Unit G 3. Motorways of the Sea and Intermodality Dortmund, October 2004.

[104] Turró M. Going trans-European: Planning and Financing Transport Networks for Europe. Pergamon Press.November 1999.

[105] Ulungun E. L. , Teghem J., Fortemps P. H., Tuyttens D. ‘MOSA method: a tool for solving multiobjective combinatorial optimization problems”, Journal of M ulticriteria DecisiOn Analysis, Vol. 8, n. 4, pp. 221-236. 1999.

[106] van der Zijpp, N. J., Fiorenzo Catalano, S. Path enumeration by finding the constrained K-shortest paths 2005

[107] Vande Walle, Stefaan, Steenberghen, Therese. Space and time related determinants of public transport use in trip chains 2006

[108] Vanesa Cruz Arque, David Canca Ortiz. "Un método exacto para la recomendación de itinerarios intermodales con ventanas de tiempo y reserva de plazas". Proyecto fin de carrera 2005

[109] Víctor M. Jiménez y Andrés Marzal. “ An Algorithm for Efficient Computation of K Shortest Paths ”. Dpto. de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia. Dpto. de Informática, Universidad Jaume I, Castellón.


90

[110] Villeneuve, Daniel, Desaulniers, Guy. The shortest path problem with forbidden paths 2005

[111] “Virtual Transport Enterprise Integration” Ricardo Chalmeta, Grupo IRIS, dpto de informática. Univ Jaume I. Castellón

[112] Wahle J., Neuhert L. and Schreckenberg M., “Modelling and Simulation of Traffic Flow”, Computer Physics Communications 121-122, 402-405, 1999.

[113] Weissenberger S., Dahlgren J., Hickman M., and Lo H., “Research and Testing for ITS Deployment and Operation”, ITS Quarterly, Vol. 4, No. 4, pp. 51-62, Fall/Winter 1996.

[114] White A., Daniel E.M. and Mohdzain M. The role of emergent information technologies and systems in enabling supply chain agility. International Journal of Information Management, Volume 25, Issue 5, October 2005, Pages 396-

[115] Wu, J., McDonald, M., and Brackstone, M. “A Fuzzy Logic Microscopic Simulation Model for Interurban ATT Assessment”. Proceedings of 10th European simulation symposium (ESS’98), October 26-28, 1998, Simulation Technology: Science and art, Bargiela A., and Kerckhoffs E., eds., pp. 347-354. Nottingham: Nottingham Trent University, 1998.

[116] Yang H., Meng Q. and Bell M.G.H., “Simultaneous Estimation of the Origin-Destination Matrices and Travel-Cost Coefficient for Congested Networks in a Stochastic User Equilibrium,” Transportation Science 35, pp. 107-123, 2001.

[117] Yang Q. “A simulation laboratory for Evaluation of Dynamic Traffic ManagementSystems”. Ph. D. Thesis, Department of Civil and Environmental Engineering, Massachusetss Inst. Of Tech., Cambridge, MA. 1997

[118] Yang, Hsu-Hao, Chen, Yen-Liang. Finding K shortest looping paths with waiting time in a time–window network 2006

[119] Yang. H. “Multiple Equilibrium Behaviour and Advanced Traveller Information Systems with Endogenous Market Penetration”, Transportation Research, B, Vol. 32, No. 3, pp. 205-218. 1998.

[120] Zhang J., Hodgson J. and Erkut E., “Using GIS to Assess tthe Risks of Hazardous Materials Transport in Networks”, European Journal of Operational Research, Volume 121, Issue 2, pp. 316-329, 2000

7.2 Referencias Web • http://ec.europa.eu/research/fp7/ • http://es.kioskea.net/initiation/concept.php3 • http://www.red.es/publicaciones/articles/id/2215/ciudadania-movil.html • http://www.coit.es • http://www.conclase.net • http://www.cplusplus.com • http://www.mityc.es • http://www.planavanza.es • http://www.red.es • http://www.wikipedia.org

Capítulo 8 – Anexos Ginés Campos Domínguez

91

8 Anexos

8.1 Proyecto Minerva El trabajo descrito en el presente documento, tiene al Proyecto Minerva como el

marco de desarrollo en el que se implementa la solución en movilidad.

El objetivo del proyecto Minerva “Plataforma de Servicios en Movilidad – Cartuja 93” es la creación de una plataforma de experimentación y desarrollo de las nuevas comunicaciones móviles, donde empresas e instituciones puedan llevar a cabo proyectos de I+D+i para generar productos y servicios de última generación, utilizando el Parque Científico y Tecnológico Cartuja 93 (Sevilla) como banco de pruebas para estas experiencias.

Este proyecto parte de la colaboración entre la Consejería de Innovación, Ciencia y Empresa, Vodafone, la Universidad de Sevilla, el Parque Científico y Tecnológico Cartuja’93, Sevilla Global S.A.M., ETICOM, y AICIA para potenciar la integración del I+D+i andaluz en el sector de las nuevas comunicaciones, servicios y aplicaciones móviles, tanto del entorno universitario como del empresarial. Con este objeto se pretende posicionar al sector andaluz a la vanguardia de la nueva revolución tecnológica en la que estamos inmersos para hacer realidad la denominada Internet Móvil. Dicha colaboración se concreta en la conexión a plataformas de experimentación y desarrollo de las nuevas comunicaciones móviles, creando una Infraestructura Piloto en el Parque Científico y Tecnológico Cartuja’93 (Isla de la Cartuja – Sevilla) como banco de pruebas en un entorno real para los servicios desarrollados. Una vez implantada la plataforma de pruebas piloto, el objetivo del proyecto es la utilización de estas nuevas tecnologías y servicios móviles para el desarrollo de aplicaciones específicas para diversos sectores económicos como la Administración, el sector Sanitario, la Banca, el Medio Ambiente, el Turismo, la Logística o los Transportes, que posibiliten el incremento de productividad, innovación y creación de valor.

La infraestructura de la Plataforma de Pruebas de Servicios Cartuja 93 consta de los siguientes elementos:

• Tecnologías de acceso: o Ampliación del despliegue de 3G y HSDPA en la Isla de la Cartuja y

posterior despliegue de HSUPA (Figura 49). o Dispositivos móviles necesarios para las pruebas de evaluación de los

desarrollos realizados. • Plataformas de servicio:

o Plataforma Red Box: conexión a la plataforma Red Box que integra servicios de SMS, MMS y LBS, permitiendo el desarrollo y gestión de servicios y contenidos multimedia innovadores.

o Plataforma DVB-H: laboratorio de desarrollo de DVB-H para realizar pruebas de aplicaciones y servicios innovadores. Dispositivos móviles necesarios para pruebas de evaluación de los desarrollos realizados.

o Plataforma IMS: Conexión a la plataforma IMS que permite desarrollar servicios horizontales, todos a la vez y orientados a la integración de multidispositivo y red. Dispositivos móviles necesarios para pruebas de evaluación de los desarrollos realizados.


92

Figura 49: Emplazamientos de estaciones móviles asociadas al Proyecto Minerva

A continuación se muestran algunos ejemplos de proyectos en desarrollo asociados

al Proyecto Minerva. El detalle de los proyectos es confidencial, por lo que sólo se muestra la descripción genérica.

• Investigación sobre tecnologías de acceso móvil: o Técnicas de optimización automática de redes 3G y HSDPA o Relación entre potencia y tráfico en GSM/GPRS o Sistemas de transmisión Multiple Input Multiple Output (MIMO) con

varias antenas transmisoras y/o receptoras. o

• Servicios sobre DVB-H (televisión móvil) o Plataforma de servicios adicionales a la televisión móvil o Plataforma servicios interactivos para tv móvil. o Aplicación códec FSVC (Fully Scalable Video Codec) o

• Desarrollo de aplicaciones multimedia o Trunking VoIP o Empleo de móvil como cámara de unidad móvil de reporteros o Herramientas captura y maquetación contenido multimedia desde móvil o

• Aplicaciones basadas en geolocalización o Red general de posicionamiento (base para otras aplicaciones) o Sistema de gestión de incidencias municipales o Desarrollo herramientas análisis movilidad o Geomarketing-Advertising o Recomendación de itinerarios de viajes en movilidad

• Integración de sistemas corporativos (ERPs) para trabajadores fuera de la oficina

o Servicios de movilidad para PYMES y Ayuntamientos. o Aplicación para red oficinas inmobiliarias


93

• Servicios de ocio y entretenimiento o Línea de amigos (aprovechando geolocalización)

• Otros o Oficina bancaria por tv móvil o Plataforma tecnológica economía local o Monitorización remota de parámetros biológicos (telemedicina)


94

8.2 SOAP Son las siglas de Simple Object Access Protocol. Este protocolo deriva de un

protocolo creado por David Winer, XML-RPC en 1998. En su sitio Web, Userland (http://www.userland.com se puede encontrar multitud de documentación acerca de este primer protocolo de comunicación bajo http mediante XML. Con este protocolo se pedían realizar RPC o remote procedure calls, es decir, podíamos bien en cliente o servidor realizar peticiones mediante http a un servidor Web. Los mensajes debían tener un formato determinado empleando XML para encapsular los parámetros de la petición. Con el paso del tiempo el proyecto iniciado por David Winer interesó a Importantes multinacionales entre las que se encuentran IBM y Microsoft y de este interés por XML-RPC se desarrollo SOAP."

En el núcleo de los servicios Web se encuentra el protocolo simple de acceso a datos

SOAP, que proporciona un mecanismo estándar de empaquetar mensajes. SOAP ha recibido gran atención debido a que facilita una comunicación del estilo RPC entre un cliente y un servidor remoto. Pero existen multitud de protocolos creados para facilitar la comunicación entre aplicaciones, incluyendo RPC de Sun, DCE de Microsoft, RMI de Java y ORPC de CORBA. ¿Por qué se presta tanta atención a SOAP? Una de las razones principales es que SOAP ha recibido un increíble apoyo por parte de la industria. SOAP es el primer protocolo de su tipo que ha sido aceptado prácticamente por todas las grandes compañías de software del mundo. Compañías que en raras ocasiones cooperan entre sí están ofreciendo su apoyo a este protocolo. Algunas de las mayores Compañías que soportan SOAP son Microsoft, IBM, SUN, Microsystems, SAP y Ariba. Algunas de las Ventajas de SOAP son:

• No esta asociado con ningún lenguaje: los desarrolladores involucrados en nuevos proyectos pueden elegir desarrollar con el último y mejor lenguaje de programación que exista pero los desarrolladores responsables de mantener antiguas aflicciones heredadas podrían no poder hacer esta elección sobre el lenguaje de programación que utilizan. SOAP no especifica una API, por lo que la implementación de la API se deja al lenguaje de programación, como en Java, y la plataforma como Microsoft .Net.

• No se encuentra fuertemente asociado a ningún protocolo de transporte: La especificación de SOAP no describe como se deberían asociar los mensajes de SOAP con HTTP. Un mensaje de SOAP no es más que un documento XML, por lo que puede transportarse utilizando cualquier protocolo capaz de transmitir texto.

• No está atado a ninguna infraestructura de objeto distribuido La mayoría de los sistemas de objetos distribuidos se pueden extender, y ya lo están alguno de ellos para que admitan SOAP.

• Aprovecha los estándares existentes en la industria: Los principales contribuyentes a la especificación SOAP evitaron, intencionadamente, reinventar las cosas. Optaron por extender los estándares existentes para que coincidieran con sus necesidades. Por ejemplo, SOAP aprovecha XML para la codificación de los mensajes, en lugar de utilizar su propio sistema de tipo que ya están definidas en la especificación esquema de XML. Y como ya se ha mencionado SOAP no define un medio de trasporte de los mensajes; los mensajes de SOAP se pueden asociar a los protocolos de transporte existentes como HTTP y SMTP.


95

• Permite la interoperabilidad entre múltiples entornos: SOAP se desarrollo sobre los estándares existentes de la industria, por lo que las aplicaciones que se ejecuten en plataformas con dicho estándares pueden comunicarse mediante mensaje SOAP con aplicaciones que se ejecuten en otras plataformas. Por ejemplo, una aplicación de escritorio que se ejecute en una PC puede comunicarse con una aplicación del back-end ejecutándose en un mainframe capaz de enviar y recibir XML sobre HTTP.


96

8.3 Índice de figuras

Figura 1: Transporte unimodal vs. multimodal ................................................................ 7

Figura 2: Sistemas ATMS .............................................................................................. 11

Figura 3: Sistema CVO .................................................................................................. 15

Figura 4: Panel de mensajes variables (PMV)................................................................ 17

Figura 5: Poste SOS........................................................................................................ 18

Figura 6: Esquema de un viaje intermodal de ejemplo.................................................. 22

Figura 7: Resumen de la notación empleada.................................................................. 25

Figura 8: Objetivos del problema ................................................................................... 26

Figura 9: Restricciones de conservación de flujo........................................................... 26

Figura 10: Restricción horaria de salida ......................................................................... 26

Figura 11: Restricción de continuación del viaje ........................................................... 26

Figura 12: Restricción de capacidad............................................................................... 27

Figura 13: Resumen de la formulación del problema.....................................................27

Figura 14: Forma general de los algoritmos de etiquetado ............................................ 32

Figura 15: Algoritmo de corrección de etiquetas ........................................................... 34

Figura 16: Ejemplo de árbol de caminos mínimos......................................................... 35

Figura 17: Algoritmo de creación del árbol de caminos mínimos ................................. 35

Figura 18: Generalización del algoritmo de Yen............................................................ 36

Figura 19: Algoritmo MPS............................................................................................. 37

Figura 20: Algoritmo Dijkstra de camino mínimo ......................................................... 38

Figura 21: Red ejemplo para resolver algoritmos de k caminos mínimos ..................... 39

Figura 22: Camino mínimo encontrado sobre la red ejemplo ........................................ 39

Figura 23: Algoritmo Dijkstra de K caminos mínimos .................................................. 40

Figura 24: K caminos mínimos encontrados sobre la red ejemplo................................. 41

Figura 25: Algoritmo Dijkstra de K caminos mínimos multiobjetivo ........................... 42

Figura 26: Red de transporte de ejemplo........................................................................ 46

Figura 27: Grafo espacio-temporal................................................................................. 48

Figura 28: Supresión de información anterior a la salida............................................... 49

Figura 29: Supresión de nodos aislados ......................................................................... 49

Figura 30: Supresión de salidas posteriores ................................................................... 50

Figura 31: Nodos candidatos a pertenecer al conjunto auxiliar...................................... 50

Figura 32: Grafo tras finalizar el paso 2 de la poda........................................................ 51

Figura 33: Supresión de primeros nodos sin arcos de entrada ....................................... 52



97

Figura 35: Supresión de nodos sin arcos de salida ......................................................... 53


Figura 37: Modelado de tiempos de espera en cada parada ........................................... 54

Figura 38: Modelado de conexiones urbanas entre paradas ........................................... 55

Figura 39: Grafo listo para la aplicación del algoritmo de caminos mínimos................ 56

Figura 40: Diagrama de flujo del algoritmo de K caminos mínimos multiobjetivo ...... 57

Figura 41: Grafo espacio-temporal de ejemplo .............................................................. 58

Figura 42: Árbol para la obtención de caminos mínimos............................................... 58

Figura 43: Caminos mínimos obtenidos......................................................................... 59

Figura 44: Ejemplo de la funcionalidad del proyecto..................................................... 61

Figura 45: Figura 45: Diagrama de bloques del sistema de recomendación .................. 68

Figura 46: Implementación del sistema de recomendación de itinerarios...................... 71

Figura 47: Diagrama entidad-relación de la base de datos implementada ..................... 76

Figura 48: Esquema de RedBox ..................................................................................... 78

Figura 49: Emplazamientos de estaciones móviles asociadas al Proyecto Minerva ...... 92


98

8.4 Índice de tablas

Tabla 1: Complejidad de los algoritmos de k caminos mínimos.................................... 43

Tabla 2: Horarios para el ejemplo .................................................................................. 47

Tabla 3: Módulos y funcionalidades del sistema de recomendación ............................. 68

mÁster de organizaciÓn industrial y gestiÓn de...

Documents