Transporte público usando autobuses en la ciudad

Question

Estoy desarrollando un sitio web Journey Planner. Hay pocas cosas que son simples en este caso actualmente, es decir, ahora mismo, el sitio web solo podrá planificar rutas de autobuses, los horarios de los autobuses no están disponibles actualmente. Esto significa que solo tenemos rutas de autobús almacenadas en el DB y dado que los horarios de los autobuses no están disponibles, por lo que los tiempos de espera para el viajero tampoco son relevantes. Lo que está disponible es el tiempo y la distancia cubiertos entre dos paradas para un autobús individual.

Creo que el uso de un gráfico ponderado indirecto que guarde los costos de tiempo y distancia de cada parada de autobús para cada autobús individual sería el camino a seguir. Entonces podría usar el algoritmo Dijkstra para calcular la ruta más corta entre dos ubicaciones ingresadas por el usuario en función del tiempo o la distancia según la preferencia del usuario. Descubriría si se requieren dos o tres autobuses a través de simples funciones de C# si las rutas de autobús se cruzan en las paradas y luego usa esas paradas de intersección para que el viajero cambie el autobús. Pero habría un gráfico individual para cada autobús. Una forma alternativa (no estoy seguro si esto es correcto) sería usar un gráfico que contenga cada parada de autobús de la ciudad como nodos y luego usar esta técnica para descubrir la manera de viajar entre dos paradas. ¿Cuál es el enfoque correcto? ¿Debería usar un algoritmo A * en lugar de Dijkstra algo?

Algunos puntos generales para el diseño: Me gustaría que la aplicación sea extensible para poder agregar otros medios de transporte más adelante cuando sea necesario. Además, los tiempos de autobús también podrían agregarse más tarde si es posible sin mayores cambios en el sitio web. He visto bastantes expertos aquí que han trabajado en proyectos de transporte muy complejos. Por lo tanto, ayúdenme con la mejor manera de implementar esta funcionalidad de la manera más escalable, modular y extensible.

Answer 1

Un gráfico debe ser un gráfico direccional: las paradas de autobús en lados opuestos de las carreteras (incluso en un país como el Reino Unido que rara vez tiene medianas) NO son la misma parada.

Answer 2

Creo que la optimización más importante es la separación de las estaciones donde puede cambiar las rutas y las estaciones donde no puede. Entonces solo necesita considerar las estaciones donde puede cambiar la ruta como estaciones intermedias en su gráfico. Esto debería hacer que el gráfico sea tan pequeño que Dijkstra esté bien.

Estoy distinguiendo nodos con solo dos bordes simplemente cortándolos del gráfico y en su lugar conectando sus dos vecinos con un borde de la longitud agregada. Luego hago pathfinding en este gráfico reducido que debería ser mucho más rápido. es decir, solo considere las estaciones donde se podría cambiar de ruta.

Answer 3

Inicié una aplicación similar el verano pasado y nunca la terminé, pero tengo algunos consejos sobre este gráfico y sobre cómo estructurar sus datos.

Mi plan era tener cada parada como un nodo, y una ruta entre cada uno de estos nodos cada vez que pasaba un bus. Por ejemplo, si un autobús se detiene cada media hora durante un período de 6 horas, entonces habrá 12 rutas entre los dos nodos. El tiempo fue el principal motor detrás del "costo" de la ruta, por lo que el camino más cercano sería el elegido.

Antes de iniciar la aplicación consultará la base de datos para ver todas las rutas en las próximas 5 horas (ajuste según corresponda). Entonces se estrellaría con el algoritmo de Dijkstra.

Otras cosas que toma en cuenta el costo son el costo de dinero real de la ruta, las transferencias (y su coste), se detiene sin techos (si tienden a tener mal tiempo), etc.

Este plan ha funcionado bien para mi. Vivo en un área con 3 sistemas de autobuses.

Finalmente, puede ser útil estructurar sus datos de forma similar al Google Transit Feed Specification, ya que muchas agencias producen este tipo de datos que usted puede importar.

Answer 4

Quizás pueda hacer un cierto uso de paddydubs para TransportDublin encontrado on github.

Answer 5

He codificado tal algoritmo para una aplicación de prueba. Tenía un diccionario para cada parada, como fuente y como destino. El algoritmo fue recursivo. Cada paso de la recursión era así: Dada la fuente y el objetivo, generaría una lista de rutas que entrarían en el objetivo, lista de rutas que salían de la fuente. Si hubo paradas comunes, terminamos, informamos la ruta. Si no, entonces genero paradas vecinas para fuente y recurse. La siguiente recursión genera una lista de paradas vecinas para sink, recurse. Antes de la recursividad, grabé el camino anterior, por supuesto, y al final tendría una lista.

Recuerdo que tuve que colocar algunas condiciones de corte porque la recursión a veces se atascaba en ciertas regiones "malas".

también consultaron este papel:

www.citeulike.org/user/rchauhan/article/819528

estoy interesado si se las arregló para resolver este problema de una manera diferente.