I believe that the big shipping companies (UPS, Fedex), have algorithms specifically designed around dynamic route planning like this. I wonder if it would be feasible for one of them to create a spin off business for just this purpose.
ArcGIS provides an API that does this, which is apparently used by all of the major shippers. They occasionally show up at hackathons and give out free low-usage accounts.