OSRM is looking at improving this exact situation right now: https://github.com/Project-OSRM/osrm-backend/pull/2912