c# - ver - tutorial metodo hungaro
Algoritmo de transporte público de autobuses. (7)
Estoy trabajando en una aplicación de C # sin conexión que puede encontrar rutas de autobús. Puedo extraer el horario / bus / datos de ruta. Estoy buscando la solución más simple que funcione con datos básicos.
¿Qué algoritmo se puede usar para encontrar una ruta desde la parada de autobús "A" hasta la parada de autobús "B"? ¿Hay una solución de código abierto lista para C # / Java? ¿Es el formato de Google GTFS para la base de datos bueno para una solución simple? http://code.google.com/transit/spec/transit_feed_specification.html
Gracias por cualquier ayuda. Estoy atascado con esto. No sé por dónde empezar: cómo almacenar los datos y cómo encontrar rutas. Sé sobre Dijkstra / A * pero los he usado solo en gráficos que no dependían del tiempo ...
Conceptualmente, toma el mismo algoritmo básico para evaluar la distancia entre A y B, pero en lugar de la distancia, debe evaluar el tiempo. Dijkstra puede hacer ambas cosas, si le das las entradas adecuadas.
Estás acostumbrado a ver un mapa como una medida de distancia. Sin embargo, el mismo mapa también puede ser una medida del tiempo; todo lo que necesita es agregar datos sobre la velocidad promedio, y el tiempo que toma cubrir una distancia particular de una carretera en particular se sacudirá. Incluso puedes visualizar el mapa en términos de tiempo; Las rutas que llevan más tiempo serán más largas. A Dijkstra no le importa lo que está evaluando, realmente; solo se preocupa por encontrar la ruta continua con el número más bajo, y si ese número representa la longitud o el tiempo es irrelevante.
Para incorporar la velocidad, los algoritmos ingenuos simplemente usan el límite de velocidad diurna y suponen que nunca tendrá que detenerse mientras va de A a B; los algoritmos más avanzados pueden incorporar información sobre la hora del día y los patrones de tráfico (lo que afectará la velocidad promedio que recorre en esa carretera en ese momento), y si una carretera es una autopista o una calle de superficie (y por lo tanto hace conjeturas informadas sobre el tiempo que se detuvo en una intersección). Lo que use dependerá de lo que tenga disponible, pero una dimensión básica de 4 o 5 capas de la hora del día debería ser adecuada para todas las aplicaciones excepto para las aplicaciones más críticas. Para cada dirección de cada camino en su mapa, necesita la velocidad promedio durante las horas de la mañana, el día, la noche y la noche, posiblemente también con los números del almuerzo. Una vez que tienes eso, es un cambio relativamente básico para que un algoritmo de Dijkstra pase en una hora del día y haga que evalúe las rutas según el tiempo.
El problema en el que estás trabajando no es una tarea trivial. Tanto es así, que tiene un nombre: el problema de programación no lineal de enteros mixtos (MINLP). En palabras de un autor (Deb 1998):
"Cuando se formuló matemáticamente, el problema de la programación de tiempo se convierte en un problema de programación no lineal de enteros mixtos (MINLP) que tiene un gran número de restricciones relacionadas con los recursos y el servicio. Técnicas de optimización clásica (Bookbinder y DCsilets, 1992; Kikuchi y Parameswaran, 1993), se observa que esta es una tarea extremadamente difícil incluso para una pequeña red de tránsito. La dificultad surge principalmente debido a la gran cantidad de variables y restricciones, de naturaleza discreta. de variables, y no linealidades involucradas en la función objetivo y las restricciones ".
En el artículo de Deb propone un algoritmo genético.
Tu otra opción sería usar simulación. Para lanzar algo al aire libre, puede intentarlo de inmediato: elija miles de rutas aleatorias que comienzan en su origen y saque las que funcionan razonablemente bien para llegar al destino.
Imagine el algoritmo de la siguiente manera: está intentando encontrar la ruta más rápida desde la parada A hasta la parada B, comenzando en un momento determinado. Usted contrata a 1,000 personas y las arma con un cuarto para voltear. Dígales que tiren la moneda cada vez que tengan la oportunidad de subir o bajar del autobús. Cabezas, bajarse (o subir, si ya están apagadas). Colas, quédate (o sigue esperando, si está apagado). Cada uno tiene una tarjeta de índice para anotar las elecciones que hacen a medida que avanzan. Vas al punto B y esperas a que aparezca el primer chico y se lleve su tarjeta.
Hay una lista extensa de publicaciones (30+) sobre algoritmos de enrutamiento de transporte público que ha sido compilada a lo largo del tiempo por colaboradores del proyecto OpenTripPlanner de código abierto (Java) aquí:
https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography
OpenTripPlanner es un motor de enrutamiento multimodal que también incluye bicicleta y paseo, desde el enlace anterior:
Esta es una lista de artículos, disertaciones y libros que han inspirado e informado tanto el motor de enrutamiento OTP existente como algunos experimentos en curso. Actualmente, OpenTripPlanner usa un único gráfico dependiente del tiempo (en oposición al expandido en el tiempo) que contiene redes tanto de calle como de tránsito. Los viajes solo para caminar y solo para bicicletas se planifican generalmente utilizando el algoritmo A * con una jerarquía heurística o de contracción euclidiana. Los viajes Walk + Transit o Bike + Transit se planifican utilizando una variante del algoritmo MOA * con predominancia de épsilon para la poda de ruta y la heurística de Tung-Chew (un gráfico que proporciona un límite inferior en el peso agregado) para el ordenamiento de la cola.
La bibliografía de enrutamiento anterior incluye referencias para las siguientes categorías de algoritmos y trabajos relacionados:
- Técnicas de aceleración de búsqueda de ruta
- Senderos más cortos de Pareto multi-objetivo
- Enrutamiento restringido por recursos
- Patrones de Contracción y Transferencia
- Enrutamiento basado en horarios
- ALT y incrustaciones métricas
- Detalles de Calibración e Implementación
- Rutas de tránsito público post-Dijkstra
Si encuentra algo nuevo que no está en la lista, ¡siéntase libre de agregarlo a la wiki!
En cuanto a otras bibliotecas de enrutamiento de transporte público de código abierto, también está el proyecto RRRR de Bliksem Labs:
https://github.com/bliksemlabs/rrrr
Desde el enlace de arriba:
RRRR (generalmente pronunciado R4) es una implementación en lenguaje C del algoritmo de enrutamiento de tránsito público RAPTOR. Es el componente principal de enrutamiento del planificador de viajes y del sistema de información de pasajeros de Bliksem. El objetivo de este proyecto es generar conjuntos de itinerarios Pareto-óptimos en grandes áreas geográficas (por ejemplo, BeNeLux o toda Europa), mejorando el consumo de recursos y la complejidad de las alternativas existentes más flexibles. Con el tiempo, el sistema debe admitir las actualizaciones de vehículos / viajes en tiempo real reflejadas en los planes de viaje y ser capaz de ejecutarse directamente en un dispositivo móvil sin conexión a Internet.
Tanto OpenTripPlanner como RRRR utilizan datos GTFS.
Lee esto:
Planificación de rutas multimodales. Tesis de maestría, Universität Karlsruhe (TH), Fakultät für Informatik, 2009. disponible en línea en http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf
La sección sobre rutas ferroviarias también se aplica a las rutas de autobuses.
Lo esencial de esto: el enfoque ingenuo de expandir el espacio y el tiempo en un solo gráfico no funciona para redes grandes. Hay soluciones más inteligentes.
Prueba esto como tu modelo de datos.
El autobús 1 va a las paradas A, B y C. El autobús 2 va a las paradas B, D y E.
Almacenaría un nodo único basado tanto en el bus como en la parada, con distancias a los nodos basadas en el tiempo. Tendríamos nodo A1, B1, C1, B2, D2 y E2. En el caso especial de transferencias, aplique la espera del siguiente bus como la distancia entre nodos. Por ejemplo, si el autobús 1 llega a la parada B 30 minutos antes del autobús 2, el tiempo de viaje de B1 a B2 es de 30 minutos.
Deberías poder aplicar el algoritmo de Dijkstra.
Sólo quería compartir mi enfoque final sobre este problema. Esto era parte de un proyecto universitario, por lo que podría no ser totalmente adecuado para el uso en el mundo real. Tenía que ser razonablemente rápido para ejecutarse en un dispositivo Windows Mobile.
Terminé usando 4 tablas (SQLite). Una tabla mantiene la lista de autobuses, la segunda mantiene una lista de estaciones. Otra tabla mantiene las combinaciones: qué autobús se detiene en una estación específica y adónde va desde esta estación y cuánto tiempo (minutos) tarda. Todas las combinaciones deben ser almacenadas. Y la última tabla es una simple tabla de tiempo. Para cada estación, se enumeran todos los buses que se detienen allí y la hora (almacené la hora como valor entero, 14:34 es 1434, para que sea más rápido para comparar).
Utilicé un algoritmo de búsqueda de amplitud bidireccional. Las estaciones vecinas (directamente accesibles) se recuperan para la estación de inicio y la estación de destino. Hay un camino desde la estación A a la estación X si estos dos "gráficos" se superponen en una estación. Por ejemplo, desde la estación A puede llegar a las estaciones B, C, D, E (utilizando autobuses específicos). Y desde la estación de destino X puede llegar directamente a N, C, Z. Estos dos gráficos se superponen en la estación C. Por lo tanto, existe una ruta A -> C -> X. Si no se encuentran rutas en esta primera iteración, entonces el algoritmo continúa y vuelve a desplegar los gráficos (BFS).
El tiempo no se tiene en cuenta en el primer paso, esto lo hace lo suficientemente rápido. Solo obtiene una lista de rutas posibles con una lista de autobuses que debe utilizar para tomar estas rutas. Los tiempos se evalúan en el último paso, recorre la lista de rutas posibles y comprueba si el autobús viaja dentro del tiempo específico (aumentando el tiempo en cada parada).
En una ciudad pequeña, con más de 250 estaciones y más de 100 autobuses / ferrocarriles, este enfoque funciona hasta en 3 cambios (donde debe cambiar los autobuses en el viaje). Solo toma unos segundos calcularlo. Pero tuve que cargar toda la base de datos en la memoria (Diccionario) para acelerar las consultas, que llevaban demasiado tiempo.
Aunque no creo que esto funcione para una red grande. Pero funciona para un transporte público de una sola ciudad pequeña y mediana.
Si está interesado en la información de tiempo, ¿por qué no etiquetar los valores de distancia en los bordes del gráfico utilizando la información de tiempo en lugar de su distancia física entre sí? De esa forma, buscará la ruta más rápida, en lugar de la ruta más corta. Luego puede usar Dijkstra / A * para calcular el resultado.
No estoy muy seguro de lo que quieres decir con dependiente del tiempo. Si quiere decir que necesita responder las consultas del formulario ''va de x a y antes de las 10 am'', entonces puede calcular qué rutas de autobús llegan antes de las 10 am, parece un simple filtro en los datos. Luego aplique Dijkstra / A * a los datos.