I work for a state health program and am looking for the most efficient way to route inspectors from restaurant to restaurant. This is something like the travelling salesman problem, but with additional complexities. We have 75 inspectors, making less than 8 hour round trips from 17 different offices, inspecting ~18,000 businesses at 1.25 hours an inspection (not counting travel time). These businesses either need inspected annually, 3 times a year, or 5 times a year depending on their assigned risk level. Does anyone have any ideas/suggestions for this? I am talking to Telogis and Viamente as far as getting quotes for using their products but am interested in looking into all avenues. It's possible this is not on the right Stackexchange, if you know of a more appropriate venue I'd appreciate knowing that as well.
[GIS] Multipoint routing logistics software solution
routingsoftware-recommendations
Related Solutions
Pretty much any solution you find that fits your needs (high usage, cost-effective) is going to based on OpenStreetMap data. Here are a couple options:
MapQuest Open Directions API is based on OSM data and is completely free for any use. See the terms on their page. They allow you to "request a multi-point route for up to 50 locations".
YOURS is also based on OSM data but, unlike the MapQuest service, the code is available so you could run everything in-house if you wanted. They've also got a hosted version at http://www.yournavigation.org that you can use though.
There are many other routing engines based on OSM data. I'd recommend taking a look at these articles:
This question has been converted to Community Wiki and wiki locked because it is an example of a question that seeks a list of answers and appears to be popular enough to protect it from closure. It should be treated as a special case and should not be viewed as the type of question that is encouraged on this, or any Stack Exchange site, but if you wish to contribute more content to it then feel free to do so by editing this answer.
Try routeXL I'm not sure how many nodes you can max out on though. Here's an example of a 12 city output
- To add destinations, find them in the search bar and press enter. click on the
Addressdrop down to change/modify the addresses you just added - Click on
find routefor it to compute it
HEre's a screenshot of a run I did:
[Disclaimer - I am the author of the UI part of this software]
ODL Studio is an open source desktop application for planning vehicle routes - so it will solve your problem. It's free and we have people using it in many different countries throughout the world. Download from here http://www.opendoorlogistics.com/ or watch the tutorial video here https://www.youtube.com/watch?v=0DJdubVWX_A
It takes an Excel as input data which will help you. You can play around with the cost-per-km and cost-per-hour to have it automatically optimise for most efficient by time or mileage (given the size of your problem it will probably find the most optimal solution as well).
There is the personal route-planning software portatour which supports multiple stops and Excel upload.
- Sign up for an account and upload your excel. Pressing "update schedule" will give you the shortest route.
- portatour is made for sales reps visiting up to 1000 addresses repeatedly, so it has many more features which are specific for field sales, consulting, and maintenance. For example, opening times or visit intervals.
- The result route can be exported as iCal calendar.
- There is a free trial
Here is a screenshot of a generated Route on an iPad:
Disclaimer: I work for portatour.
Check out Optimo Route - there is a free trial you can use. Import multiple addresses from MS Excel and easily plan optimal routes. You can also set things like service time (time you will spend at the location) and time windows (specific times you need to be at the location).
Routes can be exported to a GPS device (Garmin, Navigon, TomTom) or MS Excel.
Disclaimer: I work for Optimo Route.
Also take a look at Speedy Route - another optimal route planner website. You can bulk upload addresses, and then either print out the optimal route, or export the results to Excel via CSV.
Finding the most efficient route from a list of addresses sounds a lot like the Traveling Salesman Problem, one of the most studied problems in computer science. It's one thing to calculate a straight line distance but adding street routes makes this highly unlikely that you'll find an optimal distance.
I might have answered part of your problem on another page. This may not be useful but I'll include it anyway.
Best Answer
jsprit can solve your problem. It is a java based, open source toolkit for solving rich traveling salesman (TSP) and vehicle routing problems (VRP). Rich means here that you can model an arbitrary number of constraints that account for your business requirements such as skills, time-windows etc.. And in conjunction with jsprit, you can use GraphHopper.