TransportDublin Route Planner Github Project

paddydub

Hi,
I have been working on a Dublin Public Transport Route Planner.
Powered by neo4j a nosql graph database with spatial features & offers implementations of common graph algorithms and google maps API v3

I have just uploaded the project to github and updated the wiki with screen shots and information

http://wiki.github.com/paddydub/TransportDublin/


I still have a lot of work to do, I have If anyone would like to help me out or have any suggestions or recommendations it would be greatly appreciated.
The graph database is populated with approx 15,000 bus stops and 150 bus routes and all timetables for most bus routes extracted from the Dublin Bus website. I will add more documentation and a quick start guide.

Thanks
Paddy

Victor

http://www.boards.ie/vbulletin/showthread.php?t=2055974279

Much more important is getting it to be time sensible. With the above, it suggests using the 142 going from Rathmines to Swords - but there are only 3 buses per day.

paddydub

Hi Victor,
Nice thats my first time seeing that site, its really good

I have been been working with neo4j in implementing all timetables and days of the week in to the graph db.
a bit more info on the timetable implementation can be found here:
http://www.mail-archive.com/user@lists.neo4j.org/msg03929.html

Craig Taverner somes it up pretty well:

- Build the core model, linking buses to routes composed of stops
(containing locations on nodes and distances on relationships)
- Extend the core model with runs, specifying multiple start times for
all routes. Each route should have many runs, and each run would be a new
node.
- For each run, duplicate the routes with stop nodes containing the
actual timetable stop times. These nodes dont need locations, because they
can link directly to the original stop nodes (different relationship type of
course).
- Now you have a graph of the complete timetable, but there is one more
thing to add, walking distance between stops should the user need to change
bus. This can be done in two phases also:
- Calculate all walking distances between all core model stops on
different routes. Add relationships between the stops, but only
if less than
some maximum time (why load the graph with relationships that
will never be
used, like walking 2h between bus stops :-)
- Now go to the timetable nodes, and add relationships there. This
time you add relationships between different routes if several conditions
are met:
- The walking distance is short enough (already calculated from the
core model)
- The walking time is less than the time between the stop times
(ie. as you said before)
- Use time between node times as the cost, not the walking time, so
you get the next bus, not the one after that (the one after
gets a higher
cost, since the time difference is higher)
- Finally index all core model stops using a spatial index (eg. Neo4j
Spatial RTree), so you can made the start query you wanted.
- Now you have a graph that contains everything you need to make all
queries. All possible routes are in the graph structure itself, and the cost

is a simple sum of the costs of the relationships.

and to help you visualise it, this is one sample bus route i imported into neoclipse:
http://img245.imageshack.us/img245/1373/neoclipseicons.png

The graph is approx 1gb there are approx 10 million relationships and 1 million nodes.
Running on my local machine, to find the best route , it takes 5 seconds to do approx 100 lucene query searches and add approx 100 relationships to the graph and it can take from 3 - 10 seconds to find a shortest path , with the a star algorithm.
The route planning algorithm will need to be fine tuned to find the best route, when it is up and running

paddydub

A good introduction to neo4j :
Need a graph database like Twitter is built on? @neo4j delivers, @emileifrem tells why
http://www.youtube.com/watch?v=2ElGO1P8v0c

paddydub

I have added a Quick Install Guide on the wiki if anyone would like to try Neo4j and Jetty:

required: Sun Java JDK 1.5+ and Maven 2

First Download the source code :

1. Download latest zip source file from: http://github.com/paddydub/TransportDublin/archives/master

2. Extract zip contents into a folder C:\dev\transportdublin\

Download the neo4j database:

3. Download a prepopulated graph database from neo4j-db.zip
4. Extract the neo4j-db.zip file to folder: C:\dev\transportdublin\data\
5. open the command line in C:\dev\transportdublin\

Launch the Jetty web server
6. From the command line type: mvn jetty:run
7. This command should launch the web app, Let me know if you get any errors. Point your browser to location http://localhost:8080/transportdublin/routeplanner
Hopefully it should work