Public transport search algorithm

Question

Algorithms

Tell me the method (algorithm) or links on the topic of finding public transport. There is a list of bus stops (trolleybuses, trams) in the database, each stop has coordinates, a list of routes passing through it, there is also a list of the routes themselves in the database and the coordinates of the lines (the coordinates of the points describing the route line). How to implement a route search (taking into account possible transfers) by analogy with 2GIS or Yandex maps?

Answer 1

Thanks for the replies, need to smoke the A* search algorithm

Answer 2

I tried to solve this problem with a graph traversal algorithm, going through each stop and looking for adjacent routes. For example, at stop 1 there are routes A,B,C; at stop 2 C,Z,K. This means that you can get from stop 1 to stop 2 by route C. For “changes”, I made a recursive bypass of the stops of each of the routes of the initial stop.
BUT as practice has shown, the algorithm is VERY slow and generates a lot of requests. I'm sure there are better algorithms

Answer 3

Search by graph?
from algorithms - A*, MST, TSP

Answer 4

During my reflections, I came to a similar algorithm, but it is very inefficient for searching for transfers, especially if there are several transfers. It seems to me that some more data on routes or stops is required for the search. Thanks for the reply, looking forward to new ideas.

Answer 5

In our Twiton.com reservation system, transfers for bus lines are considered brute force, all routes are loaded into memory into a tree structure and sorted out. More efficient algorithms did not go because. users can set max. transfer waiting time.