PgRouting

pgRouting (www.pgrouting.org) provides routing functionality on a PostGIS database. Free & open source

You can populate the database with OpenStreetMap planet.osm files using the osm2pgrouting tool.