Sign in to follow this  

Shortest Paths Algorithm

This topic is 4595 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I am looking for information, links or sources for a shortest paths algorithm for public transport. My current data set includes: Transport companies Lines traveled by the companies. Each line can have multiple ways and return ways Stations Links between each of the stations, with information including distance, traveling time and waiting time Timetables of which buses leave on which day and what time, for each way. Multiple entries could be possible The algorithm should take in consideration the following: Find the shortest & logical path by forcing a starting company. Find the shortest & logical path by forcing the same line. Find the shortest & logical path by forcing the same way. Find the shortest & logical path by forcing the same company but changing any line. Find the shortest & logical path by minimizing the number of changes. Find the shortest & logical path by finding every path possible. By logical I mean that the path should stick to the same line and way if a station exists, even though it could not be the shortest path. This is logical because a person would not want to change the bus for one stop and then proceed on the same line he was originally traveling on. Distances, departure times, traveling times and waiting times should also be considered in the calculations. Thanks, Ivan

Share this post


Link to post
Share on other sites
Quote:
Original post by cryo75
Hi all,

I am looking for information, links or sources for a shortest paths algorithm for public transport.

Generally, "special cases" in pathfinding may be accomplished with a standard pathfinding algorithm such as A* by (1) editing edge costs and/or graph connectivity (the two are really the same thing), and (2) splitting or joining problems. Let's see how to do a couple of these. Define "node" as a given station, and "edge" as a single stop-to-stop of a single line (or not... see later). I'm not going to do all your work for you, since this sounds kind of homeworky.

Quote:

Find the shortest & logical path by forcing a starting company.

Simply change the graph connectivity so that the only edges leaving the start node are those of the given company.

Quote:

Find the shortest & logical path by minimizing the number of changes.

Here's where it gets fun. Suppose you define a node as not only the station a rider is at, but also what line he is currently on. The state space, in other words, is a subset of the cartesian product of the set of stations and the set of lines. Now, for a given station, make edges from every line at that station to every other line at that station, but give the edges non-zero costs. Now a rider is penalized for changing lines. If the cost is set to a very high number, the chosen route will be the route with the fewest line changes.

Share this post


Link to post
Share on other sites
This actually a project I'm currently working on and not homework! It's quite a few years since I was at school now!! :P

I've already got a working naive Dijkstra algorithm that only considers length. I've been trying to modify it to include the restrictions I need but it either takes too long or doesn't find the routes.

For each link, I have attributes for distance, travelling time and waiting time. The problem is that I have no idea how to calculate a cost combining the 3 attributes or if I need to keep 3 different costs.

I've done one change:

I added a preprocess step (run once), where I go through all links and calculate the number or start nodes that are the same as the current end node. In this way I know how many connections are available from that link, aka targets.

Furthermore, I change the visited flag of the link from a boolean to a number, starting with 0 (not visted), and incrementing it everytime the link is include in a route. Once the visited number reaches the original targets amount, it's not considered anymore for inclusion in a route.

This worked fine for 10 links but it does slow down when I use all nodes and links, and it also doesn't find all possible routes just the same :(

I've read about speed-up routines such as goal-directed, angle restriction, bi-directional, sweep but have no idea how to calculate the values and how to use these values effectively.

Ivan

Share this post


Link to post
Share on other sites

This topic is 4595 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this