Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Try to speed up the priority queue by allocating less memory and storing the score in the queue rather than in the result.
trunk/src/optimiser.c