OSRM is an Open Source Routing Machine that computes the shortest paths in a graph - designed to run on data from the OpenStreetMap project.
The OSRM project includes tools to extract and prepare data for use by the routing daemon that exposes a simple API or the Node.js bindings.
The OSRM Wiki includes a page for setting up OSRM on Heroku - but at the time of writing the instructions for doing so are not present.
I've put together a Heroku buildpack to make it easier to run the OSRM routing API (osrm-routed) on Heroku - it's available on Github.
There are a few caveats - mainly about the size of data files that can be used - more detail is in the README.
A note on memory management: It doesn't look like it's possible to use osrm-datastore and shared memory on Heroku - I'm not sure if this has any implications on running the OSRM daemon on Heroku in a Production environment.