s_06

XI CONGRESO INTERNACIONAL OBRAS DE INFRAESTRUCTURA VIAL

ELABORACIÓN DE UN PROTOTIPO DE UN SISTEMA DE INFORMACIÓN

ONLINE DE RUTAS ÓPTIMAS PARA USUARIOS DEL TRANSPORTE COLECTIVO URBANO CONSIDERANDO TRANSBORDOS

D. Sc. Fernando Ramiro Castro Aragón

Universidad Nacional de Ingeniería (UNI) Facultad de Ingeniería Civil

Maestría en Ingeniería de Transportes

RESUMEN Se propone la elaboración de un prototipo de un sistema de información online de rutas de transporte colectivo urbano disponible en internet a través de google maps, basado en un modelo de asignación de pasajeros en redes congestionadas de transporte colectivo urbano que utiliza estrategias óptimas, considerando el primer principio de Wardrop (óptimo del usuario), con demanda de viajes fija y matriz asimétrica de costos, con funciones convexas de costos. Esta formulación es representada como un problema de inecuaciones variacionales, resuelta con el método de Frank-Wolfe, implementada en Delphi 6.0. 1. NATURALEZA DEL PROBLEMA En general, en grandes y medianas ciudades en la región, la distribución modal muestra que los viajes en transporte público fluctúan entre 30 y 80%. Esta gran cantidad de usuarios de este sistema de transporte necesita, además de un buen servicio, acceso a información de las rutas disponibles, como itinerarios, ubicación de los paraderos, tipo y tamaño de los vehículos, frecuencia de las líneas, etc. Por otro lado, la disminución de los costos de equipos electrónicos portátiles facilitan el acceso a internet de gran parte de la población, a través de diversos medios disponibles como ipads, teléfonos celulares, tabletas, laptops y otros sistemas remotos de información. Por estas causas señaladas, se vislumbra una gran porción de ciudadanos usuarios del sistema de transporte colectivo, con la necesidad de acceso por internet a un sistema de información del transporte colectivo, que identifique con facilidad en un mapa, a través de una pantalla de un dispositivo electrónico móvil, cuáles son las rutas de transporte colectivo más adecuadas para llegar a sus destinos, teniendo en cuenta la minimización de tiempos y costos de viaje, considerando la opción de realizar transbordos. Entre las iniciativas relativas al tema de este trabajo de investigación que pueden mencionarse está la de la prefectura de Vitoria en el estado de espíritu Santo en Brasil, donde un sistema de consulta de transporte colectivo informa aunque solamente en texto los itinerarios de las rutas de transporte público disponibles. http://sistemas.vitoria.es.gov.br/redeiti/ (Prefeitura de Vitoria 2012). Un sistema de información similar existe en la página de la Municipalidad Metropolitana de Lima aunque aún incompleto, el cual muestra en forma gráfica en google maps itinerarios de algunas líneas disponibles. El sistema más completo encontrado disponibles en la web es el de la página http://ww.lepilote.com (2012) referente a la ciudad de Marsella en Francia, con un sistema similar al que se propone desarrollar en esta propuesta, donde se


muestran conexiones de transporte intermodal para alcanzar cualquier destino en dicha ciudad a través de tres modos: tranvía, ómnibus y tren. 2. VIABILIDAD DE SOLUCIÓN DEL PROBLEMA. El problema de asignación de equilibrio en redes de transporte colectivo, materia de esta investigación, está caracterizado por las siguientes hipótesis: - La selección de las rutas de los pasajeros está basada en las estrategias óptimas,

representación en el contexto de los hipercaminos. - La asignación de pasajeros es efectuada según el primer principio de Wardrop,

conocido como óptimo del usuario. - La repartición de los pasajeros entre los caminos elementales que componen un

hipercamino será de forma proporcional a la frecuencia de las líneas. - La demanda de viajes es considerada fija, ésto quiere decir, que la matriz origen-

destino tiene valores constantes y conocidos. - La matriz de costos en los arcos es asimétrica. - Las funciones de costos en los hipercaminos son funciones convexas. La parte analítica del problema, que consiste en la selección de caminos más cortos para los usuarios del sistema de transporte colectivo urbano, se basa en la metodología de los hipercaminos, mostrada en el CONIC 2003 por el autor de esta propuesta, donde se identifican las rutas óptimas para desplazarse desde todos los puntos de origen de los viajes hasta sus respectivos destinos, como una secuencia de arcos y nodos, donde los arcos representan trechos de viaje en determinadas líneas de transporte público, y los nodos representan los puntos de transbordo a otras líneas. Es decir, no se trata únicamente de identificar y mostrar los itinerarios de forma aislada o independiente de cada línea por separado. Esto además garantiza la accesibilidad de todas las zonas de tráfico desde cualquier nodo de la red, ya que no todas las rutas pasan por todos los nodos de la red (lo cual sería absurdo). En los casos en que no fuera posible la conexión a través de una única línea de transporte público, esta sucederá a través de una combinación de trechos en diferentes líneas, siendo identificados los puntos de transbordo. Este sistema, que para un planificador es una herramienta para la identificación de rutas óptimas para la asignación de viajes de la matriz origen destino del sistema de transporte colectivo, no era aprovechado como elemento de consulta por los usuarios del transporte público, quienes son los principales involucrados en el problema. Con la presente investigación se propone la creación de una especie de interfaz, que traduzca los resultados de dicho sistema de solución analítica, que sirva como un elemento de consulta de rutas para los usuarios del transporte público, mediante una salida gráfica accesible por internet a través de un mecanismo de consulta que utiliza las herramientas disponibles de google maps, identificando y exhibiendo en un mapa en la web, las rutas óptimas de trechos de líneas y puntos de transbordo del sistema de transporte público, mediante un sistema de coordenadas en el que se van uniendo segmentos de línea correspondientes a los caminos óptimos. 3. FORMULACION MATEMATICA DEL PROBLEMA


La metodología propuesta de asignación de flujo de pasajeros óptima en una red de transporte colectivo se basa en el concepto de los hipercaminos. Un hipercamino viene a ser la generalización de la idea de un camino en un grafo orientado. En una red de transporte particular se buscan los caminos más cortos y en una red de transporte colectivo se procura encontrar los hipercaminos más cortos. Se trata de encontrar el hiperárbol más corto que contiene los hipercaminos más cortos desde todos los nodos de la red hasta un determinado nodo de destino. El algoritmo requiere que se expanda la red con nodos y arcos adicionales debido a la superposición de líneas de ómnibus que representan trechos comunes en la red física. Spiess (1983) demuestra que las condiciones de equilibrio son la solución óptima del siguiente problema de minimización convexa:

min Aa

va0 ca(x) dx +

IiRr

wir (3.1)

sujeto a :

va = Rr

var , a A , (3.1)

var fa w i

r , a Ai+ , i I, r R, (3.2)

Ai

va r -

Ai va

r = gir , i I, r R, (3.3)

va r 0 , a A, r R, (3.4)

donde:

ca(x) es la función de costo en el arco a que depende del flujo en el propio arco, w i

r es el costo total de espera para ir desde i hasta r , y fa es la frecuencia del arco a 4. SALIDA GRÁFICA A TRAVÉS DE GOOGLE MAPS Una vez resuelto el problema de asignación de flujo de equilibrio en la red de transporte colectivo, se tienen identificados los arcos y nodos correspondientes a cada hipercamino más corto para cada nodo de destino. Con las respectivas coordenadas puede construirse gráficamente en un mapa la secuencia de nodos y arcos correspondientes a cada hipercamino óptimo, donde se identifican las líneas de ómnibus elegidas y los puntos de transbordos para las rutas más cortas para llegar a cualquier destino en la red. Para el desarrollo de esta aplicación es necesario tener conocimientos básicos de programación de páginas web donde se incluyen conocimientos de html, php, inserción de figuras y algunas instrucciones básicas para el manejo de sistemas georeferenciados. Las principales instrucciones para sistemas georeferenciados para el mapa mostrado a continuación, se basan en relacionar coordenadas de latitud y longitud a variables


dinámicas con las que se representan líneas poligonales asociadas a trechos de rutas en líneas de transporte público. 5. APLICACIÓN A UN EJEMPLO DE RED DE TRANSPORTE PUBLICO Se muestra una aplicación de una red de transporte colectivo que considera 4 zonas de tráfico y 4 líneas de transporte público. Se aplica el algoritmo de solución a la red que conecta la zona de tráfico A con las zonas B, C y D. Existe demanda de viajes de A hacia B, C y D; de B hacia C y D; y de C hacia D, 100 pasajeros en cada caso. 4 líneas de transporte pueden atender esa demanda.

Zona de tráfico longitud latitud Nombre de la zona

A -12.079103 -77.051519 Jesús María

B -12.087263 -77.032901 Lince

C -12.117225 -77.005860 La Calera

D -12.049315 -77.030589 Centro

Tabla 1: coordenadas de centróides de zonas de tráfico

L4

L2 A B

L2

L3

D C

L3

L1

Figura 1: Red de transporte público: 4 nodos y 4 líneas de ómnibus.

C

13

7

L2

A

5

11 12

L314

6

L2

18 17

L3

B

16

9 10

15

8

D

L1

L4


arco t (min) Frec. (min-1) Tipo de arco (1,5) 5 caminata (5,1) 5 caminata (2,6) 5 caminata (6,2) 5 caminata (3,7) 5 caminata (7,3) 5 caminata (4,8) 5 caminata (8,4) 5 caminata (10,8) 0.1 desembarque (16,8) 0.1 desembarque (18,8) 0.1 desembarque (13,7) 0.1 desembarque (15,7) 0.1 desembarque (12,6) 0.1 desembarque (5,9) 0 1/6 espera (5,11) 0 1/6 espera (6,12) 0 1/6 espera (6,14) 0 1/15 espera (7,15) 0 1/3 espera (7,17) 0 1/5 espera (9,10) 25 a bordo (11,12) 7 a bordo (12,13) 6 a bordo (14,15) 4 a bordo (15,16) 4 a bordo (17,18) 10 a bordo

Tabla 2: arcos de la red con sus atributos

arcos de espera [(0.8*va+0.2*vb)/70]**2arcos a bordo t + [(va+0.2*vb)/70]**2 arcos de desembarque t

Tabla 3: Funciones de costos en los arcos de la red con sus atributos (t es el tiempo en minutos que aparece en la tabla anterior)

arco Iteración 1 Iteración 2 Iteración 3(6,2) 100 100 100(7,3) 200 200 200(8,4) 300 300 300(1,5) 300 300 300(2,6) 200 200 200(12,6) 100 100 100(3,7) 100 100 100(13,7) 292,86 232,14 232,14(15,7) 28,57 28,57 28,57(10,8) 50 75 75(16,8) 65,48 91,07 91,07(18,8) 184,52 133,93 133,93(5,9) 50 75 75(9,10) 50 75 75(5,11) 250 225 225(6,12) 142,86 107,14 107,14


(11,12) 250 225 225(12,13) 292,86 232,14 232,14(6,14) 57,14 92,86 92,86(7,15) 36,9 26,79 26,79(14,15) 57,14 92,86 92,86(15,16) 65,48 91,07 91,07(7,17) 184,52 133,93 133,93(17,18) 184,52 133,93 133,93

Tabla 4: Flujos en los arcos para cada iteración

Figura 3: Mapa con conexiones de 4 zonas de tráfico con 2 tramos en 4 vías utilizadas

por las 4 líneas de transporte colectivo

Figura 4: Mapa con las vías utilizadas por la línea nº1 de transporte colectivo


Figura 8: Mapa con la combinación de líneas para ir de la zona 1 a la zona 4 en

transporte colectivo 6. CONCLUSIONES Se ha demostrado la posibilidad de mostrar en forma gráfica a través de mapas online la los resultados de un sistema de asignación de viajes donde se minimiza una función de costos y se identifican las rutas óptimas para los usuarios del sistema de transporte colectivo, sistema que puede tener acceso desde cualquier dispositivo conectado a internet. Es posible generar reportes con información adicional en base a los atributos y datos disponibles sobre tiempos de viaje, frecuencia de las líneas de ómnibus, velocidad promedio, tiempos esperados de transbordo, etc. Se considera también la factibilidad de hacer en paralelo sistemas con lenguajes apropiados a otros tipos de dispositivos como ipods o celulares, los cuales son comúnmente utilizados para acceder a internet. REFERENCIAS BIBLIOGRÁFICAS Andréasson, I. (1976) A Method for the Analysis of Transit Networks, Second European Congress on

Operations Research, Amsterdam, North-Holland. Bouzaïene-Ayari, B., M. Gendrau, S. Nguyen (1995) An Equilibrium-Fixed Point Model for Passenger

Assignment in Congested Transit Networks. Publication 1001, Centre de Recherche sur les Transports, Université de Montréal.

Castro A.,F.R., J.E. Leal (1998) Redefinição automática da rede de transporte coletivo para alocação de fluxo de equilíbrio. Transportes Vol .6, n.2, 28-45.

Castro A.,F.R (2003) Modelo de asignación de pasajeros en una red de transporte colectivo urbano. XIV CONIC Congreso de Ingeniería Civil, Iquitos, Perú.

Chriqui, C. (1974) Rèseau de Transport en Commun: Les Problémes de Cheminement et d’Accés. Ph. D. thesis. Dép. I.R.O. Université de Montréal, Canadá.

Chriqui, C., Robillard, P. (1975). Common bus lines. Transportation Science 14, 42-54. Dafermos , S. (1980) Traffic equilibria and variational inequalities. Transportation Research. 14, 42-54. De Cea, J., Fernández, J. E., Crovetto, G. (1990) Análisis comparativo de tres modelos de asignación a

redes de transporte público basados en el concepto de ruta. Apuntes de Ingeniería 39, 5-22. De Cea, J., E. Fernández (1993-I) Comportamiento de los viajeros y modelos de asignación de equilibrio

en redes de transporte público. Apuntes de Ingeniería 50, 5-20.


De Cea, J., E. Fernández (1993-II) Transit Assignment for Congested Public Transport Systems: An Equilibrium Model. Transportation Science. Vol. 27, n.2, 133-147.

Dial, R. B. (1967). Transit Pathfinder Algorithm. Highway Research Record 205, 67-85. Frank, M., P. Wolfe (1956) An Algorithm for Quadratic Programming. Naval Research Logistics

Quarterly 3, 95-110. Gendrau, M. (1984). Étude approfondie d’un modèle d’équilibre pour l’affectation des passagers dans les

réseaux de transport en commun. Publication 384, Centre de recherche sur les transports, Université de Montréal, Canadá.

Hasselströem, D. (1981) Public Transportation Planning – A Mathematical Programming Approach. Ph. D Thesis, Department of Business Administration, University of Gothenburg, Sweden.

Knoppers, P., T. Muller (1995) Optimized Transfer Opportunities in Public Transport. Transportation Science, vol 29, n.1, 101-105.

Lampkin, W, P. D. Saalmans (1967) The Design of Routes, Service Frequencies and Schedules for a Municipal Bus Undertaking: A case study. Operation Research Quarterly. 18, 375-397.

Mandl, C.E. (1978) Algorithms and computer programs in deterministic network optimization applied to public systems. Institute for Advanced Studies, Viena. Research Memorandum n. 126.

Moore, E. F. (1957) The Shortest Path through a maze. International Symposium on the Theory of Switching Proceedings, Harvard University.

Nguyen, S., Pallottino, S. (1986) Hyperpaths and Shortest Hyperpaths, Combinatorial Optimization, Lectures Notes in Mathematics, 1403, Springer-Verlag, 258-271.

Nguyen, S., Pallottino, S. (1988) Equilibrium traffic assignment for large scale transit networks. Publication 494, Centre de Recherche sur les Transports, Université de Montréal.

Pilon, J.A. (2009) Sistema de informação ao usuário do transporte coletivo por ônibus na cidade de Vitória-ES. Tesis de Maestría. Programa de Pós-Graduação em Engenharia De Produção – PPGEP. Universidade Tecnológica Federal do Paraná, campus Ponta Grossa.

Spiess, H. (1983) On optimal route choice strategies in transit networks. Publication 286, Centre de Recherch sur les Transports, Université de Montréal.

Spiess, H., Florian, M. (1989) Optimal strategies: A new assignment model for transit networks. Transportation Research, B-23(2) p. 83-102.

Wu, J.H., Florian, M., Marcotte, P. (1994) Transit equilibrium assignment: a model and solution algorithms. Transportation Science 28, n.3.

Zhan, F.B., Noon, C. E. (1998) Shortest Paths Algorithms: An Evaluation using Real Road Networks. Transportation Science. Vol. 32, n. 1, 65-73.

Prefeitura de Vitória, ES. http://sistemas.vitoria.es.gov.br/redeiti/ (acceso el 10 de Julio de 2012). Le Syndicat Mixte des Transports des Bouches-du-Rhone http://www.lepilote.com/ (acceso el 10 de Julio

de 2012).

s_06

Documents